Convergence rate of McCormick relaxations

Convergence rate of McCormick relaxations

0.00 Avg rating0 Votes
Article ID: iaor201113485
Volume: 52
Issue: 1
Start Page Number: 1
End Page Number: 28
Publication Date: Jan 2012
Journal: Journal of Global Optimization
Authors: ,
Keywords: global convergence
Abstract:

Theory for the convergence order of the convex relaxations by McCormick (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 (1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.

Reviews

Required fields are marked *. Your email address will not be published.