Convex Quadratic Relaxations of Nonconvex Quadratically Constrained
Quadratic Programs
Download the paper,
in pdf.
Authors:
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.
Bin Yu
yub at rpi dot edu
Department of
Decision Sciences and Engineering Systems,
Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Publication details:
Optimization
Methods and Software, 29(1), pages 120-136, 2014.
Abstract:
Nonconvex quadratic constraints can be linearized to obtain relaxations
in a well-understood manner.
We propose to tighten the relaxation by using second order cone constraints,
resulting in a convex quadratic relaxation.
Our quadratic approximation to the bilinear term is compared to the linear
McCormick bounds.
The second order cone constraints are based on linear combinations of
pairs of variables.
With good bounds on these linear combinations, the resulting constraints
strengthen the McCormick bounds.
Computational results are given, which indicate that the convex quadratic
relaxation can dramatically improve the solution times for some problems.
Keywords:
quadratically constrained quadratic programs;
second order cones;
convex outer approximations.
Journal submission.
Download the paper,
in pdf.
Return to my list of papers.