Abstract
Theory for the convergence order of the convex relaxations by McCormick (Math Program 10(1):147–175, 1976) for factorable functions is developed. Convergence rules are established for the addition, multiplication and composition operations. The convergence order is considered both in terms of pointwise convergence and of convergence in the Hausdorff metric. The convergence order of the composite function depends on the convergence order of the relaxations of the factors. No improvement in the order of convergence compared to that of the underlying bound calculation, e.g., via interval extensions, can be guaranteed unless the relaxations of the factors have pointwise convergence of high order. The McCormick relaxations are compared with the αBB relaxations by Floudas and coworkers (J Chem Phys, 1992, J Glob Optim, 1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adjiman C.S., Androulakis I.P., Floudas C.A.: A global optimization method, αBB for general twice-differentiable constrained NLPs—II. Implementation and computational results. Comput. Chem. Eng. 22(9), 1159–1179 (1998)
Adjiman C.S., Androulakis I.P., Maranas C.D., Floudas C.A.: A global optimization method, αBB for process design. Comput. Chem. Eng. 20(Suppl A), S419–S424 (1996)
Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αBB for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)
Adjiman C.S., Floudas C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. Glob. Optim. 9(1), 23–40 (1996)
Akrotirianakis I.G., Floudas C.A.: Computational experience with a new class of convex underestimators: Box-constrained NLP problems. J. Glob. Optim. 29(3), 249–264 (2004)
Akrotirianakis I.G., Floudas C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30(4), 367–390 (2004)
Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)
Alefeld G., Mayer G.: Interval analysis: Theory and applications. J. Comput. Appl. Math. 121(1–2), 421–464 (2000)
Androulakis I.P., Maranas C.D., Floudas C.A.: αBB: A global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337–363 (1995)
Belotti P., Lee J., Liberti L., Margot F., Wachter A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5), 597–634 (2009)
Bhattacharjee B., Green W.H. Jr., Barton P.I.: Interval methods for semi-infinite programs. Comput. Optim. Appl. 30(1), 63–93 (2005)
Bhattacharjee B., Lemonidis P., Green W.H. Jr., Barton P.I.: Global solution of semi-infinite programs. Math. Program. Ser. B 103(2), 283–307 (2005)
Chachuat, B.: libMC: A numeric library for McCormick relaxation of factorable functions. Documentation and Source Code available at: http://yoric.mit.edu/libMC/ (2007)
Chachuat, B.: MC++: A versatile library for McCormick relaxations and Taylor models. Documentation and Source Code available at: http://www3.imperial.ac.uk/people/b.chachuat/research (2010)
Du K.S., Kearfott R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5(3), 253–265 (1994)
Gatzke E.P., Tolsma J.E., Barton P.I.: Construction of convex function relaxations using automated code generation techniques. Optim. Eng. 3(3), 305–326 (2002)
Goldstein A.A., Price J.F.: Descent from local minima. Math. Comput. 25(115), 569–574 (1971)
Gounaris C.E., Floudas C.A.: Tight convex underestimators for C-2-continuous problems: I. Univariate functions. J. Glob. Optim. 42(1), 51–67 (2008)
Gounaris C.E., Floudas C.A.: Tight convex underestimators for C-2-continuous problems: II. Multivariate functions. J. Glob. Optim. 42(1), 69–89 (2008)
Maranas C.D., Floudas C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97(10), 7667–7678 (1992)
Maranas C.D., Floudas C.A.: Global optimization for molecular conformation problems. Ann. Oper. Res. 42(3), 85–117 (1993)
Maranas C.D., Floudas C.A.: Global minimum potential energy conformations of small molecules. J. Glob. Optim. 4, 135–170 (1994)
Maranas C.D., Floudas C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim. 7(2), 143–182 (1995)
McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Math. Program. 10(1), 147–175 (1976)
McCormick G.P.: Nonlinear Programming: Theory, Algorithms and Applications. Wiley, New York (1983)
Mitsos A., Chachuat B., Barton P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2), 573–601 (2009)
Mitsos A., Lemonidis P., Lee C.K., Barton P.I.: Relaxation-based bounds for semi-infinite programs. SIAM J. Optim. 19(1), 77–113 (2008)
Moore R.: Methods and Applications of Interval Analysis. SIAM, Philadelphia, PA (1979)
Munkres J.: Topology, 2nd edn. Prentice Hall, Englewood Cliffs (1999)
Neumaier A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13, 271–369 (2004)
Ratschek, H., Rokne, J.: Computer Methods for the Range of Functions. Ellis Horwood Series, Mathematics and its Applications, New York (1984)
Ryoo H.S., Sahinidis N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19(4), 403–424 (2001)
Sahinidis, N., Tawarmalani, M.: BARON. http://www.gams.com/solvers/baron.pdf (2005)
Schöbel A., Scholz D.: The theoretical and empirical rate of convergence for geometric branch-and-bound methods. J. Glob. Optim. 48(3), 473–495 (2010)
Smith E.M.B., Pantelides C.C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4–5), 457–478 (1999)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Boston (2002)
Tawarmalani M., Sahinidis N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99(3), 563–591 (2004)
Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
Zlobec S.: On the Liu-Floudas convexification of smooth programs. J. Glob. Optim. 32(3), 401–407 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bompadre, A., Mitsos, A. Convergence rate of McCormick relaxations. J Glob Optim 52, 1–28 (2012). https://doi.org/10.1007/s10898-011-9685-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9685-2