# 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
```