© Springer-Verlag GmbH Deutschland 2018
Oliver SteinGrundzüge der Nichtlinearen Optimierunghttps://doi.org/10.1007/978-3-662-55593-4_1

1. Einführung

Oliver Stein1 
(1)
Institute of Operations Research, Karlsruhe Institute of Technology, Karlrsuhe, Deutschland
 
1.1 Beispiele und Begriffe
1.2 Lösbarkeit
1.3 Rechenregeln und Umformungen
Literatur

Die endlichdimensionale kontinuierliche Optimierung behandelt die Minimierung oder Maximierung einer Zielfunktion in einer endlichen Anzahl kontinuierlicher Entscheidungsvariablen. Wichtige Anwendungen finden sich nicht nur bei linearen Modellen (wie in einfachen Modellen zur Gewinnmaximierung in Produktionsprogrammen oder bei Transportproblemen [24]), sondern auch bei diversen nichtlinearen Modellen aus Natur-, Ingenieur- und Wirtschaftswissenschaften. Dazu gehören geometrische Probleme, mechanische Probleme, Parameter-Fitting-Probleme, Schätzprobleme, Approximationsprobleme, Datenklassifikation und Sensitivitätsanalyse. Als Lösungswerkzeug benutzt man sie außerdem bei nichtkooperativen Spielen [35], in der robusten Optimierung [35] oder bei der Relaxierung diskreter und gemischt-ganzzahliger Optimierungsprobleme [32].

Das vorliegende einführende Kapitel motiviert in Abschn. 1.1 zunächst die grundlegende Terminologie und Notation von Optimierungsproblemen anhand diverser Beispiele und grenzt die endlichdimensionale glatte gegen die unendlichdimensionale und die nichtglatte Optimierung ab. Abschn. 1.2 widmet sich danach der Frage, unter welchen Voraussetzungen Optimierungsprobleme überhaupt lösbar sind (eine weitaus ausführlichere Darstellung von Lösbarkeitsfragen findet der interessierte Leser in [33]). Abschließend stellt Abschn. 1.3 einige Rechenregeln und Umformungen für Optimierungsprobleme bereit, die im Rahmen dieses Lehrbuchs eine Rolle spielen werden.

1.1 Beispiele und Begriffe

In der Optimierung vergleicht man verschiedene Alternativen bezüglich eines Zielkriteriums und sucht unter allen betrachteten Alternativen eine beste. Anhand des folgenden Beispiels eines nichtlinearen Optimierungsproblems in zwei Variablen, das sich mit Mitteln der Schulmathematik lösen lässt, führen wir zunächst einige grundlegende Begriffe ein.

1.1.1 Beispiel (Konservendose – glatte Optimierung)

Aus A Maßeinheiten (z. B. Quadratzentimeter) Blech sei eine Konservendose mit maximalem Volumen zu konstruieren. Die Dose sei als Zylinder mit Deckel und Boden modelliert, ist also durch zwei Angaben charakterisiert, nämlich ihren Radius r und ihre Höhe h. Die Dose besitzt dann das Volumen V(r, h) = πr2h und die Oberfläche 2πrh + 2πr2.

Das zu maximierende Zielkriterium ist hier also das Volumen V der Dose, und die zulässigen Alternativen sind die Paare $(r,h)\in\mathbb R^2$ in der durch die Nebenbedingungen beschriebenen Menge
$$ M\ =\ \{(r,h)\in\mathbb R^2|\ 2\pi rh + 2\pi r^2\le A,\ r,h\ge0\}. $$
Die strukturell besonders einfachen und auch in anderen Optimierungsmodellen häufig präsenten Nebenbedingungen r, h ≥ 0 heißen Nichtnegativitätsbedingungen .

Wie in diesem Beispiel lassen sich in Problemen der kontinuierlichen Optimierung die Alternativen stets geometrisch als „Punkte in einem Raum“ interpretieren, hier im zweidimensionalen euklidischen Raum $\mathbb R^2$. Da genau diese geometrische Entsprechung auf Optimalitätsbedingungen und numerische Verfahren führen wird, adressieren wir die Elemente von M im Folgenden nicht als zulässige Alternativen, sondern als zulässige Punkte . Die Menge M werden wir zulässige Menge nennen.

In allen Optimierungsproblemen ordnet das Zielkriterium jedem zulässigen Punkt einen Zahlenwert zu und ist aus mathematischer Sicht daher eine Funktion von M in die Menge $\mathbb R$ der reellen Zahlen. Diese Funktion nennen wir Zielfunktion. Im vorliegenden Beispiel ist dies die Volumenfunktion
$$ V:\ M\to\mathbb R,\ (r,h)\mapsto \pi r^2 h. $$
Die allgemeine Aufgabe, eine Funktion f über einer Menge M zu maximieren, schreiben wir als Optimierungsproblem in der Form
$$ P:\quad\max\,f(x)\quad\textnormal{ s.t. }\quad x\in M $$
auf. Das Kürzel s.t. steht dabei für das englische subject to (oder auch so that) und deutet in der Formulierung von P an, dass ab hier die Beschreibung der zulässigen Menge folgt. Ein Minimierungsproblem würde man analog in der Form
$$ P:\quad\min\,f(x)\quad\textnormal{ s.t. }\quad x\in M $$
schreiben. Wir werden später in der Tat sehen, dass es genügt, nur Minimierungsprobleme behandeln zu können.
Liegt eine explizite Beschreibung von M durch Restriktionen vor, so genügt es, im zugehörigen Optimierungsproblem P anstelle von M diese Restriktionen anzugeben. Das Optimierungsproblem zur Maximierung des Dosenvolumens lautet demnach
$$ P_{\textrm{Dose}}:\quad\max_{r,h}\,\pi r^2h\quad\textnormal{ s.t. }\quad 2\pi rh + 2\pi r^2\le A,\quad r,h\ge0. $$

Während in $P_{\textrm{Dose}}$ über die Werte von r und h eine Entscheidung getroffen werden soll, ist der Wert von A exogen vorgegeben. Wir nennen r und h daher Entscheidungsvariablen und A einen Parameter . Zur Übersichtlichkeit notiert man die Entscheidungsvariablen häufig wie in $P_{\textrm{Dose}}$ unterhalb der Optimierungsvorschrift „max“ oder „min“.

Ein Punkt $\skew2\bar x\in M$ heißt optimal für ein allgemeines Optimierungsproblem P, wenn kein Punkt x ∈ M einen besseren Zielfunktionswert besitzt. Bei Maximierungsproblemen bedeutet dies gerade, dass die Ungleichung $f(x)\le f(\skew2\bar x)$ für alle x ∈ M erfüllt ist, und bei Minimierungsproblemen kehrt sich diese Ungleichung um. Der zugehörige optimale Wert von P ist die Zahl $v=f(\skew2\bar x)$. Während ein Optimierungsproblem durchaus mehrere optimale Punkte besitzen kann, ist der optimale Wert immer eindeutig.

Häufig werden wir den optimalen Wert eines Maximierungsproblems auch in der Schreibweise
$$ v\ =\ \max_{x\in M}\,f(x) $$
angeben. Dabei ist das „max“ im obigen Optimierungsproblem P als die Aufgabe zu verstehen, f über M zu maximieren, während das „max“ im Optimalwert v eine Zahl bezeichnet.

Um nun einen optimalen Punkt und den optimalen Wert von $P_{\textrm{Dose}}$ zu bestimmen, gehen wir in diesem einführenden Beispiel etwas lax vor und bedienen uns unter anderem des aus der Schulmathematik bekannten Konzepts der Kurvendiskussion, das erst in Abschn.​ 2.​1 (in viel allgemeinerem Rahmen) behandelt wird.

Anschaulich ist zunächst klar, dass bei einer optimalen Wahl der Entscheidungsvariablen sowohl r > 0 als auch h > 0 gelten wird. Die Nichtnegativitätsbedingungen heißen dann nicht aktiv. Im Gegensatz dazu sollte die Ungleichung an die Größe der Dosenoberfläche
$$ 2\pi rh + 2\pi r^2\ \le\ A $$
aus geometrischen Überlegungen heraus in der Lösung mit Gleichheit erfüllt, also aktiv sein. Die entstehende Gleichung lässt sich im vorliegenden Fall sogar explizit nach einer Variablen auflösen, etwa zu
$$ h\ =\ \frac{A}{2\pi r}-r. $$
Für diese Punkte (r, h) kann man die Zielfunktion also genauso gut schreiben als
$$ V(r,h)\ =\ V\left(r,\frac{A}{2\pi r}-r\right)\ =\ \frac{A}2 r-\pi r^3. $$
Daher löst der optimale Radius des Ausgangsproblems auch das Problem
$$ \max_r\ \frac{A}2 r-\pi r^3 \quad\textnormal{ s.t. }\quad r>0. $$
Per Kurvendiskussion für die in Abb. 1.1 illustrierte Zielfunktion findet man als optimalen Radius nun
$$ \bar r\ =\ \sqrt{\frac{A}{6\pi}}, $$
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig1_HTML.png
Abb. 1.1

Dosenvolumen in Abhängigkeit vom Radius

woraus
$$ \bar h\ =\ \frac{A}{2\pi \bar r}-\bar r\ =\ \sqrt{\frac{3A}{2\pi}}-\sqrt{\frac{A}{6\pi}}\ =\ 2\sqrt{\frac{A}{6\pi}} $$
folgt. Der optimale Punkt des Ausgangsproblems ist daher eindeutig und lautet
$$ \begin{pmatrix}\bar r\\\bar h\end{pmatrix}\ =\ \sqrt{\frac{A}{6\pi}}\,\begin{pmatrix}1\\2\end{pmatrix}, $$
d. h., insbesondere sind Höhe und Durchmesser der Dose im optimalen Punkt identisch. Als optimalen Wert, also das mit dem optimalen Punkt realisierbare maximale Dosenvolumen, erhalten wir
$$ \max_{(r,h)\in M}\,V(r,h)\ =\ V(\bar r,\bar h)\ =\ \frac{A^{3/2}}{\sqrt{54\pi}}. $$
Während die Kurvendiskussion zur Bestimmung des optimalen Radius in Beispiel 1.1.1 sofort den global optimalen Radius geliefert hat, treten bei nichtlinearen Funktionen gerne auch andere Effekte auf, wie etwa der in Abb. 1.2 dargestellte. Hier liefert das Nullsetzen der ersten Ableitung von f die drei Lösungskandidaten x1, x2 und x3, wobei x2 wegen der positiven zweiten Ableitung $f''(x_2)$ nicht als Maximalpunkt infrage kommt. Wegen $f''(x_1)<0$ und $f''(x_3)<0$ sind als Ergebnis einer Kurvendiskussion aber sowohl x1 als auch x3 Kandidaten für Maximalpunkte von f. Allerdings ist x3 nur unter allen Punkten aus seiner „Nachbarschaft“ (also z. B. einem kleinen Intervall um x3) der beste Punkt, während x1 unter allen Punkten in $M=\mathbb R$ optimal ist.
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig2_HTML.png
Abb. 1.2

Ein globaler und ein lokaler Maximalpunkt

Diese wichtige Unterscheidung zwischen lokaler und globaler Optimalität hält die folgende Definition formal fest (Abb. 1.3). Sie konzentriert sich auf Minimierungsprobleme, während die Behandlung von Maximierungsproblemen im Anschluss diskutiert wird.
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig3_HTML.png
Abb. 1.3

Lokale und globale Minimalität

1.1.2 Definition (Minimalpunkte und Minimalwerte)

Gegeben seien eine Menge von zulässigen Punkten $M \subseteq \mathbb R^n$ und eine Zielfunktion $f:M\to\mathbb R$.

  1. a)
    $\skew2\bar x\in M$ heißt lokaler Minimalpunkt von f auf M, falls eine Umgebung U von $\skew2\bar x$ mit
    $$ \forall\ x \in U \cap M:\quad f(x) \geq f(\skew2\bar x) $$
    existiert.
     
  2. b)

    $\skew2\bar x\in M$ heißt globaler Minimalpunkt von f auf M, falls man in (a) $U = \mathbb R^n$ wählen kann.

     
  3. c)

    Ein lokaler oder globaler Minimalpunkt heißt strikt, falls in (a) bzw. (b) für $x\neq\skew2\bar x$ sogar die strikte Ungleichung > gilt.

     
  4. d)

    Zu jedem globalen Minimalpunkt $\skew2\bar x$ heißt $f(\skew2\bar x)\ (=v =\min_{x\in M}f(x)\,)$ globaler Minimalwert , und zu jedem lokalen Minimalpunkt $\skew2\bar x$ heißt $f(\skew2\bar x)$ lokaler Minimalwert.

     
Zur Definition von Minimalpunkten und -werten merken wir Folgendes an:

  • Damit die Forderung $f(x) \geq f(\skew2\bar x)$ sinnvoll ist, muss der Bildbereich von f geordnet sein. Zum Beispiel ist die Minimierung von $f:\mathbb R^n\to\mathbb R^2$ zunächst nicht sinnvoll. Allerdings befasst sich das Gebiet der Mehrzieloptimierung damit, wie man solche Probleme trotzdem behandeln kann (für eine kurze Einführung s. z. B. [24]).

  • Jeder globale Minimalpunkt ist auch lokaler Minimalpunkt.

  • Strikte globale Minimalpunkte sind eindeutig, und strikte lokale Minimalpunkte sind lokal eindeutig.

  • Lokale und globale Maximalpunkte sind analog definiert. Da die Maximalpunkte von f genau die Minimalpunkte von −f sind, reicht es, Minimierungsprobleme zu betrachten. Achtung: Dabei ändert sich allerdings das Vorzeichen des Optimalwerts, denn es gilt $\max f(x)=-\min(-f(x))$. Dies wird in Abb. 1.4 illustriert und in Übung 1.1.3 sowie etwas allgemeiner in Übung 1.3.1 bewiesen.

  • Wegen der ähnlichen Notation besteht eine Verwechslungsgefahr zwischen dem Minimalwert $\min_{x\in M}f(x)$ und der zugrunde liegenden Minimierungsaufgabe P (vgl. die Diskussion in Beispiel 1.1.1).

../images/439970_1_De_1_Chapter/439970_1_De_1_Fig4_HTML.png
Abb. 1.4

Maximierung von f durch Minimierung von −f

1.1.3 Übung

Gegeben seien eine Menge von zulässigen Punkten $M \subseteq \mathbb R^n$ und eine Zielfunktion $f:M\to\mathbb R$. Zeigen Sie:

  1. a)

    Die globalen Maximalpunkte von f auf M sind genau die globalen Minimalpunkte von −f auf M.

     
  2. b)
    Sofern f globale Maximalpunkte besitzt, gilt für den globalen Maximalwert
    $$ \max_{x\in M}\,f(x)\ =\ -\min_{x\in M}\,(-f(x)). $$
     

Per Definition 1.1.2 lassen sich lokale bzw. globale Minimalpunkte in den wenigsten Fällen berechnen. Stattdessen werden wir in Kap.​ 2 und 3 ableitungsbasierte Optimalitätsbedingungen und darauf aufbauende Lösungsverfahren entwickeln. Diese sind naturgemäß nicht anwendbar, wenn die definierenden Funktionen des betrachteten Optimierungsproblems nicht differenzierbar sind. Das folgende Beispiel zeigt allerdings, dass sich nichtdifferenzierbare Optimierungsprobleme in wichtigen Fällen in äquivalente differenzierbare Probleme umwandeln lassen.

1.1.4 Beispiel (Diskrete Approximation – glatte vs. nichtglatte Optimierung)

Gegeben seien Datenpunkte $(x_j,y_j)\in\mathbb R^2$, 1 ≤ j ≤ m. Gesucht ist eine Gerade, die diese Punkte „möglichst gut“ annähert. Setzt man eine Gerade der Form y = ax + b an, so ist also ein $(a,b)\in\mathbb R^2$ gesucht, das die Norm des Fehlervektors minimiert:
$$ \min_{a,b}\ \left\|\begin{pmatrix}ax_1 + b-y_1\\\vdots\\ax_m + b-y_m\end{pmatrix}\right\|. $$
Entscheidend ist dabei die Wahl der Norm. Beispielsweise entsteht für die euklidische Norm $\|\cdot\|_2$ das Problem
$$ \min_{a,b}\ \sqrt{\sum_{j=1}^m (ax_j + b-y_j)^2}. $$
Die Zielfunktion dieses Problems ist nicht überall differenzierbar, da die Funktion $\|\cdot\|_2$ im Nullpunkt nicht differenzierbar ist. Man spricht dann von einem nichtglatten Optimierungsproblem . Die meisten in diesem Lehrbuch vorgestellten Techniken werden sich allerdings auf glatte Optimierungsprobleme beziehen, bei denen mindestens erste Ableitungen der beteiligten Funktionen existieren . Dies ist keine zu starke Einschränkung, da sich etwa das obige Problem zu einem äquivalenten glatten Problem umformen lässt: Nach Übung 1.3.4 ändern sich die optimalen Punkte nicht, wenn man in der Zielfunktion die Wurzel weglässt. Die neue Zielfunktion ist dann überall differenzierbar. Mit der Setzung $r_j(a,b):=ax_j + b-y_j$, 1 ≤ j ≤ m, besitzt sie die Struktur $\sum_{j=1}^mr_j^2(a,b)$, und man spricht von einem Kleinste-Quadrate-Problem .
Für die Tschebyscheff-Norm $\|\cdot\|_\infty$ erhält man das nichtglatte unrestringierte Problem
$$ \min_{a,b}\ \max_{1\le j\le m}|ax_j + b-y_j|, $$
zu dem man durch einen anderen „Trick“ ein äquivalentes glattes restringiertes Problem formulieren kann, nämlich durch die sogenannte Epigraphumformulierung (Übung 1.3.5). Sie liefert zunächst das äquivalente Problem
$$ \min_{a,b,c}\ c \quad\textnormal{ s.t. }\quad \max_{1\le j\le m}|ax_j + b-y_j|\ \le\ c, $$
dessen nichtglatte Restriktion sich äquivalent erst zu
$$ |ax_j + b-y_j|\ \le\ c,\ 1\le j\le m, $$
und dann zu
$$\begin{aligned}ax_j + b-y_j \le \,& c,\ 1\le j\le m,\\ -(ax_j + b-y_j) \le \,& c,\ 1\le j\le m,\end{aligned}$$
umformulieren lässt. Man erhält insgesamt also ein lineares Optimierungsproblem mit 2m Restriktionen.

Dass endlichdimensionale Optimierungsprobleme auch „unendliche Aspekte“ besitzen können, zeigt das nächste Beispiel. Dort treten im Gegensatz zu Beispiel 1.1.1 nicht endlich viele (nämlich drei), sondern unendlich viele Ungleichungsrestriktionen auf, und dies in natürlicher Weise.

Wir folgen dort und im Folgenden außerdem einer in der mathematischen Literatur üblichen Konstruktion für Verneinungen und benutzen beispielsweise den künstlichen Begriff „nichtleer“ anstelle von „nicht leer“, damit klar ist, worauf das „nicht“ sich bezieht.

1.1.5 Beispiel (Kontinuierliche Approximation – semi-infinite Optimierung)

Gegeben seien eine nichtleere und kompakte Menge $Z\subseteq\mathbb R^m$, eine glatte Funktion $f:Z\to\mathbb R$ sowie eine Familie glatter Funktionen a(p, ·) mit Scharparameter $p\in P\subseteq\mathbb R^n$ (z. B. für m = 1 Polynome $a(p,z)=\sum_{j=0}^{n-1} p_j z^j$ vom Höchstgrad n − 1). Gesucht ist die beste Approximation an f auf Z durch eine Funktion a(p, ·) in der Tschebyscheff-Norm. Eine Formulierung als Optimierungsproblem lautet
$$ \min_{p\in\mathbb R^n}\ \underbrace{\|a(p,\cdot)-f(\cdot)\|_{\infty,Z}}_{\max_{z\in Z}\,|a(p,z)-f(z)|} \quad\textnormal{ s.t. }\quad p\in P. $$
Per Epigraphumformulierung erhält man das äquivalente Optimierungsproblem
$$ \min_{(p,q)\in \mathbb R^n\times\mathbb R}\ q\quad\textnormal{ s.t. }\quad p\in P,\quad \pm(a(p,z)-f(z))\ \le\ q\quad\forall\ z\in Z. $$
In diesem Problem an eine endlichdimensionale Entscheidungsvariable liegen unendlich viele Ungleichungsrestriktionen vor. Solche Probleme heißen semi-infinit (für Details s. z. B. [30]).

Das abschließende Beispiel dieses Abschnitts illustriert den Fall der unendlichdimensionalen Optimierung, den dieses Lehrbuch nicht thematisieren wird, obwohl sich einige Techniken vom endlichdimensionalen Fall auf ihn übertragen lassen (für Details s. z. B. [19]). Das folgende von Johann Bernoulli im Jahre 1696 gestellte Optimierungsproblem gilt als wesentlicher Ausgangspunkt zur Entwicklung der gesamten Analysis.

1.1.6 Beispiel (Brachistochrone – Variationsrechnung, infinite Optimierung)

Gegeben seien zwei Punkte A und B in einer senkrecht stehenden Ebene mit B seitlich unterhalb von A. Gesucht ist eine Kurve durch A und B, so dass ein sich unter dem Einfluss der Gravitation entlang dieser Kurve bewegender Massenpunkt den Weg von A nach B in kürzestmöglicher Zeit zurücklegt.

Legt man A wie in Abb. 1.5 in den Koordinatenursprung, beschreibt die Kurve durch die Funktionsvorschrift y = f(x) und ordnet bei nach unten zeigender y-Achse dem Punkt B die Koordinaten (a, b) zu, dann liefern physikalische Gesetze für die Durchlaufzeit der Kurve den Wert
$$ \int_0^a\frac{\sqrt{1 + (f'(x))^2}}{\sqrt{2gf(x)}}\,dx, $$
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig5_HTML.png
Abb. 1.5

Problem der Brachistochrone

wobei g die Gravitationskonstante bezeichnet. Das zugehörige Minimierungsproblem lautet demnach
$$ \min_f\ \int_0^a\frac{\sqrt{1 + (f'(x))^2}}{\sqrt{2g\,f(x)}}\,dx\quad\textnormal{ s.t. }\quad f(0)=0,\ f(a)=b. $$
Die Entscheidungsvariable f stammt dabei etwa aus dem Raum der differenzierbaren Funktionen, also einem unendlichdimensionalen Raum. Man spricht daher von unendlichdimensionaler Optimierung.

1.2 Lösbarkeit

Ob ein Optimierungsproblem überhaupt optimale Punkte besitzt, liegt nicht immer auf der Hand und muss bei vielen Lösungsverfahren vorab vom Anwender selbst geprüft werden. Eine ausführliche Diskussion dieser Problematik findet sich in [33], während wir hier nur auf die wesentlichen Punkte eingehen.

Ohne irgendwelche Voraussetzungen an die Menge $M\subseteq\mathbb R^n$ und die Funktion $f:M\to\mathbb R$ lässt sich jedenfalls jedem Minimierungsproblem
$$ P:\quad \min\,f(x) \quad\textnormal{ s.t. }\quad x \in M $$
ein „verallgemeinerter Minimalwert“ zuordnen, nämlich das Infimum von f auf M. Um es formal einzuführen, bezeichnen wir $\alpha \in \mathbb R$ als untere Schranke für f auf M, falls
$$ \forall\ x \in M:\quad \alpha\leq f(x) $$
gilt. Das Infimum von f auf M ist die größte untere Schranke von f auf M, es gilt also $v = \inf_{x \in M}\,f(x)$, falls

  • v ≤ f(x) für alle x ∈ M gilt (d. h., v ist selbst untere Schranke von f auf M) und

  • α ≤ v für alle unteren Schranken α von f auf M gilt.

Analog wird das Supremum $\sup_{x\in M}f(x)$ von f auf M als kleinste obere Schranke definiert.

1.2.1 Beispiel

Es gilt $\ \inf_{x\in\mathbb R}\,(x-5)^2=0\ $ und $\ \inf_{x\in\mathbb R}\,e^x=0$.

Falls f auf M nicht nach unten beschränkt ist, setzt man formal
$$ \inf_{x \in M} f(x)\ =\ -\infty, $$
und für das Infimum über die leere Menge definiert man formal
$$ \inf_{x \in \emptyset} f(x)\ =\ + \infty $$
(wobei die Gestalt von f dann keine Rolle spielt).

1.2.2 Beispiel

Es gilt $\ \inf_{x\in\mathbb R}\,(x-5)=-\infty\ $ und $\ \inf_{x\in\emptyset}\,(x-5)= + \infty$.

Der „verallgemeinerte Minimalwert“ $\inf_{x \in M} f(x)$ von P ist also stets ein Element der erweiterten reellen Zahlen $\overline{\mathbb R}=\mathbb R\cup\{\pm\infty\}$. In der Analysis wird gezeigt (z. B. [17]), dass das so definierte Infimum ohne Voraussetzungen an f und M stets existiert und eindeutig bestimmt ist. Außerdem wird dort eine Charakterisierung von Infima bewiesen, die wir nachfolgend benutzen werden: Das Infimum einer nichtleeren Menge reeller Zahlen ist genau diejenige ihrer Unterschranken, die sich durch Elemente der Menge beliebig genau approximieren lässt. Für die hier betrachteten Infima von Funktionen auf Mengen bedeutet dies, dass für $M\neq\emptyset$ genau dann $v=\inf_{x\in M}\,f(x)$ gilt, wenn v ≤ f(x) für alle x ∈ M gilt und wenn eine Folge (xk) ⊆ M mit $v=\lim_k f(x^k)$ existiert. Dabei schreiben wir hier und im Folgenden kurz (xk) für eine Folge $(x^k)_{k\in\mathbb N}$ sowie limk für $\lim_{k\to\infty}$.

1.2.3 Definition (Lösbarkeit)

Das Minimierungsproblem P heißt lösbar , falls ein $\skew2\bar x\in M$ mit $\inf_{x\in M}\,f(x)=f(\skew2\bar x)$ existiert.

Lösbarkeit von P bedeutet also, dass das Infimum von f auf M als Zielfunktionswert eines zulässigen Punkts realisiert werden kann, dass also das Infimum angenommen wird. Um anzudeuten, dass das Infimum angenommen wird, schreiben wir $\,\min_{x \in M}f(x)\,$ anstelle von $\,\inf_{x \in M}f(x)$.

1.2.4 Beispiel

Es gilt $\ 0=\min_{x\in\mathbb R}\,(x-5)^2=(\skew2\bar x-5)^2\ $ mit $\skew2\bar x=5$, aber es gibt kein $\skew2\bar x\in\mathbb R$ mit $\ 0=\inf_{x\in\mathbb R}\,e^x=e^{\skew2\bar x}$.

Der folgende Satz besagt (wenig überraschend), dass man zur Lösbarkeit genauso gut die Existenz eines globalen Minimalpunkts fordern kann (zum Beweis s. [33]).

1.2.5 Satz

Das Minimierungsproblem P ist genau dann lösbar, wenn es einen globalen Minimalpunkt besitzt.

Es gibt genau drei Gründe dafür, dass P unlösbar sein kann (dass es keine weiteren Gründe gibt, wird in [33] bewiesen):

  • Es gilt $\inf_{x\in M}f(x)= + \infty$.

    Dies entspricht per Definition dem trivial erscheinenden Fall $M=\emptyset$, ist aber nicht immer leicht zu erkennen. Wenn etwa in Beispiel 1.1.1 (z. B. aus Marketinggründen) die zusätzliche Restriktion r ≥ 1 eingeführt wird, dann besitzt $P_{\textrm{Dose}}$ im Fall A < 2π keine zulässigen Punkte. Hinreichende Bedingungen für die Lösbarkeit von P werden natürlich stets $M\neq\emptyset$ fordern.

  • Es gilt $\inf_{x\in M}f(x)=-\infty$.

    Bei stetiger Zielfunktion f muss M in diesem Fall unbeschränkt sein. Beispielsweise ist die Menge der zulässigen Punkte des Optimierungsproblems $P_{\textrm{Dose}}$ aus Beispiel 1.1.1 unbeschränkt (Übung 1.2.7). Dass $P_{\textrm{Dose}}$ trotzdem lösbar ist, zeigt andererseits, dass eine unbeschränkte Menge nicht notwendigerweise die Lösbarkeit verhindert. Als hinreichende Bedingung für Lösbarkeit bietet es sich trotzdem an, M als beschränkt vorauszusetzen. Man fordert also, dass sich ein Radius R > 0 finden lässt, so dass die Kugel um den Nullpunkt mit Radius R die Menge M umschließt:
    $$ \exists \ R &gt; 0 \ \forall \ x \in M:\quad \Vert x \Vert \leq R\ \text{ (die Wahl der Norm ist dabei egal)}. $$

  • Ein endliches Infimum $\inf_{x\in M}f(x)$ wird nicht angenommen.

    Grund dafür kann wiederum eine unbeschränkte Menge M sein, etwa bei der Funktion f(x) = ex auf der Menge $M=\mathbb R$. Aber auch für beschränkte Mengen M ist dieser Effekt möglich, etwa wenn Teile des Rands nicht zu M gehören, wie für f(x) = x und M = (0, 1]. Hier gibt es zu jedem Lösungskandidaten x ∈ M eine Verbesserungsmöglichkeit (Abb. 1.6).

    Als Gegenmittel kann man M als abgeschlossen voraussetzen, d. h., für alle Folgen (xk) ⊆ M mit $\lim_k x^k=x^\star$ gelte $x^\star\in M$ (z. B. ist M = (0, 1] wegen (1/k) ⊆ M und $\lim_k(1/k)= 0 \notin M$ nicht abgeschlossen). Falls M durch endlich viele Ungleichungen und Gleichungen beschrieben ist, d. h., falls
    $$ M\ =\ \{x\in\mathbb R^n|\ g_i(x)\le0,\ i\in I,\ h_j(x)=0,\ j\in J\} $$
    mit endlichen Indexmengen I und J gilt, dann ist die Stetigkeit der Funktionen $g_i:\mathbb R^n\to\mathbb R$, i ∈ I, und $h_j:\mathbb R^n\to\mathbb R$, j ∈ J, hinreichend für die Abgeschlossenheit von M (Übung 1.2.11). Wenn M gleichzeitig beschränkt und abgeschlossen ist, heißt M auch kompakt .
    Schließlich ist es möglich, dass ein endliches Infimum selbst auf einer nichtleeren und kompakten Menge M nicht angenommen wird, nämlich wenn f Sprungstellen besitzt. Zum Beispiel besitzt die Funktion
    $$ f(x)\ =\ \left\lbrace \begin{array}{l} 1,\quad x\leq 0 \\ x,\quad x &gt; 0 \end{array} \right. $$
    keinen globalen Minimalpunkt auf der nichtleeren und kompakten Menge M = [−1, 1], denn wieder gibt es zu jedem Lösungskandidaten eine Verbesserungsmöglichkeit (Abb. 1.7). Als Gegenmittel kann man f als stetig voraussetzen.
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig6_HTML.png
Abb. 1.6

Unlösbarkeit wegen fehlender Abgeschlossenheit von M

../images/439970_1_De_1_Chapter/439970_1_De_1_Fig7_HTML.png
Abb. 1.7

Unlösbarkeit wegen Sprungstelle von f

Der folgende grundlegende Satz zur Existenz von Minimal- und Maximalpunkten zeigt, dass unter den oben motivierten „Mitteln gegen Unlösbarkeit“ tatsächlich stets optimale Punkte existieren. Eine Version des Satzes, die unter schwächeren Voraussetzungen an f noch die Existenz von Minimalpunkten (aber nicht von Maximalpunkten) garantiert, findet sich in [35].

1.2.6 Satz (Satz von Weierstraß)

Die Menge $M \subseteq \mathbb R^n$ sei nichtleer und kompakt, und die Funktion $f:M\to\mathbb R$ sei stetig. Dann besitzt f auf M (mindestens) einen globalen Minimalpunkt und einen globalen Maximalpunkt.

Beweis.

Es sei $v = \inf_{x \in M}f(x)$ . Wegen $M\neq\emptyset$ gilt $v&lt; + \infty$. Zu zeigen ist die Existenz eines $\skew2\bar x$ in M mit $v = f(\bar x).$ Da v Infimum ist, existiert eine Folge (xk) ⊆ M mit $\lim_k f(x^k) = v$. In der Analysis wird bewiesen (im Satz von Bolzano-Weierstraß; z. B. [18]), dass jede in einer kompakten Menge M liegende Folge (xk) eine in M konvergente Teilfolge besitzt. Um nicht eine mühsame Teilfolgennotation benutzen zu müssen, wählen wir unsere Folge (xk) direkt als eine solche konvergente Folge, es existiert also ein $x^\star \in M$ mit $\lim_k x^k = x^\star$. Aufgrund der Stetigkeit von f auf M gilt nun
$$ f(x^\star)\ =\ f\left(\lim_k\, x^k\right)\ =\ \lim_k f(x^k)\ =\ v, $$
man kann also $\skew2\bar x:=x^\star$ wählen. Der Beweis zur Existenz eines globales Maximalpunkts verläuft analog.

Obwohl Satz 1.2.6 einerseits viele praktische Anwendungen besitzt, sind seine Voraussetzungen andererseits selbst bei manchen einfachen lösbaren Problemen verletzt, beispielsweise beim Problems $P_{\textrm{Dose}}$ aus Beispiel 1.1.1.

1.2.7 Übung

Zeigen Sie, dass die Menge der zulässigen Punkte des Optimierungsproblems $P_{\textrm{Dose}}$ aus Beispiel 1.1.1 zwar nichtleer und abgeschlossen, aber unbeschränkt ist.

Für Probleme ohne Nebenbedingungen, sogenannte unrestringierte Probleme, gilt $M = \mathbb R^n$ (etwa in Beispiel 1.1.4). Auch dann ist M zwar nichtleer und abgeschlossen, aber nicht beschränkt. Daher ist Satz 1.2.6 auf kein unrestringiertes Problem anwendbar.

Um den Satz von Weierstraß für Probleme mit unbeschränkter Menge M anwendbar zu machen, bedient man sich eines Tricks und betrachtet untere Niveaumengen (lower level sets) von f. In deren sowie einigen späteren Definitionen werden wir den Definitionsbereich von f nicht mit M, sondern mit X bezeichnen, da er nicht unbedingt die zulässige Menge eines Optimierungsproblems sein muss.

1.2.8 Definition (Untere Niveaumenge)

Für $X\subseteq\mathbb R^n$, $f:X\to\mathbb R$ und $\alpha \in\mathbb R$ heißt
$$ \textrm{lev}_\le^\alpha(f,X)\ =\ \{x\in X|\ f(x)\le\alpha\} $$
untere Niveaumenge von f auf X zum Niveau α . Im Fall $X=\mathbb R^n$ schreiben wir auch kurz
$$ f_{\le}^\alpha\ :=\ \textrm{lev}_\le^\alpha(f,\mathbb R^n)\quad (\,=\ \{x\in\mathbb R^n|\ f(x)\le\alpha\}\,). $$

1.2.9 Beispiel

Für f(x) = x2 gilt $f_{\le}^1 = \left[-1,1\right],\ f_{\le}^0 = \left\lbrace 0 \right\rbrace$ und $f_{\le}^{-1} = \emptyset$ (Abb. 1.8), und für $f(x) = x_1^2 + x_2^2$ gilt $f_{\le}^1 = \left\lbrace x \in \mathbb R^2 \vert\ x_1^2 + x_2^2 \leq 1 \right\rbrace$ (die Einheitskreisscheibe), $f_{\le}^0 = \left\lbrace 0 \right\rbrace$ sowie $f_{\le}^{-1} = \emptyset$ (Abb. 1.9).
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig8_HTML.png
Abb. 1.8

Untere Niveaumenge $f_{\le}^1$ von f(x) = x2 auf $\mathbb R$

../images/439970_1_De_1_Chapter/439970_1_De_1_Fig9_HTML.png
Abb. 1.9

Untere Niveaumenge $f_{\le}^1$ von $f(x)=x_1^2 + x_2^2$ auf $\mathbb R^2$

1.2.10 Übung

Für eine abgeschlossene Menge $X\subseteq\mathbb R^n$ sei die Funktion $f:X\to\mathbb R$ stetig. Zeigen Sie, dass dann die Mengen $\textrm{lev}_{\le}^\alpha(f,X)$ für alle $\alpha\in\mathbb R$ abgeschlossen sind.

1.2.11 Übung

Für eine abgeschlossene Menge $X\subseteq\mathbb R^n$ und endliche Indexmengen I und J seien die Funktionen $g_i:X\to\mathbb R$, i ∈ I, und $h_j:X\to\mathbb R$, j ∈ J, stetig. Zeigen Sie, dass dann die Menge
$$ M\ =\ \{x\in X|\ g_i(x)\le0,\ i\in I,\ h_j(x)=0,\ j\in J\} $$
abgeschlossen ist.
Für das folgenden Ergebnis führen wir die Menge der globalen Minimalpunkte
$$ S\ =\ \{\skew2\bar x\in M|\ \forall\,x\in M:\ f(x)\ge f(\skew2\bar x)\} $$
von P ein. Die Lösbarkeit von P lässt sich dann auch durch die Bedingung $S\neq\emptyset$ ausdrücken (in [33] werden aber noch interessantere Eigenschaften der Menge S gezeigt).

1.2.12 Lemma

Für ein $\alpha \in \mathbb R$ sei $\textrm{lev}_\le^\alpha(f,M)\neq \emptyset$. Dann gilt $S \subseteq\textrm{lev}_\le^\alpha(f,M)$.

Beweis.

Wegen $\textrm{lev}_\le^\alpha(f,M)\neq \emptyset$ gibt es einen Punkt $\widetilde{x}$ in M mit $f(\widetilde{x}) \leq \alpha$. Nun sei $\skew2\bar x$ ein beliebiger globaler Minimalpunkt von P. Dann gilt $\skew2\bar x \in M$ und $f(\skew2\bar x) \leq f(\widetilde{x}) \leq \alpha$, also $\skew2\bar x \in \textrm{lev}_\le^\alpha(f,M)$.

Das Konzept der unteren Niveaumengen erlaubt es, in einer hinreichenden Bedingung zur Lösbarkeit von P das Zusammenspiel der Eigenschaften der Zielfunktion f und der zulässigen Menge M zu berücksichtigen.

1.2.13 Satz (Verschärfter Satz von Weierstraß)

Für eine (nicht notwendigerweise beschränkte oder abgeschlossene) Menge $M \subseteq \mathbb R^n$ sei $f:M\to\mathbb R$ stetig, und mit einem $\alpha \in \mathbb R$ sei $\textrm{lev}_\le^\alpha(f,M)$ nichtleer und kompakt. Dann besitzt f auf M (mindestens) einen globalen Minimalpunkt.

Beweis.

Wegen Lemma 1.2.12 besitzen P und das Hilfsproblem
$$ \widetilde{P}:\quad \min\, f(x) \quad\textnormal{ s.t. }\quad x \in \textrm{lev}_\le^\alpha(f,M) $$
dieselben Optimalpunkte und denselben Optimalwert. $\widetilde{P}$ erfüllt aber die Voraussetzungen von Satz 1.2.6, so dass die Behauptung folgt.

1.2.14 Übung

Zeigen Sie, dass die Voraussetzungen von Satz 1.2.13 schwächer sind als die von Satz 1.2.6, dass sie also unter den Voraussetzungen von Satz 1.2.6 stets erfüllbar sind.

Die Verschärfung von Satz 1.2.13 gegenüber Satz 1.2.6 bezieht sich darauf, dass die uns interessierende Aussage des Satzes von Weierstraß, nämlich die Existenz eines globalen Minimalpunkts, auch unter der schwächeren Voraussetzung von Satz 1.2.13 folgt. Da nun allerdings keine Aussage mehr zur Existenz eines globalen Maximalpunkts von P getroffen werden kann, sind die beiden Sätze genau genommen unabhängig voneinander.

1.2.15 Beispiel

Betrachtet werde das Problem
$$ P:\quad \min\, e^x \quad\textnormal{ s.t. }\quad x \geq 0 $$
(Abb. 1.10).
../images/439970_1_De_1_Chapter/439970_1_De_1_Fig10_HTML.png
Abb. 1.10

ex mit x ≥ 0

Hier ist $M = \lbrace x \in \mathbb R \vert\, x \geq 0 \rbrace$ unbeschränkt, Satz 1.2.6 also nicht anwendbar. Aber beispielsweise mit α = e ist
$$ \textrm{lev}_{\le}^e(f,M)\ =\ \lbrace x \in M \vert\ e^x \leq e \rbrace\ =\ \lbrace x\ge0 \vert\ x \leq 1 \rbrace\ =\ \left[ 0,1 \right] $$
nichtleer und kompakt. Folglich ist Satz 1.2.13 anwendbar und P daher lösbar.

1.2.16 Übung

Zeigen Sie die Lösbarkeit des Optimierungsproblems $P_{\textrm{Dose}}$ aus Beispiel 1.1.1 mit Hilfe von Satz 1.2.13.

1.2.17 Korollar (Verschärfter Satz von Weierstraß für unrestringierte Probleme)

Die Funktion $f:\mathbb R^n\to\mathbb R$ sei stetig, und mit einem $\alpha \in \mathbb R$ sei $f_{\le}^\alpha$ nichtleer und kompakt. Dann besitzt f auf $\mathbb R^n$ (mindestens) einen globalen Minimalpunkt.

Beweis.

Satz 1.2.13 mit $M = \mathbb R^n$.

1.2.18 Beispiel

Für f(x) = (x − 5)2 ist $f_{\le}^1 = \left[ 4,6\right]$ nichtleer und kompakt, also besitzt f nach Korollar 1.2.17 einen globalen Minimalpunkt auf $\mathbb R$.

1.2.19 Beispiel

Mit f(x) = ex gilt $f_{\le}^\alpha=\emptyset$ für alle α ≤ 0 sowie $f_{\le}^\alpha = \left( -\infty, \log(\alpha)\right]$ für alle α > 0. Daher ist $f_{\le}^\alpha$ für kein α nichtleer und kompakt, Korollar 1.2.17 also nicht anwendbar. f besitzt auch tatsächlich keinen globalen Minimalpunkt auf $\mathbb R$.

1.2.20 Beispiel

Für f(x) = sin(x) ist Korollar 1.2.17 ebenfalls nicht anwendbar, da alle Mengen $f_{\le}^\alpha$ mit $\alpha\in\mathbb R$ unbeschränkt oder leer sind. f besitzt aber trotzdem globale Minimalpunkte auf $\mathbb R$.

Im Folgenden geben wir ein einfaches Kriterium an, aus dem die Kompaktheit von $\textrm{lev}_\le^\alpha(f,X)$ mit jedem $\alpha\in\mathbb R$ folgt. Dadurch kann man die Voraussetzungen von Satz 1.2.13 und Korollar 1.2.17 garantieren, ohne ein explizites Niveau α angeben zu müssen.

1.2.21 Definition (Koerzivität)

Gegeben seien eine abgeschlossene Menge $X\subseteq\mathbb R^n$ und eine Funktion $f:X\to\mathbb R$. Falls für alle Folgen (xk) ⊆ X mit $\lim_k\,\|x^k\|= + \infty$ auch
$$ \lim_k f(x^k)\ =\ + \infty $$
gilt, dann heißt f koerziv auf X.

1.2.22 Beispiel

f(x) = (x − 5)2 ist koerziv auf $\mathbb R$.

1.2.23 Beispiel

f(x) = ex ist nicht koerziv auf $X=\mathbb R$, wohl aber auf der Menge $X=\{x\in\mathbb R|\ x\ge0\}$.

1.2.24 Übung

Gegeben sei die quadratische Funktion $q(x)=\frac12x^\intercal Ax + b^\intercal x$ mit einer symmetrischen (n, n)-Matrix A (d. h., es gilt $A=A^\intercal$) und $b\in\mathbb R^n$. Zeigen Sie, dass q genau dann koerziv auf $\mathbb R^n$ ist, wenn A positiv definit ist (d. h. wenn $d^\intercal A d&gt;0$ für alle $d\in\mathbb R^n\setminus\{0\}$ gilt; Details zu positiv definiten Matrizen finden sich in Abschn.​ 2.​1.​4).

1.2.25 Beispiel

Auf kompakten Mengen X ist jede Funktion f trivialerweise koerziv.

Zur Formulierung von Beispiel 1.2.25 sei angemerkt, dass wir den Begriff „trivial “ in diesem Lehrbuch sparsam benutzen. Er bezeichnet nicht Aussagen, die aus Sicht des Autors „leicht“ zu beweisen sind, sondern solche, die wegen einer logischen Trivialität gelten. Zum Beispiel ist die Aussage „Alle grünen Kühe können fliegen“ trivialerweise wahr, denn um sie zu widerlegen, müsste man eine grüne Kuh finden, die nicht fliegen kann. Da man aber schon keine grüne Kuh findet, braucht man nicht noch darüber hinaus nach einer grünen Kuh zu suchen, die nicht fliegen kann. Damit lässt die Aussage sich aus einem trivialen Grund nicht widerlegen und ist folglich wahr. In Beispiel 1.2.25 lautet die analoge Argumentation, dass in einer kompakten Menge X keine einzige Folge (xk) mit $\lim_k\,\|x^k\|\to + \infty$ liegt. Um zu zeigen, dass f nicht koerziv ist, müsste aber eine solche Folge existieren und außerdem noch $\lim_k f(x^k) = + \infty$ erfüllen. Letzteres ist aber irrelevant, weil schon die Existenz der Folge nicht vorliegt. Folglich ist f auf X aus einem trivialen Grund koerziv.

Im Satz von Weierstraß können wir nun im Sinne der folgenden beiden Resultate die Beschränktheit von M durch die Koerzivität von f auf M ersetzen. Beweise dazu finden sich beispielsweise in [33].

1.2.26 Lemma

Die Funktion $f:X\to\mathbb R$ sei stetig und koerziv auf der (nicht notwendigerweise beschränkten) abgeschlossenen Menge $X\subseteq\mathbb R^n$. Dann ist die Menge $\textrm{lev}_\le^\alpha(f,X)$ für jedes Niveau $\alpha\in\mathbb R$ kompakt.

Hieraus und aus dem Satz von Weierstraß folgt das zweite Resultat, das insbesondere ein häufig einsetzbares Kriterium zum Nachweis der Lösbarkeit unrestringierter Optimierungsprobleme liefert.

1.2.27 Korollar

Es sei M nichtleer und abgeschlossen, aber nicht notwendigerweise beschränkt. Ferner sei die Funktion $f:M\to\mathbb R$ stetig und koerziv auf M. Dann besitzt f auf M (mindestens) einen globalen Minimalpunkt.

1.3 Rechenregeln und Umformungen

Dieser Abschnitt führt eine Reihe von Rechenregeln und äquivalenten Umformungen von Optimierungsproblemen auf, die im Rahmen dieses Lehrbuchs von Interesse sind. Die Existenz aller auftretenden Optimalpunkte und -werte wird in diesem Abschnitt ohne weitere Erwähnung vorausgesetzt und muss bei Anwendung der Resultate zunächst zum Beispiel mit den Techniken aus Abschn. 1.2 garantiert werden. Die Übertragung der Resultate zu Optimalwerten auf Fälle von nicht angenommenen Infima und Suprema ist dem Leser als weitere Übung überlassen.

1.3.1 Übung (Skalare Vielfache und Summen)

Gegeben seien $M\subseteq\mathbb R^n$ und $f,g:M\to\mathbb R.$ Dann gilt:

  1. a)

    $ \forall \alpha \geq 0,\ \beta \in \mathbb R:\ \min_{x \in M}\,(\alpha f(x) + \beta)\ =\ \alpha\, (\min_{x \in M}\,f(x)) + \beta$.

     
  2. b)

    $ \forall \alpha &lt; 0,\ \beta \in \mathbb R:\ \min_{x \in M}\,(\alpha f(x) + \beta)\ =\ \alpha\, (\max_{x \in M}\,f(x)) + \beta$.

     
  3. c)

    $ \min_{x \in M}\,(f(x) + g(x))\ \geq\ \min_{x \in M}\,f(x) + \min_{x \in M}\,g(x)$.

     
  4. d)

    In (c) kann die strikte Ungleichung > auftreten.

     
In (a) und (b) stimmen außerdem jeweils die lokalen bzw. globalen Optimalpunkte der Optimierungsprobleme überein.

1.3.2 Übung (Separable Zielfunktion auf kartesischem Produkt)

Es seien $X\subseteq\mathbb R^n$, $Y\subseteq\mathbb R^m$, $f:X\to\mathbb R$ und $g:Y\to\mathbb R$. Dann gilt
$$ \min_{(x,y) \in X \times Y}\,(f(x) + g(y))\ =\ \min_{x \in X}\,f(x) + \min_{y \in Y}\,g(y). $$

1.3.3 Übung (Vertauschung von Minima und Maxima)

Es seien $X \subseteq \mathbb R^n$, $Y \subseteq \mathbb R^m$, M = X × Y und $f:M\to\mathbb R$ gegeben. Dann gilt:

  1. a)

    $ \min_{(x,y)\in M}\,f(x,y)\ =\ \min_{x \in X} \min_{y \in Y}\,f(x,y)\ =\ \min_{y \in Y} \min_{x \in X}\, f(x,y).$

     
  2. b)

    $ \max_{(x,y)\in M}\,f(x,y)\ =\ \max_{x \in X} \max_{y \in Y}\,f(x,y)\ =\ \max_{y \in Y} \max_{x \in X}\, f(x,y).$

     
  3. c)

    $ \min_{x \in X} \max_{y \in Y}\, f(x,y)\ \geq\ \max_{y \in Y} \min_{x \in X}\, f(x,y).$

     
  4. d)

    In (c) kann die strikte Ungleichung > auftreten.

     

1.3.4 Übung (Monotone Transformation)

Zu $M\subseteq\mathbb R^n$ und einer Funktion f : M → Y mit $Y\subseteq\mathbb R$ sei $\psi:Y\to\mathbb R$ eine streng monoton wachsende Funktion. Dann gilt
$$ \min_{x \in M}\,\psi(f(x))\ =\ \psi\,(\min_{x \in M}\,f(x)), $$
und die lokalen bzw. globalen Minimalpunkte stimmen überein.

1.3.5 Übung (Epigraphumformulierung)

Gegeben seien $M\subseteq\mathbb R^n$ und eine Funktion $f:M\to\mathbb R$. Dann sind die Probleme
$$ P:\qquad \min_{x \in \mathbb R^n}\, f(x) \quad\textnormal{ s.t. }\quad x \in M $$
und
$$ P_\textrm{epi}:\qquad \min_{(x,\alpha) \in \mathbb R^n \times \mathbb R}\,\alpha \quad\textnormal{ s.t. }\quad f(x)\le\alpha,\quad x \in M $$
in folgendem Sinne äquivalent:
  1. a)

    Für jeden lokalen bzw. globalen Minimalpunkt $x^\star$ von P ist $(x^\star,f(x^\star))$ lokaler bzw. globaler Minimalpunkt von $P_\textrm{epi}$.

     
  2. b)

    Für jeden lokalen bzw. globalen Minimalpunkt $(x^\star,\alpha^\star)$ von $P_\textrm{epi}$ ist $x^\star$ lokaler bzw. globaler Minimalpunkt von P.

     
  3. c)

    Die Minimalwerte von P und $P_\textrm{epi}$ stimmen überein.

     

1.3.6 Definition (Parallelprojektion)

Es sei $M \subseteq \mathbb R^n \times \mathbb R^m$. Dann heißt
$$ \textrm{pr}_x\,M\ =\ \{x \in \mathbb R^n|\ \exists\, y\in \mathbb R^m:\ (x,y) \in M\} $$
Parallelprojektion von M auf (den „x-Raum“) $\mathbb R^n$.

1.3.7 Übung (Projektionsumformulierung)

Gegeben seien $M\subseteq\mathbb R^n\times\mathbb R^m$ und eine Funktion $f:\mathbb R^n\to\mathbb R$, die nicht von den Variablen aus $\mathbb R^m$ abhängt. Dann sind die Probleme
$$ P:\qquad \min_{(x,y) \in \mathbb R^n \times \mathbb R^m}\, f(x) \quad\textnormal{ s.t. }\quad (x,y) \in M $$
und
$$ P_\textrm{proj}:\qquad \min_{x \in \mathbb R^n}\, f(x) \quad\textnormal{ s.t. }\quad x \in \textrm{pr}_x\,M $$
in folgendem Sinne äquivalent:
  1. a)

    Für jeden lokalen bzw. globalen Minimalpunkt $(x^\star,y^\star)$ von P ist $x^\star$ lokaler bzw. globaler Minimalpunkt von $P_\textrm{proj}$.

     
  2. b)

    Für jeden lokalen bzw. globalen Minimalpunkt $x^\star$ von $P_\textrm{proj}$ existiert ein $y^\star \in \mathbb R^m$, so dass $(x^\star,y^\star)$ lokaler bzw. globaler Minimalpunkt von P ist.

     
  3. c)

    Die Minimalwerte von P und $P_\textrm{proj}$ stimmen überein.