Semidefinite Optimization

Nina Dokeva, Wolfram Research Inc

Join the Conversation #WolframTechConf

Introduction

This talk includes

a brief discussion of semidefinite optimization and its relationship to conic and convex optimization

an introduction of the SemidefiniteOptimization function currently under development

several examples of semidefinite optimization problems solved with Mathematica

Convex optimization

Convex mimimization studies the problem of minimizing convex functons over convex sets.

A broad class of problems in various application domans can be represented as convex optimization problems and can be solved efficiently.

Definition. A set C ⊂ (ℝ^n)is called convex if for any x, y ∈ C and 0≤t≤1 then t x + (1-t )y ∈C.

Definition. A function f : (ℝ^n)->ℝ is called convex if its domain C is a convex set and f(t x+ (1-t) y) ≤t f(x)+(1-t)f(y) for all x,(Subscript[y,  ])∈C and all 0≤t≤1.

An important property for convex minimization is the following 

Theorem. If (SuperStar[x])is a locally optimal point (a local minimum or a local maximum) for the convex function f over a convex set C, then (SuperStar[x]) is globally optimal.

Conic optimization

Cone definitions

A cone is a region K⊂(ℝ^n)with all rays from the origin included, i.e. x ∈K ⟹α x ∈ K for all α ≥0.
A cone K is convex if x, y ∈ K ⟹α x + β y ∈ K for all α, β ≥0.
A pointed cone is a convex cone K that does not contain a full subspace: K ⋂ (-K) = {0}. 
Finally, a proper cone is a pointed cone that is closed and full-dimensional.

Let K be a proper cone, then we can introduce a partial ordering (Subscript[⪯, K]) by: x(Subscript[⪯, K])yifandonlyify-x∈Kand  x(Subscript[≺, K])yifandonlyify-x∈(K^◦)(the interior of K)

Cone examples

Some examples of proper cones include

• the positive orthant 						(Subscript[ℝ, +]^n)={ x ∈ (ℝ^n) : x ≥0 }
		• the second order (ice-cream) cone		(ℚ^(n+1))={ (x,t )∈(ℝ^n)× ℝ : ||x(Subscript[||, 2])≤t }
		• the set of positive semidefinite matrices 	(Subscript[𝕊, +]^n) = { S ∈ (ℝ^(n ×n)):Sᵀ=S, xᵀ·S ·x ≥0 for x ∈(ℝ^n) }

Problem formulation

A conic optimization problem consists of minimizing a convex function over the intersection of an affine subspace and a proper cone.
Often the objective function f is linear, in which case the standard form of a conic linear optimization problem is

Minimize f=cᵀ·x subject to x (Subscript[⪰, K]) 0 and A x = b

Alternatively, the constraints can also be combined and formulated as A x + b (Subscript[⪯, K])0.

The above reduces to a linear optimization problem if the cone K is (Subscript[ℝ, +]^n), a second order cone optimization problem in the case  K=(ℚ^(n+1)) and a semidefinite optimization problem when K=(Subscript[𝕊, +]^n) respectively.

Epigraph transformation

It is possible to reformulate problems with nonlinear objectives using the epigraph transformation

Minimize f(x) with constraints g(x) for x∈(ℝ^n) ⟺ minimize (OverTilde[f])(x, y):=y with constraints f(x) ≤y and g(x) for (x,y) ∈(ℝ^n)× ℝ

where the new constraint involving f can sometimes be put in a conic inequality form.

Semidefinite optimization

Many convex optimization problems can be represented in semidefinite form. 
Many conic optimization problems that use simpler cones can also be represented in semidefinite form.

An SDP problem can be formulated as optimizing a linear function subject to a linear matrix inequality (LMI):

Minimize cᵀ·x subject to (Subscript[x, 1])(Subscript[A, 1])+…+(Subscript[x, n])(Subscript[A, n  ])(Subscript[⪰, (Subscript[𝕊, +]^n)])B
((Subscript[A, 1]), …, (Subscript[A, n])and B are symmetric matrices)

The dual formulation of the same problem is given by

Maximize Tr(B·Y) subject to Tr((Subscript[A, i])·Y)+(Subscript[c, i])=0 and Y(Subscript[⪰, (Subscript[𝕊, +]^n)]) 0 	(i=1,…, n)

Duality theory similar to LP but weaker: if either the primal or the dual problem is strictly feasible, the primal and dual optimum values are the same.

Interior point methods for LP can usually be generalized for SDP problems and still have polynomial worst-case complexity.

Semidfefinite programming has many applications: computational geometry, graph theory, optimal control, structural optimization etc. [2]

New SDP functionality

Usage

SemidefiniteOptimization is the new function for solving semidefinite optimization problems that will be included in a future release.

SemidefiniteOptimization[c, {(Subscript[a, 1]),… , (Subscript[a, k])},b] finds a vector x={(Subscript[x, 1]),… , (Subscript[x, m])} that minimizes the quantity c·x subject to the linear matrix inequality constraint (Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])⪰ b.

The above semidefinite optimization problem may equivalently be expressed as minimizing c·x subject to the equality constraints (Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])-b==z where the slack matrix z is subject to z ⪰0.

The semidefinite minimization has a dual, that is the maximization of Tr[b·y] subject to the constraints Tr[(Subscript[a, i])·y] == (Subscript[c, i]) and y ⪰ 0.

SemidefiniteOptimization[c, a,b,"prop"] specifies what solution property "prop" should be returned. Possible properties include

"PrimalVector"					x				the vector that minimizes c·x (default)
	"PrimalMinimumValue"			c·x				the minimum value
	"DualMatrix"					y				the vector that maximizes Tr[b·y]
	"DualMaximumValue"				Tr[b·y]			the dual maximum value
	"DualityGap"					Tr[b·y]-c.x	the difference between the dual and primal optimal values
	"SlackMatrix"					z				(Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])-b
	{"(Subscript[prop, 1])", "(Subscript[prop, 2])", … }						several solution properties

Solvers

Under the hood, several open-source SDP libraries can be used to solve machine precision problems. 

This is done by calling SemidefiniteOptimization with a method option like Method -> "CSDP". 

The input will automatically be converted to the appropriate form for each solver implementation. The available libraries in the current development version include

CSDP: A C Library for Semidefinite Programming [5]

Part of the COIN-OR project, uses a predictor-corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz.
Implemented in C, can use multithreading and take advantage of sparsity in the constraint matrices.

DSDP: Software for Semidefinite Programming by S. J. Benson and Y. Ye. [6]

Uses dual-scaling interior-point method for semidefinite programming, has low memory requirements and efficient low-rank and sparse data structures.

SCS: Splitting Conic Solver by B. O'Donoghue, E. Chu, N. Parikh and S. Boyd [7]

Can solve large scale convex cone problems using the alternating direction method of multipliers. In addition to SDPs, can also solve LP, SOCP, exponential and power cone problems.

Example 1: Eigenvalue optimization

Let the matrix A be defined as A(x) = (Subscript[A, 0])+(Subscript[A, 1])(Subscript[x, 1])+…+(Subscript[A, n])(Subscript[x, n]) where all (Subscript[A, i]) are symmetric matrices. Find the minimum of the largest eigenvalue of A(x) for x∈(ℝ^n).

This can be directly stated as the semidefinite minimization problem 
	
	Minimize λ subject to λ (Subscript[I, n])- A(x) ⪰ 0

because of the following linear algebra theorem: for any real symmetric matrix A its largest eigenvalue (Subscript[λ, max]) satisfies (Subscript[λ, max])=(max_(x≠0))((xᵀ·A·x)/(xᵀ·x))

Consider an n=2 case:

x={x1,x2};vars={λ,x1,x2};
A0={{2,-3},{-3,4}};A1={{1,2},{2,3}};A2={{4,5},{5,6}};
A[{x1_,x2_}]:=A0+A1 x1+A2 x2;

Solve the problem and compute the corresponding eigenvalues:

{(SuperStar[λ]),(SuperStar[x1]),(SuperStar[x2])}=SemidefiniteOptimization[{1,0,0}, {IdentityMatrix[2],-A1,-A2},A0]

Eigenvalues[A[{(SuperStar[x1]),(SuperStar[x2])}]]

Compare with a simulation:

Min[Table[Max[Eigenvalues[A[RandomReal[{-10000,10000},2]]]],10000]]

Example 2: Nonlinear example to SDP

Problem

Consider the following non-linear problem

Minimize (((cᵀx)^2)/(dᵀx)) subject to A x + b ≥ 0 (assuming that dᵀx > 0 whenever A x + b ≥ 0 )

Using the epigraph transformation it can be written as

Minimize t subject to A x + b ≥ 0 and (((cᵀx)^2)/(dᵀx))≤t

The second constraint can be written as 
(({{t, (c^T) x}, {(c^T) x, (d^T) x}})) ⪰ 0 which is equivalent to dᵀx≥ 0 and (Schur complement) t- (((cᵀx)^2)/(dᵀx))≥ 0.
and the first constraint is equivalent to DiagonalMatrix[A x+b] ⪰ 0 which leads to the following problem in SDP form:

Minimize t subject to (({{diag[A x+b], 0, 0}, {0, t, (c^T) x}, {0, (c^T) x, (d^T) x}})) ⪰ 0.

Mathematica solution

Solve an example 2 × 2 case:

c={1,2};d={-3,4};
A={{1,-2},{-3,4}};b={-5,-1};

FindMinimum[{((({1,2}.{x1,x2})^2)/({-3,4}.{x1,x2})),x1-2x2-5≥0, -3x1+4x2-1≥0},{x1,x2}]//RepeatedTiming

Minimize t subject to (({{-5+(Subscript[x , 1])-2 (Subscript[x , 2]), 0, 0, 0}, {0, -1-3 (Subscript[x , 1])+4 (Subscript[x,  2]), 0, 0}, {0, 0, t, (Subscript[x , 1])+2 (Subscript[x,  2])}, {0, 0, (Subscript[x,  1])+2 (Subscript[x,  2]), -3 (Subscript[x,  1])+4 (Subscript[x , 2])}})) ⪰ 0

SemidefiniteOptimization[{1,0,0},{{{0,0,0,0},{0,0,0,0},{0,0, 1,0},{0,0,0, 0}},{{1,0,0,0},{0,-3 ,0,0},{0,0, 0,1},{0,0,1, -3}},{{-2 ,0,0,0},{0,4 ,0,0},{0,0, 0,2},{0,0,2, 4}}}, {{5,0,0,0},{0,1,0,0},{0,0, 0,0},{0,0,0, 0}}]//RepeatedTiming

Example 3: Max-Cut problem

The Max-Cut problem is an important NP-complete problem in graph theory that has been extensively studied. 

Goemans and Williamson published a semidefinite approach allowing an approximate solution in polynomial time in 1995 and their paper has been cited more than 3000 times since then.

The Max-Cut problem is to determine a subset S of the vertices V of a graph, for which the sum of the weights (Subscript[w,  i j]) of the edges that cross from S to its complement V \ S is maximized.

Let (Subscript[x, k])=1 for k∈S and (Subscript[x, k])=-1 for k∈V \ S. Then we need to solve an integer programming problem of maximizing the sum
(Underoverscript[(1/4)∑, (i,j=1), n])(Subscript[w, i j ])(1-(Subscript[x, i])(Subscript[x, j])) where (Subscript[x, k])∈{-1, 1}, k=1,…, n. The objective function can be represented in vector notation as (1/4)xᵀ·L·x, where x=((Subscript[x, 1]),…, (Subscript[x, n])) and L is the Laplacian (sometimes called Kirchoff) matrix of the graph: 
(Underoverscript[(1/4)∑, (i,j=1), n])(Subscript[w, i j ])(1-(Subscript[x, i])(Subscript[x, j])) = (Underoverscript[(1/4)∑, (i,j=1), n])(Subscript[x, i])(Subscript[w, i j ])(Subscript[x, i])-(Subscript[x, i])(Subscript[w, i j ])(Subscript[x, j]) = (1/4)xᵀ·(W·(1, 1, …,1) - W)·x = (1/4) xᵀ·L·x =Tr ((1/4)  L · (x·xᵀ))

If we let Y=x·xᵀ the problem becomes to minimize (1/4)Tr(L·Y) where Y is a symmetric rank-1 positive semidefinite matrix with (Subscript[Y, i i])=1. 
Dropping the rank-1 condition we obtain a SDP problem with the constraints (Subscript[Y, i i]) = 1 and Y ⪰ 0.  The condition (Subscript[Y, i i]) = 1 can be written as Tr[(Subscript[E, i i]) · Y] = 1.

If Y is a solution of the SDP problem, a cut can be constructed by following the procedure of randomized rounding: decompose Y = UᵀU, let ρ be an uniformly distrubuted random vector of unit norm and let (Subscript[x, k])=1⟺ρ·(Subscript[U, k])>0.

The solution of the relaxed problem clearly satisfies RELAX ≥ MAXCUT. Goemans and Williamson proved that the randomized rounding leads to a cut with expected value MAXCUT≥ E(Cut) ≥ α ×MAXCUT, where the constant α is given by

α=MinValue[{2/π *θ/(1-Cos[θ]),0≤θ≤π}, θ];
N[α,20]

Max-Cut code and examples

Code

laplacianMatrix[G_?GraphQ]:=(DiagonalMatrix[Total[#,{1}]]-#)&[WeightedAdjacencyMatrix[G]]

maxCutExact[G_?GraphQ]:=Module[{A=laplacianMatrix[G],n,x},
n=Length[First[A]];
x=Array["var",n];
MaxValue[{1/4x.A.x,x^2==ConstantArray[1,n]},x,Integers]
]

maxCutSDP[G_?GraphQ, trials_:10]:=Module[{L=laplacianMatrix[G],Y,U,n,sdpmax,x},
n=Length[First[L]];{Y,sdpmax}=SemidefiniteOptimization[ConstantArray[1,n], Table[SparseArray[{i,i}->1.,{n,n},0.], {i,n}], L/4,{"DualMatrix","DualMaximumValue"}];
U=CholeskyDecomposition[Y];
x=First[MaximalBy[Table[Sign[RandomPoint[Sphere[n]].U],trials],1/4#.L.#&]];
{sdpmax,HighlightGraph[G,Pick[Range[n],x,1]],1/4x.L.x}
]

Examples

Triangle

triang=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1},EdgeWeight->{2,3,4}, VertexSize->Small,VertexLabels->Placed["Name",Center],EdgeLabels->"EdgeWeight"]

maxCutSDP[triang]

maxCutExact[triang]

GridGraph

grid=GridGraph[{3,4},PlotLabel->(Subscript[G, 3,4]),VertexLabels->"Name",VertexSize->Medium]

maxCutSDP[grid]

maxCutExact[grid]

CompleteGraph

c15=CompleteGraph[15,VertexSize->Medium]

maxCutSDP[c15]

maxCutExact[c15]

PetersenGraph

pet=PetersenGraph[7,3,VertexSize->Medium]

maxCutSDP[pet]

maxCutExact[pet]

RandomGraph

g1=RandomGraph[{15,24}]

maxCutSDP[g1]

maxCutExact[g1]

g2=RandomGraph[{500,800}]

maxCutSDP[g2]//AbsoluteTiming

Table[Last[maxCutSDP[g2]],5]

Larger example

lg=RandomGraph[{1000,3000},EdgeWeight->RandomReal[1,3000]]

AbsoluteTiming[maxCutSDP[lg]]

Conclusion

Semidefinite optimization is a large and well-studied subfield of convex and conic optimization.

SDP problems can be solved by efficient methods and have been successfully used in numerous application domains.

Future versions of Mathematica will include SDP capabilities with an easy, unified interface.

References

Vandenberghe, Lieven, and Stephen Boyd. “Semidefinite programming.” SIAM review 38, no. 1 (1996): 49-95.

Vandenberghe, Lieven, and Stephen Boyd. “Applications of semidefinite programming.” Applied Numerical Mathematics 29, no. 3 (1999): 283-299.

Freund, Robert M. “Introduction to semidefinite programming (SDP).” Massachusetts Institute of Technology (2004).

Goemans, Michel X., and David P. Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.” Journal of the ACM (JACM) 42, no. 6 (1995): 1115-1145.

Borchers, Brian, and Joseph G. Young. “Implementation of a primal–dual method for SDP on a shared memory parallel architecture.” Computational Optimization and Applications 37, no. 3 (2007): 355-369.

Benson, Steven J., and Yinyu Ye. “DSDP5 user guide the dual-scaling algorithm for semidefinite programming.” Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, Tech. Rep. ANL/MCSTM-255 (2004).

O’Donoghue, Brendan, Eric Chu, Neal Parikh, and Stephen Boyd. “Conic optimization via operator splitting and homogeneous self-dual embedding.” Journal of Optimization Theory and Applications 169, no. 3 (2016): 1042-1068.