The paper shows how one can solve a semidefinite program using basic techniques from nonlinear programming, as opposed to sophisticated interior-point methods. Moreover, by taking such an approach, one can solve much larger semidefinite programs than can be solved with interior-point methods.

It describes a new methodology for semidefinite programs that is built upon basic ideas known to all mathematical programmers.

Since semidefinite programming problems arise in many applications in continuous optimization, matrix analysis, engineering, statistics and discrete/combinatorial optimization, it is of paramount importance to develop fast and reliable algorithms to solve them. This research provides new insight into the behavior of nonlinear programming methods for semidefinite programming and develops efficient implementations that will enable practitioners to solve large-scale semidefinite programming problems arising in the types of applications mentioned above.

This research grew naturally from our previous work regarding theoretically and practically efficient algorithms for mathematical programming, including linear programming and semidefinite programming.

Samuel Burer
Assistant Professor
Dept. of Management Sciences
University of Iowa
Iowa City, Iowa, USA

Renato D.C. Monteiro
Professor
School of Industrial and Systems Engineering
Georgia Institute of Technology
Atlanta, Georgia, USA

Yin Zhang
Professor
Dept. of Computational and Applied Mathematics
Rice University
Houston, Texas, USA