Relaxing the Optimality Conditions of Box QP

Samuel Burer(samuel-bureruiowa.edu)
Jieqiu Chen(jieqiu-chenuiowa.edu)

Abstract: We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions. We compare these relaxations with a basic semidefinite relaxation due to Shor, particularly in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger. We also establish theoretical relationships between the new relaxations and Shor's relaxation.

Keywords: Nonconvex optimization, quadratic programming, optimality conditions, semidefinite relaxation

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Theory )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52240, USA, October 2007.

Download: [PDF]

Entry Submitted: 10/26/2007
Entry Accepted: 10/26/2007
Entry Last Modified: 10/26/2007

Modify/Update this entry