Effective Convex
Optimization Solvers

Nina Dokeva, Wolfram Research Inc

Overview of the talk

This talk includes

a brief discussion of convex optimization in the Wolfram Language

new convex optimization functionality

external libraries and methods

plug-in method to add solvers

Convex optimization definitions

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

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|x(Subscript[\[VectorGreaterEqual], 𝒦])0, 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}

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

“NonNegativeCone”

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

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}]

“PowerCone”

The power 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[α=0.3;(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])}]

“ExponentialCone”

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])}]

From Convex to Conic example

Maximize the area of a rectangle such that the perimeter is at most 1:

Minimize[{(1/(w h)),{2w+2h≤1, h>0, w>0}},{h,w}]

To use ConicOptimization we need a linear objective

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

transf={h->Exp[x], w->Exp[y]};

obj= (1/(w h));constr={2w+2h≤1, h>0, w>0};

{obj, constr}/.transf

Take Log of the objective and the new objective is  linear: -x -y

Replace 2 (e^x)+ 2 (e^y)≤ 1 with   {2 (e^x)≤ (Subscript[t, 1, ])2 (e^y)≤ (Subscript[t, 2]), (Subscript[t, 1])+(Subscript[t, 2])≤1},

2 (e^x)≤ (Subscript[t, 1]) ⧦  1(e^(x/1))≤ (Subscript[t, 1])/2 can be written as conic linear using the  exponential cone ({{(Subscript[𝒦, exp]):, x∈(ℝ^3) such that (Subscript[x, 2])(e^(((Subscript[x, 1])/(Subscript[x, 2]))))≤(Subscript[x, 3])∧(Subscript[x, 2])≥0}})

VectorGreaterEqual[{{x,1,t1/2},0}, "ExponentialCone"]

(Subscript[t, 1])+(Subscript[t, 2])≤1  in canonical form is {{-1.,-1.}}.{t1,t2}+{1.}(Underscript[\[VectorGreaterEqual], (NonNegativeConeList[1])])0

The problem in conic form becomes

res=ConicOptimization[-x-y, {{x,1,(t1/2)}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0, {y,1,(t2/2)}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0,  {{-1.,-1.}}.{t1,t2}+{1.}(Underscript[\[VectorGreaterEqual], (NonNegativeConeList[1])])0},{x,y, t1, t2} ]

res=ConicOptimization[-x-y, {{x,1,(t1/2)}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0, {y,1,(t2/2)}(Underscript[\[VectorGreaterEqual], (ExponentialConeString)])0,  {{-1.,-1.}}.{t1,t2}+{1.}(Underscript[\[VectorGreaterEqual], (NonNegativeConeList[1])])0},{x,y, t1, t2}, Tolerance->(10^(-7)) ]

res1=transf/.res

GeometricOptimization[(1/(w h)),{2w+2h≤1},{h,w}]

Geometric optimization

Definitions

GeometricOptimization[f,cons,vars] 
finds positive values of variables vars that minimize the posynomial objective subject to posynomial constraints cons.

Geometric optimization is often used when minimizing quantities like area, volume or power.

Geometric optimization finds x\[VectorGreater]0 that solves the primal problem:

A monomial is a product of powers, m(x)= (Subscript[x, 1]^(Subscript[α, 1]))(Subscript[x, 2]^(Subscript[α, 2]))(Subscript[…x, k]^(Subscript[α, k])) with (Subscript[α, i])∈ℝ. A posynomial is a positive sum of monomials p(x)=(Subscript[Σ, j]) (Subscript[c, j])(Subscript[m, j])(x) with (Subscript[c, j])≥0.

A generalized posynomial g(x) is a posynomial or a combination of generalized posynomials:

Examples

Minimize the length of the diagonal of a rectangle of area 4 such that the width plus three times the height is less than 7:

GeometricOptimization[Sqrt[w^2+h^2],{w h ==4, w + 3h ≤ 7},{w,h}]

Minimize[Sqrt[w^2+h^2],{w h ==4, w + 3h ≤ 7,h>0,w>0},{w,h}]

%//N

Given an n×n matrix A with nonnegative real entries, find a diagonal matrix D with positive entries that minimizes the sum of squares (the Frobenius norm squared) of the similar matrix D.A.(D^(-1)):

n = 10;
A = BlockRandom[10^RandomReal[{-5,5},{n,n}], RandomSeeding->1234];

Let d={(Subscript[d, 1]),…,(Subscript[d, n])} be the diagonal entries of D.  Since (Subscript[d, i]) is positive, the entries of (D^(-1)) are {1/(Subscript[d, 1]),…,1/(Subscript[d, n])} so the entries of the product are ((Subscript[(D.A.(D^(-1))), i j])=(Subscript[A, i j])((Subscript[d, i])/(Subscript[d, j])):

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}]

Compare norms of the original and scaled matrices:

scaledA = DiagonalMatrix[d /. drule].A.DiagonalMatrix[1/d /. drule];

{Norm[A,"Frobenius"], Norm[scaledA,"Frobenius"]}

The matrices are similar, so the eigenvalues are equal:

Eigenvalues[A] ==  Eigenvalues[scaledA]

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]

Convex optimization functions

Convex Optimization Classes

(RefLink[LinearOptimization, paclet:ref/LinearOptimization]) — minimize {c.x|a.x+b \[VectorGreaterEqual]0}

(RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]) — minimize {(α.x+β)/(γ.x+δ)|a.x+b\[VectorGreaterEqual]0}

(RefLink[QuadraticOptimization, paclet:ref/QuadraticOptimization]) — minimize {(1/2)x.q.x+c.x|a.x+b\[VectorGreaterEqual]0}

(RefLink[SecondOrderConeOptimization, paclet:ref/SecondOrderConeOptimization]) — minimize {c.x|‖(Subscript[a, j]).x+(Subscript[b, j])‖≤(Subscript[α, j])+(Subscript[β, j]),j=1… k}

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

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

The following is generally non-convex but can be transformed and solved as convex:

(RefLink[GeometricOptimization, paclet:ref/GeometricOptimization]) — minimize {(Subscript[g, 0])(x)|(Subscript[g, i])(x)≤ 1,i=1,…,s, (Subscript[c, (Subscript[i, eq])])(Subscript[m, (Subscript[i, eq])])(x)=1, j=1… k}

General Convex & Nonconvex Optimization

(RefLink[FindMinimum, paclet:ref/FindMinimum]) — numerical local constrained optimization

(RefLink[NMinimize, paclet:ref/NMinimize]) — numerical global constrained optimization

(RefLink[Minimize, paclet:ref/Minimize]) — symbolic global constrained optimization

Mixed integer solvers and methods (1)

Solve conic optimization problems where some of the variables are real and some are Integer.

For linear problems ConicOptimization calls LinearOptimization which uses the CBC library (method ”BranchAndBound”) for mixed integer problems.

ConicOptimization[x+y,{x+2y≥4,x≥0.5},{x,y}]

ConicOptimization[x+y,{x+2y≥4,x≥ 0.5},{x,y∈Integers}]

LinearOptimization[x+y,{x+2y≥4,x≥ 0.5},{x,y∈Integers}, Method->"BranchAndBound"]

ConicOptimization[x+y,{x+2y≥4,x≥0.5},{x,y∈Integers}, Method->"MOSEK"]

Mixed integer solvers and methods (2)

Non-linear conic optimization mixed integer problems use method “OuterApproximation”:

ConicOptimization[x+2y,{(x^2)+2(y^2)≤ 3,x+y==2},{x,y}]

ConicOptimization[x+2y,{(x^2)+2(y^2)≤ 3,x+y==2},{x∈Integers,y}]

ConicOptimization[x+2y,{(x^2)+2(y^2)≤ 3,x+y==2},{x∈Integers,y}, Method->"OuterApproximation"]

ConicOptimization[x+2y,{(x^2)+2(y^2)≤ 3,x+y==2},{x∈Integers,y}, Method->"MOSEK"]

Library Solvers

External libraries

COIN: CLP (linear programming) and CBC (branch and cut)

Part of the COIN-OR project, CLP is a linear and quadratic programming solver and CBC is a mixed integer programming solver

IPOPT (Interior point optimizer)

Part of the COIN-OR project, IPOPT is a software package for large-scale nonlinear optimization

CSDP: A C Library for Semidefinite Programming [4]

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. [5]

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 [6]

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.

MOSEK: Commercial solver for large-scale sparse linear, quadratic and conic optimization problems by Erling D. Andersen [7]
 (must already have MOSEK license)

In addition to real conic problems MOSEK allows mixed-integer variables in combination with the linear, the quadratic, the exponential and the power cones.

Library examples and comparison

The open source libraries used for convex optimization in the Wolfram Language are generally quite good for the particular areas that they target, such as CLP and CBC for real valued and mixed integer linear problems and CSDP/DSDP for real valued semidefinite problems.

When available, MOSEK can have an advantage in several places where we use SCS by default (in real valued second order cone problems and problems with power and exponential cones). Also it is the only external library option that supports conic mixed integer problems, but we are adding our own OuterApproximation algorithm.

SOCP

SeedRandom[1234];
n=1000;
m=800;
a=RandomReal[1,{n,m}];
b=RandomReal[1,n];

AbsoluteTiming[t/.ConicOptimization[t, Norm[Inactive[Plus][a.x,-b]]^2+Norm[x,1]<t,{Element[x,Vectors[m]],t}]]

AbsoluteTiming[t/.ConicOptimization[t, Norm[Inactive[Plus][a.x,-b]]^2+Norm[x,1]<t,{Element[x,Vectors[m]],t}, {Method->"SCS", Tolerance->10^-6}]]

AbsoluteTiming[t/.ConicOptimization[t, Norm[Inactive[Plus][a.x,-b]]^2+Norm[x,1]<t,{Element[x,Vectors[m]],t},Method->"MOSEK"] ]

Exponential cones

GeometricOptimization calls ConicOptimization with linear and exponential cones.

n = 10;
A = BlockRandom[10^RandomReal[{-5,5},{n,n}], RandomSeeding->1234];

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}, "PrimalMinimumValue"]//AbsoluteTiming

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}, "PrimalMinimumValue", Method->{"SCS", Tolerance->10^-6}]//AbsoluteTiming

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}, "PrimalMinimumValue", Method->{"SCS", Tolerance->10^-3}]//AbsoluteTiming

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}, "PrimalMinimumValue",Method->"MOSEK"]//AbsoluteTiming

drule = GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]}, "PrimalMinimumValue",Method->"IPOPT"]//AbsoluteTiming

Plug-in method

for ConicOptimization and related functions

The solver name method should be a string.  Once a solver is registered, it can be using in the Wolfram Language optimization functions using Method->method.

The following keys are considered in the Association assoc:

Example with MOSEK

The primal formulation of conic optimization problem in MOSEK  is closer to the dual formulation in Wolfram Language. Since the mixed-integer solver works only for the primal MOSEK problem, Wolfram Language transforms its primal formulation to fit MOSEK’s by adding variables and constraints when a mixed integer problem is specified and uses the solver MOSEKPrimal.

MOSEK primal: minimize {c.x+(c^f)| (l^c)≤A x≤(u^c), (l^x)≤x≤(u^x), x (Subscript[⪰, 𝒦])0}

Optimization`ConvexSolvers`RegisterConvexMethod["MOSEKPrimal",Association["SolveFunction"->MOSEKSolvePrimal,"ConicConstraintSupport"->{"EqualityConstraint"->"Affine","NonNegativeCone"->"Affine","NormCone"->"Membership","SemidefiniteCone"->"Membership","ExponentialCone"->"Membership","DualExponentialCone"->"Membership","PowerCone"->"Membership","DualPowerCone"->"Membership"},"MixedIntegerSupport"->True]]

For real valued problems it uses MOSEKSolveDual since it is a more direct match and is more efficient (has less variables and constraints).

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

Optimization`ConvexSolvers`RegisterConvexMethod["MOSEKDual",Association["SolveFunction"->MOSEKSolveDual,"ConicConstraintSupport"->Thread[{"EqualityConstraint","NonNegativeCone","NormCone","SemidefiniteCone","ExponentialCone","DualExponentialCone","PowerCone","DualPowerCone"}->"Affine"],"MixedIntegerSupport"->False]]

Optimization`ConvexSolvers`RegisterConvexMethod["MOSEK",Association["Submethods"->{"MOSEKDual","MOSEKPrimal"}]]

MOSEKSolvePrimal[problemData_,pmopts___]:=...
MOSEKSolveDual[problemData_,pmopts___]:=...

Conclusions

Many convex optimization problems can be modeled into semidefinite and conic optimization form (using several particular cone types) and solved efficiently.

Version 12 of the Wolfram Language added new capabilities for conic and semidefinite optimization with an unified interface.

Version 12.1 expands these in several ways, including but not limited to mixed-integer optimization, geometric optimization and an interface to MOSEK.

In addition to  several built-in external library solvers, more interfaces to third party solvers can be included in the future. Customers will also have the ability to make use of the convex optimization framework by registering their own methods as plug-ins.

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).

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.

Andersen, Erling D., and Knud D. Andersen. “The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm.” In High performance optimization, pp. 197-232. Springer, Boston, MA, 2000.