Optimization Online


A scaled Gauss-Newton Primal--Dual Search Direction for Semidefinite Optimization

E. de Klerk (E.deKlerk***at***its.tudelft.nl)
J Peng (J.Peng***at***its.tudelft.nl)
C Roos (C.Roos***at***its.tudelft.nl)
T Terlaky (terlaky***at***cas.mcmaster.ca)

Abstract: Interior point methods for semidefinite optimization (SDO) have recently been studied intensively, due to their polynomial complexity and practical efficiency. Most of these methods are extensions of linear optimization (LO) algorithms. Unlike in the LO case, there are several different ways of constructing primal-dual search directions in SDO. The usual scheme is to apply linearization in conjunction with symmetrization to the perturbed optimality conditions of the SDO problem. Symmetrization is necessary since the linearized system is overdetermined. A way of avoiding symmetrization is to find a least squares solution of the overdetermined system. Such a `Gauss Newton' direction was investigated by Kruk {\em et al.}\ \cite{Kruk98}, without giving any complexity analysis. In this paper we present a similar direction where a local norm is used in the least squares formulation, and we give a polynomial complexity analysis and computational evaluation of the resulting primal-dual algorithm.

Keywords: Semidefinite optimization, primal-dual search directions, interior point algorithms

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Linear, Cone and Semidefinite Programming

Citation: Manuscript, TU Delft, Delft, NL, February 1999.

Download: [Postscript]

Entry Submitted: 08/18/2000
Entry Last Modified: 08/28/2000

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society