A Combinatorial, Primal-Dual Approach to Semidefinite Programs Satyen Kale Microsoft Research Joint work with Sanjeev Arora Princeton University The Ubiquity of Semidefinite Programming Max Cut [GW95] Balanced Partitioning [ARV04] dx(t)/dt = Ax(t) Control Theory SDP (a :b) (:a c) (a b) (:c b) 1 0 0 0 1 1 0 1 Constraint Satisfaction [ACMM05]
Graph Coloring [KMS98, ACC06] Algorithms for SDP Ellipsoid method [GLS81]: O(n8) iterations Interior point methods [NN90, A95]: O(m(n3 + m)) time Combinatorial, Primal-Dual algorithms A1 X b1 Am X bm i wi(Ai X bi) 0 Lagrangian Relaxation [KL95], [AHK05]: Reduction to eigenvectors poly(1/) dependence on , limits applicability (e.g. Sparsest Cut) Primal-Dual algorithms for LP: Multicommodity Flows Unit capacities
Objective: Maximize total flow, while respecting edge capacities Primal-Dual algorithms for LP: Multicommodity Flows 11 + 1 1 1 1 Edge weights we = 1 Repeat until some e reaches capacity: Find shortest path p Route 2/log(m) flow on p Update w for all e 2 p as e 1 1
1 1 1 1 1 1 we we (1 + ) 1 Output flow. Thm [GK98]: Stops in (m) rounds with (1 2)OPT flow. Total running time is (m2). Primal-Dual algorithms for LP: Multicommodity Flows 1. Primal-Dual algorithm Edge weights we = 1
Repeat until some e reaches capacity: Find shortest path p Route 2/log(m) flow on p Update w for all e 2 p as e 2. Combinatorial 3. Multiplicative Weights Update Rule we we (1 + ) Output flow. Thm [GK98]: Stops in (m) rounds with (1 2)OPT flow. Total running time is (m2). Starting point for our work: Analogous primal-dual algorithms for SDP?
Difficulties: Positive semidefiniteness hard to maintain Rounding algorithms exploit geometric structure (e.g. negative-type metrics) Matrix operations inefficient to implement Our work: a generic scheme that yields fast, combinatorial, primal-dual algorithms for various optimization problems using SDP Our Results: Primal-Dual algorithms Problem Previous best: O(log n) apx [AHK04] Our alg.:
O(log n) apx Our alg.: O(log n) apx (n2) (n2) (m + n1.5) [AHK04] (n2) (n2) (m + n1.5) Directed Sparsest Cut (n4.5) 2+) (m1.5 + n2+ (m1.5)
Directed Balanced Sep. (n4.5) 2+) (m1.5 + n2+ (m1.5) Undirected Sparsest Cut Undirected Balanced Sep. Our Results: Primal-Dual algorithms Problem Undirected Sparsest Cut Undirected Balanced Sep. Previous best:
O(log n) apx [AHK04] Our alg.: O(log n) apx Our alg.: O(log n) apx (n2) (n2) (m + n1.5) [AHK04] (n2) Cannot be achieved (n2) (m + n1.5) by LPs even! Directed Sparsest Cut
(n4.5) 2+) (m1.5 + n2+ (m1.5) Directed Balanced Sep. (n4.5) 2+) (m1.5 + n2+ (m1.5) Our Results: Near-linear time algorithm for Max Cut (n + m) time algorithm to approximate Max Cut SDP to (1 + o(1)) factor
Previous best: (n2) time algorithm by Klein, Lu 95 Prototype MW for LPs: Winnow [L88] a1 x - 0 0 a2 x - 0 am x - x0 i xi = 1 MW for LP: Init: x = (1/n, , 1/n) Update: xj = xj exp(- aij)/ = norm. factor MW algorithm: boosting, Analysissets, useszero hard-core asgames, potential fn. sum flows,
Thm: Finds x in O(2log(n)/2) iterations. = maxij |aij| x Oracle Find i s.t. ai x < - ai Convex comb. of constraints allowed: i yi ai x < -, where yi 0, i yi Prototype Matrix MW for SDPs A1 X - 0 0 A2 X - 0 Am X - X0 Tr(X) = 1 Matrix MW for SDP: Init: X = I/n Update: X = exp(- ts=1 Ais)/ = norm. factor
Analysis uses as potential fn. Thm: Finds X in O(2log(n)/2) iterations. = maxi kAik X Oracle Find it s.t. Ait X < - Ai t Convex comb. of constraints allowed: i yi AiX < -, where yi 0, i yi = The Matrix Exponential Matrix MW for SDP: Init: X = I/n Update: X = exp(- ts=1 Ais)/ = norm. factor Matrix exponential: exp(A) = I + A + A2/2! + A3/3! +
Always PSD: exp(A) 0 Golden-Thompson inequality: Tricky beast: Tr(exp(A)exp(B)) Tr(exp(A+B)) exp(A+B) = exp(A) exp(B) Computation: O(n3) time Usually, can use J-L lemma Only need exp(A)v products: (m) time Approximation via SDP Relaxations Reduction Input Rounding Algorithm v1 Primal-Dual SDP
0-1 Quadratic Program Relaxation v2 SDP Solver SDP Opt vn SDP: Vector vars Primal-Dual SDP Framework Reduction Input Rounding Algorithm v1 Primal-Dual SDP 0-1 Quadratic Program
Relaxation v2 y1,, ym X vn Matrix MW SDP: Vector vars Approximating Balanced Separator G = (V, E) S S Cut (S, S) is c-balanced if
|S|, |S| cn Min c-Balanced Separator: cbalanced cut of min capacity Numerous applications: Divide-and-conquer algorithms Markov chains Geometric embeddings Clustering Layout problems SDP for Balanced Separator G = (V, E) kvi vjk2 = 0 if i, j on same side, = 1 otherwise S SDP: min i,j 2 E kvi vjk2 S vi = -1 vi = 1 8i: kvik2 = 1
8ijk: kvivjk2 + kvjvkk2 kvivkk2 i, j kvi vjk2 c(1-c)n2 Implementing Oracle Primal: min i,j 2 E kvi vjk2 8i: kvik2 = 1 8ijk: kvivjk2 + kvjvkk2 kvivkk2 i, j kvi vjk2 c(1-c)n2 Oracle: given X (thus, vi), : Bounds checkThm: Given vi, constraints : first and third eigenvalues via inequalities: Max-flow ) desired flow or cut of flow dual vars , multicommodity s.t. demand graph
fij = total1. flow O(log(n)). Laplacian 1. totali,value flow from any node is d between j Multicommodity flow ) desired flow 2. no2. capacity is exceeded ori cut O(log(n)). 2 value 3. i,j fijkv vjkof Conclusions and Future Work Matrix MW algorithm: more applications in
Solving SDPs: e.g. Min Linear Arrangement Quantum algorithms: density matrix is a central concept Learning: e.g. online variance minimization [WK COLT06], online PCA [WK NIPS06] Other applications? Linear time algorithm for Sparsest Cut? Our algorithm runs in (m + n1.5) time for an O(log n) approximation Thank you!
