(135d) Convergence Rate of Convex Relaxations

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 [1] and the alphaBB relaxations [2] and the use of auxiliary variables [3]. To ensure finite termination, these relaxations must converge to the nonconvex functions in the limit, i.e., as the diameter of the host sets vanishes (reduction to singleton), e.g., through branching or subdivision. In interval extensions [4] this convergence is characterized using the convergence order which compares the rate of convergence of the estimation error to the rate of the decrease of the range of the function.

In this talk, first the notion of convergence order is extended from interval extensions to convex relaxations in the pointwise metric and Hausdorff metric. The main part of the talk develops theory for the well-known McCormick relaxations of factorable functions [1]. Convergence rules are established 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 [2], which guarantee quadratic pointwise convergence. 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.

[1] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Mathematical Programming, 10(2):147--175, 1976.

[2] 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.

[3] M. Tawarmalani and N. V. Sahinidis. Convexification and Global Optimization in
Continuous and Mixed-Integer Nonlinear Programming. Nonconvex Optimization and its
Applications. Kluwer Academic Publishers, Boston, 2002

[4] R. Moore. Methods and Applications of Interval Analysis. SIAM, Philadelphia, PA, 1979