12.3 Semidefinite Optimization

Semidefinite optimization is an extension of conic optimization (see Sec. 12.2 (Conic Optimization)) allowing positive semidefinite matrix variables to be used in addition to the usual scalar variables. All the other parts of the input are defined exactly as in Sec. 12.2 (Conic Optimization), and the discussion from that section applies verbatim to all properties of problems with semidefinite variables. We only briefly indicate how the corresponding formulae should be modified with semidefinite terms.

A semidefinite optimization problem can be written as

(12.17)
minimizecTx+C,X+cfsubject tolcAx+A,Xuc,lxxux,Fx+F,X+gD,XjS+rj,j=1,,s

where

  • m is the number of constraints.

  • n is the number of decision variables.

  • xRn is a vector of decision variables.

  • cRn is the linear part of the objective function.

  • cfR is a constant term in the objective

  • ARm×n is the constraint matrix.

  • lcRm is the lower limit on the activity for the constraints.

  • ucRm is the upper limit on the activity for the constraints.

  • lxRn is the lower limit on the activity for the variables.

  • uxRn is the upper limit on the activity for the variables.

  • FRk×n is the affine conic constraint matrix.,

  • gRk is the affine conic constraint constant term vector.,

  • D is a Cartesian product of conic domains, namely D=D1××Dp, where p is the number of individual affine conic constraints (ACCs), and each domain is one from Sec. 14.8 (Supported domains).

is the same as in Sec. 12.2 (Conic Optimization) and moreover:

  • there are s symmetric positive semidefinite variables, the j-th of which is XjS+rj of dimension rj,

  • C=(Cj)j=1,,s is a collection of symmetric coefficient matrices in the objective, with CjSrj, and we interpret the notation C,X as a shorthand for

    C,X:=j=1sCj,Xj.
  • A=(Aij)i=1,,m,j=1,,s is a collection of symmetric coefficient matrices in the constraints, with AijSrj, and we interpret the notation A,X as a shorthand for the vector

    A,X:=(j=1sAij,Xj)i=1,,m.
  • F=(Fij)i=1,,k,j=1,,s is a collection of symmetric coefficient matrices in the affine conic constraints, with FijSrj, and we interpret the notation F,X as a shorthand for the vector

    F,X:=(j=1sFij,Xj)i=1,,k.

In each case the matrix inner product between symmetric matrices of the same dimension r is defined as

U,V:=i=1rj=1rUijVij.

To summarize, above the formulation extends that from Sec. 12.2 (Conic Optimization) by the possibility of including semidefinite terms in the objective, constraints and affine conic constraints.

Duality

The definition of the dual problem (12.9) becomes:

(12.18)maximize(lc)Tslc(uc)Tsuc+(lx)Tslx(ux)TsuxgTy˙+cfsubject toATy+slxsux+FTy˙=c,y+slcsuc=0,Cji=1myiAiji=1ky˙iFij=Sj,j=1,,s,slc,suc,slx,sux0,y˙D,SjS+rj,j=1,,s.

Complementarity conditions (12.11) include the additional relation:

(12.19)Xj,Sj=0j=1,,s.

Infeasibility

A certificate of primal infeasibility (12.12) is now a feasible solution to:

(12.20)maximize(lc)Tslc(uc)Tsuc+(lx)Tslx(ux)TsuxgTy˙subject toATy+slxsux+FTy˙=0,y+slcsuc=0,i=1myiAiji=1ky˙iFij=Sj,j=1,,s,slc,suc,slx,sux0,y˙D,SjS+rj,j=1,,s.

such that the objective value is strictly positive.

Similarly, a dual infeasibility certificate (12.13) is a feasible solution to

(12.21)minimizecTx+C,Xsubject tol^cAx+A,Xu^c,l^xxu^x,Fx+F,XD,XjS+rj,j=1,,s

where the modified bounds are as in (12.14) and (12.15) and the objective value is strictly negative.