A semidefinite programming heuristic for
quadratic programming problems with
complementarity constraints
Download the paper,
postscript or pdf.
Authors:
Stephen Braun
Warren & Selbert, Inc.
Santa Barbara, CA 93101
brauns2@alum.rpi.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
November 30, 2002.
Revised: February 7, 2004.
Abstract:
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.