Optimization Online


Relaxing the Optimality Conditions of Box QP

Samuel Burer(samuel-burer***at***uiowa.edu)
Jieqiu Chen(jieqiu-chen***at***uiowa.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

  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 Programming Society