Optimization Online


A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

Stephen Braun (brauns2***at***alum.rpi.edu)
John E. Mitchell (mitchj***at***rpi.edu)

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

Category 1: Complementarity and Variational Inequalities

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation: Math Sciences, RPI, Troy NY 12180, USA. http://www.rpi.edu/~mitchj/papers/sdpheur.html

Download: [Postscript][PDF]

Entry Submitted: 11/30/2002
Entry Accepted: 12/02/2002
Entry Last Modified: 11/30/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society