(253f) Quadratic Underestimators of Differentiable Mccormick Relaxations for Deterministic Global Optimization

Global optimization is extremely important in process systems engineering due to the nonconvexity of commonly-encountered models. Deterministic global solvers are comprised of a spatial branch-and-bound algorithm in conjunction with a means of calculating and tightening valid bounds, and creating valid convex relaxations of the original problem on relevant subdomains [1,2]. Typically, upper bounds can be determined by solving locally the original nonlinear program (NLP) to feasibility [3]. The computation of the lower bound has been the proven challenge. While the auxiliary variable methods provide a valid approach to computing lower bounds, the use of generalized McCormick relaxations may have significant benefits: they allow for the naive relaxation of algorithmically-defined functions and a potentially smaller decision space for the global optimization problem [4-7].

Lower-bounding problems obtained through standard or multivariate McCormick relaxations are potentially nonsmooth NLPs necessitating the use of nonsmooth solvers such as the proximal bundle method, PBUN [3,6-9]. Nonsmooth solvers are typically restricted to affine constraints and are generally not as robust as commercial local solvers such as IPOPT [10]. Mitsos et al. makes use of affine relaxations of McCormick relaxations of the objective function and constraints in order to generate linear programs [7]. Khan et al. developed differentiable McCormick relaxations which can be used to form smooth NLPs that can be readily addressed by local solvers [11]. However, these potentially-tighter relaxations are not without a cost. LP relaxations only require a single function and constraint evaluation to generate the lower-bounding problem. While the number of function evaluations for commercial solvers vary greatly depending on the problem [7,9].

In this work, we introduce a novel manner of generating nonlinear differentiable lower bounds based on differentiable McCormick relaxations. We utilize these new relaxations to generate convex quadratic programs (QP) and quadratically-constrained quadratic programs (QCQP) [12]. Each of these subproblems requires a single function (gradient and hessian) evaluation to generate a small QP or QCQP. These relaxations are often tighter than affine relaxations of similar functions, require fewer original function evaluations than full NLP subproblems, and can be readily solved using commercial solvers such as Gurobi [13].

We will introduce the theory behind these QP/QCQP relaxations. Practical aspects of generating these relaxed problems, such as the varying automatic differentiation schemes, will be reviewed [14]. Lastly, the performance of this relaxation scheme will be compared to nonsmooth NLP, smooth NLP, and LP relaxations within a global optimization routine using literature examples and problems taken from the COCONUT library [15].

[1] Horst, R. and Tuy, H., A. Global Optimization: Deterministic Approaches. Springer Berlin Heidelberg. 2013.

[2] Floudas, Christodoulos A., and Chrysanthos E. Gounaris. "A review of recent advances in global optimization." Journal of Global Optimization 45.1 (2009): 3-38.

[3] Stuber, M.D., Scott, J.K., and P.I. Barton. Convex and Concave Relaxations of Implicit Functions. Optimization Methods and Software. 30(3), 424-460, 2014.

[4] Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, 103(2), 225-249, 2005.

[5] Sahinidis, N. V., BARON 14.4.0: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2014.

[6] Scott, J.K., Stuber, M.D., and Barton, P.I. Generalized McCormick Relaxations. J Global Optim, 51:569-606, 2011.

[7] Mitsos, A., Chachuat, B., and Barton, P.I. McCormick-Based Relaxations of Algorithms. SIAM J. Optim. 20(2): 573-601.

[8] Tsoukalas, A. and Mitsos, A. Mutlivariate McCormick Relaxations. J Global Optim, 59:633-662, 2014.

[9] L. Luksan and J. Vlcek. Algorithms for non-differentiable optimization. ACM

Transactions on Mathematical Software, 27(2):193–213, June 2001.

[10] Waechter, A.W., Biegler, L.T., On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming. Mathematical Programming 106(1): 25-57, 2006.

[11] Khan, K.A., Watson, H.A., and Barton, P.I. Differentiable McCormick Relaxations. J Global Optim, 67(4):687-729, 2017.

[12] Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004. [13] Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual. http://www.gurobi.com. 2016

[14] Griewank, A. Evaluating derivatives: Principles and techniques of algorithmic differentiation (2. rev. ed.). Philadelphia: Soc. for Industrial and Applied Mathematics. 2009.

[15] O. Shcherbina, et al. Benchmarking Global Optimization and Constraint Satisfaction Codes, In Global Optimization and Constraint Satisfaction, Bliek, Ch., Jermann, Ch. and Neumaier, A. Springer, Berlin 2003, 212-222.