SDP -- construct a semidefinite program

Synopsis

Usage:

P = sdp(C,A,b)

P = sdp(var,M,objFun)
Inputs:
- C, a matrix, a symmetric $n\times n$ matrix
- A, a sequence, consisting of $m$ symmetric $n\times n$ matrices
- b, a matrix, a $m\times 1$ matrix
- var, a list, of variables
- M, a matrix, constraint matrix with affine-linear entries
- objFun, a ring element, 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.