Regularization Methods for Semidefinite Programming
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 20 (1), 336-356
- https://doi.org/10.1137/070704575
Abstract
International audienceWe introduce a new class of algorithms for solving linear semidefinite programming (SDP) problems. Our approach is based on classical tools from convex optimization such as quadratic regularization and augmented Lagrangian techniques. We study the theoretical properties and we show that practical implementations behave very well on some instances of SDP having a large number of constraints. We also show that the ''boundary point method'' is an instance of this classKeywords
This publication has 20 references indexed in Scilit:
- An Augmented Primal-Dual Method for Linear Conic ProgramsSIAM Journal on Optimization, 2008
- Large-scale semidefinite programming via a saddle point Mirror-Prox algorithmMathematical Programming, 2006
- On the solution of large-scale SDP problems by the modified barrier method using iterative solversMathematical Programming, 2006
- Semidefinite programming relaxations for graph coloring and maximal clique problemsMathematical Programming, 2006
- Solving Lift-and-Project Relaxations of Binary Integer ProgramsSIAM Journal on Optimization, 2006
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- Computing the nearest correlation matrix--a problem from financeIMA Journal of Numerical Analysis, 2002
- A Spectral Bundle Method for Semidefinite ProgrammingSIAM Journal on Optimization, 2000
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Multiplier and gradient methodsJournal of Optimization Theory and Applications, 1969