Differentiable McCormick relaxations. (English) Zbl 1365.49027
J. Glob. Optim. 67, No. 4, 687-729 (2017); correction ibid. 70, No. 3, 705-706 (2018).
Summary: McCormick’s classical relaxation technique constructs closed-form convex and concave relaxations of compositions of simple intrinsic functions. These relaxations have several properties which make them useful for lower bounding problems in global optimization: they can be evaluated automatically, accurately, and computationally inexpensively, and they converge rapidly to the relaxed function as the underlying domain is reduced in size. They may also be adapted to yield relaxations of certain implicit functions and differential equation solutions. However, McCormick’s relaxations may be nonsmooth, and this nonsmoothness can create theoretical and computational obstacles when relaxations are to be deployed. This article presents a continuously differentiable variant of McCormick’s original relaxations in the multivariate McCormick framework of Tsoukalas and Mitsos. Gradients of the new differentiable relaxations may be computed efficiently using the standard forward or reverse modes of automatic
differentiation. Extensions to differentiable relaxations of implicit functions and solutions of parametric ordinary differential equations are discussed. A C++ implementation based on the library MC++ is described and applied to a case study in nonsmooth nonconvex optimization.
MSC:
| 49M20 | Numerical methods of relaxation type |
| 90C26 | Nonconvex programming, global optimization |
| 65G40 | General methods in interval analysis |
| 26B25 | Convexity of real functions of several variables, generalizations |
| 49J45 | Methods involving semicontinuity and convergence; relaxation |
Software:
SCIP; BARON; SNOPT; Couenne; LINDO; MPBNGC; MC++; LINDOGlobal; PBNCGC; ANTIGONE; amodMC; libMCReferences:
| [1] | Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1, 1-41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1 |
| [2] | Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: a new approach to integrate CP and MIP. In: Proceedings of the Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 6-20. Paris (2008) · Zbl 1142.68504 |
| [3] | Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, \[ \alpha\] αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22, 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1 |
| [4] | Alefeld, G., Mayer, G.: Interval analysis: theory and applications. J. Comput. Appl. Math. 121, 421-464 (2000) · Zbl 0995.65056 · doi:10.1016/S0377-0427(00)00342-3 |
| [5] | Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, Hoboken (2006) · Zbl 1140.90040 · doi:10.1002/0471787779 |
| [6] | Beckers, M.; Mosenkis, V.; Naumann, U.; Forth, S. (ed.); Hovland, P. (ed.); Phipps, E. (ed.); Utke, J. (ed.); Walther, A. (ed.), Adjoint mode computation of subgradients for McCormick relaxations, 103-113 (2012), Berlin · Zbl 1253.65031 · doi:10.1007/978-3-642-30023-3_10 |
| [7] | Belotti, P.: COUENNE: A user’s manual. https://projects.coin-or.org/Couenne (2006) |
| [8] | Bertsekas, DP; Balinski, M. (ed.); Wolfe, P. (ed.), Nondifferentiable optimization via approximation, 1-25 (1975), Amsterdam · Zbl 0383.49025 |
| [9] | Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077 |
| [10] | Bompadre, A., Mitsos, A.: Convergence rate of McCormick relaxations. J. Glob. Optim. 52, 1-28 (2012) · Zbl 1257.90077 · doi:10.1007/s10898-011-9685-2 |
| [11] | Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [12] | Broyden, C.G., Dennis Jr., J.E., Moré, J.J.: On the local and superlinear convergence of quasi-Newton methods. J. Inst. Math. Appl. 12, 223-245 (1973) · Zbl 0282.65041 · doi:10.1093/imamat/12.3.223 |
| [13] | Chachuat, B.: MC++: a toolkit for bounding factorable functions, v1.0. Retrieved 2 July 2014 https://projects.coin-or.org/MCpp (2014) |
| [14] | Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309 |
| [15] | Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. McGraw Hill Co., Inc., New York (1955) · Zbl 0064.33002 |
| [16] | Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5, 253-265 (1994) · Zbl 0824.90121 · doi:10.1007/BF01096455 |
| [17] | Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. 2. Springer, New York (2003) · Zbl 1062.90002 |
| [18] | Feehery, W.F., Tolsma, J.E., Barton, P.I.: Efficient sensitivity analysis of large-scale differential-algebraic systems. Appl. Numer. Math. 25, 41-54 (1997) · Zbl 0884.65086 · doi:10.1016/S0168-9274(97)00050-0 |
| [19] | Gabriel, S.A., Moré, J.J.: Smoothing of Mixed Complementarity Problems. Preprint MCS-P541-0995, Argonne National Laboratory (1995) · Zbl 0886.90154 |
| [20] | Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47(1), 99-131 (2002) · Zbl 1210.90176 · doi:10.1137/S0036144504446096 |
| [21] | Griewank, A., Rabier, P.J.: On the smoothness of convex envelopes. Trans. Am. Math. Soc. 322, 691-709 (1990) · Zbl 0712.49010 · doi:10.1090/S0002-9947-1990-0986024-2 |
| [22] | Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Other Titles in Applied Mathematics, 2nd edn. SIAM, Philadelphia (2008) · Zbl 1159.65026 · doi:10.1137/1.9780898717761 |
| [23] | Grossmann, I.E., Yeomans, H., Kravanja, Z.: A rigorous disjunctive optimization model for simultaneous flowsheet optimization and heat integration. Comput. Chem. Eng. 22(98), 157-164 (1998) · doi:10.1016/S0098-1354(98)00050-7 |
| [24] | Hartman, P.: Ordinary Differential Equations, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1009.34001 · doi:10.1137/1.9780898719222 |
| [25] | Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. A Series of Comprehensive Studies in Mathematics. Springer, Berlin (1993) · Zbl 0795.49001 |
| [26] | Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. A Series of Comprehensive Studies in Mathematics. Springer, Berlin (1993) · Zbl 0795.49002 |
| [27] | Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993) · Zbl 0704.90057 · doi:10.1007/978-3-662-02947-3 |
| [28] | Kesavan, P., Allgor, R.J., Gatzke, E.P., Barton, P.I.: Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. Math. Program. Ser. A 100, 517-535 (2004) · Zbl 1136.90024 · doi:10.1007/s10107-004-0503-1 |
| [29] | Khan, K.A.: Sensitivity analysis for nonsmooth dynamic systems. Ph.D. thesis, Massachusetts Institute of Technology (2015) |
| [30] | Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. Springer, Berlin (1985) · Zbl 0561.90059 · doi:10.1007/BFb0074500 |
| [31] | Lemaréchal, C.; Strodiot, JJ; Bihain, A.; Mangasarian, OL (ed.); Meyer, RR (ed.); Robinson, SM (ed.), On a bundle algorithm for nonsmooth optimization (1981), New York · Zbl 0533.49023 |
| [32] | Li, X., Tomasgard, A., Barton, P.I.: Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs. J. Optim. Theory Appl. 151, 425-454 (2011) · Zbl 1245.90079 · doi:10.1007/s10957-011-9888-1 |
| [33] | Liberti, L., Pantelides, C.C.: Convex envelopes of monomials of odd degree. J. Glob. Optim. 25, 157-168 (2003) · Zbl 1030.90117 · doi:10.1023/A:1021924706467 |
| [34] | Lin, Y., Schrage, L.: The global solver in the LINDO API. Optim. Methods Softw. 24, 657-668 (2009) · Zbl 1177.90325 · doi:10.1080/10556780902753221 |
| [35] | Mäkelä, M.M.: Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0. Reports of the Department of Mathematical Information Technology, Series B, Scientific computing B 13/2003, University of Jyväskylä (2003) |
| [36] | Maly, T., Petzold, L.R.: Numerical methods and software for sensitivity analysis of differential-algebraic systems. Appl. Numer. Math. 20, 57-79 (1996) · Zbl 0854.65056 · doi:10.1016/0168-9274(95)00117-4 |
| [37] | Mangasarian, O.L.: A simple characterization of solution sets of convex programs. Oper. Res. Lett. 7(1), 21-26 (1988) · Zbl 0653.90055 · doi:10.1016/0167-6377(88)90047-8 |
| [38] | McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I—convex underestimating problems. Math. Program. 10, 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [39] | Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59, 503-526 (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [40] | Mitsos, A., Chachuat, B., Barton, P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20, 573-601 (2009) · Zbl 1192.65083 · doi:10.1137/080717341 |
| [41] | Moore, R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979) · Zbl 0417.65022 · doi:10.1137/1.9781611970906 |
| [42] | Najman, J., Mitsos, A.: Convergence analysis of multivariate McCormick relaxations. J. Glob. Optim. in press (2016) · Zbl 1394.90471 |
| [43] | Naumann, U.: The Art of Differentiating Computer Programs. SIAM, Philadelphia (2012) · Zbl 1275.65015 |
| [44] | Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1990) · Zbl 0715.65030 |
| [45] | Nocedal, J., Wright, S.J.: Numerical Optimization. Springer series in operations research and financial engineering, 2nd edn. Springer, New York (2006) · Zbl 1104.65059 |
| [46] | Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics. SIAM, Philadelphia (2000) · Zbl 0949.65053 · doi:10.1137/1.9780898719468 |
| [47] | Qi, L., Sun, D.: Smoothing functions and smoothing Newton method for complementarity and variational inequality problems. J. Optim. Theory Appl. 113, 121-147 (2002) · Zbl 1032.49017 · doi:10.1023/A:1014861331301 |
| [48] | Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1970) · Zbl 0193.18401 |
| [49] | Ryoo, H.S., Sahinidis, N.V.: Global optimization of nonconvex NLPs and MINLPs with applications in process design. Comput. Chem. Eng. 19(5), 551-566 (1995) · doi:10.1016/0098-1354(94)00097-2 |
| [50] | Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201-205 (1996) · Zbl 0856.90104 · doi:10.1007/BF00138693 |
| [51] | Sahinidis, N.V.: BARON 15.9: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual. https://www.gams.com/help/topic/gams.doc/solvers/baron/index.html (2015) |
| [52] | Schaber, S.D.: Tools for dynamic model development. Ph.D. thesis, Massachusetts Institute of Technology (2014) |
| [53] | Scholz, D.: Theoretical rate of convergence for interval inclusion functions. J. Glob. Optim. 53, 749-767 (2012) · Zbl 1259.90104 · doi:10.1007/s10898-011-9735-9 |
| [54] | Scott, J.K.: Reachability analysis and deterministic global optimization of differential-algebraic systems. Ph.D. thesis, Massachusetts Institute of Technology (2012) |
| [55] | Scott, J.K., Barton, P.I.: Convex and concave relaxations for the parametric solutions of semi-explicit index-one differential-algebraic equations. J. Optim. Theory Appl. 156, 617-649 (2013) · Zbl 1284.65095 · doi:10.1007/s10957-012-0149-8 |
| [56] | Scott, J.K., Barton, P.I.: Improved relaxations for the parametric solutions of ODEs using differential inequalities. J. Glob. Optim. 57, 143-176 (2013) · Zbl 1273.49034 · doi:10.1007/s10898-012-9909-0 |
| [57] | Scott, J.K., Chachuat, B., Barton, P.I.: Nonlinear convex and concave relaxations for the solutions of parametric ODEs. Optim. Control Appl. Methods 34, 145-163 (2013) · Zbl 1273.93089 · doi:10.1002/oca.2014 |
| [58] | Scott, J.K., Stuber, M.D., Barton, P.I.: Generalized McCormick relaxations. J. Glob. Optim. 51, 569-606 (2011) · Zbl 1232.49033 · doi:10.1007/s10898-011-9664-7 |
| [59] | Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer series in computational mathematics. Springer, Berlin (1985) · Zbl 0561.90058 · doi:10.1007/978-3-642-82118-9 |
| [60] | Stuber, M.D., Scott, J.K., Barton, P.I.: Convex and concave relaxations of implicit functions. Optim. Methods Softw. 30(3), 424-460 (2015) · Zbl 1327.65114 · doi:10.1080/10556788.2014.924514 |
| [61] | Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Nonconvex Optimization and Its Applications. Springer, Dordrecht (2002) · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1 |
| [62] | Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. A 99, 563-591 (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6 |
| [63] | Tsoukalas, A., Mitsos, A.: Multivariate McCormick relaxations. J. Glob. Optim. 59, 633-662 (2014) · Zbl 1312.90068 · doi:10.1007/s10898-014-0176-0 |
| [64] | Watson, H.A.J., Khan, K.A., Barton, P.I.: Multistream heat exchanger modeling and design. AIChE J. 61(10), 3390-3403 (2015) · doi:10.1002/aic.14965 |
| [65] | Wechsung, A.: Global optimization in reduced space. Ph.D. thesis, Massachusetts Institute of Technology (2014) |
| [66] | Wechsung, A., Aspelund, A., Gundersen, T., Barton, P.I.: Synthesis of heat exchanger networks at subambient conditions with compression and expansion of process streams. AIChE J. 57(8), 2090-2108 (2011) · doi:10.1002/aic.12412 |
| [67] | Wechsung, A., Schaber, S.D., Barton, P.I.: The cluster problem revisited. J. Glob. Optim. 58, 429-438 (2014) · Zbl 1297.49046 · doi:10.1007/s10898-013-0059-9 |
| [68] | Wechsung, A., Scott, J.K., Watson, H.A.J., Barton, P.I.: Reverse propagation of McCormick relaxations. J. Glob. Optim. 63(1), 1-36 (2015) · Zbl 1322.49048 · doi:10.1007/s10898-015-0303-6 |
| [69] | Whitney, H.: Analytic extensions of differentiable functions defined in closed sets. Trans. Amer. Math. Soc. 36, 63-89 (1934) · Zbl 0008.24902 · doi:10.1090/S0002-9947-1934-1501735-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
