=======================================
cpysdp & SDP & SemidefiniteProgram
=======================================
This module provides basic general features for semidefinite programming
in Sage. PyCsdp is a Cython interface to the famous CSDP solver and SDP
aims to provides a unified interface for semidefinite programming using
various solvers that are available for Sage (so far CvxOpt, CSDP through
Sage and SeDuMi, SDPNAL through Matlab).
One can include these modules like this::
#!/usr/bin/env python
from cpycsdp import cpycsdp
from SDP import SDP
from SDP import SemidefiniteProgram
% OR
from SDP import *
Installation
======================
In Sage -sh mode, simply run
python setup.py build_ext install
cpysdp
======================
This is an interface for CSDP written in Cython based on the optional
Sage compatible installation of CSDP. The main purpose of PyCsdp is to
define the 'easy_sdp' function of CSDP which provides a convenient way
of solving semidefinite programs, for Sage. The Sage version of
'easy_sdp' is the python 'cpycsdp' function.
* cpycsdp
This function takes three arguments as input::
cpycsdp(C, A, a)
and returns a python dictionary consist of output data of 'easy_sdp'.
This function aims to solve a primal or dual semidefinite program in the
following form:
Primal:
maximize
tr(C*X)
subject to
tr(A1*X) = a1
.
.
.
tr(Am*X) = am
X is psd
Dual:
minimize
a^t*y
subject to
A^t(y) - C = Z
Z is psd
where
A^t(y) = y1 A1 + ... + ym Am
and
C = [C1 0
0 C2 0
0 . 0
. . .
0 . Cm]
Arguments
--------------------
1. 'C' is a python list C = [C1,..., Cm] where 'C1' .... 'Cm' are 2-dim
numpy matrices defining the block matrices as are shown above.
2. 'A' is a python list of block matrices [A1,..., Ak] where each 'Ai'
is a python list of the similar structure of 'C'. In other words,
Ai = [Ai1,..., Aim], where 'Aij' is a numpy matrix of the size of 'Cj'.
3. 'a' is 1-dim python list. Simply a=[a1,..., am] as is shown above.
Output
--------------------
Is a python dictionary with the following keys:
1. 'primal'
the final value of primal objective function.
2. 'dual'
the final value of dual objective function.
3. 'y'
the vector y in above problem.
4. 'Z'
the sdp matrix Z in above problem.
5. 'X'
the sdp matrix X in above problem.
6. 'message'
a descriptive text explaining the result of CSDP.
SDP
======================
This module aims to provide a unified interface for various sdp solver
that are supported by Sage. Currently 'CvxOpt' is by default available in
Sage and also 'CSDP' can be installed inside Sage. A Sage installable spkg
is available at <https://github.com/dimpase/csdp.git>.
Moreover, if either of 'SeDuMi' or 'SDPNAL' are available in 'Matlab' and
Matlab is added to the system PATH, then they can be called by SDP.
SDP solves a semidefinite program of the form given above. A typical usage
of SDP looks like the following:
#!/usr/bin/env python
from SDP import SDP
program = SDP.sdp()
program.solve(C, a, A)
The arguments and output of each method are described below.
* Initialization
SDP.sdp() accepts two optional arguments:
1. solver:
currently there is four possible choices for solver:
+ 'cvxopt'
+ 'csdp'
+ 'sedumi'
+ 'sdpnal'
that are subject to availability of each one under Sage. The value
of silver is preset to 'cvxopt'.
2. Settings:
a python dictionary for fine tuning of the sdp solver. Acceptable
keys are the followings:
+ 'detail':
is preset to 'True'. Switch to 'False' in order to hide the
progress detail of the solver (Currently only works for cvxopt).
+ 'Iterations':
the maximum number of iteration. Default is 100 steps (Currently
only works for cvxopt).
+ 'refinement':
A positive integer number. If the solver encounters a singular
KKT matrix, it continues to iterate for this given number of
iterations (Currently only works for cvxopt).
* solve
The solve method requires three arguments and sets the 'Info' dictionary
of the class based on the output of the solver. Arguments and outputs
are described bellow:
Arguments
--------------------
1. 'C' is a list of matrices C1,..., Cm. The following types of data for
Ci's are acceptable:
+ Python 2-dimensional list,
+ Sage matrix,
+ Numpy matrix,
+ Blas type matrix that is compatible with CvxOpt.
2. 'a' is a list of scalars.
3. 'A' is a list of block matrices. Any type which is admissible for 'C'
is also admissible for 'A'.
Output
--------------------
'SDP.solve' method fills a dictionary 'SDP.Info' of following keys:
+ 'Status'
shows the final status of the solver,
+ 'PObj'
the final value of primal objective function,
+ 'DObj'
the final value of dual objective function,
+ 'y'
the vector y in above problem as a numpy vector,
+ 'Z'
the sdp matrix Z in above problem as a numpy matrix,
+ 'X'
the sdp matrix X in above problem as a numpy matrix,
+ 'Wall'
the wall time spent by the solver,
+ 'CPU'
the CPU time spent by the solver,
SemidefiniteProgram
======================
The SemidefiniteProgram class provides a user friendly interface to solve
primal or dual semidefinite programming (sdp) problems within Sage.
A typical semidefinite program in primal form is the following:
minimize
a^t*y
subject to
y_1 A_{11} + ... + y_n A_{1n} - C_1 = Z_1
. .
. .
. .
y_1 A_{m1} + ... + y_n A_{mn} - C_m = Z_m
where
Z = [Z_1 0 ... 0
0 Z_2 0...0
... ...
... ...
0 ... 0 Z_m]
is psd.
A typical semidefinite program in dual form is the following:
maximize
tr(C*X)
subject to
tr(A_1 * X) = a_1
. .
. .
. .
tr(A_m * X) = a_m
where
X is psd.
and each A_i is a symmetric block diagonal matrix
Currently supports 4 solvers subject to availability:
'CvxOpt':
The default solver which comes with Sage.
see http://cvxopt.org/
'csdp':
If CSDP is installed for Sage.
see https://projects.coin-or.org/Csdp/
'SeDuMi':
Available through MATLAB, if MATLAB is installed and it
is added to system PATH.
see http://sedumi.ie.lehigh.edu/
'SDPNAL'
Available through MATLAB, if MATLAB is installed and it
is added to system PATH.
see http://www.math.nus.edu.sg/~mattohkc/SDPNAL.html
A typical usage of SemidefiniteProgram looks like the following:
#!/usr/bin/env python
from SDP import SemidefiniteProgram
program = SDP.SemidefiniteProgram(primal = True)
The arguments and output of methods are described below.
* Initialization
SDP.SemidefiniteProgram() accepts two optional arguments:
1. primal:
should be either True or False which determine the type of the
sdp. The default value is preset to True.
2. solver:
currently there is four possible choices for solver:
+ 'cvxopt'
+ 'csdp'
+ 'sedumi'
+ 'sdpnal'
that are subject to availability of each one under Sage. The value
of silver is preset to 'cvxopt'.
* Setting the objective
SemidefiniteProgram.set_objective() sets the objective of the sdp and requires
one argument:
Argument:
--------------------
1. M:
depends on the type of the sdp:
Primal:
A vector of real numbers ('a').
Dual:
A sparse square matrix ('C') in one of the following types:
BlockMat;
Sage matrix;
Numpy matrix;
Double indexed python list;
CvxOpt matrix.
* Adding a constraint
SemidefiniteProgram.add_constraint() adds a constraint to the sdp and needs two
arguments:
Arguments:
--------------------
1. M1:
depends on the type of the sdp:
Primal:
A python list of equi-size square matrices ('A_{i1},..., A_{in}')
in either of the following formats:
Sage matrix;
Numpy matrix;
Double indexed python list;
CvxOpt matrix.
Dual:
A square or diagonal block matrix ('A_i') in one of the following types:
BlockMat;
Sage matrix;
Numpy matrix;
Double indexed python list;
CvxOpt matrix.
2. M2:
depends on the type of the sdp:
Primal:
A square matrix ('C_i') in a format similar to 'M1'.
Dual:
A constant real number ('a_i').
* solve
SemidefiniteProgram.solve solves the sdp
Arguments:
--------------------
None.
Output:
--------------------
Returns a dictionary 'SemidefiniteProgram.Result' with following keys:
+ 'Status':
either 'Optimal' or 'Infeasible'
+ 'PObj':
value of primal objective function
+ 'DObj':
value of dual objective function
+ 'X':
the psd matrix X in the primal problem
+ 'Z':
the psd matrix Z in the dual problem
+ 'y':
the vector y for the dual problem
+ 'Wall':
Wall time spent by sdp solver (in seconds)
+ 'CPU':
CPU time spent by sdp solver (in seconds)
The output matrix are in numpy format
The latest version of this code is available at:
<https://github.com/mghasemi/pycsdp.git>