(621c) Global Optimization of Nonconvex Quadratic Programs and Mixed-Integer Quadratic Programs

Nonconvex Quadratic programs (QPs) and mixed-integer quadratic programs (MIQPs) arise in a wide variety of scientific and engineering applications including facility location [21], quadratic assignment [9], molecular conformation [13] and max-cut problems [8]. Given their practical importance, these classes of problems have been studied extensively in the mathematical programming literature. State-of-the-art global optimization solvers rely on spatial branch-and-bound methods to solve problems of these form to global optimality. The efficiency of these methods primarily depends on the quality of the relaxations constructed during the bounding step. Tighter relaxations lead to tighter bounds, and often speed up convergence of the branch-and-bound algorithm.

Commonly used relaxations for these type of problems can be classified into four groups. The first group involves relaxations obtained via factorable programming techniques [10, 18, 20]. While these relaxations are relatively simple to construct, they typically result in large relaxation gaps. The second group is given by semi-definite programming (SDP) relaxations. This approach has received significant attention in recent years [1, 5, 6, 19]. Even though SDP relaxations often provide strong bounds, they are computationally expensive to solve, which has limited their use within general purpose branch-and-bound solvers. The third group relies on the reformulation-linearization techniques (RLT) [15–17]. Though these techniques typically yield tight bounds, the resulting relaxations grow quickly in size, and thus can become expensive to solve. The fourth group consists of factorable relaxations augmented by adding various classes of valid inequalities such as SDP-based cuts [7, 14], RTL-based cuts [22, 23], facets of the envelopes of edge-concave and multilinear subexpressions [2, 3, 11, 12], and mixed-integer cuts [4]. These augmented relaxations provide stronger bounds than those of factorable relaxations while remaining computationally inexpensive to solve. Due to its practicality, this class of relaxations is employed in most general-purpose global optimization packages.

In this talk, we investigate a different class of relaxations for nonconvex QPs and MIQPs. In particular, we derive convex quadratic relaxations by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We demonstrate that the resulting quadratic relaxations are in many cases significantly tighter than other relaxations commonly used in state-of-the-art optimization solvers. We also introduce novel branching variable selection strategies which can be used in conjunction with the quadratic relaxations investigated in this work. We integrate the proposed relaxation and branching techniques into the global optimization solver BARON, and test our implementation by conducting numerical experiments on a large collection of problems. Results demonstrate that the proposed implementation accelerates the convergence speed of the branch-and-bound algorithm, leading to very significant reductions in the computational times required to solve the test problems.

[1] Anstreicher, K. M. Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43:471–484, 2009.

[2] Bao, X., Khajavirad, A., Sahinidis, N.V., and Tawarmalani, M. Global optimization of nonconvex problems with multilinear intermediates. Mathematical Programming Computation, 7:1–37, 2015.

[3] Bao, X., Sahinidis, N.V., and Tawarmalani, M. Multiterm polyhedral relaxations for nonconvex quadratically constrained quadratic programs. Optimization Methods and Software, 24:485–504, 2009.

[4] Bonami, P., Günlük, O., and Linderoth, J. Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Mathematical Programming Computation, 2018, https://doi.org/10.1007/s12532-018-0133-x

[5] Buchheim, C. and Wiegele, A. Semidefinite relaxations for non-convex quadratic mixed-integer programming, Mathematical Programming, 141:435–452, 2013.

[6] Burer, S., Vandenbussche, D. A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Mathematical Programming, 112:259–282, 2008.

[7] Dong, H. Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM Journal on Optimization, 26:1962–1985, 2016.

[8] Goemans, M. X. and Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42:1115–1145, 1995.

[9] Loiola, E.M., De Abreu, N.M.M. Boaventura-Netto, P.O., Hahn, P., and Querido, T., A survey for the quadratic assignment problem, European Journal of Operational Research, 176:657–690, 2007.

[10] McCormick, G. P. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems, Mathematical Programming, 10:147–175, 1976.

[11] Misener, R. and Floudas, C.A. Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Mathematical Programming, 136:155–182, 2012.

[12] Misener, R., Smadbeck, J.B, and Floudas, C.A. Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optimization Methods and Software, 30:215–249, 2015.

[13] Phillips, A.T. and Rosen, J.B. A quadratic assignment formulation of the molecular conformation problem. Journal of Global Optimization, 4:229–241, 1994.

[14] Saxena A., Bonami, P., and Lee, J. Convex relaxations of mixed integer quadratically constrained programs: Projected formulations, Mathematical Programming, 130:359–413, 2011.

[15] Sherali, H.D. and Adams, W.P. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3:411–430, 1990.

[16] Sherali, H.D., and Alameddine, A. A new reformulation-linearization technique for bilinear programming problems, Journal of Global Optimization, 2:379–410, 1992.

[17] Sherali, H.D. and Tuncbilek, C.H. A reformulation–convexification approach for solving nonconvex quadratic programming problems, Journal of Global Optimization, 7:1–31, 1995.

[18] Sherali, H. D. and Wang, H. Global optimization of nonconvex factorable programming problems, Mathematical Programming, 89:459–478, 2001.

[19] Shor, N.Z. Quadratic optimization problems, Soviet Journal of Computer and Systems Sciences, 25:1–11, 1987.

[20] Tawarmalani, M. and Sahinidis, N. V. Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99:563–591, 2004.

[21] Xie, W. and Sahinidis, N.V. A branch-and-bound algorithm for the continuous facility layout problem, Computers and Chemical Engineering, 32:1016–1028, 2008.

[22] Zorn, K. and Sahinidis, N.V. Global optimization of general non-convex problems with intermediate bilinear substructures, Optimization Methods and Software, 29:442–462, 2013.

[23] Zorn, K. and Sahinidis, N.V. Global optimization of general nonconvex problems with intermediate polynomial substructures, Journal of Global Optimization, 59:673–693, 2014.