Semidefinite and Conic Optimization Models

Nina Dokeva, Wolfram Research Inc

Join the Conversation #WolframTechConf

Introduction

This talk includes

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

modeling of convex optimization problems in conic and semidefinite form.

an introduction to the SemidefiniteOptimization and ConicOptimization Wolfram Language functions

examples and applications

From Linear to Conic Optimization

LinearOptimization — minimize {c.x|a.x+b \[VectorGreaterEqual]0}

ConicOptimization — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1,… ,k}

Conic inequality: x (Subscript[\[VectorGreaterEqual], 𝒦]) 0 ⧦ x ∈ 𝒦 for a proper cone 𝒦

“NonNegativeCone”

Let v={x,y} ∈ (((Reals))^2) . Then  v\[VectorGreaterEqual]0  ⟺ {x≥ 0,y≥0}  ⟺ v ∈ (NonNegativeConeList[2])

VectorGreaterEqual[{v,0}]

VectorGreaterEqual[{{x,y}, 0}]

VectorGreaterEqual[{{x,y},0}, {"NonNegativeCone",2}]

Graphics[{LightBlue,Rectangle[]}, Axes->True, Epilog->{Disk[{.4,.43},.01],Inset[Style["{x,y}",15],{Center, Center},{Center,Center}]}]

“NormCone”

First define the n-dimensional NormCone  (𝒬^n) as x∈(ℝ^n) such that ||{(Subscript[x, 1]),..., (Subscript[x, n-1])}||≤(Subscript[x, n])

When n=2, (Q^2) is the set of all {x,y} such that (Abs[x])≤y.

v={x,y}(Subscript[\[VectorGreaterEqual], (NormConeList[2])])0⧦ v={x,y} ∈ (NormConeList[2])⧦|x|≤ y

Plot[Abs[x],{x,-1,1},Filling->Top]

VectorGreaterEqual[{{x,y},0},{"NormCone",2}]

When n=3,  (𝒬^3) is the set of all {x,y,z} such that ||{x,y}||≤z⧦(Sqrt[(x^2)+(y^2)])≤z.

v={x,y,z}(Subscript[\[VectorGreaterEqual], (NormConeList[3])])0⧦ v={x,y,z} ∈ (NormConeList[3])⧦(Sqrt[(x^2)+(y^2)])≤z

RegionPlot3D[x^2+y^2≤z^2,{x, -1,1},{y,-1,1},{z,0,1}, PlotPoints->100]

VectorGreaterEqual[{{x,y,z},0},{"NormCone",3}]

Example: represent the nonlinear inequality (x^2)+(y^2)≤4  in conic form:

  (x^2)+(y^2)≤4 ⧦||{x,y}||≤2 ⧦{x,y,2}∈(Q^3)⧦{x,y,2}(Underscript[\[VectorGreaterEqual], (NormConeList[3])])0

VectorGreaterEqual[{{x,y,2} ,0}, {"NormCone",3}]

ConicOptimization transforms the problem internally and we can ask for the canonical form of the conic constraints.

ConicOptimization[0, (x^2)+(y^2)≤4, {x,y},"ConicConstraints"]

“SemidefiniteCone”

Define the SemidefiniteCone (Subscript[𝒮, +]^n) as the set of symmetric positive semidefinite matrices S∈(ℝ^n)×(ℝ^n)
 (Subscript[𝒮, +]^n) = { S ∈ (ℝ^(n ×n)):Sᵀ=S, xᵀ·S ·x ≥0  for  any  x ∈(ℝ^n) }

for n = 2 : S=(({{x, y}, {y, z}}))∈(SemidefiniteConeList[2]) ⧦S=(({{x, y}, {y, z}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[2])])0⟺{x ≥ 0, z ≥ 0, x z -(y^2)≥0}

RegionPlot3D[x≥0&&z≥0&&x z≥y^2, {x,0,1},{y,-1,1}, {z,0,1}, PlotPoints->100, AxesLabel->{"x","y","z"}]

VectorGreaterEqual[{{{x,y},{y,z}} ,0}, {"SemidefiniteCone",2}]

Later we will show that we can write the constraint (x^2)+(y^2)≤4  in semidefinite form as: (({{2, x, y}, {x, 2, 0}, {y, 0, 2}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[3])])0

The nonlinear constraint (x^2)+(y^2)≤4  can be represented as a conic linear inequality with respect to the norm cone or the semidefinite cone:

x^2+y^2≤4  ⟺  {x,y,2}(Underscript[\[VectorGreaterEqual], (NormConeList[3])])0 ⟺ (({{2, x, y}, {x, 2, 0}, {y, 0, 2}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[3])])0

Library Solvers

Once in semidefinite or conic form, several different libraries can be used to solve the problems at machine precision. 
This is done by calling SemidefiniteOptimization and ConicOptimization with a method option like Method -> "CSDP". 

Inputs will be automatically converted to an appropriate form for each solver implementation. 
The available libraries in the conference beta 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.

Convex optimization

Convex minimization studies the problem of minimizing convex functions over convex sets .

More specifically, the optimization problem

minimize    (Subscript[f, 0])(x)

subject to   (Subscript[f, i])(x)≤ 0, i = 1,...m
(Subscript[h, j])(x)=0, j=1,...p

is a convex optimization problem if (Subscript[f, i])(x) are convex and (Subscript[h, j])(x) are affine ((Subscript[h, j])(x) = (Subscript[a, j]).x+(Subscript[b, j]))

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.

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

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

Available cones

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[⪰, 𝒦]) 0 and A x = b

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

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

ConicOptimization — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1,… ,k}

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[a, 0])+(Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])(Subscript[\[VectorGreaterEqual], (Subscript[𝒮, +]^n)])0

The dual formulation of the same problem is given by

maximize -Tr[(Subscript[a, 0]).y] subject to Tr[(Subscript[a, i]).y]=(Subscript[c, i]),i=1,..., k and y ⪰ 0

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.

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

Modeling transformations

Modeling convex optimization problems into conic and semidefinite form.

ConicOptimization — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1,…, k}

SemidefiniteOptimization — minimize {c.x|(Subscript[a, 0])+(Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])(Subscript[\[VectorGreaterEqual], (Subscript[𝒮, +]^n)])0}

1. Epigraph Transformation (and power cone)

The epigraph transformation uses an auxiliary variable ( t ) which becomes a linear objective function.

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

Minimize ((Abs[x+y])^1.5) over a unit disk centered at {1, 1}.

ConicOptimization[t,{{x,y}∈Disk[{1,1}], ((Abs[x+y])^1.5)≤t},{x,y,t}]

Power Cone

Let α=1/1.5. Then the constraint ((Abs[x+ y])^(1/α))≤t ⟺ (Abs[x+y])≤(t^α)⟺ (Abs[x+y])≤(t^α)(1^(1-α)) or  {t,1,x+y}(Underscript[\[VectorGreaterEqual], (PowerConeList[α])])0:

The exponential cone (Subscript[𝒦, α]), 0<α<1, is defined as  x∈(ℝ^3) such that (Subscript[x, 1]^α)(Subscript[x, 2]^(1-α))≥|(Subscript[x, 3])|,(Subscript[x, 1])≥0 ,(Subscript[x, 2])≥0.

RegionPlot3D[α=1/1.5;(Subscript[x, 1]^α) (Subscript[x, 2]^(1-α))≥Abs[(Subscript[x, 3])],{(Subscript[x, 1]),0,1},{(Subscript[x, 2]),0,1},{(Subscript[x, 3]),-1,1},PlotPoints->100,AxesLabel->{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}]

ConicOptimization[t,{{x-1,y-1,1}(Underscript[\[VectorGreaterEqual], (NormConeList[3])])0, {t,1,x+y}(Underscript[\[VectorGreaterEqual], (PowerConeList[α])])0},{x,y,t}]

NMinimize[{((Abs[x+y])^1.5),{x,y}∈Disk[{1,1}]},{x,y}]

2. Norm transformations

(L^1) norm

Minimize ||{x+1,x-y}(Subscript[||, 1])=(Abs[x+1])+(Abs[x-y]) over a regular pentagon. Convert the objective to  (Subscript[s, 1])+(Subscript[s, 2])  with the additional constraints -(Subscript[s, 1])≤x+1≤(Subscript[s, 1]),-(Subscript[s, 2])≤x-y≤(Subscript[s, 2]):

ConicOptimization[s1+s2,{{x,y}∈RegularPolygon[5],-s1≤x+1≤s1,-s2≤x-y≤s2},{x,y,s1,s2}]

ConicOptimization[t,{{x,y}∈RegularPolygon[5],Norm[{x+1,x-y},1]≤t},{x,y,t}]

(L^2) norm

Minimize ||{x+1,x-y}(Subscript[||, 2]) over a regular pentagon. Convert the objective to t  with the additional constraint ||{x+y,x-y}(Subscript[||, 2])≤t.

ConicOptimization[t,{{x,y}∈RegularPolygon[5],Norm[{x+1,x-y}]≤t},{x,y,t}]

(L^∞) norm

Minimize ||{x+1,x-y}(Subscript[||, ∞])=max{(Abs[x+1]),(Abs[x-y])} over a regular pentagon. Convert the objective into a linear function t subject to the constraints  -t≤x+1≤t,-t≤x-y≤t:

ConicOptimization[t,{{x,y}∈RegularPolygon[5],-t≤x+1≤t,-t≤x-y≤t},{x,y,t}]

ConicOptimization[t,{{x,y}∈RegularPolygon[5],Norm[{x+1,x-y},∞]≤t},{x,y,t}]

(L^p) norm

Minimize ||{x+1,x-y}(Subscript[||, 1.5]) = (((((Abs[x+1])^(1/α))+((Abs[x-y])^(1/α))))^(α )) (with α=1/1.5) over a regular pentagon.

Since ||a.x+b(Subscript[||, 1.5])= ((((∑_(i=1)^n)((Abs[(Subscript[a, i])x+(Subscript[b, i])])^(1/α))))^α)≤t ⟺ (∑_(i=1)^n)(((Abs[(Subscript[a, i])x+(Subscript[b, i])])^(1/α))/(t^(1/α-1)))≤t,  bounding (((Abs[(Subscript[a, i])x+(Subscript[b, i])])^(1/α))/(t^(1/α-1))) with (Subscript[s, i]) where (∑_(i=1)^n)(Subscript[s, i])=t gives {(Subscript[s, i]),t,(Subscript[a, i])x+(Subscript[b, i])}(Underscript[\[VectorGreaterEqual], (PowerConeList[α])])0,   i=1,…,n.

a= {{1.,0.},{1.,-1.}}; b = {1.,0.};α=1/1.5;
ConicOptimization[t,{x∈RegularPolygon[5],{s1,t,a[[1]].x +b[[1]]}(Underscript[\[VectorGreaterEqual], (PowerConeList[α])])0,{s2,t,a[[2]].x +b[[2]]}(Underscript[\[VectorGreaterEqual], (PowerConeList[α])])0,s1+s2==t},{x∈Vectors[2],t,s1,s2}]

ConicOptimization[t,{x∈RegularPolygon[5],Norm[a.x+b, 1.5]≤t},{x,t}]

3. Schur complement condition

A Schur complement condition says that

If C\[VectorGreater]0, a block matrix (({{A, B}, {(B^T), C}}))\[VectorGreaterEqual]0 iff A-B.(C^(-1)).(B^T)\[VectorGreaterEqual]0.

Example 1. Minimize||a.x-b||.  Using an auxiliary variablet  the transformed problem is to minimizetsuch that||a.x-b||≤t.

||a.x-b||≤t ⟺ (a.x-b)ᵀ.(a.x-b)≤(t^2)⟺t-(a.x-b)ᵀ.(((t I))^(-1)).(a.x-b)≥0:

Therefore, ||a.x-b||≤t is equivalent to  (({{t, (((a.x-b))^T)}, {a.x-b, t I}}))\[VectorGreaterEqual]0 for t>0 and for t=0 since then a.x-b must be 0:

SemidefiniteOptimization[t,{ℐ==IdentityMatrix[3],a=={{1,2},{3,4},{5,6}},b=={7,8,10},(({{t, a.x-b}, {a.x-b, t ℐ}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeString)])0},{t,x∈Vectors[2]}]

SemidefiniteOptimization[t,{ℐ==IdentityMatrix[3],a=={{1,2},{3,4},{5,6}},b=={7,8,10},Norm[a.x-b]≤t},{t,x∈Vectors[2]}]

Example 2. Convert the constraint  (x^2)+(y^2)≤4  ⟺ ||{x,y}||≤ 2  into semidefinite form:

In ||a.v-b||≤t   ⟺ (({{t, (((a.v-b))^T)}, {a.v-b, t I}}))\[VectorGreaterEqual]0 use  v={x,y}, a=(({{1, 0}, {0, 1}})),b=0  to get ||{x,y}||≤2 ⟺ (({{2, x, y}, {x, 2, 0}, {y, 0, 2}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[3])])0

4. S-procedure

For quadratic sets (these include which includes ellipsoids, quadratic cones and paraboloids)
 (Subscript[𝒬, i])={x∈(ℝ^n)|(x^T).(Subscript[a, i]) .x+2 x.(Subscript[b, i]^T)+(Subscript[c, i])≤0}, where (Subscript[a, i]) are symmetric matrices, (Subscript[b, i]) are vectors and (Subscript[c, i]) scalars, determine whether (Subscript[𝒬, 1])⊆(Subscript[𝒬, 2]) :

Assuming that the sets  (Subscript[𝒬, i]) are full dimensional, the S-procedure says that

(Subscript[𝒬, 1])⊆(Subscript[𝒬, 2 ])⧦ there exists λ≥0 such that λ (({{(Subscript[a, 1]), (Subscript[b, 1])}, {(Subscript[b, 1]^T), (Subscript[c, 1])}})) ⪰ (({{(Subscript[a, 2]), (Subscript[b, 2])}, {(Subscript[b, 2]^T), (Subscript[c, 2])}}))

{a1,b1,c1}={{{0.7,0.68},{0.68,0.94}},{0.35,.42},0.12};{a2,b2,c2}={{{0.13,0.2},{0.2,0.62}},{.2,.35},.01};

SemidefiniteOptimization[0, {λ(({{a1, b1}, {b1, c1}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[3])])(({{a2, b2}, {b2, c2}})),λ≥0},λ]

With[{x={x1,x2}},RegionPlot[{x.a1.x+2 b1.x+c1≤0,x.a2.x+2 b2.x+c2≤0},{x1,-4,2},{x2,-2,2},PlotLegends->{(Subscript[𝒬, 1]),(Subscript[𝒬, 2])}]]

{a1,b1,c1}={{{0.7,0.68},{0.68,0.94}},{0.35,.2},0.12};{a2,b2,c2}={{{0.13,0.2},{0.2,0.62}},{.2,.35},.01};

SemidefiniteOptimization[0, {λ(({{a1, b1}, {b1, c1}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[3])])(({{a2, b2}, {b2, c2}})),λ≥0},λ]

With[{x={x1,x2}},RegionPlot[{x.a1.x+2 b1.x+c1≤0,x.a2.x+2 b2.x+c2≤0},{x1,-4,2},{x2,-2,2},PlotLegends->{(Subscript[𝒬, 1]),(Subscript[𝒬, 2])}]]

5. Eigenvalue optimization

Find {x,y} that minimizes the largest eigenvalue of a symmetric matrix A(x,y) =(Subscript[a, 0])+(Subscript[a, 1])x+(Subscript[a, 2])y.

The problem can be formulated as linear matrix inequality, since
 λℐ⪰A(x,y)⧦λ≥(Subscript[λ, 1]),…,λ≥(Subscript[λ, n])   where (Subscript[λ, i]) is the i(^th) eigenvalue of A(x,y).

A[x_,y_]:=(({{2, -3}, {-3, 4}}))+(({{1, 2}, {2, 3}})) x+(({{4, 5}, {5, 6}})) y

A[x,y]//MatrixForm

A real symmetric matrix A can be diagonalized with an orthogonal matrix Q so (Q^T).A.Q=diag({(Subscript[λ, 1]),…,(Subscript[λ, n])}). Hence (Q^T).(λ ℐ-A).Q=diag({λ-(Subscript[λ, 1]),…,λ-(Subscript[λ, n])})⪰0 iff λ≥(Subscript[λ, 1]),…,λ≥(Subscript[λ, n]). Since any u=Q .(Q^T)u, taking v=(Q^T).u, (u^T).(λ ℐ-A). u=(v^T).(Q^T).(λ ℐ-A). Q .v≥0, hence λ ℐ-A⪰0 iff λ≥(Subscript[λ, 1]),…,λ≥(Subscript[λ, n]).

res=SemidefiniteOptimization[λ,λ (({{1, 0}, {0, 1}})) (Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[2])])A[x,y],{λ,x,y}]

Run a Monte Carlo simulation to check the plausibility of the result:

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

Similar eigenvalue examples:

Maximize the smallest eigenvalue:   λℐ⪯A(x,y)

res=SemidefiniteOptimization[-λ,λ (({{1, 0}, {0, 1}})) (Underscript[\[VectorLessEqual], (SemidefiniteConeList[2])])A[x,y],{λ,x,y}]

Minimizes the difference between the largest and the smallest eigenvalue:

res=SemidefiniteOptimization[μ-λ,{λ (({{1, 0}, {0, 1}})) (Underscript[\[VectorLessEqual], (SemidefiniteConeList[2])])A[x,y](Underscript[\[VectorLessEqual], (SemidefiniteConeList[2])])μ (({{1, 0}, {0, 1}}))},{λ,μ,x,y}]

Minimize the largest by absolute value eigenvalue:

res=SemidefiniteOptimization[λ,{-λ (({{1, 0}, {0, 1}}))(Underscript[\[VectorLessEqual], (SemidefiniteConeList[2])])A[x,y](Underscript[\[VectorLessEqual], (SemidefiniteConeList[2])])λ (({{1, 0}, {0, 1}}))},{λ,x,y}]

Exponential cone example and application

Simple exponential cone example

Minimize -log(x+y) over a unit disk centered at {2,2}. 
Using the auxiliary variable t, the objective is transformed to minimizing -t with the additional constraint  -log(x+y)≤-t:

The exponential cone (Subscript[𝒦, exp]) is defined as x∈(ℝ^3) such that  (Subscript[x, 2])(e^(((Subscript[x, 1])/(Subscript[x, 2]))))≤(Subscript[x, 3]), (Subscript[x, 2])≥ 0.

RegionPlot3D[(Subscript[x, 2])(E^((Subscript[x, 1])/(Subscript[x, 2])))≤(Subscript[x, 3]),{(Subscript[x, 1]),-2,1},{(Subscript[x, 2]),0.01,1},{(Subscript[x, 3]),0,2},PlotPoints->100,AxesLabel->{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}]

The constraint -log(x+y)≤-t   ⟺  t≤log(x+y)⟺ (e^t)≤x+y ⟺ {t,1,x+y}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0.

ConicOptimization[-t,{{x,y}∈Disk[{2,2}], {t,1,x+y}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0},{x,y,t}]

ConicOptimization[-t,{{x,y}∈Disk[{2,2}], -Log[x+y]≤-t},{x,y,t}]

Find the analytic center of linear inequalities defining a polygon

Construct a random convex polygon.

SeedRandom[123];
pts=RandomReal[{-1,1},{5,2}];
cmesh = ConvexHullMesh[pts]

It can be represented as intersections of half-planes (Subscript[a, i]).x +(Subscript[b, i])≥ 0,i=1,2,…,n.

{a,b} =First[ConicOptimization[0,x∈cmesh,x,"ConicConstraintAffineLists"]];

The analytic center is defined as x that maximizes (∏_(i=1)^n)((Subscript[a, i]).x+(Subscript[b, i]))  or it can also be defined as a point that maximizes the product of distances to the constraints.

The distance of point x  in the polyhedron to each side is  (Subscript[d, i ])= ((Abs[(Subscript[a, i]).x + (Subscript[b, i])])/( (Norm[(Subscript[a, i])])))= (((Subscript[a, i]).x + (Subscript[b, i]))/( (Norm[(Subscript[a, i])]))).

 Taking log and negating the objective, the transformed objective is -(∑_(i=1)^m)log((Subscript[a, i]).x+(Subscript[b, i])):

n=Length[a];
obj=Total[Table[-Log[a[[i]].x+b[[i]]],{i,n}]];

res=ConicOptimization[t,obj≤t,{t,x}, Method->{"SCS", Tolerance->10^-7}]

xc=x/.res

Show[cmesh, Graphics[{PointSize[0.02],Point[xc]}]]

Given the analytic center, the following are known to be inscribed and covering ellipsoids centered at it:

m=Transpose[a].DiagonalMatrix[Table[(((a[[i]].xc+b[[i]]))^(-2)),{i,Length[a]}]].a;
ellipses = With[{x={x1,x2}},RegionPlot[{(x-xc).m.(x-xc)≤1,(x-xc).m.(x-xc)≤(n^2)-n},{x1,-2,2},{x2,-2,2}]];
Show[cmesh,ellipses,Graphics[{PointSize[0.02],Point[xc]}]]

Lovász number ϑ of a graph G

Let G = (V, E) is a graph with vertices V and edges E.

The Lovász (theta) number ϑ(G) is a graph property (real number), introduced by László Lovász in 1979 [4].

ϑ(G)  is an upper bound for the Shannon capacity of a graph.

“Sandwich” theorem: ω(G)≤ ϑ(G)≤χ(G) . Clique ω(G) and chromatic χ(G) numbers are NP-complete problems, while ϑ(G) can be approximated in polynomial time.

Several alternative definitions, including as a semidefinite problem.

Primal:
 Let A a be any symmetric matrix such that (Subscript[a, i j])=1 if i=j or i j ∉ E , and let λ(A) be the largest eigenvalue of A. 
Then  ϑ(G) =min λ(A) over all such matrices.

Dual:
Let Y be a positive semidefinite matrix such that (Subscript[Y, i j])=0 whenever i j ∈ E and Tr(Y)=(∑_(i=1)^n)(Subscript[Y, i i]) =1. 
Then ϑ(G)=max Σ (Subscript[Y, i j]) over all such matrices.

The dual formulation is convenient for direct translation to SemidefiniteOptimization:

Σ(Y)=Tr(J.Y),(Subscript[J, i j])=1

Tr(Y)=1⧦Tr(I.Y)=1

(Subscript[Y, i j])=0 ⧦ Tr((Subscript[S, i j]).Y) = 0, (Subscript[S, i j])=(Subscript[S, j i])=1, all other elements 0 (for all adjacent i and j).

SemidefiniteOptimization[c, {(Subscript[a, 0]),(Subscript[a, 1]), ... , (Subscript[a, n])}]
Primal: minimize {c.x|(Subscript[a, 0])+(Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])(Subscript[\[VectorGreaterEqual], (Subscript[𝒮, +]^n)])0}
Dual: maximize {-Tr[(Subscript[a, 0]).y]|Tr[(Subscript[a, i]).y]=(Subscript[c, i]),i=1,..., k, y⪰0}

c = {1, 0, ..., 0} , (Subscript[a, 0])=-J, (Subscript[a, 1]) = I, all other (Subscript[a, k]) are (Subscript[S, i j]) for  i j ∈E

LovaszTheta[g_?GraphQ]:=Module[{n=VertexCount[g],m=AdjacencyMatrix[g],amats,adjvs},
adjvs=UpperTriangularize[m]["NonzeroPositions"];amats=Join[{ConstantArray[-1,{n,n}],IdentityMatrix[n]},Apply[Function[SparseArray[{{#1,#2}->1,{#2,#1}->1},{n,n}]],adjvs,1]];
SemidefiniteOptimization[Flatten[{1, ConstantArray[0,Length[adjvs]]}],amats,"DualMaximumValue"]]

Verify numerically the original result from 1979:

LovaszTheta[CycleGraph[5]]

Sqrt[5.]

GraphData contains precomputed exact values for some graphs

Length[known=Select[all=GraphData[All],GraphData[#,"LovaszNumber"]=!=Missing["NotAvailable"]&]]

Length[unknown=Complement[all,known]]

Easily obtain an approximate value for any of the others:

Map[Function[g,LovaszTheta[GraphData[g,"Graph"]]],RandomChoice[unknown,{5}]]

Compute the Lovasz number of a larger random graph:

g=RandomGraph[{300,500}]

AbsoluteTiming[LovaszTheta[g]]

Conclusions

Many convex optimization problems can be modeled into semidefinite and conic optimization form and solved efficiently.

Version 12 of the Wolfram Language includes new capabilities for conic and semidefinite optimization with an 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).

Lovász, László. “On the Shannon capacity of a graph.” IEEE Transactions on Information theory 25.1 (1979): 1-7.

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.

Thank you!
Questions?