Abstract:
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 establishing 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, in which case at least quadratic conver- gence order can be guaranteed. Additionally, the McCormick relaxations are compared with the alphaBB relaxations by Floudas and coworkers, which also 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.
Biography:
Alexander Mitsos is a Full Professor (W3) in RWTH Aachen University, and the Director of the Laboratory for Process Sys- tems Engineering (AVT.SVT), comprising 40 research and administrative staff. Mitsos received his Dipl-Ing from University of Karlsruhe in 1999 and his Ph.D.
from MIT in 2006, both in Chemical Engineering. Prior appointments include military service, free-lance engineering, involvement in a start-up company, a junior research group leader position in the Aachen Institute of Computational Engineering Science and the Rockwell International Assistant Professorship at MIT. Mitsos has over 60 publications in peer-reviewed journals and has received a number of awards. His research focuses on optimization of energy and chemical systems and development of enabling numerical algorithms.