Semi-infinite Optimierung

In der semi-infiniten Optimierung (englisch Semi-infinite programming SIP) geht es um Optimierungsprobleme mit einer endlichen Anzahl Entscheidungsvariablen und einer unendlichen Anzahl Nebenbedingungen, oder einer unendlichen Anzahl Entscheidungsvariablen bei endlicher Anzahl Nebenbedingungen.

Problemformulierung

Das Grundproblem lässt sich wie folgt formulieren

${\begin{aligned}{\text{minimiere}}&\quad f(x),x\in X\\{\text{unter Nebenbedingungen:}}&\quad g(x,y)\leq 0,\forall y\in Y\end{aligned}}$

Lösungsansätze

Lösen von Problemen mit unendlich vielen Nebenbedingungen per lokaler Reduktion

Für den Fall, dass das semiunendliche Problem eine unendliche Anzahl Nebenbedingungen, aber eine endliche Zahl Entscheidungsvariablen aufweist, kann das Problem zumindest lokal auf ein äquivalentes Problem mit endlicher Anzahl Nebenbedingungen reduziert werden.

Dieser in der Literatur als „lokale Reduktion“ bezeichnete Algorithmus sieht dafür folgende Schritte vor:

Initialisierung des Algorithmus:

• Wähle eine Untermenge von $Y_{0}\subset Y$, die durch eine endliche Anzahl Nebenbedinungen ausgedrückt werden kann
• Definiere $k:=0$

Kernalgorithmus:

• Berechne $x_{k}\in \arg \min _{x_{k}\in F_{k}}f(x)$
• Berechne $y_{k+1}\in \arg \max _{y\in Y_{k}}g(x^{k},y)$
• Erweitere $Y_{k+1}:=Y^{k}\cup \{y_{k+1}\}$
• Und bereite den Algorithmus auf die nächste Iteration vor: $k:=k+1$

Abbruchkriterium:

Falls $g(x_{k},y_{k+1})\leq 0$ hat der Algorithmus eine lokal äquivalente Formulierung des semiunendlichen Problems gefunden.

Weblinks

• semi-infinite Optimierung (Lexikon der Mathematik)