Using quadratic convex reformulation to tighten the convex relaxation of a
quadratic program with complementarity constraints
Download the paper,
in pdf.
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.
Abstract:
Quadratic Convex Reformulation (QCR) is a technique
that has been proposed for binary and mixed integer quadratic programs.
In this paper, we extend the QCR method to convex quadratic programs with linear complementarity constraints (QPCCs). Due to the complementarity relationship between the nonnegative variables $y$ and $w$, a term $y^TDw$ can be added to the QPCC objective
function, where $D$ is a nonnegative diagonal matrix chosen to maintain the convexity of the objective function and the global resolution of the QPCC. Following the QCR method, the products of linear equality constraints can also be used to perturb the QPCC objective function, with the goal that the new QP relaxation provides a tighter lower bound.
By solving a semidefinite program, an equivalent QPCC can be obtained whose QP relaxation is as tight as possible. In addition, we extend the QCR to a general quadratically constrained quadratic program (QCQP), of which the QPCC is a special example.
Computational tests on QPCCs are presented.
Keywords:
QCQP, QPCC, SDP, QCR
Download the paper,
in pdf.
Return to my list of papers.