Discretization-based algorithms for the global solution of hierarchical programs

  • Diskretisierungsbasierte Algorithmen für die globale Lösung hierarchischer Optimierungsprobleme

Djelassi, Hatim; Mitsos, Alexander (Thesis advisor); Stein, Oliver (Thesis advisor)

Aachen (2020)
Book, Dissertation / PhD Thesis

In: Aachener Verfahrenstechnik series - AVT.SVT - Process systems engineering 8(2020)
Page(s)/Article-Nr.: 1 Online-Ressource (XV, 146 Seiten) : Illustrationen, Diagramme

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


Hierarchical programs are mathematical programs that are constrained by optimality of embedded lower-level programs. Different kinds of hierarchical programs such as (generalized) semi-infinite and bilevel programs arise in various applications reaching from design centering and robust optimization to multi-agent problems and problems with equilibrium conditions. However, the hierarchical structure of these problems makes them notoriously difficult to solve, especially, if their lower-level programs are nonconvex. In this thesis, an adaptive discretization approach is employed and improved in order to solve such hierarchical programs with nonconvex lower-level programs. First, considering a published discretization algorithm for the global solution of semi-infinite programs, the underlying assumptions are relaxed and a proof of convergence and finite termination is provided under the relaxed assumptions. Additionally, a hybridization of the same algorithm and another discretization algorithm from literature is proposed. While inheriting the relatively strong convergence guarantees of its first predecessor, it improves over both of its predecessors in terms of performance on standard test cases. Furthermore, a variant of the discretization strategy underlying all these algorithms is developed in an effort to improve computational performance. Second, generalized semi-infinite and bilevel programs with coupling equality constraints on their lower levels are considered. While this case usually conflicts with the discretization approach, the previously discussed algorithms and a bilevel algorithm from literature can be extended to cover this case. Under a uniqueness assumption for the solution of the coupling equality constraints that is satisfied for important applications, convergence and finite termination of the extended algorithms are proven. Furthermore, the algorithms' computational performance is analyzed. Third, existence-constrained semi-infinite programs are considered, which are a generalization of semi-infinite programs. It is shown that the previously developed hybrid algorithm for the solution of semi-infinite programs can be extended to this case. Under similar assumptions as for semi-infinite programs, convergence and finite termination of the extended algorithm are proven. Furthermore, the algorithm is applied to the solution of an adjustable robust design problem from chemical engineering. Finally, the application problem of categorizing contingencies in power grids according to their severity is considered. Building a categorization approach from the power systems literature, an existence-constrained semi-infinite program is proposed that can be used to perform the categorization. Furthermore, new models for the active components of the power grid are provided and it is shown that the resulting problem can be solved using the algorithms developed in this thesis. Based on this, a screening of contingencies in a large-scale power grid instance is performed and the results are discussed.