|
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]
-
R. D. C. Monteiro,
"First- and second-order methods for semidefinite programming,"
Mathematical Programming B97, 209-244, 2003.
-
J. Renegar,
"A Mathematical View of Interior-Point Methods in Convex Optimization
(MPS-SIAM Series on Optimization),"
SIAM, 2001.
-
A. Ben-Tal and A. Nemirovski,
"Lectures on Modern Convex Optimization: Analysis, Algorithms, and
Engineering Applications (MPS-SIAM Series on Optimization),"
SIAM, 2001.
-
M. J. Todd,
"Semidefinite optimization,"
Acta Numerica 10, 515-560, 2001.
-
H. Wolkowicz, R. Saigal, and L. Vandenberghe (eds.),
"Handbook on Semidefinite Programming: Theory, Algorithms, and Applications,"
Kluwer Academic, 2000.
-
L. Vandenberghe and S. Boyd,
"Semidefinite programming,"
SIAM Review
38, 49-95, 1996.
-
Yu. Nesterov and A. Nemirovskii,
"Interior-Point Polynomial Algorithms in Convex Programming (SIAM
Studies in Applied Mathematics, Vol. 13),"
SIAM, 1994.
- Control Theory
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).
-
S. P. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan,
"Linear Matrix Inequalities in System and Control Theory (SIAM Studies
in Applied Mathematics, Vol. 15),"
SIAM , 1994.
- Combinatorial Optimization
SDP relaxation techniques can give surprisingly good approximate optimal
solutions/values for hard combinatorial optimization problems in
polynomial time.
-
M. X. Goemans and D. P. Williamson,
"Improved approximation algorithms for maximum cut and satisfiability
problems using semidefinite programming,"
Journal of the ACM 42, 1115-1145, 1995.
-
M. Grotschel, L. Lovász, and A. Schrijver,
"Geometric Algorithms and Combinatorial Optimization (2 edition),"
Springer-Verlag, 1993.
- Optimization Problems Involving Polynomials
Global optima of Polynomial Optimization Problems (POPs) can be
computed solving a nested sequence of SDPs.
-
S. Kim, M. Kojima, and H. Waki,
"Generalized Lagrangian duals and sums of squares relaxations of
polynomial optimization problems,"
SIAM Journal on Optimization 15, 697-719 (2005).
-
P. A. Parrilo,
"Semidefinite programming relaxations for semialgebraic problems,"
Mathematical Programming 96, 293-320 (2003).
-
J. B. Lasserre,
"Global optimization with polynomials and the problem of moments,"
SIAM Journal on Optimization 11, 796-817 (2001).
- Quantum Chemistry
The ground-state energy of an atomic-molecular system can be
closely approximated by a reduced density matrix model
formulated as an SDP.
-
D. A. Mazziotti,
"Realization of quantum chemistry without wave functions
through first-order semidefinite programming,"
Physical Review Letters 93, 213001 (2004).
-
Z. Zhao, B. J. Braams, M. Fukuda,
M. L. Overton, and J. K. Percus,
"The reduced density matrix method for electronic structure
calculations and the role of three-index representability conditions,"
Journal of Chemical Physics 120, 2095-2104 (2004).
-
M. Nakata, H. Nakatsuji, M. Ehara,
M. Fukuda, K. Nakata, and K. Fujisawa,
"Variational calculations of fermion second-order
reduced density matrices by semidefinite programming algorithm,"
Journal of Chemical Physics 114, 8282-8292 (2001).
- Quantum Information
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.
-
F. G. S. L. Brandão and R. O. Vianna,
"Separable multipartite mixed states: Operational
asymtotically necessary and sufficient conditions,"
Physical Review Letters 93, 220503 (2004).
-
A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri,
"Distinguishing separable and entangled states,"
Physical Review Letters 88, 187904 (2002).
SDP has been extensively studied and many methods have been proposed
to solve SDPs.
- Primal-Dual Interior-Point Methods (PD-IPM)
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
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.
- Spectral Bundle Methods
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.
- Generalized Augmented Lagrangian
Method
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.
- Other Nonlinear Programming Approaches
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.
-
SDPA
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.
-
CSDP
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.
-
DSDP and PDSDP
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.
-
SBMethod
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.
-
SDPLR
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.
-
SDPT3
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.
-
SeDuMi
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
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.
-
YALMIP
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.
|
