McCormick-based efficient global optimization in the space of degrees of freedom

  • McCormick-basierte effiziente globale Optimierung im Raum der Freiheitsgrade

Najman, Jaromil; Mitsos, Alexander (Thesis advisor); Naumann, Uwe (Thesis advisor)

Aachen : RWTH Aachen University (2020, 2021)
Book, Dissertation / PhD Thesis

In: Aachener Verfahrenstechnik series. Process systems engineering 7 (2020)
Page(s)/Article-Nr.: 1 Online-Ressource (XIV, 174 Seiten) : Illustrationen, Diagramme

Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2020


The popularity of deterministic global optimization in the field of mathematical programming increases steadily. The development of novel algorithms combined with the increasing computational power allows for the solution of more complex optimization problems. As the computation of convex relaxations constitutes a major element of deterministic global optimization, the importance of general methods for the construction of valid relaxations rises.The propagation rules introduced by McCormick represent one such general technique with the advantage of operating in the original space of optimization variables. We analyze convergence properties of and develop tailored algorithms and heuristics for McCormick relaxations. Moreover, we develop tight relaxations and envelopes for specific functions commonly found in the field of process systems engineering and present a way to construct convex relaxations for componentwise convex function. First, the convergence order in the Hausdorff and pointwise metric for multivariate McCormick relaxations is established. Additionally, specialized results for convergence order at a specific point of the underlying domain are provided. The convergence order of relaxations obtained through the multivariate rule is at least as good as the convergence order of the relaxations computed with the use of the original McCormick propagation rules. Moreover, we analyze the property when a given relaxation is exact at specific points in the domain in terms of convergence order. We provide theoretical results supported by illustrative examples. Then, we propose envelopes and tight relaxations respectively for the logarithmic mean temperature difference function, functions commonly found in mixture models and equipment cost correlations. The relaxations and envelopes are deduced analytically. All resulting relaxations provide significant computational advantages when used within a Branch-and-Bound framework. Additionally, we provide a result allowing the construction of convex relaxations of componentwise convex functions if certain monotonicity properties of the partial derivatives are fulfilled. Finally, we develop algorithms suited for the application of McCormick relaxations in a Branch-and-Bound algorithm. The first method exploits information obtainable during subgradient propagation of McCormick relaxations to first tighten the intermediate factors and subsequently the final relaxation. The subsequent algorithms aim to provide a set of good linearization points used in order to construct an affine relaxation of the lower bounding problem. The algorithm developed last combines the McCormick method with the state-of-the-art auxiliary variable method. The hybrid method introduces only a limited number of auxiliary variables in the lower bounding problem. All heuristic yield drastic improvements with respect to computational time within a Branch-and-Bound framework on the considered optimization problems.