Concave Quadratic Cuts for Mixed-Integer Quadratic Problems

2015/10/21 by Park, Jaehyun, Boyd, Stephen
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1510.06421

Abstract

The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice \bf Zⁿ, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.

Related

• SDP-quality bounds via convex quadratic relaxations for global\n optimization of mixed-integer quadratic programs
• Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs: Algorithms and Approximation Bounds
• Compact mixed-integer programming relaxations in quadratic optimization
• Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations
• Progressive Bound Strengthening via Doubly Nonnegative Cutting Planes for Nonconvex Quadratic Programs