SemidefiniteProgramming -- A package for solving semidefinite programs

Description

This is a package for solving semidefinite programming (SDP) problems.

Given symmetric matrices $C, A_i$ and a vector $b$, the primal SDP problem is

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

and the dual SDP 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$$

We can construct a semidefinite program using the method sdp.

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 semidefinite program can be solved numerically using the method optimize.

i2 : (X,y,Z,stat) = optimize P;

i3 : (X,y)

o3 = (| .707057 -.5     |, | -1.41421 |)
      | -.5     .353578 |

o3 : Sequence

See Solver for a discussion of the available SDP solvers. The method refine can be used to improve the precision of the solution.

In small cases it is possible to solve the SDP symbolically, by forming the ideal of critical equations.

i4 : (I,X,y,Z) = criticalIdeal P;

i5 : radical I

                                          2
o5 = ideal (4x  + y , 2x  + 1, 2x  + y , y  - 2)
              2    0    1        0    0   0

o5 : Ideal of QQ[x ..x , y ]
                  0   2   0

Authors

Version

This documentation describes version 0.3 of SemidefiniteProgramming.

Source code

The source code from which this documentation is derived is in the file SemidefiniteProgramming.m2. The auxiliary files accompanying it are in the directory SemidefiniteProgramming/.

Exports

Types
- SDP -- construct a semidefinite program
Functions and commands
- changeSolver -- change the SDP solver
- checkOptimize -- check an SDP solver
- criticalIdeal -- ideal of critical equations of a semidefinite program
- optimize -- solve a semidefinite program
- PSDdecomposition -- factorization of a positive semidefinite matrix
- roundPSDmatrix -- rational rounding of a PSD matrix
- sdp -- see SDP -- construct a semidefinite program
- smat2vec -- vectorization of a symmetric matrix
- vec2smat -- see smat2vec -- vectorization of a symmetric matrix
Methods
- checkOptimize(String) -- see checkOptimize -- check an SDP solver
- 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) -- see SDP -- construct a semidefinite program
- sdp(List,Matrix,RingElement) -- see SDP -- construct a semidefinite program
- sdp(Matrix,Matrix,Matrix) -- see SDP -- construct a semidefinite program
- sdp(Matrix,Sequence,Matrix) -- see SDP -- construct a semidefinite program
- smat2vec(List) -- see smat2vec -- vectorization of a symmetric matrix
- smat2vec(Matrix) -- see smat2vec -- vectorization of a symmetric matrix
- vec2smat(List) -- see smat2vec -- vectorization of a symmetric matrix
- vec2smat(Matrix) -- see smat2vec -- vectorization of a symmetric matrix
Symbols
- Scaling -- see smat2vec -- vectorization of a symmetric matrix
- Solver -- picking a semidefinite programming solver
- Verbosity -- control the level of information printed

For the programmer

The object SemidefiniteProgramming is a package.