An Interior-Point Method for Semidefinite Programming
Christoph Helmberg, Franz Rendl, Robert J. Vanderbei et al. · SIAM Journal on Optimization · 1996
We propose a new interior-point-based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We show that the approach is very efficient for graph bisection problems such as max–cut. Other applications include max–min eigenvalue problems and relaxations for the stable set problem.
Cited by 706 works. doi:10.1137/0806020
Authors
References
- Interior-Point Polynomial Algorithms in Convex Programming
- On the Shannon capacity of a graph
- Eigenvalues and graph bisection: An average-case analysis
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Large-Scale Optimization of Eigenvalues
- A primal—dual potential reduction method for problems involving matrix inequalities
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
- The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices
- An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices