Relaxing the Optimality Conditions of Box QP
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.
Entry Submitted: 10/26/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|