Optimization Online


A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming

Franz Rendl (franz.rendl***at***uni-klu.ac.at)
Renata Sotirov (renata.sotirov***at***uni-klu.ac.at)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

Abstract: Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the SDP relaxations of NP-hard problems, a simple primal-dual feasible starting point is available. In theory, the Newton type search directions maintain feasibility. However, in practice it is assumed that roundoff-error must be taken into account and the residuals are used to recover feasibility. We introduce preprocessing for SDP to obtain a modified HKM direction. This direction attains {\em exact primal and dual feasibility} throughout the iterations while: setting the residuals to 0; reducing the arithmetic expense; maintaining the same iteration counts for well-conditioned problems; and reducing the iteration count for ill-conditioned problems. We apply the technique to the Max-Cut, Lov\'asz Theta, and Quadratic Assignment problems. We include an illustration on an ill-conditioned two dimensional problem, a discussion on convergence, and a similar simplification for the Monteiro-Zhang family of search directions. This paper can serve as an introduction to both the HKM search direction and preprocessing (presolve) for SDP.

Keywords: Semidefinite Programming, Max-Cut, Theta function, Quadratic Assignment

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

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: CORR Report 2002-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 08/12/2002
Entry Accepted: 08/12/2002
Entry Last Modified: 08/13/2002

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