Semidefinite Programming
Lieven Vandenberghe, Stephen Boyd · SIAM Review · 1996
In semidefinite programming, one minimizes a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programs are convex optimization problems. semidefinite programming unifies several standard problems (e.g., linear and quadratic programming) and finds many applications in engineering and combinatorial optimization. Although semidefinite programs are much more general than linear programs, they are not much harder to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs and an introduction to primaldual interior-point methods for their solution.
Cited by 4,105 works. doi:10.1137/1038003
Authors
References
- Linear Matrix Inequalities in System and Control Theory
- Convex Analysis
- A new polynomial-time algorithm for linear programming
- Interior-Point Polynomial Algorithms in Convex Programming
- Geometric Algorithms and Combinatorial Optimization
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Lower Bounds for the Partitioning of Graphs
- Iterative Solution Methods
- Solution of Sparse Indefinite Systems of Linear Equations
- On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations I