Optimization Online


Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming

Jieqiu Chen (jieqchen***at***mcs.anl.gov)
Samuel Burer (samuel-burer***at***uiowa.edu)

Abstract: Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature---finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.

Keywords: nonconvex quadratic programming, global optimization, branch-and-bound, SDP, copositive programming

Category 1: Global Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Optimization Software and Modeling Systems (Other )

Citation: Argonne National Laboratory Mathematics and Computer Science Division Preprint ANL/MCS-P1837-0211

Download: [PDF]

Entry Submitted: 02/24/2011
Entry Accepted: 02/24/2011
Entry Last Modified: 08/15/2011

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