TY - JOUR
T1 - A Lagrangian–DNN relaxation
T2 - a fast method for computing tight lower bounds for a class of quadratic optimization problems
AU - Kim, Sunyoung
AU - Kojima, Masakazu
AU - Toh, Kim Chuan
N1 - Funding Information:
Sunyoung Kim's research was supported by NRF 2012-R1A1A2-038982 and NRF 2014-R1A2A1A11049618. Masakazu Kojima's research was supported by the Japan Science and Technology Agency (JST), the Core Research of Evolutionary Science and Technology (CREST) research project. Kim-Chuan Toh's research was supported in part by Ministry of Education Academic Research Fund R-146-000-168-112.
Publisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
PY - 2016/3/1
Y1 - 2016/3/1
N2 - We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian–completely positive programming (CPP) relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem with a single Lagrangian parameter in a CPP matrix variable with its upper-left element fixed to 1. Replacing the CPP matrix variable by a DNN matrix variable, we derive the Lagrangian–DNN relaxation, and establish the equivalence between the optimal value of the DNN relaxation of the original QOP and that of the Lagrangian–DNN relaxation. We then propose an efficient numerical method for the Lagrangian–DNN relaxation using a bisection method combined with the proximal alternating direction multiplier and the accelerated proximal gradient methods. Numerical results on binary QOPs, quadratic multiple knapsack problems, maximum stable set problems, and quadratic assignment problems illustrate the superior performance of the proposed method for attaining tight lower bounds in shorter computational time.
AB - We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian–completely positive programming (CPP) relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem with a single Lagrangian parameter in a CPP matrix variable with its upper-left element fixed to 1. Replacing the CPP matrix variable by a DNN matrix variable, we derive the Lagrangian–DNN relaxation, and establish the equivalence between the optimal value of the DNN relaxation of the original QOP and that of the Lagrangian–DNN relaxation. We then propose an efficient numerical method for the Lagrangian–DNN relaxation using a bisection method combined with the proximal alternating direction multiplier and the accelerated proximal gradient methods. Numerical results on binary QOPs, quadratic multiple knapsack problems, maximum stable set problems, and quadratic assignment problems illustrate the superior performance of the proposed method for attaining tight lower bounds in shorter computational time.
KW - Bisection method
KW - Iterative solver
KW - Linearly constrained quadratic optimization problems with complementarity constraints
KW - The Lagrangian–conic relaxation
UR - http://www.scopus.com/inward/record.url?scp=84958107736&partnerID=8YFLogxK
U2 - 10.1007/s10107-015-0874-5
DO - 10.1007/s10107-015-0874-5
M3 - Article
AN - SCOPUS:84958107736
SN - 0025-5610
VL - 156
SP - 161
EP - 187
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -