Detailansicht

Conic and quadratic optimization tools for optimization under uncertainty

Markus Gerald Alexander Gabl

Art der Arbeit

Dissertation

Universität

Universität Wien

Fakultät

Fakultät für Wirtschaftswissenschaften

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Doctor of Philosophy-Doktoratsstudium Wirtschaftswissenschaften (Dissertationsgebiet: Statistik und Operations Research)

Betreuer*in

Bomze Immanuel

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.66289

URN

urn:nbn:at:at-ubw:1-20809.20300.273468-7

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Der erste Teil beschäftigt sich mit quadratisch beschränkten, quadratischen Optimierungsproblemen (QCQPs) und deren konvexen Reformulierungen. Die ersten beiden Kapitel dienen der Einführung in diese Materie. Bei QCQPs handelt es sich um eine große und ausdrucksstarke Klasse von, im allgemeinen nicht-konvexen, Optimierungsproblemen. Es ist jedoch oft möglich sie zu konvexifizieren indem man die zulässigen Menge der Entscheidungsvariablen in einem höher-dimensionalen Raum einbettet, wobei eine geeignete konvexe Teilmenge in diesen Räumen beschrieben werden muss. Die Kegel der mengenspezifischen komplett-positiven Matrizen (set-completely postive matrices), wie etwa der Kegel der positive semidefiniten Matrizen oder der Kegel der komplett-positiven Matrizen, sind zentrale Zutaten in diesem Unterfangen. Wir präsentieren zwei neue Resultate auf diesem Forschungsfeld. Bei dem Ersten handelt es sich um eine Verallgemeinerung eines bekannten Resultats, das auf Pataki's Rang-Theorem beruht. Es ermöglicht die Reformulierung von homogenen QCQPs die eine bestimmte geometrische Voraussetzung erfüllen. Darauf aufbauend können wir eine Verallgemeinerung des weithin bekannten S-Lemmas herleiten, und erhalten darüber hinaus Einsichten in geometrische Eigenschaften des so genannten gemeinsamen numerischen Wertebereichs, der ein weiteres zentrales Objekt in der Analyse von QCQPs darstellt. Das Zweite Resultat behandelt reduzierte konische Reformulierungen von QCQPs, bei denen, wie bei der traditionellen Herangehensweise, die zulässigen Menge der Entscheidungsvariablen in einem höher-dimensionalen Raum eingebettet wird, dessen Dimension aber niedriger ist als bei bereits bekannten Reformulierungen. Wir diskutieren dieses Resultat im Kontext von Matrixvervollständigungsproblemen und zeigen auf, dass die beiden Gebiete eng zusammenhängen. Tatsächlich erlaubt unser Reformulierungsresultat die Herleitung eines neuartigen Resultats zu Vervollständigung von mengenspezifisch komplett positiven Matrizen. Im zweiten Teil des Buches wenden wir die oben beschriebene Theorie auf Probleme der Stochastischen und Robusten Optimierung an. Als erstes diskutieren wir eine zwei-stufige, stochastische Version des Standard-Quadratischen Optimierungsproblems (StQP). Wir beschäftigen uns mit unteren Schranken basierend auf einem Szenario-Ansatz, bei dem das zugrundeliegende Wahrscheinlichkeitsmaß diskretisiert und unterteilt wird um eine Hierarchie an unteren Schranken zu erstellen. Für jeden der unterschiedlichen Grade der Unterteilung lösen wir die sich ergebenden Subprobleme mit Hilfe der unteren und oberen Schranken die wir aus der reduzierten konischen Reformulierung des entsprechenden QCQPs gewinnen, sowie einer oberen Schranke auf Basis des Infection-Immunization-Dynamics Algorithmus für StQPs. Wir untersuchen die Effektivität dieser Methoden in einer Reihe von numerischen Experimenten. Weiters diskutieren wir eine allgemeine Strategie für die Verwendung von konvexen Reformulierung von QCQPs zum Zwecke der Reformulierung von semi-infiniten Nebenbedingungen mit quadratischer Abhängigkeit vom Index, die in der Robusten Optimierung auftreten. Wir wenden diese Strategie auf verschiedene Probleme der Robusten Optimierung an, wie etwa der Anpassungsfähigen Robust Optimierung (adjustable robust optimization) und der Konvex-Quadratischen Robusten Optimierung. Wir diskutieren darüber hinaus theoretische Aspekte des, für die Anwendung der allgemeinen Strategie kritischen, Problems der vollen, starken Dualität. Inspiriert durch jüngste Entwicklungen in der Literatur untersuchen wir die Anwendung von Anpassungsfähiger Robust Optimierung für die Reformulierung einer bestimmten Klasse von QCQPs. Diese Reformulierung des QCQPs als anpassungsfähiges, robustes Optimierungsproblem ist ihrerseits geeignet für die allgemeine Reformulierungsstrategie, was uns erlaubt untere Schranken für das ursprüngliche QCQP herzuleiten. Wir vergleichen diese Schranken mit anderen Schranken aus der Literatur im Rahmen von numerischen Experimenten. Im Finalen Teil des Buches führen wir ein neues Konzept für die Robuste Optimierung ein, basierend auf der relativ neuen Idee der Optimierung mit endogener Unsicherheit. Dabei wird angenommen, dass die Entscheidungsträger*in Einfluss auf die Art der Unsicherheit nehmen kann, etwa durch Investition in Markt-Forschung oder genauere Maschinen. Dieser Einfluss wird typischerweise über diskrete Entscheidungsvariablen modelliert, die steuern, welche Art von Unsicherheit sich die Entscheidungsträger*in aussetzen will. Diese Konstellation bedingt aber ein neues Phänomen: Jedes der verschiedenen Unsicherheitsregime hat eine andere robuste, optimale Lösung. Doch diese unterschiedlichen Lösungen unterscheiden sich nicht nur hinsichtlich ihrer Performancegarantie sondern auch hinsichtlich anderer Qualitäten wie etwa der Vorhersehbarkeit der Performance, der möglichen Reue im Nachhinein und der potentiell bestmöglichen Performance. Eine Entscheidungsträger*in die vornehmlich an einer Performancegarantie interessiert ist, möchte diese zusätzlichen Qualitäten vielleicht trotzdem berücksichtigen. Wir beschreiben eine solche Haltung als Unsicherheitspräferenz. Im letzten Kapitel des Buches führen wir die entsprechenden mathematischen Modelle ein und diskutieren mögliche Lösungsmethoden. Wir wenden dieses Konzept auf das Problem des Kürzesten Pfads mit endogener Unsicherheit an und zeigen, dass man das resultierende Problem mit Standardmethoden der diskreten, konischen Optimierung lösen kann und dass die Ergebnisse dazu geeignet sind bei der Entscheidungsfindung zu assistieren.

Abstract

(Englisch)

The first part is concerned with the quadratically constrained quadratic optimization problems (QCQPs) and their convex reformulations. We give an introduction to this topic in the first two sections of that part of the book. QCQPs form a large and versatile class of optimization problems which are in general nonconvex. However one can obtain exact convexifications by lifting the space of variables and restricting them to an appropriately structured convex set. The cones of set-completely positive matrices (for example the cone of positive semidefinite matrices, or the completely positive matrix cone) are a central ingredient for the characterizations of these lifted convex sets. We present two new results on this topic. The first one is a generalization of a known result that is based on Pataki's rank theorem. It allows us to reformulate homogeneous QCQPs that fulfill a certain geometric condition. Based on that, we can derive a generalized version of the well known S-lemma and infer some geometric properties of the so called joint numerical range, which is another central object in the study of QCQPs. The second result is about reduced conic reformulations of QCQPs, where we proof the exactness of a reformulation that involves a lifting of the variables into a smaller space compared to traditional approaches. We contextualize this result in the theory of matrix completion and show that these to fields have mutual implications. In fact, our exactness result implies a new result in set-completely positive matrix completion. In the second part of the book, we apply quadratic optimization theory to stochastic and robust optimization problems. We start out by considering a two-stage stochastic version of the well known standard quadratic optimization problem. We consider lower bounds based on a scenario approach where the probability measures is discretized and dissected in order to obtain a chain of lower bounds. For each level of the dissection one has to solve a number of quadratic optimization problems for which we provide lower bounds based on the reduced conic reformulation mentioned above and upper bounds based on the infection-immunization-dynamics algorithm for standard quadratic optimization problems. We investigate the efficacy of these methods in an array of numerical experiments. We also discuss a general strategy of using convex reformulations of QCQPs in order to obtain finite reformulations of the semi-infinite constraints present in robust optimization for the case where the left-hand side depends quadratically on the index. We apply this general strategy to various instances of robust optimization such as adjustable robust optimization and convex-quadratic robust optimization. We also investigate some theoretical aspects of the problem associated with dual attainability of the QCQP reformulations when applying the general strategy. Following a recent development in literature, we also show that adjustable robust optimization theory also can be used to obtain an adjustable robust reformulation of a certain class of QCQPs. This reformulation is in turn amendable to the general strategy so that we can obtain a lower bound for the original problem. We compare this lower bound to alternative approaches in a set of numerical experiments. The final part of the book is concerned with a new concept of robust optimization based on the recently introduced setting of endogenously uncertain optimization. In this setting the decision maker may influence parts of the uncertainty that she is facing, for example by investing in market research. This influence is typically modeled as a discrete decision on the uncertainty regime under which the decision maker wishes to operate. However, this situation gives rise to a new phenomenon: Each of the different uncertainty regimes has its own robustly optimal solutions. But these solutions may not only vary with respect to their worst case performance but, due to the different structures of the uncertainty in each individual regime, may also exhibit different qualities with respect to best case performance, regret and predictability. A decision maker who wishes to have a performance guarantee, i.e. wants to select one of the robustly optimal solutions, may still want to take these characteristics into account as additional decision criteria. We conceptualize such a desire as uncertainty preference. In the final chapter of the book we introduce the respective mathematical model and discuss solution methods and modeling capabilities. We also apply this new framework to the endogenously uncertain shortest path problem and provide some numerical experiments that show that we can solve this problem using mixed integer conic optimization techniques and that the obtained solutions have a meaningful impact on the decision making process.

Autor*innen

Markus Gerald Alexander Gabl

Haupttitel (Englisch)

Conic and quadratic optimization tools for optimization under uncertainty

Paralleltitel (Deutsch)

Anwendung von Methoden der Konischen und Quadratischen Optimierung auf Optimierungsprobleme mit Unsicherheit

Publikationsjahr

2021

Umfangsangabe

156 Seiten : Illustrationen

Sprache

Englisch

Beurteiler*innen

Kurt Anstreicher ,

Dick <<den>> Hertog

Klassifikation

31 Mathematik > 31.80 Angewandte Mathematik

AC Nummer

AC16329352

Utheses ID

58720

Studienkennzahl

UA | 794 | 370 | 136 |

Detailansicht

Abstracts

Schlagwörter