The gauss-newton direction in semidefinite programming

Serge Kruk, Masakazu Muramatsu, Franz Rendl, Robert J. Vanderbei, Henry Wolkowicz

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

Most of the directions used in practical interior-point methods for semidefinite programming try to follow the approach used in linear programming, i.e., they are defined using the optimality conditions which are modified with a symmetrization of the perturbed complementarity conditions to allow for application of Newton's method. It is now understood that all the Monteiro-Zhang family, which include, among others, the popular AHO, NT, HKM, Gu, and Toh directions, can be expressed as a scaling of the problem data and of the iterate followed by the solution of the AHO system of equations, followed by the inverse scaling. All these directions therefore share a defining system of equations. The focus of this work is to propose a defining system of equations that is essentially different from the AHO system: the over-determined system obtained from the minimization of a nonlinear equation. The resulting solution is called the Gauss-Newton search direction. We state some of the properties of this system that make it attractive for accurate solutions of semidefinite programs. We also offer some preliminary numerical results that highlight the conditioning of the system and the accuracy of the resulting solutions.

Original languageEnglish (US)
Pages (from-to)1-28
Number of pages28
JournalOptimization Methods and Software
Volume15
Issue number1
StatePublished - Dec 1 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Newton direction
  • Semidefinite programming
  • Symmetrization

Fingerprint Dive into the research topics of 'The gauss-newton direction in semidefinite programming'. Together they form a unique fingerprint.

  • Cite this

    Kruk, S., Muramatsu, M., Rendl, F., Vanderbei, R. J., & Wolkowicz, H. (2001). The gauss-newton direction in semidefinite programming. Optimization Methods and Software, 15(1), 1-28.