Title | ||
---|---|---|
Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation |
Abstract | ||
---|---|---|
Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1023/A:1014834318702 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
semidefinite program,semidefinite relaxation,nonlinear programming,interior-point methods | Second-order cone programming,Mathematical optimization,Nonlinear system,Quadratically constrained quadratic program,Mathematical analysis,Nonlinear programming,Algorithm,Positive definiteness,Semidefinite embedding,Interior point method,Semidefinite programming,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 1 | 1573-2894 |
Citations | PageRank | References |
4 | 1.09 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Samuel Burer | 1 | 1148 | 73.09 |
Renato D. C. Monteiro | 2 | 1250 | 138.18 |
Yin Zhang | 3 | 687 | 36.24 |