Journal article
A General Framework for Establishing Polynomial Convergence of Long-Step Methods for Semidefinite Programming
Optimization methods & software, Vol.18(1), pp.1-38
02/2003
DOI: 10.1080/1055678031000111227
Abstract
This article considers feasible long-step primal-dual path-following methods for semidefinite programming based on Newton directions associated with central path equations of the form Φ(PXPT, P-T SP-1) - vI = 0, where the map Φ and the nonsingular matrix P satisfy several key properties. An iteration-complexity bound for the long-step method is derived in terms of an upper bound on a certain scaled norm of the second derivative of Φ. As a consequence of our general framework, we derive polynomial iteration-complexity bounds for long-step algorithms based on the following four maps: Φ(X, S) = (XS + SX)/2, Φ(X, S) = LxTSLx, Φ(X, S) = X1/2SX1/2, and Φ(X, S) = W1/2XSW-1/2, where Lx is the lower Cholesky factor of X and W is the unique symmetric matrix satisfying S = WXW.
Details
- Title: Subtitle
- A General Framework for Establishing Polynomial Convergence of Long-Step Methods for Semidefinite Programming
- Creators
- Samuel Burer - University of IowaRenato D.C. Monteiro - Georgia Institute of Technology
- Resource Type
- Journal article
- Publication Details
- Optimization methods & software, Vol.18(1), pp.1-38
- DOI
- 10.1080/1055678031000111227
- ISSN
- 1055-6788
- eISSN
- 1029-4937
- Language
- English
- Date published
- 02/2003
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380423702771
Metrics
1 Record Views