Journal article
Solving a class of semidefinite programs via nonlinear programming
Mathematical programming, Vol.93(1), pp.97-122
06/01/2002
DOI: 10.1007/s101070100279
Abstract
In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions.
Details
- Title: Subtitle
- Solving a class of semidefinite programs via nonlinear programming
- Creators
- Samuel Burer - University of IowaRenato D. C Monteiro - Georgia Institute of TechnologyYIN Zhang - Rice University
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.93(1), pp.97-122
- Publisher
- Springer
- DOI
- 10.1007/s101070100279
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 06/01/2002
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380427602771
Metrics
1 Record Views