Name
Title | ||
|---|---|---|
A GENERAL FRAMEWORK FOR ESTABLISHING POLYNOMIAL CONVERGENCE OF LONG-STEP METHODS FOR SEMIDEFINITE PROGRAMMING |
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 Phi ( PXPT , P-T SP-1) - nu I = 0, where the map Phi 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 Phi. As a consequence of our general framework, we derive polynomial iteration-complexity bounds for long-step algorithms based on the following four maps: Phi(X, S) = (XS + SX) /2 , Phi(X,S) = L-x(T) SLx , Phi(X,S) = X-1/2 S X-1/2, and Phi (X , S) = W-1/2 XSW-1/2 , where L-x is the lower Cholesky factor of X and W is the unique symmetric matrix satisfying S = WXW . |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1080/1055678031000111227 | OPTIMIZATION METHODS & SOFTWARE |
Keywords | Field | DocType |
semidefinite programming,interior-point methods,path-following methods,long-step methods,Newton directions,central path | Discrete mathematics,Combinatorics,Mathematical optimization,Second derivative,Polynomial,Matrix (mathematics),Upper and lower bounds,Symmetric matrix,Invertible matrix,Interior point method,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
18 | 1 | 1055-6788 |
Citations | PageRank | References |
2 | 0.40 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Burer | 1 | 1148 | 73.09 |
| renato d c monteiro | 2 | 43 | 3.24 |