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.
Citation
CORR Report 2002-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada