Semidefinite Programming¶
A positive semidefinite matrix is a symmetric real matrix whose eigenvalues are all nonnegative. A semidefinite programming problem is simply a linear program where the solutions are positive semidefinite matrices instead of points in Euclidean space.
Primal and Dual formulations¶
A typical semidefinite program (SDP for short) in the primal form is the following optimization problem:
The dual program associated to the above SDP will be the following:
For convenience, we use a block representation for the matrices as follows:
and
This simplifies the \(k\) constraints of the primal form in to one constraint \(\sum_{i=1}^m A_i x_i - C \succeq 0\) and the objective and constraints of the dual form as \(tr(C\times Y)\) and \(tr(A_i\times Z_i) = b_i\) for \(i=1,\dots,m\).
The sdp
class¶
The sdp
class provides an interface to solve semidefinite programs using various range of
well-known SDP solvers. Currently, the following solvers are supported:
CVXOPT
¶
This is a python native convex optimization solver which can be obtained from CVXOPT.
Beside semidefinite programs, it has various other solvers to handle convex optimization problems.
In order to use this solver, the python package CVXOPT
must be installed.
DSDP
¶
If DSDP and CVXOPT
are installed and DSDP
is callable from command line,
then it can be used as a SDP solver. Note that the current implementation uses CVXOPT
to call DSDP
, so CVXOPT
is a
requirement too.
SDPA
¶
In case one manages to install SDPA and it can be called from command line, one can use
SDPA
as a SDP solver.
CSDP
¶
Also, if csdp is installed and can be reached from command, then it can be used to solve
SDP problems through sdp
class.
To initialize and set the solver to one of the above simply use:
SDP = sdp('cvxopt') # initializes and uses `cvxopt` as solver.
Note
In windows, one can provide the path to each of the above solvers as the second parameter of the constructor:
SDP = sdp('csdp', {'csdp':"Path to executable csdp"}) # initializes and uses `csdp` as solver existing at the given path.
Set the \(b\) vector:¶
To set the vector \(b=(b_1,\dots,b_m)\) one should use the method sdp.SetObjective
which takes a list or a numpy array of
numbers as \(b\).
Set a block constraint:¶
To introduce the block of matrices \(A_{i1},\dots, A_{ik}\) associated with \(x_i\), one should use the method
sdp.AddConstraintBlock
that takes a list of matrices as blocks.
Set the constant block C:¶
The method sdp.AddConstantBlock
takes a list of square matrices and use them to construct \(C\).
Solve the input SDP:¶
To solve the input SDP simply call the method sdp.solve()
. This will call the selected solver on the entered SDP and
the output of the solver will be set as dictionary in sdp.Info
with the following keys:
PObj
: The value of the primal objective.DObj
: The value of the dual objective.X
: The final \(X\) matrix.Z
: The final \(Z\) matrix.Status
: The final status of the solver.CPU
: Total run time of the solver.
Example:¶
Consider the following SDP:
The following code solves the above program:
from numpy import matrix
from Irene import sdp
b = [1, -1, 1]
C = [matrix([[-33, 9], [9, -26]]),
matrix([[-14, -9, -40], [-9, -91, -10], [-40, -10, -15]])]
A1 = [matrix([[7, 11], [11, -3]]),
matrix([[21, 11, 0], [11, -10, -8], [0, -8, -5]])]
A2 = [matrix([[-7, 18], [18, -8]]),
matrix([[0, -10, -16], [-10, 10, 10], [-16, 10, -3]])]
A3 = [matrix([[2, 8], [8, -1]]),
matrix([[5, -2, 17], [-2, 6, -8], [17, -8, -6]])]
SDP = sdp('cvxopt')
SDP.SetObjective(b)
SDP.AddConstantBlock(C)
SDP.AddConstraintBlock(A1)
SDP.AddConstraintBlock(A2)
SDP.AddConstraintBlock(A3)
SDP.solve()
print SDP.Info