Convex Programming Brookes Vision Reading Group
Huh? • What is convex ???
• What is programming ??? • What is convex programming ???
Huh? • What is convex ???
• What is programming ??? • What is convex programming ???
Convex Function
f(t x + (1-t) y) <= t f(x) + (1-t) f(y)
Convex Function
Is a linear function convex ???
Convex Set
Region above a convex function is a convex set.
Convex Set
Is the set of all positive semidefinite matrices convex??
Huh? • What is convex ???
• What is programming ??? • What is convex programming ???
Programming • Objective function to be minimized/maximized. • Constraints to be satisfied. Example
Constraints
Objective function
Example
Optimal solution Vertices
Objective function Feasible region
Huh? • What is convex ???
• What is programming ??? • What is convex programming ???
Convex Programming • Convex optimization function • Convex feasible region • Why is it so important ??? • Global optimum can be found in polynomial time. • Many practical problems are convex • Non-convex problems can be relaxed to convex ones.
Convex Programming • Convex optimization function • Convex feasible region • Examples ??? • Linear Programming • Refer to Vladimir/Pushmeet’s reading group • Second Order Cone Programming • What ??? • Semidefinite Programming • All this sounds Greek and Latin !!!!
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
2 out of 3 is not bad !!!
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
Second Order Cone • || u || < t • u - vector of dimension ‘d-1’ • t - scalar • Cone lies in ‘d’ dimensions
• Second Order Cone defines a convex set
• Example: Second Order Cone in 3D
x2 + y2 <= z2
x2 + y2 <= z2 Hmmm ICE CREAM !!
Second Order Cone Programming Minimize
fTx
Linear Objective Function
Subject to || Ai x+ bi || <= ciT x + di i = 1, … , L Affine mapping of SOC Constraints are SOC of ni dimensions Feasible regions are intersections of conic regions
Example
Why SOCP ?? • A more general convex problem than LP – LP SOCP
• Fast algorithms for finding global optimum – LP - O(n3) – SOCP - O(L1/2) iterations of O(n2∑ni)
• Many standard problems are SOCP-able
SOCP-able Problems • Convex quadratically constrained quadratic programming • Sum of norms
• Maximum of norms • Problems with hyperbolic constraints
SOCP-able Problems • Convex quadratically constrained quadratic programming • Sum of norms
• Maximum of norms • Problems with hyperbolic constraints
QCQP Minimize
xT P0 x + 2 q0T x + r0
Pi >= 0
Subject to xT Pi x + 2 qiT x + ri
|| P01/2 x + P0-1/2 x ||2 + r0 -q0TP0-1p0
QCQP Minimize
xT P0 x + 2 q0T x + r0
Subject to xT Pi x + 2 qiT x + ri Minimize t Subject to || P01/2 x + P0-1/2 x || < = t || P01/2 x + P0-1/2 x || < = (r0 -q0TP0-1p0)1/2
SOCP-able Problems • Convex quadratically constrained quadratic programming • Sum of norms
• Maximum of norms • Problems with hyperbolic constraints
Sum of Norms Minimize || Fi x + gi || Minimize ti Subject to || Fi x + gi || <= ti
Special Case: L-1 norm minimization
SOCP-able Problems • Convex quadratically constrained quadratic programming • Sum of norms
• Maximum of norms • Problems with hyperbolic constraints
Maximum of Norms Minimize max || Fi x + gi || Minimize t Subject to || Fi x + gi || <= t
Special Case: L-inf norm minimization
You weren’t expecting a question, were you ??
SOCP-able Problems • Convex quadratically constrained quadratic programming • Sum of norms
• Maximum of norms • Problems with hyperbolic constraints
Hyperbolic Constraints w2 <= xy
x >= 0 , y >= 0
|| [2w; x-y] || <= x+y
Let’s see if everyone was awake !
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
Semidefinite Programming Minimize C X Subject to Ai X = bi X >= 0 Linear Objective Function Linear Constraints Linear Programming on Semidefinite Matrices
Why SDP ?? • A more general convex problem than SOCP – LP SOCP SDP
• Generality comes at a cost though – SOCP - O(L1/2) iterations of O(n2∑ni) – SDP - O((∑ni)1/2) iterations of O(n2∑ni2)
• Many standard problems are SDP-able
SDP-able Problems • Minimizing the maximum eigenvalue
• Class separation with ellipsoids
SDP-able Problems • Minimizing the maximum eigenvalue
• Class separation with ellipsoids
Minimizing the Maximum Eigenvalue Matrix M(z) To find vector z* such that max is minimized.
Let max(M(z)) <= n max(M(z)-nI) <= 0
min(nI - M(z)) >= 0 nI - M(z) >= 0
Minimizing the Maximum Eigenvalue Matrix M(z) To find vector z* such that max is minimized.
Max -n nI - M(z) >= 0
SDP-able Problems • Minimizing the maximum eigenvalue
• Class separation with ellipsoids
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
Non-Convex Problems Minimize xTQ0x + 2q0Tx + r0 Subject to xTQix + 2qiTx + ri < = 0
Qi >= 0 => Convex
Non-Convex Quadratic Programming Problem !!! Redefine x in homogenous coordinates. y = (1; x)
Non-Convex Problems Minimize xTQ0x + 2q0Tx + r0 Subject to xTQix + 2qiTx + ri < = 0
Minimize yTM0y
Mi = [ ri qiT; qi Qi]
Subject to yTMiy < = 0 Let’s solve this now !!!
Non-Convex Problems • Problem is NP-hard.
• Let’s relax the problem to make it convex. • Pray !!!
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
SDP Relaxation Minimize yTM0y Subject to yTMiy < = 0
Minimize M0 Y Subject to Mi Y < = 0
Y = yyT
Bad Constraint !!!! No donut for you !!!
SDP Relaxation Minimize yTM0y Subject to yTMiy < = 0
Minimize M0 Y Subject to Mi Y < = 0
Y >= 0
SDP Problem
Nothing left to do …. but Pray
Note that we have squared the number of variables.
Example - Max Cut • Graph: G=(V,E) • Maximum-Cut
Example - Max Cut • Graph: G=(V,E) • Maximum-Cut
- xi = -1 - xi = +1
Example - Max Cut • Graph: G=(V,E) • Maximum-Cut
Alright !!! So it’s an integer programming problem !!! Doesn’t look like quadratic programming to me !!!
Max Cut as an IQP Max Cut problem can be written as
Naah !! Let’s get it into the standard quadratic form.
Max Cut as an IQP Max Cut problem can be written as
Naah !! Let’s get it into the standard quadratic form.
Solving Max Cut using SDP Relaxations To the white board. (You didn’t think I’ll prepare slides for this, did you??)
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
SOCP Relaxation Minimize yTM0y Subject to yTMiy < = 0
Minimize M0 Y
Remember
Subject to Mi Y < = 0
Y = [1 xT; x X]
Y >= 0 X - xxT >= 0
SOCP Relaxation Say you’re given C = { C1, C2, … Cn} such that Cj >= 0 Cj (X - xxT) >= 0
(Ux)T (Ux) <= Cj X Wait .. Isn’t this a hyperbolic constraint Therefore, it’s SOCP-able.
SOCP Relaxation Minimize yTM0y Subject to yTMiy < = 0
Minimize Q0 X + 2q0Tx + r0 Subject to Qi X + 2qiTx + ri < = 0
Cj (X - xxT) >= 0 Cj C
SOCP Relaxation If C is the infinite set of all semidefinite matrices SOCP Relaxation = SDP Relaxation If C is finite, SOCP relaxation is ‘looser’ than SDP relaxation. Then why SOCP relaxation ??? Efficiency - Accuracy Tradeoff
Choice of C Remember we had squared the number of variables. Let’s try to reduce them with our choice of C. For a general problem - Kim and Kojima
Using the structure of a specific problem e.g. Muramatsu and Suzuki for Max Cut
Choice of C Minimize cT x
Subject to Qi X + 2qiTx + ri < = 0 Q X + 2qTx + r <= 0
Q = n i uiuiT Let
1 >= 2 >= …. k >= 0 >= k+1 >= n
Choice of C C=
Q+ = k i uiuiT
Q X + 2qTx + r <= 0 xT Q+ x - Q+ X <= 0
xT Q+ x + k+1 i uiuiT X + 2qTx + r <= 0
zi
Choice of C C=
Q+ = k i uiuiT uiuiT i = k+1, k+2, … n Q X + 2qTx + r <= 0
xT Q+ x + k+1 i zi+ 2qTx + r <= 0
xTuiuiTx - uiuiT X <= 0
Choice of C C=
Q+ = k i uiuiT uiuiT i = k+1, k+2, … n Q X + 2qTx + r <= 0
xT Q+ x + k+1 i zi+ 2qTx + r <= 0
xTuiuiTx - zi <= 0
Specific Problem Example Max Cut ei = [0 0 …. 1 0 …0] uij = ei + ej vij = ei - ej
C=
ei eiT
i = 1, … , |V|
uij uijT
(i,j) E
vij vijT
(i,j) E
Specific Problem Example Max Cut Warning: Scary equations to follow.
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
Outline • Convex Optimization – Second Order Cone Programming (SOCP) – Semidefinite Programming (SDP)
• Non-convex optimization – SDP relaxations – SOCP relaxations
• Optimization Algorithms – Interior Point Method for SOCP – Interior Point Method for SDP
Back to work now !!!