title: Pareto efficiency and budget uncertainties in robust nonlinear optimization
title: Pareto-Effizienz und Budgetunsicherheiten in der robusten nichtlinearen Optimierung
Creators: name: Adelhuette, Dennis
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024
Subjects: subject: Robuste Optimierung

description: To deal with uncertain data in mathematical programs, robust optimization has emerged as one of the most important approaches. Several concepts have been developed in this field over the last decades, and many successful applications throughout mathematical programming have legitimized robust optimization. This dissertation studies nonlinear robust optimization problems, mostly under linear or concave uncertainty. We have discussed the question whether the concepts of Pareto efficiency and budget uncertainty can be extended from uncertain linear programs to uncertain nonlinear programs. We show that Pareto optimal solutions for general programs under linear cost uncertainty can be computed by applying reformulations as long as the uncertainty set is modeled as a convex set. We focus on semidefinite programs. Furthermore, we characterize Pareto optimal solutions for binary programs with a linear objective function under interval uncertainty. For the sake of illustration, we apply our results to the largest eigenvalue problem, and the max-cut problem. Moreover, we show that budget uncertainties, originally introduced for mixed- integer linear programs under interval uncertainty, can be applied to mixed- integer nonlinear programs under concave uncertainties. The resulting robust counterpart can be reformulated into a certain mixed-integer nonlinear program that is tractable when the involved support and conjugate functions admit a closed form. We also observe that binary programs under interval uncertainty in the objective that underlie an assignment structure admit a reformulation that is solvable in oracle-polynomial time. We conduct an exemplary numerical study to demonstrate the efficiency of our proposed formulations. As an application, we discuss the patient transport problem. We show that the budget uncertainty approach is not suitable for the ‘on the fly’ nature of the problem, as the computation time would be too long. Therefore we shorten the computation time by introducing by a heuristic approach inspired by recoverable robustness and demonstrate the efficiency of our approach in a numerical study with historical data. We interpret our results and consequently propose how to improve the real situation.
description: Die robuste Optimierung hat sich als einer der wichtigsten Ansätze zum Um- gang mit unsicheren Daten in Optimierungsproblemen erwiesen. In den letzten Jahrzehnten wurden mehrere Konzepte entwickelt, und viele erfolgreiche An- wendungen in der gesamten mathematischen Optimierung haben die robuste Optimierung legitimiert. Diese Dissertation untersucht nichtlineare robuste Optimierungsprobleme, meist unter linearer oder konkaver Unsicherheit. Wir erörtern die Frage, ob die Konzepte der Pareto-Effizienz und der Budgetunsicherheit von unsicheren linearen Programmen auf unsichere nichtlineare Programme übertragen bzw. erweitert werden können. Wir zeigen, dass Pareto-optimale Lösungen für allgemeine Programme unter linearer Kostenunsicherheit durch Reformulierungen bestimmt werden können, solange die Unsicherheitsmenge konvex modelliert wird. Dabei legen wir einen Fokus auf semidefinite Programme. Außerdem charakterisieren wir Pareto- optimale Lösungen für binäre Programme mit einer linearer Zielfunktion unter Intervall-Unsicherheit. Zur Veranschaulichung wenden wir unsere Ergebnisse bei der Bestimmung des maximalen Eigenwerts sowie des Max-Cut-Problems unter Unsicherheit an. Zudem zeigen wir, dass Budgetunsicherheiten von gemischt-ganzzahligen linearen Programmen auf gemischt-ganzzahlige nichtlineare Programme über- tragen werden können. Das daraus resultierende robuste Gegenstück kann in ein Programm ohne Unsicherheit umformuliert werden. Dieses kann zumindest theoretisch gelöst werden, solange sich alle auftretenden Funktionen algebraisch darstellen lassen, ohne die Größe des Problems exponentiell steigen zu lassen. Wir stellen überdies fest, dass binäre Programme, die einer Zuweisungsstruktur zugrunde liegen, eine äquivalente Reformulierung besitzen, welche in orakelpoly- nomialer Zeit lösbar ist. Wir führen eine beispielhafte numerische Studie durch, um die Effizienz der von uns vorgeschlagenen Formulierungen zu demonstrieren. Als Anwendung diskutieren wir das Patiententransportproblem. Wir zeigen, dass der Ansatz der Budgetunsicherheit für die “on the fly”-Natur des Problems nicht geeignet ist, da die Lösung der jeweiligen Programme zu lange dauert. Daher verkürzen wir die Berechnungszeit durch die Einführung eines heuristi- schen Ansatzes, der vom Konzept der wiederherstellbaren Robustheit inspiriert ist. Wir demonstrieren die Effizienz unseres Ansatzes in einer numerischen Studie mit historischen Daten. Wir interpretieren unsere Ergebnisse und geben Vorschläge, wie die reale Situation verbessert werden kann.