next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SemidefiniteProgramming :: SDP

SDP -- construct a semidefinite program

Synopsis

Description

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

minX   C •X     s.t.     Ai •X = bi   and   X ≥0

and the dual problem is

maxy,Z   ∑i bi yi     s.t.     Z = C - ∑i yi Ai   and   Z ≥0

The type SDP stores semidefinite programs. There are two ways to construct an SDP. The first option is to provide the matrices C,Ai,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)≥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 :

For the programmer

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