Name
Abstract | ||
|---|---|---|
The contribution of this article is to describe a general technique to solve some classes of large but sparse semidefinite problems via a robust primal-dual interior-point technique, which uses an inexact Gauss-Newton approach with a matrix free preconditioned conjugate gradient method. This approach avoids the ill-conditioning pitfalls that result from symmetrization and from forming the so-called normal equations, while maintaining the primal-dual framework. First, we apply a preprocessing step that reduces the optimality conditions before linearization and results in a single, well-conditioned, overdetermined bilinear operator equation. We then use preconditioned conjugate-gradients to approximately solve the linearization at every step of a path-following approach. We do not form the matrix representation of the linearization. In addition, once close to the optimal solution, we apply a crossover technique after which the iterates are no longer forced to be positive definite. In the experimental part of this article, we use Max-Cut to illustrate the technique. We describe preconditioners that exploit the operator structure of the constraints and show how the crossover can be effective in practice and how it allows for warm starts. In all cases we obtain high-accuracy solutions. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1080/1055678042000193162 | OPTIMIZATION METHODS & SOFTWARE |
Keywords | Field | DocType |
semidefinite programming,large sparse problems,inexact Gauss-Newton method,preconditioned conjugate gradients,crossover,max-cut problem | Conjugate gradient method,Overdetermined system,Mathematical optimization,Matrix (mathematics),Positive-definite matrix,Symmetrization,Matrix representation,Semidefinite programming,Linearization,Mathematics | Journal |
Volume | Issue | ISSN |
19 | 6 | 1055-6788 |
Citations | PageRank | References |
5 | 0.52 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henry Wolkowicz | 1 | 1444 | 260.72 |