A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

被引：10

作者：

Braun, S ^{[1
]}

Mitchell, JE

机构：

[1] Warren & Selbert Inc, Santa Barbara, CA 93101 USA

[2] Rensselaer Polytech Inst, Dept Math Sci, Troy, NY 12180 USA

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2005年 / 31卷 / 01期

基金：

美国国家科学基金会;

关键词：

complementarity constraints; quadratic programming; semidefinite programming;

D O I：

10.1007/s10589-005-1014-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：5 / 29

页数：25

共 39 条

[1] A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].