A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

Download the paper, postscript or pdf.


Stephen Braun
Warren & Selbert, Inc.
Santa Barbara, CA 93101

John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA

Computational Optimization and Applications, Volume 31(1), May 2005, pages 5-29.

November 30, 2002. Revised: February 7, 2004.


The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.

Keywords: Complementarity constraints, quadratic programming, semidefinite programming.

Download the paper, postscript or pdf.

Return to my list of papers.