  


A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming
Franz Rendl (franz.rendluniklu.ac.at) Abstract: Semidefinite Programming (SDP) provides strong bounds for many NPhard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primaldual interior point (pd ip) 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 NPhard problems, a simple primaldual feasible starting point is available. In theory, the Newton type search directions maintain feasibility. However, in practice it is assumed that roundofferror 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 wellconditioned problems; and reducing the iteration count for illconditioned problems. We apply the technique to the MaxCut, Lov\'asz Theta, and Quadratic Assignment problems. We include an illustration on an illconditioned two dimensional problem, a discussion on convergence, and a similar simplification for the MonteiroZhang 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, MaxCut, Theta function, Quadratic Assignment Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: CORR Report 200216, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada Download: [Postscript][Compressed Postscript][PDF] Entry Submitted: 08/12/2002 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  