In short, SDP is an optimization problem which minimizes/maximizes
a linear objective function
subject to linear equality and inequality constraints
on the symmetric variable matrix X, and the positive semidefinite
constraint on X.
These inequality constraints are also known as Linear Matrix Inequalities.
The following PDF file summarizes the mathematical
definition of the SDP, an algorithm to solve it,
and an actual software which implements the algorithm.
[whatissdp.pdf]
The stability of a homogeneous linear differential equation can be
described as an SDP constraint through the Lyapunov theory.
This is one of the earliest applications of SDP known as Linear
Matrix Inequality (LMI).
SDP relaxation techniques can give surprisingly good approximate optimal
solutions/values for hard combinatorial optimization problems in
polynomial time.
Global optima of Polynomial Optimization Problems (POPs) can be
computed solving a nested sequence of SDPs.
The ground-state energy of an atomic-molecular system can be
closely approximated by a reduced density matrix model
formulated as an SDP.
It is possible to use the SDPs to determine deterministically or
probabilistically if a quantum system is a separable or an
entangled state, which is an extremely importance issue for
quantum information theory.
SDP has been extensively studied and many methods have been proposed to solve SDPs.
Considered the most robust method to solve SDPs. The PD-IPMs solve the primal and the dual problems simultaneously by searching an optimal solution in the space of variables defined by both problems. The polynomial-time solvability of an SDP is proved by the use of the self-concordant barrier function or the central path neighborhood.
Dual interior-point methods solve only the dual problem (in SDPA, this problem is called primal). It is advantageous to use this method when the dual matrix variable is very sparse. Polynomial convergence is still attained.
These methods use a cutting-plane model of the nonsmooth convex objective function by computing its subgradients. Usually, they cannot attain high accuracy, while they can handle extremely large SDPs.
Uses the augmented Lagrangian method as a framework with a special penalty/barrier function which satisfies certain properties. It can solve linear and non-linear SDPs as well as nonlinear programs in general.
The SDP can be formulated as a nonlinear programming problem and then general and efficient methods to solve nonlinear programs can be applied to it. The spectral bundle methods and the generalized augmented Lagrangian method also use nonlinear formulations of the SDP.
The SDPA is an implementation of the PD-IPM in C++ language. The SDPA family of software includes a callable library (from C/C++), a MATLAB interface, a parallel version, and a positive definite matrix completion implementation. All of these software obtain high accurate solutions for different classes of SDP problems. Details of each package of the family can be found here.
The CSDP is an implementation of the PD-IPM in C language, available in stand-alone and as a callable library for C/C++. It has a MATLAB interface too. Optimized binaries for Linux, Windows, Mac OS X platforms are available.
The DSDP is an implementation of the dual interior-point method in C language. It is suited for extremely sparse SDPs and/or SDPs which have special structures such as arising from combinatorial optimization. A MATLAB interface, a callable library and its parallel version, the PDSDP, are available.
The SBMethod is an implementation of the spectral bundle method in C++ language. It is suited for large-scale problems such as relaxation of combinatorial optimization problems which do not require high accuracy.
The SDPLR reformulates the SDP as a nonlinear program, and then solves it by the augmented Lagrangian method. It is recommended for large-scale problems which do not require high accuracy.
The SDPT3 is an implementation of the PD-IPM which a MATLAB interface. It can handle SDPs and problems involving second-order cone programs and/or linear programs.
The SeDuMi is also an implemention of the PD-IPM which a MATLAB interface. It can handle problems with real and complex variables for SDPs, second-order cone programs and/or linear programs. The remarkable characteristics of this software is its numerical stability and efficiency.
PENNON is the most generic software which can solve convex and non-convex nonlinear programs, including nonlinear SDPs and BMIs. It is an implementation of the generalized augmented Lagrangian method. It is the unique commercial code which solves SDPs.
A MATLAB toolbox which provides a easy-to-use interface for problem from system and control which can be combine with almost all of the above software, and other free or commercial optimization software.