(253c) Online Generation Via Offline Selection of Strong Linear Cuts from a Semidefinite Programming Relaxation

Deterministic global optimization is highly relevant solving quadratically-constrained quadratic optimisation (QCQP) problems that arise in a variety of engineering applications [1]. In a branch-and-cut framework, cutting planes are known to significantly expedite the solution for certain classes of QCQP problems [2-4].

Convex, particularly semidefinite programming (SDP), relaxations for non-convex continuous quadratic optimization can provide tighter bounds than the reformulation-linearization technique [5]. But using SDP relaxations directly in branch and cut is impeded by a lack of warm starting and inefficiency when combined with linear cut classes, e.g. the McCormick bilinear envelopes [6] or the reformulation-linearization technique [7]. State-of-the-art deterministic global optimization solvers use linear relaxations [4, 8-12], so SDP technology is effectively unavailable.

Previous work in developing SDP-based cutting planes has shown that these cuts can be very effective for certain classes of QCQP [13, 14]. But it’s still unclear when to generate these relatively expensive cuts, i.e. when to solve an SDP problem with the goal of generating a cutting plane. We seek an inexpensive oracle that will tell us when it is relevant to generate a cut and over which variables.

We present a general framework based on machine learning for a strong linear outer-approximation that can retain most tightness of such SDP relaxations, in the form of few strong low-dimensional linear cuts selected offline. The cut selection complexity is taken offline by using a neural network estimator (trained before installing solver software) as a selection device for the strongest cuts. Once the neural network estimator selects the appropriate subsets of variables, we generate hyperplanes cutting off the current objective based on negative eigenvalues [15, 16].

We present results of our method on several classes of non-convex application problems from the engineering literature. We also test the strategy on generic QCQP and integrate into the global optimization solver ANTIGONE [17].

References

[1] Boukouvala F, Misener R, Floudas CA. Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO. Eur J Oper Res. 252(3): 701-727, 2016.

[2] Bao X, Sahinidis NV, Tawarmalani M. Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim Met Softw. 24(4-5): 485-504, 2009.

[3] Misener R, Smadbeck JB, Floudas CA. Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. Optim Met Softw. 30(1): 215-49, 2015.

[4] Bonami P, Günlük O, Linderoth J. Solving box-constrained nonconvex quadratic programs. Optimization online. 2016.

[5] Anstreicher KM. Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J Glob Optim. 43(2-3): 471 – 484, 2009.

[6] McCormick GP. Computability of global solutions to factorable nonconvex programs: Part 1-convex underestimating problems. Math Program. 10: 147–175, 1976.

[7] Sherali HD, Adams WP. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1999.

[8] Tawarmalani M, Sahinidis NV. A polyhedral branch-and-cut approach to global optimization. Math Program. 103: 225-249, 2005.

[9] Belotti P, Lee J, Liberti L, Margot F, Wächter A. Branching and bounds tightening techniques for non-convex MINLP. Optim Met Softw. 24: 597-634, 2009.

[10] Misener R, Floudas CA. Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math Program B. 136: 155–182, 2012.

[11] Berthold T, Heinz S, Vigerske S. Extending a CIP framework to solve MIQCPs, in Mixed Integer Nonlinear Programming, In Lee, Leyffer (ed) Mixed Integer Nonlinear Program-ming, The IMA Volumes in Mathematics and its Applications. 154: 427-444, 2012.

[12] Misener R, Floudas CA, GloMIQO: Global mixed-integer quadratic optimizer. J Glob Optim. 57: 3-50, 2013.

[13] Saxena A, Bonami P, Lee J. Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Math Program. 124: 383-411, 2010.

[14] Saxena A, Bonami P, Lee J. Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations. Math Program. 130: 359-413, 2011.

[15] Qualizza A, Belotti P, Margot, F. Linear programming relaxations of quadratically constrained quadratic programs. In Lee, Leyffer (ed) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, 154: 407-426, 2012.

[16] Sherali HD, Fraticelli BMP. Enhancing RLT relaxations via a new class of semidefinite cuts.J Glob Optim. 22(1-4): 233-261, 2002.

[17] Misener R, Floudas CA, ANTIGONE: Algorithms for continuous / integer global optimization of nonlinear equations, J Glob Optim. 59(2-3): 503-526, 2014.