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

Franz Rendl (franz.rendluni-klu.ac.at)
Renata Sotirov (renata.sotirovuni-klu.ac.at)
Henry Wolkowicz (hwolkowiczuwaterloo.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