(253f) Quadratic Underestimators of Differentiable Mccormick Relaxations for Deterministic Global Optimization
AIChE Annual Meeting
2018
2018 AIChE Annual Meeting
Computing and Systems Technology Division
Advances in Deterministic Global Optimization
Tuesday, October 30, 2018 - 9:35am to 9:54am
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.