I³MS - Mitsos Seminar
Prof. Dr. Alexander Mitsos - McCormick Relaxations: Convergence Rate and Extension to Multivariate Outer Functions
Process Systems Engineering, RWTH Aachen University
Optimization is a widely used tool in process systems engineering, but often the optimization problems have multiple suboptimal local minima. Deterministic global optimization algorithms can solve such problems, typically employing convex/concave relaxations of the objective and constraints. Several methods have been proposed for the construction of convergent relaxations, including the McCormick relaxations . These provide the framework for the computation of convex relaxations of composite functions. McCormick's relaxations are clearly a very important tool, but they have the limitation of only allowing univariate composition. Although most functions can be decomposed in a way that only univariate functions are used as building blocks, this often results in weak relaxations. Moreover, McCormick has not provided results for the convergence rate of these relaxations.
We propose a reformulation of McCormick's composition theorem, which while equivalent to the original, suggests a straight forward generalization to multi-variate outer functions. In addition to extending the framework, the multi-variate McCormick relaxation is a useful tool for the proof of relaxations: by direct application to the product, division and minimum/maximum of two functions, we obtain improved relaxations when comparing with uni-variate McCormick. Furthermore, we generalize the theory for the computation of subgradients  to the multi-variate case, envisioning practical methods that utilize the framework.
Further, we extend the notion of convergence order from interval extensions to convex relaxations in the pointwise metric and Hausdorff metric. We develop theory for the McCormick relaxations by extablishing convergence rules for the addition, multiplication and composition operations. 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. Additionally, the McCormick relaxations are compared with the alphaBB relaxations by Floudas and coworkers , which guarantee quadratic pointwise convergence. Finally, the convergence order of McCormick-Taylor models  is addressed. Illustrative and numerical examples are given and hybrid methods are discussed. The implication of the results are discussed for practical bound calculations as well as for convex/concave relaxations of factors commonly found in process systems engineering models.
 G.P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Mathematical Programming, 10(1):147–175, 1976.
 A. Mitsos, B. Chachuat and P.I. Barton. McCormick-based relaxations of algorithms. SIAM Journal on Optimization, 20(2):573–601, 2009.
 I.P. Androulakis, C.D. Maranas and C.A. Floudas. alphaBB: A Global Optimization Method for General Constrained Nonconvex Problems, Journal of Global Optimization, 7(4):337–363, 1995.
 A.M. Sahlodin and B. Chachuat. Convex/concave relaxations of parametric ODEs using Taylor models. Computers & Chemical Engineering 35(5):844–857, 2011