Zugl.: Freiberg (Sachsen), Techn. Univ., Diss., 2008

The subject of this thesis are mathematical programs with complementarity conditions (MPCC). At first, an economic example of this problem class is analyzed, the problem of effort maximization in asymmetric n-person contest games. While an analytical solution for this special problem could be derived, this is not possible in general for MPCCs. Therefore, optimality conditions which might be used for numerical approaches where considered next. More precisely, a Fritz-John result for MPCCs with stronger properties than those known so far was derived together with some new constraint qualifications and subsequently used to prove an exact penalty result. Finally, to solve MPCCs numerically, the so called relaxation approach was used. Besides improving the results for existing relaxation methods, a new relaxation with strong convergence properties was suggested and a numerical comparison of all methods based on the MacMPEC collection conducted. / Das Thema dieser Dissertation sind mathematische Programme mit Komplementaritätsrestriktionen (MPCC). Zunächst wurde eine ökonomische Anwendung dieses Problemklasse betrachtet, das sogenannte Wettbewerbsdesignproblem. Während es für dieses spezielle Problem möglich war eine analytische Lösung herzuleiten, ist dies im Allgemeinen nicht möglich. Daher wurden anschließend Optimalitätsbedingungen, die für eine numerische Lösung verwendet werden können, betrachtet. Genauer wurde ein stärkeres Fritz-John Resultat als die bisher bekannten zusammen mit neuen Constraint Qualifications hergeleitet und anschließend zum Beweis eines exakten Penaltyresultates benutzt. Schließlich wurden zur numerischen Lösung von MPCCs sogenannte Relaxationsverfahren betrachtet. Zusätzlich zur Verbesserung der Resultate für bekannte Verfahren wurde eine neue Relaxierung mit starken Konvergenzeigenschaften vorgeschlagen und ein numerischer Vergleich aller Verfahren auf Basis der MacMPEC Testsammlung durchgeführt.

In der Arbeit werden Zwei-Ebenen-Optimierungaufgaben mit einer nichtkonvexen Zielfunktion in der unteren Ebene betrachtet. Dazu werden die bekannten Begriffe der optimistischen und pessimistischen Lösung erweitert, um auch so genannte stationäre Lösungen zu definieren, deren Existenz unter schwächeren als den bisher geläufigen Halbstetigkeitsbedingungen gezeigt werden kann. Für den Fall der einparametrischen Zwei-Ebenen-Optimierung wird abschließend eine Verallgemeinerung des von Jongen, Jonker und Twilt eingeführten Generizitätsbegriffes vorgeschlagen, dessen Verwendung die numerische Behandlung solcher Aufgaben realisierbar macht.

In der Dissertation werden Zwei-Ebenen-Optimierungsaufgaben mit spezieller Struktur untersucht. Von Interesse sind hierbei für den sogenannten pessimistischen Lösungszugang Existenzresultate für Lösungen, die Eckpunkteigenschaft einer Lösung, eine Regularisierungstechnik, Optimalitätsbedingungen sowie für den linearen Fall ein Verfahren zur Bestimmung einer global pessimistischen Lösung. Beim optimistischen Lösungszugang wird zunächst eine Verallgemeinerung des Lösungsbegriffes angegeben. Anschließend finden sich Betrachtungen zur Komplexität des Problems, zu Optimalitätsbedingungen sowie ein Abstiegs- und Branch&Bound-Verfahren für den linearen Fall wieder. Den Abschluss der Arbeit bilden ein Anwendungsbeispiel und numerische Testrechnungen.

This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem. The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented

In this thesis, we derive necessary optimality conditions for bilevel programming problems (BPPs for short) in Banach spaces. This rather abstract setting reflects our desire to characterize the local optimal solutions of hierarchical optimization problems in function spaces arising from several applications. Since our considerations are based on the tools of variational analysis introduced by Boris Mordukhovich, we study related properties of pointwise defined sets in function spaces. The presence of sequential normal compactness for such sets in Lebesgue and Sobolev spaces as well as the variational geometry of decomposable sets in Lebesgue spaces is discussed. Afterwards, we investigate mathematical problems with complementarity constraints (MPCCs for short) in Banach spaces which are closely related to BPPs. We introduce reasonable stationarity concepts and constraint qualifications which can be used to handle MPCCs. The relations between the mentioned stationarity notions are studied in the setting where the underlying complementarity cone is polyhedric. The results are applied to the situations where the complementarity cone equals the nonnegative cone in a Lebesgue space or is polyhedral. Next, we use the three main approaches of transforming a BPP into a single-level program (namely the presence of a unique lower level solution, the KKT approach, and the optimal value approach) to derive necessary optimality conditions for BPPs. Furthermore, we comment on the relation between the original BPP and the respective surrogate problem. We apply our findings to formulate necessary optimality conditions for three different classes of BPPs. First, we study a BPP with semidefinite lower level problem possessing a unique solution. Afterwards, we deal with bilevel optimal control problems with dynamical systems of ordinary differential equations at both decision levels. Finally, an optimal control problem of ordinary or partial differential equations with implicitly given pointwise state constraints is investigated.

In der Dissertation werden Zwei-Ebenen-Optimierungsaufgaben mit spezieller Struktur untersucht. Von Interesse sind hierbei für den sogenannten pessimistischen Lösungszugang Existenzresultate für Lösungen, die Eckpunkteigenschaft einer Lösung, eine Regularisierungstechnik, Optimalitätsbedingungen sowie für den linearen Fall ein Verfahren zur Bestimmung einer global pessimistischen Lösung. Beim optimistischen Lösungszugang wird zunächst eine Verallgemeinerung des Lösungsbegriffes angegeben. Anschließend finden sich Betrachtungen zur Komplexität des Problems, zu Optimalitätsbedingungen sowie ein Abstiegs- und Branch&Bound-Verfahren für den linearen Fall wieder. Den Abschluss der Arbeit bilden ein Anwendungsbeispiel und numerische Testrechnungen.

In der Dissertation werden Aufgaben der Zwei-Ebenen-Optimierung mit diskreter unterer und stetiger oberer Ebene betrachtet. Es werden die Struktur dieser Aufgaben analysiert und Optimalitätsbedingungen angegeben. Dies erfolgt sowohl für den optimistischen und den pessimistischen Lösungszugang als auch für einen Lösungszugang mittels Auswahlfunktionen. Anschließend werden die theoretischen Ergebnisse auf drei verschiedene Aufgabenklassen angewendet.

In der Dissertation werden Aufgaben der Zwei-Ebenen-Optimierung mit diskreter unterer und stetiger oberer Ebene betrachtet. Es werden die Struktur dieser Aufgaben analysiert und Optimalitätsbedingungen angegeben. Dies erfolgt sowohl für den optimistischen und den pessimistischen Lösungszugang als auch für einen Lösungszugang mittels Auswahlfunktionen. Anschließend werden die theoretischen Ergebnisse auf drei verschiedene Aufgabenklassen angewendet.

In der Arbeit werden Zwei-Ebenen-Optimierungaufgaben mit einer nichtkonvexen Zielfunktion in der unteren Ebene betrachtet. Dazu werden die bekannten Begriffe der optimistischen und pessimistischen Lösung erweitert, um auch so genannte stationäre Lösungen zu definieren, deren Existenz unter schwächeren als den bisher geläufigen Halbstetigkeitsbedingungen gezeigt werden kann. Für den Fall der einparametrischen Zwei-Ebenen-Optimierung wird abschließend eine Verallgemeinerung des von Jongen, Jonker und Twilt eingeführten Generizitätsbegriffes vorgeschlagen, dessen Verwendung die numerische Behandlung solcher Aufgaben realisierbar macht.