On Convex Quadratic Programs with Linear Complementarity Constraints
Download the paper,
in pdf,
along with a
correct statement of Proposition 1.
Authors:
Lijie Bai
bail at rpi dot edu
Department of
Mathematical Sciences,
Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
John E. Mitchell
mitchj at rpi dot edu
Department of
Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Jong-Shi
Pang
jspang at illinois dot edu
Industrial and Enterprise Systems
Engineering,
University of Illinois at Urbana-Champaign,
117 Transportation Bldg., 104 S. Mathews Ave., Urbana, IL 61801.
Note: there was an error in the statement of Proposition 1 in the
published version of the paper.
Here is a
correct statement of Proposition 1.
Note that the proof is not changed, and the remainder of the paper is
unaffected by the error in the statement of the proposition.
Abstract:
The paper shows that the global resolution of a general
convex quadratic program with complementarity constraints (QPCC),
possibly infeasible or unbounded,
can be accomplished
in finite time. The method constructs a minmax mixed integer
formulation by introducing finitely many binary variables, one for
each complementarity constraint. Based on the primal-dual
relationship of a pair of convex quadratic programs and on a logical
Benders scheme, an extreme ray/point generation
procedure is developed, which relies on valid satisfiability constraints for the
integer program. To improve this scheme, we propose a
two-stage approach wherein the first stage solves the mixed integer
quadratic program with pre-set upper bounds
on the complementarity variables, and the second stage solves the
program outside this bounded region by the Benders scheme. We
report computational results with our method. We also investigate
the addition of a penalty term yDw to the objective function,
where y and w are the complementary variables and D is a
nonnegative diagonal matrix. The matrix D can be chosen
effectively by solving a semidefinite program, ensuring
that the objective function remains convex.
The addition of the penalty term can often reduce the overall
runtime by at least 50%. We report preliminary
computational testing on a QP relaxation method which can be used
to obtain better lower bounds from infeasible points; this method
could be incorporated into a branching scheme. By combining the
penalty method and the QP relaxation method, more than 90% of the
gap can be closed for some QPCC problems.
Keywords:
Convex quadratic programming. Logical Benders
decomposition. Satisfiability constraints. Semidefinite
programming
Download the paper,
in pdf,
along with a
correct statement of Proposition 1.
Return to my list of papers.