(449d) Mccormick Relaxations: Extension to Multivariate Outer Function and Analysis of Convergence Rates

Converging convex/concave relaxations is of primal significance for the global solution of nonconvex programs. High convergence rates of the relaxations of the nonconvex functions assure finite termination of methods relying on the estimators in the limits, e.g., [8].
The technique for constructing convex and concave relaxations for factorable functions was originally presented by McCormick [4]. Factorable functions are constructed by using a finite recursive composition of binary sums, binary products and a known library of univariate intrinsic functions. Propagation of the relaxations of functions of the form F₁º f₁ + F₂ º f₂ · F₃ º f₃ is possible with two main theorems. Tsoukalas and Mitsos [9] extended the McCormick univariate to multivariate outer functions, i.e., functions of the form g=F(f₁,...,f_m). It was also shown in [9] that this extension provides at least as tight relaxations as the relaxations obtained by the original McCormick rules and in special cases, such as the binary product, minimum and maximum functions and fractional terms, strictly tighter relaxations.
The well-known branch-and-bound (B&B) algorithm performs better if fast convergence of the relaxations can be achieved, since nodes with almost optimal objective value can only be fathomed if the relaxations used in the computations are sufficiently tight. The discussions in [3, 6, 10] on the cluster effect and additionally the recent article about convergence of geometric B&B methods [7] give a deeper insight on the problem.
Bompadre and Mitsos [2] discussed the concept of convergence order of McCormick relaxations. The analysis is based on interval analysis concepts [1, 5], where the convergence orders of the relaxations is considered by the comparison of the estimation error to the decrease of the range of the function. 
In this work we establish the convergence order in the McCormick relaxations developed in [9]. We consider the convergence orders in the Hausdorff metric by comparing the range of the original functions to the range of its estimators and pointwise convergence orders by comparing the maximum distance between the original functions and its estimators over a given domain. Similar to the results in [2] the convergence orders are resolved by the orders of the inclusion functions of the inner functions and the convergence order of the multivariate outer function. We show supported by examples that in the case of the binary sum with the usage of results in [9], the convergence rate remains the same, while for the binary product and the minimum function higher convergence orders are possible.
References
[1] G. Alefeld and G. Mayer. Interval analysis: Theory and applications. Journal of Computational and Applied Mathematics, 121(12):421-464, 2000.
[2] A. Bompadre and A. Mitsos. Convergence rate of McCormick relaxations. Journal of Global Optimization, 52(1):1-28, 2012.
[3] K. Du and R. B. Kearfott. The cluster problem in multivariate global optimization. Journal of Global Optimization, 5(3):253-265, 1994.
[4] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical Programming, 10(1):147-175, 1976.
[5] R. E. Moore and F. Bierbaum. Methods and applications of interval analysis (SIAM Studies in Applied and Numerical Mathematics). Society for Industrial & Applied Math, 1979.
[6] A. Neumaier. Complete search in continuous global optimization and constraint satisfaction. Acta Numerica, 13:271-369, 5 2004.
[7] A. Schöbel and D. Scholz. The theoretical and empirical rate of convergence for geometric branch-and-bound methods. Journal of Global Optimization, 48(3):473-495, 2010.
[8] M. Tawarmalani and N. V. Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2):225-249, 2005.
[9] A. Tsoukalas and A. Mitsos. Multivariate McCormick relaxations. Journal of Global Optimization, 59:633-662, 2014.
[10] A. Wechsung, S. D. Schaber, and P. I. Barton. The cluster problem revisited. Journal of Global Optimization, 58(3):429-438, 2014.