Anwendungen - Atlas optimization

Übersicht: Anwendungen Optimierung

Allgemeines

Auf den folgenden Unterseiten finden Sie Informationen zu den Arten von Problemen, die sich mit Hilfe der mathematischen Optimierung lösen lassen. Die dazu verwendeten Methoden und die grundlegende Theorie werden kurz umrissen; Codebeispiele detaillieren praktische Anwendungen.

Relevanz

Sobald es darum geht, zwischen mehreren Optionen zu wählen, stellt sich natürlicherweise die Frage nach der besten Option — ein Optimierungsproblem. Dabei mag die konkrete Anwendung darin bestehen, Produktparameter zu wählen, Ablaufpläne zu designen, Unbekannte Grössen zu schätzen oder Entscheidungen in komplexen Systemen zu treffen. Daher findet sich die Optimierung mittlerweile überall und wird verwendet in Finanzwesen, Schätztheorie, optimaler Steuerung, Belegungsplanung, industriellem Produktdesign, Messtechnik, Telekommunikationstechnik und vielem mehr.

Die mathematische Optimierung beschäftigt sich mit der Minimierung oder Maximierung einer Zielfunktion $f(x)$ unter Randbedingungen für die Variable $x$. Die formelle Schreibweise für diese Aufgabe lautet

$$ \begin{align} \min_x ~~~&f(x) \\ \text{subject to} ~~~&x \in D \end{align}$$

Dies codiert die Anweisungen, dass ein $x$ zu suchen sei, welches den Funktionswert $f(x)$ minimiert ($\min _x f(x)$). Dabei darf $x$ nur aus einer bestimmten Menge $D$ gewählt werden ($x\in D$), welche die die Anforderungen an die Optimierungsvariable $x$ formalisiert.

Beispiele

Das oben formulierte Problem inkludiert eine grosse Menge praxisrelevanter Aufgaben. Oft quantifiziert $f(x)$ Kosten, Materialaufwand, Zeitdauern, Unsicherheiten, Fehlerwahrscheinlichkeiten oder sonstige negative Leistungsmasse, deren Verminderung gewünscht ist. Die (oft hochdimensionale) Variable $x$ repräsentiert Entscheidungen mit direkten Auswirkungen auf die Leistungsmasse; etwa Investitionsentschiedungen, Produkteigenschaften, Belegungspläne, Experimenendesigns oder Sicherheitsgrenzwerte. Diese unterliegen nutzerdefinierten Forderungen, die z.B die Einhaltung bestimmter Standards formalisieren. Die nachfolgende Abbildung illustriert dies und die Tabelle listet beispielhafte Interpretationen.

Beispiele	$f(x)$	$x_1,x_2, …$	$D$
Aktienportfolio	- Erwarteter Gewinn	Investition in Aktie 1, 2, …	Kaufbeschränkungen
Tragwerksdesign	Materialverbrauch	Länge, Dicke Stabwerk	Tragfähigkeitsnachweis
Werkstattanordnung	Produktionsdauern	Anordnung Produktionsmittel 1, 2, …	Maschinennachbarschaften
Pharmazeutischer Test	Unsicherheit Signifikanzniveau	Tests vom Typ 1,2, …	Abhängigkeit Testtypen
Transportplanung	Zeitverbrauch	Abfolge Ortsanfahrten	Ladekapazität
Arbeitszeitplanung	Arbeitsbelastung	Aufgaben zu Zeitpunkten	Keine Doppelbelegungen

Tabelle mit Beispielen für Anwendungen der mathematische Optimierung. Der Term $f(x)$ ist die zu minimierende Zielfunktion, $x_1,x_2, …$ sind die Optimierungsvariablen, und $D$ sind die Randbedingungen an eine Lösung.

Aufgabenfelder

Viele praxisrelevante Aufgaben aus den Disziplinen Finanzwesen, Betriebswirtschaft, Logistik, Physik, Ingenieurwesen, Telekommunikation, Spieltheorie, Datenanalyse, … können als Optimierungsproblem $\min _x f(x), x\in D$ formuliert werden. Unabhängig von der konkreten Anwendung identifizieren wir drei Aufgabenklassen, in welche sich Aufgaben aus den obigen Disziplinen einordnen lassen:

Optimales Design

Die Optimierungsvariablen $x$ repräsentieren statische Designparameter eines Produktes. Sie sind unter Berücksichtigung eines auf Vorüberlegungen basierenden Modelles so zu wählen, dass das Produkt ein bestimmtes Leistungsmass $-f(x)$ maximiert und gewisse Eigenschaften gewährleistet bleiben.

In diese Aufgabenklasse fallen zum Beispiel Experimentendesign, Portfoliooptimierung, Transport- , Routing‑, und Logistikprobleme, die Optimierung Maschinen und Bauwerken und deren Anordnung.

Optimale Schätzung

Die Optimierungsvariable $x$ sind Parameter eines prädiktiven Modelles $g(x,z)$ mit unabhängiger Variable $z$. Das Modell soll Aussagen treffen darüber, welches Resultat $l$ eintritt in Abhängigkeit einer vorher getätigten Beobachtung $z$.

Der Zusammenhang zwischen $z$ und $l$ ist nachzubilden, wobei Datensätze $\{z_k,l_k\}_{k=1}^n$ beobachtet wurden und das Modell $g(x,z)$ so anzupassen ist, dass es der Datengrundlage möglichst wenig wiederspricht. In diese Aufgabenklasse fallen klassiche Regressionsprobleme der Parameterschätzung und des reverse Engineerings aber auch räumliche Statistik, Prädiktion, das Lernen von Korrelationsstrukturen, statistische Signaltrennung und Rekonstruktion. Diese Aufgaben treten z.B. bei komplizierten messtechnischen Problemen auf.

Optimales Control

Die Optimierungsvariable $x$ repäsentiert eine Abfolge von Steuerungsinputs in einem System, welches sich dynamisch und womöglich zufällig verhält. Dieser Input ist so zu wählen, dass die Diskrepanz $f(x)$ zwischen der vom System vollzogenen Entwicklung und einer präferierten Zielentwicklung minimal wird.

Dabei dürfen die Steuerungsgrössen $x$ auf einen bestimmten Bereich $D$ beschränkt werden. Probleme dieser Aufgabenklasse sind unter anderem sequentielle statistische Entscheidungsprobleme wie Verkehrsflussregulierungm Supply chain management, Presifindung für Finanzderivate, adaptive medizinische behandlung sowie die Aufgaben der klassischen Regelungstechnik.

Aussicht

Aufgaben aus sämtlichen obig genannten bereichen sind bereits erfolgreich als mathematisches Optimierungsproblem formuliert und gelöst worden. Die nachfolgende Auswahl umfasst simplifizierte Beispielprobleme, die dennoch ohne das entspechende Instrumentarium nicht trivial zu lösen sind. Dabei illustrieren Skizzen und kleine Beschreibungen das Problem, und eine kommentierte Formulierung als mathematisches Optimierungsproblem verdeutlicht die Zusammenhänge zwischen Echtweltproblematik und mathematischer Modellierungsebene. Wir benutzen dabei spezielle formelle Anordnungen von Zielfunktionen und Gleichungen und Ungleichungen, die sich durch lineare Programmierung, quadratische Programmierung, semidefinite Programmierung, und dynamische Programmierung zuverlässig lösen lassen.