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.

Citation

If you have used this package in your research, please cite it as follows:

@misc{SemidefiniteProgrammingSource,
  title = {{SemidefiniteProgramming: A \emph{Macaulay2} package. Version~0.3}},
  author = {Diego Cifuentes and Thomas Kahle and Pablo A. Parrilo and Helfried Peyrl},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

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

For the programmer

The object SemidefiniteProgramming is a package, defined in SemidefiniteProgramming.m2, with auxiliary files in SemidefiniteProgramming/.

The source of this document is in SemidefiniteProgramming/SDPdoc.m2:39:0.