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

SemidefiniteProgramming -- A package for solving semidefinite programs

Description

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

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

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

and the dual SDP problem is

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

We can construct a semidefinite program using the method sdp, as follows:

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) = optimize P;
Executing CSDP
Input file: /tmp/M2-2317-0/4.dat-s
Output file: /tmp/M2-2317-0/5
Status: SDP solved, primal-dual feasible
i3 : (X,y)

o3 = (| .707109 -.5     |, | -1.41421 |)
      | -.5     .353555 |

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 , x , y ]
                  0   1   2   0

Authors

Version

This documentation describes version 0.2 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
  • Methods
    • 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
  • Symbols
    • Scaling, see smat2vec -- vectorization of a symmetric matrix
    • Solver -- picking a semidefinite programming solver
  • Other things