-

 

 

 




Optimization Online





 

Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations

Hongbo Dong (hongbo.dong***at***wsu.edu)

Abstract: The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our resulting relaxation does not use significantly more variables than the original problem, in contrast to many other relaxations based on lifting. The corresponding separation problem is a highly structured semidefinite program (SDP) with convex but non-smooth objective. We propose to solve this separation problem with a specialized primal-barrier coordinate minimization algorithm. Computational results show that our approach is very promising. Firstly, our separation algorithm is at least an order of magnitude faster than interior point methods for SDPs on problems up to a few hundred variables. Secondly, on nonconvex quadratic integer problems, our cutting surface procedure provides lower bounds of almost the same strength with the “diagonal” SDP bounds used by (Buchheim and Wiegele, 2013) in their branch-and-bound code Q-MIST, while our procedure is at least an order of magnitude faster on problems with dimension greater than 70. Finally, combined with (linear) projected RLT cutting planes proposed by (Saxena, Bonami and Lee, 2011), our procedure provides slightly weaker bounds than their projected SDP+RLT cutting surface procedure, but in several order of magnitude shorter time. Finally we discuss various avenues to extend our work to design more efficient branch-and-bound algorithms for MIQCPs.

Keywords: Quadratic Programming; Convex Relaxation; Cutting Plane Procedure;

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Theory )

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

Citation: Working paper, Department of Mathematics, Washington State University, 03/2014

Download: [PDF]

Entry Submitted: 03/12/2014
Entry Accepted: 03/12/2014
Entry Last Modified: 09/18/2016

Modify/Update this entry


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

 

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