Optimization Online


A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojimamasakazu***at***mac.com)
Kim-Chuan Toh(mattohkc***at***nus.edu.sg)

Abstract: 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-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 completely positive (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.

Keywords: Linearly constrained quadratic optimization problems with complementarity constraints, the Lagrangian-conic relaxation, Bisection method, Iterative solver

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 10/08/2013
Entry Accepted: 10/09/2013
Entry Last Modified: 10/08/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society