##
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.