南京大学：《高级算法 Advanced Algorithms》课程教学资源（课件讲稿）12 SDP-Based Algorithms

Advanced Algorithms SDP-Based Algorithms 尹一通Nanjing University,2022Fall

尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms SDP-Based Algorithms

Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of Vinto S and Ithat maximizes the cut E(S,T)={w,v}∈E|w∈S∧v∈T}. NP-hard. One of Karp's 21 NP-complete problems(reduction from the Partition problem). a typical Max-CSP(Constraint Satisfaction Problem). Greedy is 1/2-approximate. Local search is 1/2-approximate

Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S • NP-hard. • One of Karp’s 21 NP-complete problems (reduction from the Partition problem). • a typical Max-CSP (Constraint Satisfaction Problem). • Greedy is 1/2-approximate. • Local search is 1/2-approximate

Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of Vinto S and Ithat maximizes the cut E(S,T)={w,v}∈E|w∈S∧v∈T}. max Yuv uv∈E not linear S.t. yuu≤lEu-xul, Vuw∈E xu∈{0,1， Vu∈V

Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S max X uv2E yuv s.t. yuv  |xu ￾ xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V not linear

Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={u,v}∈E|u∈S∧v∈T. max Yuv uw∈E s.t. yuv≤yuw+ywv, ,v,w∈V yuw+yuw+yu≤2，u,v,2w∈V yuw∈{0,1}， u,v∈V u,y,w∈V:0or2of{u,y以，{y,w以，{u,w} are“crossing pairs

Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S max X uv2E yuv s.t. yuv 2 {0, 1}, yuv  yuw + ywv, yuv + yuw + ywv  2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V ∀u,v,w ∈ V: 0 or 2 of {u,v}, {v,w}, {u,w} are “crossing pairs

Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={w,v}∈E|uw∈S∧v∈T}. max ∑aw integrality gap≥2 uw∈E S.t.yuw≤yuw+yww, u,v,w∈V 人 yuw+yuw+ywu≤2，，v,w∈V yuv∈{0,1}， u,v∈V V8>0:3G s.t.OPTLP(G)/OPTIP(G)>2-8

Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S max X uv2E yuv s.t. yuv 2 {0, 1}, yuv  yuw + ywv, yuv + yuw + ywv  2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V integrality gap ≥ 2 ∀ε>0: ∃G s.t. OPTLP(G)/OPTIP(G) > 2-ε

Quadratic Program for Max-Cut max Yuv uw∈E s.t. yuu≤lxu-xul, uw∈E xv∈{0,1}， u∈V quadratic program: max ∑a uv∈E s.t. yuw≤(1-Eucw),uw∈E xw∈{-1,1}， Vu∈V

Quadratic Program for Max-Cut 1 2 yuv  (1 ￾ xuxv) yuv X uv2E T S max s.t. 8uv 2 E xv 2 {￾1, 1}, 8v 2 V quadratic program: , max X uv2E yuv s.t. yuv  |xu ￾ xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V

Quadratic Program for Max-Cut max Yuv uw∈E S.t.yuw≤lxu-xv, /uv∈E xv∈{0,1， V∈V strictly quadratic program: max ∑1-xuo) uw∈E S.t. x=1, u∈V Nonlinear,non-convex!

Quadratic Program for Max-Cut T S strictly quadratic program: max s.t. 1 2 (1 ￾ xuxv) X uv2E x 8v 2 V 2 v = 1, Nonlinear, non-convex! max X uv2E yuv s.t. yuv  |xu ￾ xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V

Relaxation strictly quadratic program: max (1-au2o) uw∈E S.t. 品=1， H∈V relax to vector program: semidefinite program (SDP) max 2∑1-,》 inner-products: uv∈E (cu,x〉=x(zu() i=1 S.t. (cu,cu〉=1， v∈V cu∈Rn, Hu∈V n =IV

Relaxation strictly quadratic program: max s.t. 1 2 (1 ￾ xuxv) X uv2E x 8v 2 V 2 v = 1, relax to vector program: n = |V| semidefinite program (SDP) 1 2 X uv2E max (1 ￾ hxu, xvi) s.t. 8v 2 V xv 2 R 8v 2 V n , hxv, xvi = 1, hxu, xvi = X n i=1 xv(i)xu(i) inner-products:

Positive Semidefiniteness (PSD) Definition(Positive Semidefiniteness): A symmetric square matrix A E R"x is said to be positive semidefinite,denoted A>≥0，ifVx∈R”,xTAx≥0. Theorem: For symmetric A E R"X",the followings are equivalent: ·A≥0 all eigenvalues(A)≥0 ·A=BB for some B∈Rnxn

Positive Semidefiniteness (PSD) Definition (Positive Semidefiniteness): A symmetric square matrix is said to be positive semidefinite, denoted , if , . A ∈ ℝn×n A ≽ 0 ∀x ∈ ℝn xTAx ≥ 0 Theorem: For symmetric , the followings are equivalent: • • all eigenvalues • for some A ∈ ℝn×n A ≽ 0 λ(A) ≥ 0 A = BTB B ∈ ℝn×n

Semidefinite Programing (SDP) ·Given C,A,,Ak∈Rmx"andb1,b2,,bk∈R maximize 1 (cry)=∑∑c i-1 j=1 subject to tr(AY)≤b, V1≤r≤k Y≥0 symmetric Y∈Rnxn

• Given C, A and 1,…, Ak ∈ ℝn×n b1, b2,…, bk ∈ ℝ Semidefinite Programing (SDP) maximize subject to , symmetric tr(CTY) = n ∑ i=1 n ∑ j=1 cij yij tr(AT r Y) ≤ br ∀1 ≤ r ≤ k Y ≽ 0 Y ∈ ℝn×n