# SDP -- construct a semidefinite program

## Synopsis

• Usage:
P = sdp(C,A,b)
P = sdp(var,M,objFun)
• Inputs:
• C, , a symmetric $n\times n$ matrix
• A, , consisting of $m$ symmetric $n\times n$ matrices
• b, , a $m\times 1$ matrix
• var, a list, of variables
• M, , constraint matrix with affine-linear entries
• objFun, , linear function to be minimized
• Outputs:
• P, an instance of the type SDP, a semidefinite programming problem

## Description

A semidefinite program (SDP) is defined by a some symmetric matrices $C, A_i$ and a vector $b$. The SDP has a primal and a dual problem. The primal problem is

$$min_{X} \, C \bullet X \,\,\, s.t. \,\,\, A_i \bullet X = b_i \, and \, X \geq 0$$

and the dual problem is

$$max_{y,Z} \, \sum_i b_i y_i \,\,\, s.t. \,\,\, Z = C - \sum_i y_i A_i \, and \, Z \geq 0$$

The type SDP stores semidefinite programs. There are two ways to construct an SDP. The first option is to provide the matrices $C,A_i,b$.

 i1 : P = sdp(matrix{{1,0},{0,2}}, matrix{{0,1},{1,0}}, matrix{{-1}}) o1 = SDP{A => 1 : (| 0 1 |)} | 1 0 | b => | -1 | C => | 1 0 | | 0 2 | o1 : SDP

The second option is to provide a matrix $M(v)$, with affine entries, and a linear function $f(v)$. This constructs an SDP in dual form: minimize $f(v)$ subject to $M(v)\geq 0$.

 i2 : R = QQ[u,v,w]; i3 : M = matrix {{1,u,3-v},{u,5,w},{3-v,w,9+u}} o3 = | 1 u -v+3 | | u 5 w | | -v+3 w u+9 | 3 3 o3 : Matrix R <--- R i4 : objFun = u+v+w; i5 : P = sdp({u,v,w}, M, objFun);

Semidefinite programs can be solved numerically using the method optimize, and in small cases also symbolically with the method criticalIdeal.

## Methods that use an object of class SDP :

• "criticalIdeal(SDP)" -- see criticalIdeal -- ideal of critical equations of a semidefinite program
• "criticalIdeal(SDP,ZZ)" -- see criticalIdeal -- ideal of critical equations of a semidefinite program
• "optimize(SDP)" -- see optimize -- solve a semidefinite program
• "optimize(SDP,Matrix)" -- see optimize -- solve a semidefinite program
• refine(SDP,Sequence) -- refine an SDP solution
• "ring(SDP)"

## For the programmer

The object SDP is a type, with ancestor classes HashTable < Thing.