Optimalitätsbedingungen für konvexe Optimierungsprobleme

In diesem Kapitel werden Bedingungen hergeleitet, die es erlauben, für konvexe Optimierungsprobleme zu entscheiden, ob ein gegebener Punkt optimal ist oder nicht. Diese Frage ist bei Funktionen von mehreren Unbekannten – und bei gegebenen Nebenbedingungen an die Unbekannten – in der Tat nicht leicht zu beantworten. Die Resultate dieses Kapitels sind Ausgangspunkt für viele numerische Verfahren zur Bestimmung einer Optimallösung und sind für das Verständnis dieser Verfahren wichtig, so dass sich ihr Studium lohnt. Ihre Bedeutung ist grundlegend, während die praktische Bedeutung einzelner Optimierungsverfahren relativ ist: die Vorzüge vieler Verfahren hängen häufig von der benutzten Computerarchitektur und davon ab, wie gut sie die besondere Struktur des jeweiligen Problems berücksichtigen.

8.1 Konvexe Ungleichungssysteme

Eine differenzierbare konvexe Funktion $f:\mathbbm {R}^n\rightarrow \mathbbm {R}$ besitzt $$x^*$$ genau dann als Minimalpunkt, wenn $\nabla f( x^*)=0$ gilt. (Wir überlassen den Nachweis dieser Aussage als einfache Übung.) Ziel der folgenden Betrachtungen ist es, diese Bedingung auf konvexe Optimierungsprobleme zu verallgemeinern, bei denen endlich viele Nebenbedingungen in der Form von Gleichungen oder Ungleichungen zu berücksichtigen sind.

Wir beginnen mit einem Resultat über die Lösbarkeit von Systemen von konvexen strikten Ungleichungen:

Satz 8.1.1

Seien $f_i:\mathbbm {R}^n\rightarrow \overline{\mathbbm {R}}$ , $$i=1$$

, ..., m, konvexe Funktionen auf dem $\mathbbm {R}^n$ und $C \subset \mathbbm {R}^n$ eine konvexe Menge mit $\emptyset \ne C \subset \bigcap ^m_{i=1}\mathrm{dom}\, f_i$ . Dann gilt: Die Ungleichung

$\begin{aligned} F(x) := {\textstyle \left( \begin{array}{c}f_1(x)\\ \vdots \\ f_m(x)\end{array}\right) } < 0 \end{aligned}$

(8.1.2)

ist genau dann für $x\in C$ unlösbar, wenn es ein $z \in \mathbbm {R}^m$ gibt mit $z \ge 0$ , $z\ne 0$ und

$\begin{aligned} z^TF(x) = \sum ^m_{i=1}z_if_i(x) \ge 0\quad {\text {f}}{\ddot{\text {u}}}{\text {r }} \,\, alle \,\, x\in C. \end{aligned}$

(8.1.3)

Beweis

„ $\Longleftarrow$ “: Diese Richtung ist offensichtlich richtig, weil (8.1.3) und $z\ge 0$ implizieren, dass für jedes $x\in C$ mindestens ein i mit $f_i(x)\ge 0$ existiert.
„ $\Longrightarrow$ “: Die Menge $A := \big \{ v \in \mathbbm {R}^m \mid \exists x \in C:\ v > F(x)\big \}$ ist konvex, da alle konvex sind. Weiter ist $A\subset \mathbbm {R}^m$ , $A\ne \emptyset$ und $0 \not \in A$ wegen der Unlösbarkeit von (8.1.2). Nach Satz 7.2.2 kann $\{0\}$ von A getrennt werden, d. h. es gibt ein $z \in \mathbbm {R}^m$ , $z\ne 0$ , so dass $z^T v \ge z^T0 = 0$ für alle $v \in A$ . Nun ist mit $v\in A$ auch $v+w\in A$ für alle $0\le w\in \mathbbm {R}^m$ . Aus $\lim _{\lambda \rightarrow \infty } z^T(v+\lambda w)\ge 0$ folgt $z^Tw\ge 0$ für alle $w\ge 0$ , also $z\ge 0$ . Weiter kann man zu jedem $x\in C$ ein finden, das beliebig nahe bei F(x) liegt. Nach Definition ist $v\in A$ und daher $z^Tv\ge 0$ . Insgesamt gilt also $z \ge 0$ und $z^T F(x) \ge 0$ für alle $x \in C$ . $\square$

Der letzte Satz betrifft die Lösbarkeit eines Systems von strikten Ungleichungen. Dies ist für Anwendungen auf Optimierungsprobleme der Form

$\begin{aligned} \begin{array}{cl}\inf \ &{} f(x)\\ x\in \mathbbm {R}^n:\ &{} f_i(x)\le 0\; {\text {f}}{\ddot{\text {u}}}{\text {r}}\, i=1,\,\ldots ,\, p,\\ &{} f_j(x)=0\;{\text {f}}{\ddot{\text {u}}}{\text {r}}\, p+1,\,\ldots ,\, m,\\ &{} x\in C, \end{array} \end{aligned}$

(8.1.4)

zu eng, bei denen üblicherweise die zulässige Menge durch ein System von nichtstrikten Ungleichungen und von Gleichungen beschrieben wird. Hier repräsentiert C weitere Nebenbedingungen, die man nicht in der Form endlich vieler Ungleichungen oder Gleichungen schreiben kann oder will. In den meisten Anwendungen ist $C=\mathbbm {R}^n$ .

Für f schreiben wir im Folgenden auch $$f_0:=f$$

und fassen die Restriktionen zu Vektoren von Funktionen zusammen:

$F_1(x) := \left( \begin{array}{c}f_1(x)\\ \vdots \\ f_p(x)\end{array}\right) , \quad F_2(x) := \left( \begin{array}{c}f_{p+1} (x)\\ \vdots \\ f_m(x)\end{array}\right) ;\quad F(x) = \left( \begin{array}{c}F_1(x)\\ F_2(x)\end{array}\right) ,$

so dass die zulässige Menge $\mathcal{S}$ von (8.1.4) durch

$\begin{aligned} \mathcal{S}:=\{\, x\in C\mid F_1(x)\le 0,\ F_2(x)=0\,\} \end{aligned}$

(8.1.5)

gegeben ist.

Damit (8.1.4) ein konvexes Optimierungsproblem wird, treffen wir die

Voraussetzung 8.1.6

1.
$C\subseteq \mathbbm {R}^n$ ist eine konvexe Menge mit $C \subset \mathrm{dom}\, f_i\ \, {\text {f}}{\ddot{\text {u}}}{\text {r }} \,\, i=0,\, 1,\,\ldots ,\, m$ . Dabei ist in (8.1.4)
2.
Die Funktionen $f_i:\mathbbm {R}^n\rightarrow \overline{\mathbbm {R}}=\mathbbm {R}\cup \{+\infty \}$ sind für , 1, ..., p konvex (s. Definition 7.3.3).
3.
Die Funktionen $f_j:\mathbbm {R}^n\rightarrow \mathbbm {R}$ sind für , , ..., m affin.

Man überzeugt sich leicht, dass die Menge $\mathcal{S}$ unter dieser Voraussetzung konvex ist. Darüber hinaus ist sie auch abgeschlossen, falls C eine abgeschlossene konvexe Menge und die Einschränkungen aller $$f_i$$ , $$i=1$$ , 2, ..., p, auf C reellwertige stetige Funktionen sind.

Ein wichtiges Resultat zur Charakterisierung von Optimalpunkten von konvexen Programmen der Form (8.1.4) ist der folgende Satz:

Satz 8.1.7

Seien folgende Voraussetzungen erfüllt:

1.
Voraussetzung 8.1.6.
2.
Für die konvexe Menge $\mathcal{S}$ (8.1.5) gelte:
1. a)
  Es gibt ein $\bar{x}\in \mathcal{S}\cap C^i$ . (Dabei ist das relativ Innere von C.)
2. b)
  Zu jeder nichtaffinen Funktion mit $i\ge 1$ gibt es ein $x^i \in \mathcal{S}$ mit .
3.
Das Optimierungsproblem (8.1.4) besitzt einen endlichen Optimalwert $\alpha :=\inf \{f_0(x)\mid x\in \mathcal{S}\}\in \mathbbm {R}$ .

Dann gibt es ein $y \in \mathbbm {R}^m$ mit $y_i \ge 0$ für $i=1,\, \ldots ,\, p$ , so dass

$\begin{aligned} f(x) + y^T F(x) \ge \alpha \quad {\text {f}}{\ddot{\text {u}}}{\text {r }} \;\; alle \, \, x\in C. \end{aligned}$

(8.1.8)

Bemerkungen

Voraussetzung 2) stellt eine Regularitätsforderung dar; sie wird weiter unten noch näher erläutert und analysiert. Ferner wird nur die Endlichkeit des Optimalwerts $\alpha$ von (8.1.4) verlangt, keine Differenzierbarkeit und auch nicht die Existenz einer Optimallösung. So erfüllt z. B. für $$n=2$$ das Problem $\inf \{x_2\mid x_2\ge e^{x_1}\}$ , das keine Optimallösung besitzt, alle Voraussetzungen des Satzes mit $\alpha =0$ . Satz 8.1.7 ist also auch auf solche Probleme anwendbar. Beachte, dass es kein $\epsilon > 0$ gibt, sodass (8.1.8) mit rechter Seite $\alpha +\epsilon$ anstelle von $\alpha$ erfüllt ist. Denn für $x\in \mathcal{S}$ ist $y^T F(x)\le 0$ und nach Definition von $\alpha$ existiert zu $\epsilon >0$ ein $x\in \mathcal{S}$ mit $f(x) < \alpha +\epsilon$ . Der Vektor y aus Satz 8.1.7 maximiert also die „rechte Seite $\alpha$ “ unter allen $y\in \mathbbm {R}^m$ mit $y_i\ge 0$ für $1\le i\le p$ . Tritt dieses Maximierungsproblem wie in Punkt (3) in Satz 8.3.4 auf, so wird es auch als Lagrange-Duales bezeichnet.

Wir zeigen zunächst, dass die Bedingung 2)b) zu der Forderung äquivalent ist, dass es einen Punkt $\hat{x} \in \mathcal{S}$ gibt, mit $f_i(\hat{x}) < 0$ für alle nichtaffinen Funktionen $$f_i$$ mit $i\ge 1$ .

Beweis: Seien ohne Einschränkung der Allgemeinheit $$f_1$$

, ...,

die nichtaffinen Funktionen $$f_i$$

mit $i\ge 1$ . Dann ist $l\le p$ . Wegen 2)b) gibt es zu jedem i mit $1\le i\le l$ ein $x^i \in \mathcal{S}$ mit $$f_i(x^i)<0$$

, $f_k(x^i) \le 0$ für $k\not = i$ , $$k=1$$

, ..., p, sowie $$f_j(x^i) =0$$

für

, ..., m. Für $\hat{x} := (x^1 + x^2 + \cdots + x^l)/l$ gilt dann $\hat{x}\in \mathcal{S}$ wegen der Konvexität von $\mathcal{S}$ . Weiter folgt aus der Konvexität der $$f_i$$

für

, 2, ..., l

$\begin{aligned} f_i(\hat{x})= & {} f_i\bigl ({1\over l} (x^1 + \cdots + x^i + \cdots + x^l)\bigr )\\\le & {} {1\over l}\bigl (\underbrace{f_i(x^1)}_{\le 0}+ \cdots + \underbrace{f_i(x^i)}_{< 0} + \cdots + \underbrace{f_i(x^l)}_{\le 0} \bigr )<0. \end{aligned}$

$\square$

Beweis von Satz 8.1.7

Wir setzen zunächst voraus, dass es ein $\hat{x}\in \mathcal{S}$ gibt mit $F_1(\hat{x})<0$ , d. h. wir fordern zunächst $f_i(\hat{x})< 0$ auch für die affinen Funktionen $$f_i$$ mit $i\in \{1, \ldots , p\}$ .

Wie im Beweis der vorangegangenen Bemerkung, können wir durch eine Konvexkombination von $\bar{x}$ aus Bedingung 2)a) und $\hat{x}$ sogar ein neues $\hat{x}$ mit folgenden Eigenschaften finden:

$\begin{aligned} \hat{x} \in \mathcal{S}\cap C^i,\quad F_1(\hat{x})<0. \end{aligned}$

(8.1.9)

Indem wir „f(x)“ durch „ $f(x)-\alpha$ “ ersetzen, nehmen wir für den nachfolgenden Beweis ohne Einschränkung zusätzlich an, dass $\alpha = 0$ gilt.

Der Beweis von Satz 8.1.7 teilt sich nun in zwei Schritte auf:

1.
Ohne die Regularitätsvoraussetzung 2) des Satzes zu benutzen, zeigen wir zunächst, dass es einen Vektor $z\in \mathbbm {R}^{m+1}$ , $z\ne 0$ , gibt mit den Eigenschaften
$\begin{aligned} z_i \ge 0\ \ {\text {f}}{\ddot{\text {u}}}{\text {r }} 0 \le i \le p\ \ \text{ und } \sum ^m_{i=0} z_i f_i(x) \ge 0\ \ {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x \in C. \end{aligned}$

(8.1.10)
2.
Unter Verwendung von Voraussetzung 2) zeigen wir dann . Dann erfüllt der Vektor $y :=\Bigl (z_1,z_2, \ldots , z_m\Bigr )^T/z_0$ die Behauptung des Satzes.

Zu 1) Der Beweis lässt sich wie bei Satz 8.1.1 mit Hilfe eines Trennungssatzes führen. Sei $A\subset \mathbbm {R}^{m+1}$ die Menge

../images/71756_2_De_8_Chapter/71756_2_De_8_Equ116_HTML.png

Aus der Konvexität von C, der Funktionen $$f_i$$

, 1, ..., p, und der Affinität der Funktionen $$f_j$$

, $p+1\le j\le m$ , folgt wie im Beweis von Satz 8.1.1, dass A eine nichtleere konvexe Menge ist. Wegen Voraussetzung 3) ist $0\not \in A$ . Also kann $\{0\}$ wegen Korollar 7.2.10, Teil 1) von A eigentlich getrennt werden. Es gibt also einen Vektor $z=(z_0,z_1,\ldots , z_m)^T$ , der nicht verschwindet, $z\ne 0$ , so dass

$z^T v\ge 0\ {\text {f}}{\ddot{\text {u}}}{\text {r alle }} v \in A,$

und es gibt ein $\tilde{v}\in A$ mit $z^T\tilde{v} > 0$ .

Aus der Definition von A folgt wieder $z_i \ge 0$ für $0\le i\le p$ und es gilt

$v_\varepsilon :=\left( \begin{array}{c}f_0(x) + \varepsilon \\ F(x)\end{array}\right) \in A$

für alle $\varepsilon >0$ und alle $x\in C$ . Wegen

$0\le z^Tv_\varepsilon = z_0 (f(x)+\varepsilon ) + \sum _{i\ge 1} z_i f_i(x)\ {\text { f}}{\ddot{\text {u}}}{\text {r alle }} \varepsilon >0,\ x\in C$

folgt für $\varepsilon \rightarrow 0$ die Teilbehauptung 1).

Zu 2). Falls $$z_0 = 0$$

wäre, so gilt wegen (8.1.9)

$v:= \bigl (f_0(\hat{x})+1, f_1(\hat{x}), \ldots , f_p(\hat{x}), 0,\ldots , 0)^T\in A.$

Also ist $z^T v \ge 0$ . Aus $$z_0=0$$

, $z_1\ge 0$ , ..., $z_p\ge 0$ und $f_i(\hat{x})<0$ für $$i=1$$

, ..., p folgt deshalb $z_1=\cdots =z_p=0$ .

Die Definition von A zeigt dann

$\begin{aligned} z_{p+1} f_{p+1}(x) + \cdots + z_m f_m(x) \ge 0 \quad {\text { f}}{\ddot{\text {u}}}{\text {r alle }} x\in C. \end{aligned}$

(8.1.11)

Da $\{0\}$ von A eigentlich getrennt wird, folgt sogar

$\ z_{p+1}f_{p+1}(\tilde{x}) + \cdots + z_mf_m(\tilde{x}) >0 \quad {\text { f}}{\ddot{\text {u}}}{\text {r ein }} \tilde{x}\in C.$

Nach Satz 7.2.7 ist wegen $\hat{x}\in C^i$ für kleines $\varepsilon > 0$ auch $\hat{x} - \varepsilon (\tilde{x} - \hat{x}) \in C$ . Da die $$f_j$$

für $j\ge p+1$ affin sind, folgt

$f_j\bigl (\hat{x}-\varepsilon (\tilde{x}-\hat{x})\bigr ) = \underbrace{f_j(\hat{x})}_{{}=0} - \varepsilon \bigl (f_j(\tilde{x}) - f_j(\hat{x})\bigr ) = -{\varepsilon } f_j(\tilde{x}) \qquad {\text {f}}{\ddot{\text {u}}}{\text {r}}\,\, j \ge p+1.$

Also ist

$\begin{aligned}&z_{p+1} f_{p+1}\bigl ( \hat{x} - \varepsilon (\tilde{x} - \hat{x})\bigr ) + \cdots + z_m f_m\bigl ( \hat{x} - \varepsilon (\tilde{x} - \hat{x})\bigr ) \\= & {} -\varepsilon \bigl (z_{p+1}f_{p+1}(\tilde{x}) + \cdots + z_mf_m(\tilde{x})\bigr ) < 0 \end{aligned}$

im Widerspruch zu (8.1.11).

Für den Fall $\hbox {aff}(C) = \mathbbm {R}^n$ skizzieren wir nun noch kurz den Fall, dass Voraussetzung 2) b) in Satz 8.1.7 nur für die nichtaffinen Nebenbedingungen erfüllt ist, d. h. wir nehmen an, dass es ein $$k<p$$

gibt, sodass $$f_i(x)=0$$

für alle $x\in \mathcal{S}$ und für alle $i\in$ $\{k+1,\ldots , p\}$ . In diesem Fall kann man die affinen Ungleichungen $k+1,\ldots , p$ durch Gleichungen ersetzen. Aus obigem Beweis lässt sich dann aber zunächst nicht ablesen, dass eine Wahl von y mit $y_i\ge 0$ auch für $i\in \{k+1,\ldots , p\}$ möglich ist. Nun gibt es aber ein $\epsilon >0$ , sodass $\hat{x}+\Delta x$ die Bedingungen (8.1.9) (für die nichtaffinen Ungleichungen) ebenfalls erfüllt, sofern nur $\Vert \Delta x\Vert \le \epsilon$ gilt. Die affinen Ungleichungen $k+1,\ldots , p$ sind also bereits durch Hinzunahme der affinen Gleichungen $p+1,\ldots , m$ nur als Gleichung erfüllbar, d. h. für $\nu \in \{k+1,\ldots , p\}$ gilt

$0 = \max \{\ t \ \mid \ \left( \begin{array}{c}f_{k+1}(x)\\ \vdots \\ f_{p}(x)\end{array}\right) -te_\nu \le 0, \ \ \ \left( \begin{array}{c}f_{p+1}(x)\\ \vdots \\ f_{m}(x)\end{array}\right) = 0\ \},$

wobei $e_\nu$ den $\nu$ -ten kanonischen Einheitsvektor in $\mathbbm {R}^{p-k}$ bezeichne. Dies ist ein lineares Programm, dessen Duales eine Optimallösung $z_{k+1},\ldots , z_m$ besitzt mit $z_\nu =1$ , $z_i\ge 0$ für die restlichen i mit $k+1\le i\le p$ und

$\textstyle \sum _{i=k+1}^pz_i\nabla f_i(x)=-\sum _{j=p+1}^mz_m\nabla f_m(x).$

Addition von positiven Vielfachen von z zu den entsprechenden Komponenten von y zeigt, dass $y_\nu \ge 0$ erreicht werden kann, ohne dabei die restlichen Indizes aus $\{k+1,\ldots , p\}$ zu verkleinern oder $$y^TF(x)$$

zu ändern. $\square$

Definition 8.1.12

Die zur Voraussetzung 2) von Satz 8.1.7 äquivalente Bedingung

$\exists x^1\in C^i \cap \mathcal{S}: \quad f_i(x^1) < 0\ \ {\text {f}}{\ddot{\text {u}}}{\text {r }}\; \; alle \;\; {nichtaffinen} \,\,\, f_i \, \, mit\,\, i\le p$

heißt Regularitätsbedingung von Slater (Slater’s constraint qualification) oder auch kurz Slater-Bedingung.

Diese Bedingung schließt gewisse Entartungen der nichtaffinen Nebenbedingungen aus. Wir erläutern sie an zwei einfachen Beispielen im $\mathbbm {R}^1=\mathbbm {R}$ , $$n=1$$ , die zeigen, dass die Aussage des Satzes falsch sein kann, wenn die Slater-Bedingung verletzt ist:

Beispiel 8.1.13

Wir betrachten das Optimierungsproblem vom Typ (8.1.4)

$\min \ \{x\in \mathbbm {R}\mid x^2\le 0\},$

d. h. es ist $$n=m=p=1$$

, $C:=\mathbbm {R}$ , $$f(x):=x$$

und

. Es besitzt die zulässige Menge $\mathcal{S}:=\{0\}$ , die einzige Optimallösung $$x^*=0$$

und den Optimalwert $\alpha :=0$ . Das Problem verletzt nur die Bedingung 2)b) des Satzes. In diesem Beispiel gibt es aber kein $y\ge 0$ mit $x+y\, x^2 \ge 0$ für alle $x\in C=\mathbbm {R}$ . Man kann deshalb Bedingung 2)b) nicht fortlassen.

Beispiel 8.1.14

Die Unverzichtbarkeit der Voraussetzung 2)a) in Satz 8.1.7 zeigt folgendes Beispiel mit $$n=m=p=1$$

: Man wähle

$f(x) :=\left\{ \begin{array}{lcl} -\sqrt{x} &{}\ &{}{\text {f}}{\ddot{\text {u}}}{\text {r}}\,\, x\ge 0,\\ \infty &{}\ &{} \text{ sonst, } \end{array}\right.$

und $C := \{x\in \mathbbm {R}\mid x \ge 0\}$ . Das zugehörige Optimierungsproblem

$\min \ \{f(x)\mid x\in C,\ x\le 0\}$

besitzt die zulässige Menge $\mathcal{S}= \{x\in C \mid f_1(x) \le 0\} = \{0\}$ , die einzige Optimallösung $$x^*=0$$

und den Optimalwert $\alpha =0$ . Jetzt ist Bedingung 2a) des Satzes verletzt, $C^i \cap \mathcal{S}= \emptyset$ . Wir prüfen die Existenz von $y \ge 0$ mit

$f(x) + yf_1(x) \ge 0\ \ {\text { f}}{\ddot{\text {u}}}{\text {r alle }} x \in C,$

d. h. $-\sqrt{x}+ y x \ge 0$ für alle $x \ge 0$ . Es existiert kein solches y, denn für jedes $$y > 0$$

gilt für

die Ungleichung $-\sqrt{x} + y x = - 1/(2y) + 1/(4 y)< 0$ .

8.2 Die KKT-Bedingungen

Im ersten Teil des Beweises von Satz 8.1.7 wurde die Voraussetzung 2) (die Slater-Bedingung) nicht benötigt. Er zeigt, dass es allein unter den Voraussetzungen 1) und 3) ein $z\in \mathbbm {R}^{m+1}$ gibt mit $z\ne 0$ und (8.1.10). Wir wollen dieses Teilresultat auf das Optimierungsproblem (8.1.4) mit einer Optimallösung $x^*\in \mathcal{S}$ anwenden,

$\alpha =f(x^*)=\min \,\{f(x)\mid x\in \mathcal{S}\}.$

Man erhält so allein unter der Voraussetzung 8.1.6, dass es einen Vektor $z=(z_0,z_1,\ldots z_m)^T$ gibt mit $z\ne 0$ , $z_i\ge 0$ für $$i=0$$

, 1, ..., p und

$\begin{aligned} z_0(f(x)-f(x^*)) +\sum _{i=1}^mz_if_i(x)\ge 0\quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x\in C. \end{aligned}$

(8.2.1)

Wir betrachten nun den häufigsten Spezialfall $C:=\mathbbm {R}^n$ von (8.1.4), nämlich das Optimierungsproblem

$\begin{aligned} \begin{array}{cl}\inf \ &{}\ f(x)\\ x\in \mathbbm {R}^n: &{}\ f_i(x)\le 0\quad \, {\text {f}}{\ddot{\text {u}}}{\text {r }} i=1,\,\ldots ,\, p,\\ &{}\ f_j(x)=0\quad {\text {f}}{\ddot{\text {u}}}{\text {r }} j= p+1,\,\ldots ,\, m, \end{array} \end{aligned}$

(8.2.2)

wobei wir jetzt annehmen, dass die Funktionen $f,\, f_i:\mathbbm {R}^n\rightarrow \mathbbm {R}$ , $$i=1$$

, 2, ..., p, differenzierbare konvexe Funktionen, und die $$f_j$$

, ..., m, wieder affin sind. Wenn nun $$x^*$$

eine Optimallösung von (8.2.2) ist, so folgt sofort aus (8.2.1) ohne weitere Regularitätsbedingung, dass das folgende System in den Variablen (x, z) eine Lösung $$x=x^*$$

und $z=(z_0,\ldots , z_m)$ mit $z\ne 0$ besitzt (hier ist wieder $$f_0:=f$$

$\begin{aligned} \begin{array}{c} \sum ^m_{i=0} z_i \nabla f_i(x) = 0, \\ f_i(x) z_i = 0,\;\, f_i (x) \le 0\quad {\text {f}}{\ddot{\text {u}}}{\text {r}}\quad 1 \le i\le p,\quad z_i\ge 0 \quad {\text {f}}{\ddot{\text {u}}}{\text {r}}\quad 0 \le i\le p,\\ f_j(x) = 0 \quad {\text {f}}{\ddot{\text {u}}}{\text {r}}\quad p+1 \le j \le m.\end{array} \end{aligned}$

(8.2.3)

Diese Bedingungen für z und $$x^*$$

heißen Fritz-John-Bedingungen.

Zur Begründung von (8.2.3) beachte man, dass die Funktion

$\phi (x):= z_0(f(x)-f(x^*)) +\sum _{i=1}^mz_if_i(x)$

konvex und differenzierbar ist und $\phi (x^*)\le 0$ gilt (wegen $z_i\ge 0$ für $0\le i\le p$ , $f_i(x^*)\le 0$ für $1\le i\le p$ , sowie $$f_j(x^*)=0$$

für $j\ge p+1$ ). Außerdem gilt $\phi (x)\ge 0$ für alle $x\in \mathbbm {R}^n$ wegen (8.2.1), und so nimmt $\phi$ bei $$x^*$$

sein Minimum an, d. h. der Gradient von $\phi$ bei $$x=x^*$$

ist Null. Dies ist genau die erste Zeile von (8.2.3). Die zweite Zeile folgt aus $z_i\ge 0,\ f_i(x)\le 0$ für $x\in \mathcal{S}$ und $1\le i\le p$ . Wäre nämlich eines der Produkte von Null verschieden, so müsste es strikt negativ sein, und dann wäre $\phi (x^*)<0$ , ein Widerspruch. Die dritte Zeile schließlich folgt wieder aus $x\in \mathcal{S}$ .

Falls die Slater-Bedingung für das Optimierungsproblem (8.2.2) erfüllt ist, d. h. wenn es $x^1\in \mathcal{S}$ mit $$f_i( x^1)<0$$

für alle nichtaffinen Funktionen $$f_i$$

mit $1\le i\le p$ gibt, dann gibt es nach Satz 8.1.7 einen Vektor $y\in \mathbbm {R}^m$ mit $y_1\ge 0$ , ..., $y_p\ge 0$ , so dass

$f(x)+\sum _{i=1}^my_if_i(x) \ge f(x^*) \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x\in \mathbbm {R}^n.$

Wie eben folgt dann, dass das folgende System in den Variablen (x, y)

$\begin{aligned} \begin{array}{c} \nabla f(x)+\sum ^m_{i=1} y_i \nabla f_i(x) = 0, \\ f_i(x) y_i = 0,\;\, f_i (x) \le 0,\; y_i\ge 0 \quad {\text {f}}{\ddot{\text {u}}}{\text {r}}\quad 1 \le i\le p,\\ f_j(x) = 0 \quad {\text {f}}{\ddot{\text {u}}}{\text {r}}\quad p+1 \le j \le m,\end{array} \end{aligned}$

(8.2.4)

eine Lösung besitzt, jedenfalls für eine Optimallösung $$x=x^*$$

von (8.2.2). (Ohne die Ungleichungen stellt (8.2.4) ein Gleichungssystem von $$n+m$$

Gleichungen für die $$n+m$$

Unbekannten (x, y) dar.)

Die Bedingungen (8.2.4) werden KKT-Bedingungen für das Optimierungsproblem (8.2.2) genannt: Sie gehen auf Karush, Kuhn und Tucker zurück.

Für Probleme (8.2.2), die die Slater-Bedingung erfüllen, werden wir im nächsten Abschnitt sehen (s. Satz 8.3.4), dass die Lösung des KKT-Systems (8.2.4) mit der Lösung des Optimierungsproblems (8.2.2) äquivalent ist.

8.3 Die Lagrangefunktion

Eines der wichtigsten Werkzeuge der Optimierung ist die Lagrangefunktion, die dazu dient, ein gewisses „Gleichgewicht“ zwischen der Zielfunktion und den Nebenbedingungen zu beschreiben. Bevor wir die Lagrangefunktion formal einführen, soll sie anhand eines kleinen Beispiels motiviert werden.

Beispiel:: Wir betrachten ein konvexes Optimierungsproblem im $\mathbbm {R}^1=\mathbbm {R}$ mit nur einer Ungleichungsrestriktion
$\begin{aligned} \inf \ \{f_0(x)\mid f_1(x)\le 0\}. \end{aligned}$

(8.3.1)
Man führt dann zu jedem Parameter $y\ge 0$ , $y\in \mathbbm {R}$ , Hilfsprobleme ein, die von y abhängen:
$\begin{aligned} \inf \ \{f_0(x)+y f_1(x)\mid x\in \mathbbm {R}\}. \end{aligned}$

(8.3.2)
Der Parameter y beschreibt das Gewicht, das man der Erfüllung der Nebenbedingung $f_1(x)\le 0$ beimisst. Wir nehmen an, dass (8.3.2) für jedes feste $y\ge 0$ eine Optimallösung besitzt. Für wird vermutlich der Optimalpunkt die Nebenbedingung $f_1(x)\le 0$ im Allgemeinen verletzen, es sei denn, die Nebenbedingung $f_1(x)\le 0$ war „überflüssig“. Wenn man aber y sehr groß wählt, wird das Hauptgewicht des Problems (8.3.2) bei der Minimierung von liegen; in der Regel wird dann gelten und wird für (8.3.1) nicht optimal sein. Lässt man nun, beginnend bei , den Wert von y langsam wachsen und verfolgt die zugehörigen Lösungen , so wird es einen Zwischenwert oder „Gleichgewichtspunkt“ $\bar{y}>0$ geben, für den $f_1(x^*(\bar{y}))=0$ gilt. Dann löst $x^*(\bar{y})$ auch (8.3.1).

Die Zielfunktion $$L(x, y):=f_0(x)+y f_1(x)$$

des Hilfsproblems ist die Lagrangefunktion zu (8.3.1), die wir nun allgemein für Optimierungsprobleme (8.1.4) definieren wollen.

Definition 8.3.3

1.
Sei D die Menge $D := \bigl \{ y\in \mathbbm {R}^m \mid y_i \ge 0 \,\, {{\text {f}}{\ddot{\text {u}}}{\text {r }}}\,\, 1 \le i \le p\}$ . Dann heißt die Funktion $L :C \times D\rightarrow \mathbbm {R}$ , die durch
$L(x, y) := f(x) + \sum ^m_{i=1} y_i f_i(x) = f(x) + y^T F(x)$
definiert ist, die Lagrangefunktion von (8.1.4).
2.
Ein Punkt $(\bar{x}, \bar{y}) \in C\times D$ heißt Sattelpunkt von L auf $C\times D$ , falls
$L(x, \bar{y})\ge L(\bar{x}, \bar{y})\ge L(\bar{x}, y) \quad {{\text {f}}{\ddot{\text {u}}}{\text {r }}} \,\, alle \,\, x\in C\ \, und \,\, alle\,\, y\in D.$

Diese Definitionen erlauben es, den folgenden Satz zu zeigen, der im wesentlichen äquivalent zu Satz 8.1.7 und als Satz von Karush, Kuhn und Tucker für konvexe Optimierungsprobleme (8.1.4) bekannt ist:

Satz 8.3.4

(Karush, Kuhn & Tucker)

Sei Voraussetzung 8.1.6 für Problem (8.1.4) erfüllt. Dann gilt:

1.
Falls $(\bar{x}, \bar{y})$ Sattelpunkt der Lagrangefunktion auf $C\times D$ ist, dann ist $\bar{x}$ optimal für (8.1.4) und $\bar{y}_i f_i (\bar{x}) = 0$ für $1 \le i \le m$ , d. h.
$L (\bar{x},\bar{y}) = f(\bar{x}).$
2.
Falls umgekehrt $\bar{x}$ Optimallösung von (8.1.4) ist und die Slater-Bedingung (siehe Definition 8.1.12) erfüllt ist, gibt es ein $\bar{y}\in D$ , so dass $(\bar{x}, \bar{y})$ Sattelpunkt von L ist.
3.
Falls der Optimalwert $\alpha$ von (8.1.4) endlich ist,
$\alpha =\inf \{f(x)\mid x\in \mathcal{S}\}\in \mathbbm {R},$
und die Slater-Bedingung erfüllt ist, gibt es ein $\bar{y}\in D$ , so dass
$\alpha =\inf _{x\in C}\,L(x,\bar{y})=\max _{y\in D}\,\inf _{x\in C} L(x, y).$

Beweis

1.
Sei $(\bar{x}, \bar{y})$ ein Sattelpunkt von L auf $C\times D$ . Dann ist für alle $y\in D$
$L(\bar{x}, \bar{y}) \ge L(\bar{x}, y) = f(\bar{x}) + \sum ^p_{i=1}y_if_i(\bar{x}) + \sum ^m_{j=p+1}y_jf_j(\bar{x}).$
Aus der Definition von D folgt dann $f_i(\bar{x}) \le 0$ für $1\le i\le p$ und $f_j(\bar{x}) =0$ für $p+1\le j\le m$ , denn die linke Seite ist beschränkt und die $y_i\ge 0$ , bzw. $y_j\in \mathbbm {R}$ können für $1\le i\le p$ bzw. für $p+1\le j\le m$ beliebig gewählt werden. Also ist $\bar{x} \in \mathcal{S}$ .
Falls $f_i(\bar{x}) \bar{y}_i \ne 0$ für ein $i\in \{1,\ldots , p\}$ , so muss $f_i(\bar{x})<0$ und $\bar{y}_i>0$ sein. Wir setzen dann für dieses i und $y_l = \bar{y}_l$ für alle anderen Komponenten von y. Daraus folgt dann $L (\bar{x}, y) > L(\bar{x}, \bar{y})$ , im Widerspruch zur Definition des Sattelpunktes. Also ist $\bar{y}_i f_i(\bar{x}) = 0$ für alle , ..., m. Für beliebiges $x\in \mathcal{S}$ ist
$f(\bar{x}) = L (\bar{x}, \bar{y}) \le L (x,\bar{y}) = f(x) + \sum ^p_{i=1} f_i(x) \bar{y}_i + \sum ^m_{j=p+1} f_j(x)\bar{y}_j \le f(x),$
wegen $f_i(x)\le 0$ und $\bar{y}_i\ge 0$ für $1\le i\le p$ und für $p+1\le j\le m$ .
Also ist $\bar{x}$ eine Optimallösung von (8.1.4).
2.
Falls $\bar{x}$ für (8.1.4) optimal ist und die Slater-Bedingung erfüllt ist, ist Satz 8.1.7 mit $\alpha :=f (\bar{x})$ anwendbar, d. h. es gibt ein $\bar{y} \in D$ mit
$L(x,\bar{y})=f(x) + \bar{y}^TF(x) \ge f(\bar{x}) \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x \in C.$
Für $x=\bar{x}$ folgt daraus $\bar{y}^T F(\bar{x}) \ge 0$ . Wegen $f_j(\bar{x}) = 0$ für $j\ge p+1$ , ist daher $\sum ^p_{i=1}\bar{y}_if_i(\bar{x})\ge 0$ , und wegen $\bar{y}_i \ge 0$ , $f_i(\bar{x})\le 0$ gilt $\bar{y}^T F(\bar{x}) = 0$ . Zusammenfassend erhält man wegen $y_i\ge 0$ , $f_i(\bar{x})\le 0$ für $1\le i\le p$ und $f_j(\bar{x})=0$ für $j\ge p+1$
$L(x,\bar{y}) \ge L(\bar{x}, \bar{y}) = f(\bar{x}) \ge f(\bar{x}) + \sum ^p_{i=1}y_i f_i(\bar{x}) + \sum ^m_{p+1} y_j f_j(\bar{x}) = L(\bar{x}, y)$
für alle $(x, y) \in C\times D$ . Also ist $(\bar{x}, \bar{y})$ ein Sattelpunkt von L.
3.
Es folgt sofort aus Satz 8.1.7 und (8.1.8) die Existenz eines $\bar{y}\in D$ mit
$\begin{aligned} \alpha =\inf _{x\in C} L(x,\bar{y}). \end{aligned}$

(8.3.5)
Andererseits folgt für jedes $x\in C$ aus der Definition von L
$\sup _{y\in D} L(x, y)=\left\{ \begin{array}{ll} f(x),&{}\ \text{ falls } F_1(x)\le 0,\ F_2(x)=0,\\ +\infty ,&{}\ \text{ sonst }, \end{array}\right.$
so dass
$\begin{aligned} \inf _{x\in C}\sup _{y\in D} L(x, y)= \inf \,\{f(x)\mid x\in C,\ F_1(x)\le 0,\ F_2(x)=0\}=\alpha . \end{aligned}$

(8.3.6)
Da generell gilt
$\inf _{x\in C}\sup _{y\in D}L(x,y)\ge \sup _{y\in D}\inf _{x\in C} L(x, y)\ge \inf _{x\in C} L(x,\bar{y})=\alpha$
folgt aus (8.3.5) und (8.3.6) sofort
$\alpha =\inf _{x\in C} L(x,\bar{y})=\max _{y\in D}\inf _{x\in C} L(x, y).$

$\square$

Satz 8.3.4 gibt eine sehr allgemeine Fassung des Satzes von Karush-Kuhn-Tucker an, die für beliebige konvexe Mengen C und beliebige konvexe Funktionen f und $$f_i$$ , $1\le i\le p$ , gilt, die sogar nichtdifferenzierbar sein können.

Für $C=\mathbbm {R}^n$ und differenzierbare konvexe Funktionen f, $$f_i$$

ist $(\bar{x},\bar{y})$ Sattelpunkt von L auf $C\times D=\mathbbm {R}^n\times D$ genau wenn die KKT-Bedingungen (8.2.4) für $(x, y):=(\bar{x},\bar{y})$ erfüllt sind. Zum Beispiel folgt die erste Zeile dieser Bedingungen aus

$L(x,\bar{y})\ge L(\bar{x},\bar{y}) \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x\in C=\mathbbm {R}^n,$

so dass

$\nabla _x L(x,\bar{y})|_{x=\bar{x}}\equiv \nabla f(\bar{x})+\sum _{i=1}^m\bar{y}_i\nabla f_i(\bar{x})=0.$

8.4 Dualität bei konisch konvexen Programmen

In Anlehnung an das Buch [128] schildern wir hier noch eine weitere elegante Möglichkeit, für konvexe Probleme ein duales Problem zu formulieren. Sie beruht auf der Beobachtung, dass sich ein konvexes Problem stets in einer konischen Standardform schreiben lässt, in der Kegel $\mathcal{K}\subseteq \mathbbm {R}^n$ und ihre dualen Kegel $\mathcal{K}^D$ bezüglich eines Skalarprodukts $\langle .,.\rangle$ eine wesentliche Rolle spielen.

Wir erinnern zunächst an die Definition 7.3.1 des polaren Kegels und des dualen Kegels

$\begin{aligned} \mathcal{K}^D =-\mathcal{K}^P=\{ y \in \mathbbm {R}^n \mid \langle y, x\rangle \ge 0 \ {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x \in \mathcal{K}\}. \end{aligned}$

(8.4.1)

Natürlich sind beide Kegel für jedes Skalarprodukt $\langle .,.\rangle$ im $\mathbbm {R}^n$ definiert und nicht nur für das Standard-Skalarprodukt $\langle x, y\rangle =x^Ty$ .

Ein konisches Programm im $\mathbbm {R}^n$ (versehen mit dem Skalarprodukt $\langle .,.\rangle$ ) ist ein konvexes Optimierungsproblem der Form

$\begin{aligned} (P)\qquad \qquad \qquad \inf \{\langle c, x\rangle \mid x\in \mathcal{K},\ x\in \mathcal{L}+b\}.\qquad \qquad \qquad \end{aligned}$

(8.4.2)

Hier ist $\mathcal{K}\subseteq \mathbbm {R}^n$ ein nichtleerer abgeschlossener konvexer Kegel, b, $c\in \mathbbm {R}^n$ Vektoren und $\mathcal{L}\subseteq \mathbbm {R}^n$ ein linearer Teilraum. Die Menge

$\mathcal{L}+b=\{x+b\mid x\in \mathcal{L}\}$

ist eine affine Menge (eine lineare Mannigfaltigkeit) des $\mathbbm {R}^n$ , so dass die Menge der zulässigen Lösungen von (P) der Durchschnitt eines abgeschlossenen konvexen Kegels mit einer linearen Mannigfaltigkeit ist. Konische Programme verallgemeinern lineare Programme: Wählt man als Kegel $\mathcal{K}$ den positiven Orthanten $\mathcal{K}=\mathbbm {R}^n_+:=\{x\in \mathbbm {R}^n\mid x\ge 0\}$ des $\mathbbm {R}^n$ , so erhält man ein lineares Programm.

Als duales konisches Programm zu (P) bezeichnet man das konische Programm

$\begin{aligned} (D)\qquad \qquad \qquad \inf \{\langle b, s\rangle \mid s\in \mathcal{K}^D,\ s\in \mathcal{L}^\perp +c\}.\qquad \qquad \qquad \end{aligned}$

(8.4.3)

Hier ist $\mathcal{L}^\perp$ der Orthogonalraum von $\mathcal{L}$ ,

$\mathcal{L}^\perp :=\{y\in \mathbbm {R}^n\mid \langle y, x\rangle =0\ {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x\in \mathcal{L}\}.$

(D) ist vollkommen symmetrisch zu (P) formuliert: Wegen $\mathcal{K}\ne \emptyset$ , der Abgeschlossenheit von $\mathcal{K}$ und Satz 7.3.2 ist $\mathcal{K}^{DD}=\mathcal{K}$ , so dass das duale Programm zu (D) wieder (P) ist. Man beachte aber, dass anders als bisher sowohl (P) wie (D) Minimierungsprobleme sind.

Der weiter unten bewiesene Dualitätssatz 8.4.4 wird die Bezeichnung von (P) und (D) als duale Programme rechtfertigen.

Die Bedeutung von konischen Programmen liegt darin, dass man (nahezu) jedes konvexe Optimierungsproblem (8.1.4)

$\inf \{f(x)\mid x\in \mathcal{S}\}$

mit

$\mathcal{S}:=\bigl \{ x \in C \mid f_i(x) \le 0\ {\text {f}}{\ddot{\text {u}}}{\text {r }} 1\le i \le p, \ f_j(x) = 0\ {\text {f}}{\ddot{\text {u}}}{\text {r }} j = p+1, \ldots , m \bigr \}$

in ein äquivalentes konisches Programm umwandeln kann. Zunächst können wir ohne Einschränkung der Allgemeinheit annehmen, dass die Zielfunktion $f(x)=\langle c, x\rangle$ linear ist. Dies kann man stets erreichen, indem man z. B. eine neue Variable $x_{n+1}$ und eine zusätzliche Nebenbedingung $f(x)\le x_{n+1}$ einführt und dann $x_{n+1}$ minimiert. Letzteres ist natürlich eine lineare Funktion des erweiterten Vektors $(x, x_{n+1})$ der Unbekannten.

Im Folgenden sei deshalb $f(x)=\langle c, x\rangle$ linear und wieder $x\in \mathbbm {R}^n$ , d. h. $\mathcal{S}\subseteq \mathbbm {R}^n$ . Wir setzen jetzt voraus, dass $\mathcal{S}$ eine abgeschlossene konvexe Menge ist. Dies ist sicher der Fall, wenn C eine abgeschlossene konvexe Menge ist und die Einschränkungen der Funktionen $$f_i$$ , $$i=1$$ , 2, ..., m, auf C reellwertig stetig und konvex sind.

Wir „liften“ nun die Menge $\mathcal{S}$ in einen abgeschlossenen konvexen Kegel im $\mathbbm {R}^{n+1}$ , indem wir definieren

$\mathcal{K}:=\overline{\mathrm{cone}}\,\{(x, 1)\in \mathbbm {R}^{n+1}\mid x\in \mathcal{S}\}.$

(Für die Definition des Abschluss der konvexen konischen Hülle $\overline{\mathrm{cone}}\,$ siehe Abschn. 7.3.) Da sowohl $\mathcal{S}$ wie $\mathcal{K}$ abgeschlossen und konvex sind, zeigt man leicht

$x\in \mathcal{S}\Longleftrightarrow (x, 1)\in \mathcal{K}.$

Damit ist das konvexe Programm (8.1.4) äquivalent zu dem speziellen konischen Programm

$\inf \,\{\langle c, x\rangle \mid x\in \mathcal{K},\ x_{n+1}=1\}.$

In den Übungen 8.6 wird gezeigt, dass sich diese abstrakte Definition von $\mathcal{K}$ auch mit Hilfe konvexer Funktionen konkret angeben lässt.

Es gilt nun folgender Dualitätssatz

Satz 8.4.4

Für die dualen Programme (P) (8.4.2) und (D) (8.4.3) gelten folgende Aussagen:

1.
Für jede zulässige Lösung x von (P) und s von (D) ist
$\langle c,x\rangle +\langle b,s\rangle \ge \langle b, c\rangle .$
2.
Falls (P) einen endlichen Optimalwert $\alpha$ besitzt,
$\alpha =\inf \ \{\langle c, x\rangle \mid x\in \mathcal{K}\cap (\mathcal{L}+b)\}\in \mathbbm {R},$
und (P) die Slater-Bedingung $\mathcal{K}^i\cap (\mathcal{L}+b)\ne \emptyset$ erfüllt, dann besitzt (D) eine Optimallösung und es gilt
$\alpha +\langle b,s^*\rangle =\langle b, c\rangle .$
Für jede Optimallösung von (P) gilt dann
$\langle c,x^*\rangle +\langle b,s^*\rangle =\langle b, c\rangle .$

Beweis

Sei $\dim \mathcal{L}=n-m$ . Dann gibt es eine reelle $m\times n$ -Matrix A vom Rang $$A=m$$

mit $\mathcal{L}=\{x\in \mathbbm {R}^n\mid Ax=0\}$ , so dass

$\mathcal{L}+b=\{x\in \mathbbm {R}^n\mid A(x-b)=0\}.$

Mit $A^*\in \mathbbm {R}^{n\times m}$ bezeichnen wir die adjungierte Matrix mit der charakteristischen Eigenschaft

$\langle A^*y, x\rangle =\langle y, Ax\rangle \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x\in \mathbbm {R}^n,\ y\in \mathbbm {R}^m.$

(Hier ist $\mathbbm {R}^m$ mit dem Standard-Skalarprodukt versehen, $\langle y, z\rangle :=y^Tz$ für $y,\, z\in \mathbbm {R}^m$ , das wir ebenfalls mit $\langle .,.\rangle$ bezeichnen.) Dann ist nach einem bekannten Resultat der linearen Algebra

$\mathcal{L}^\perp =\{A^*y\mid y\in \mathbbm {R}^m\}.$

Das konische Programm (P) besitzt die Form (8.1.4) mit $f(x)=\langle c, x\rangle$ , $C=\mathcal{K}$ , $$p=0$$

(keine Ungleichungen) und

Die Lagrangefunktion $L:\mathcal{K}\times \mathbbm {R}^m\rightarrow \mathbbm {R}$ (siehe Definition 8.3.3) für (P) ist deshalb

$L( x, y) = \langle c, x\rangle + \langle y, A( x- b)\rangle .$

1. Wir verwenden die bekannte Eigenschaft

$\inf _{x\in \mathcal{K} {\mathbbm {R}^m}}\sup _{y\in \mathbbm {R}^m}L(x,y)\ge \sup _{y\in \mathbbm {R}^m} \inf _{x\in \mathcal{K} {\mathbbm {R}^m}} L(x, y).$

Nun ist für jedes $x\in \mathcal{K}$

$\sup _{y\in \mathbbm {R}^m}L(x,y)=\left\{ \begin{array}{ll} \langle c, x\rangle ,&{}\ \text{ falls } A(x-b)=0,\\ +\infty , &{}\ \text{ sonst, } \end{array}\right.$

so dass

$\begin{aligned} \inf _{x\in \mathcal{K} {\mathbbm {R}^m}}\sup _{y\in \mathbbm {R}^m}L(x,y)=\inf _{x\in \mathcal{K}\cap (\mathcal{L}+b)}\langle c,x\rangle \le \langle c, x\rangle \end{aligned}$

(8.4.5)

für jede zulässige Lösung x von (P).

Weiter ist für jedes $y\in \mathbbm {R}^m$

$\begin{aligned}\inf _{x\in \mathcal{K}} L(x,y) =&-\langle A^*y,b\rangle + \inf _{x\in \mathcal{K}}\langle c+A^*y,x\rangle \\ =&\left\{ \begin{array}{ll} -\langle y, Ab\rangle ,&{}\ \text{ falls } c+A^*y\in \mathcal{K}^D,\\ -\infty ,&{}\ \text{ sonst. } \end{array} \right. \end{aligned}$

Wegen $\mathcal{L}^\perp =\{A^*y\mid y\in \mathbbm {R}^m\}$ folgt dann

$\begin{aligned} \sup _{y\in \mathbbm {R}^m}\inf _{x\in \mathcal{K} {\mathbbm {R}^m}} L(x,y)= & {} \sup _{y:\; c+A^*y\in \mathcal{K}^D} -\langle A^* y,b\rangle \nonumber \\= & {} \sup _{s:\; s\in \mathcal{K}^D\cap (\mathcal{L}^\perp +c)} -\langle s-c,b\rangle \\\ge & {} -\langle b,s\rangle + \langle b, c\rangle \nonumber \end{aligned}$

(8.4.6)

für jede zulässige Lösung von (D). Die zweite Gleichung nutzt dabei, dass ein Vektor s genau dann die Darstellung $$s=A^*y+c$$

besitzt, wenn $s\in \mathcal{L}^\perp +c$ . Wegen (8.4.5) folgt also für alle zulässigen Lösungen x und s von (P) bzw. (D) die Behauptung

$\langle c,x\rangle +\langle b,s\rangle \ge \langle b, c\rangle .$

2. Falls der Optimalwert $\alpha$ von (P) endlich ist und (P) die Slater-Bedingung erfüllt, gibt es wegen Satz 8.3.4, (3), ein $y^*\in \mathbbm {R}^m$ , so dass

$\alpha =\inf \,\{\langle c,x\rangle \mid x\in \mathcal{K}\cap (\mathcal{L}+b)\}= \inf _{x\in \mathcal{K}}\,L(x, y^*).$

Andererseits folgt

$\begin{aligned}\alpha = \inf _{x\in \mathcal{K}}\,L(x,y^*)\le & {} \sup _{y\in \mathbbm {R}^m}\inf _{x\in \mathcal{K}}\,L(x,y)\\\le & {} \inf _{x\in \mathcal{K}}\sup _{y\in \mathbbm {R}^m}\,L(x, y)\\= & {} \alpha , \end{aligned}$

wobei in der letzten Gleichung (8.4.6) und die Definition von $\alpha$ benutzt werden. Also ist

$\alpha =\inf _{x\in \mathcal{K}}\,L(x,y^*)=\max _{y\in \mathbbm {R}^m}\inf _{x\in \mathcal{K}}\,L(x, y)$

und

ist Optimallösung von

$\sup _{y\in \mathbbm {R}^m}\inf _{x\in \mathcal{K}}\,L(x, y).$

Weiter folgt aus (8.4.5)

$\sup _{y\in \mathbbm {R}^m}\inf _{x\in \mathcal{K}} L(x,y)=\sup \,\{-\langle b,s\rangle +\langle b, c\rangle \mid s\in \mathcal{K}^D\cap (\mathcal{L}^\perp +c)\}.$

Optimallösung der linken Seite ist, folgt aus (8.4.6), dass $$s^*:=A^*y^*+c$$

Optimallösung der rechten Seite, also von (D) ist, und es gilt

$\alpha =-\langle b,s^*\rangle +\langle b, c\rangle .$

Falls (P) zusätzlich eine Optimallösung $$x^*$$

besitzt, ist $\alpha =\langle c, x^*\rangle$ und daher

$\langle c,x^*\rangle + \langle b,s^*\rangle =\langle b, c\rangle .$

Damit ist der Satz bewiesen. $\square$

Da (P) wegen $\mathcal{K}^{DD}=\mathcal{K}$ das duale Programm zu (D) ist, folgt sofort aus dem letzten Satz:

Korollar 8.4.7

Falls beide konischen Programme (P) und (D) (siehe (8.4.2) und (8.4.3)) strikt zulässige Lösungen besitzen, besitzen sie auch Optimallösungen $$x^*$$

bzw.

mit

$\langle c,x^*\rangle + \langle b,s^*\rangle =\langle b, c\rangle .$

8.5 Dualität bei semidefiniten Programmen

Weitere Beispiele konischer Programme, in denen die Dualitätsbeziehungen zwischen (8.4.2) und (8.4.3) in natürlicher Weise auftreten, liefern die sogenannten semidefiniten Programme: In einer Reihe von Anwendungen treten – wie wir in Kap. 16 sehen werden – Optimierungsprobleme auf, bei denen eine unbekannte symmetrische Matrix X so zu bestimmen ist, dass X positiv semidefinit ist und gegebene lineare Gleichungen erfüllt.

Um dies zu präzisieren, bezeichnen wir im Folgenden mit $\mathcal{S}^n$ die Menge $\mathcal{S}^n:=\{A\in \mathbbm {R}^{n\times n}\mid A=A^T\}$ aller reellen n-reihigen symmetrischen Matrizen. Sie ist ein reeller Vektorraum der Dimension $\bar{n}:=n\,(n+1)/2$ (jede Matrix $A=(a_{ik})\in \mathcal{S}^n$ wird durch die $\bar{n}$ Komponenten $a_{ik}$ mit $1\le i\le k\le n$ eindeutig bestimmt). Wir versehen $\mathcal{S}^n$ mit dem Skalarprodukt

$\begin{aligned} \langle X, Z \rangle := \hbox {Spur}\,(X^T Z)= \sum _{i=1}^n\sum _{k=1}^n x_{i,k}z_{i,k}, \quad {\text {f}}{\ddot{\text {u}}}{\text {r }} X=(x_{i,k}),\ Z=(z_{i, k})\in \mathcal{S}^n. \end{aligned}$

(8.5.7)

(Die obige Definition gilt auch für nichtsymmetrische Matrizen $X,\, Z\in \mathbbm {R}^{n\times n}$ ; für symmetrisches X, Z kann man natürlich kürzer $\hbox {Spur}\,(X Z)$ an Stelle von $\hbox {Spur}\,(X^T Z)$ schreiben.) Dieses Skalarprodukt definiert die Frobeniusnorm,

$\left\| X\right\| _F := \sqrt{\langle X,X \rangle } = \sqrt{\sum _{i,j} x_{i, j}^2}.$

In $\mathcal{S}^n$ ist die Menge der symmetrischen positiv semidefiniten Matrizen $\mathcal{S}^n_+$ durch

$\mathcal{S}^n_+:=\{X\in \mathcal{S}^n\mid h^TXh \ge 0 \ {\text {f}}{\ddot{\text {u}}}{\text {r alle}}\,\, h\in \mathbbm {R}^n\}$

gegeben. Man überzeugt sich leicht, dass $\mathcal{S}^n_+$ ein abgeschlossener konvexer Kegel ist. Mit $\mathcal{S}^n_{++}$ bezeichnen wir den Kegel aller positiv definiten Matrizen in $\mathcal{S}^n$ , und wir schreiben kurz $X\succeq 0$ für $X\in \mathcal{S}^n_+$ , und $X\succ 0$ für $X\in \mathcal{S}^n_{++}$ .

Bezüglich des Skalarprodukts (8.5.7) ist nach einem Satz von Féjer der Kegel $\mathcal{S}^n_+$ selbstdual, $\mathcal{S}^n_+=(\mathcal{S}^n_+)^D$ . Er spielt damit in $\mathcal{S}^n$ die gleiche Rolle wie der positive Orthant $\mathbbm {R}^n_+:=\{x\in \mathbbm {R}^n\mid x\ge 0\}$ im $\mathbbm {R}^n$ versehen mit dem Standard-Skalarprodukt $\langle x, y\rangle :=x^Ty$ .

Satz 8.5.2

(Féjer) Eine symmetrische Matrix Z ist positiv semidefinit genau dann, wenn $\langle X, Z\rangle \ge 0$ für alle positiv semidefiniten Matrizen X gilt. Mit anderen Worten: $(\mathcal{S}^n_+)^D=\mathcal{S}^n_+$ .

Beweis

Wir zeigen zunächst $\langle X, Z\rangle \ge 0$ für alle $X,\, Z\in \mathcal{S}^n_+$ . Jede positiv semidefinite Matrix besitzt eine positiv semidefinite Wurzel. (Siehe auch Übung 8.6.) Es folgt daher für $X,\, Z\in \mathcal{S}^n_+$ wegen $\hbox {Spur}\,(AB)=\hbox {Spur}\,(BA)$

$\begin{aligned} \langle X, Z\rangle= & {} \hbox {Spur}\,(XZ^{1/2}Z^{1/2})=\hbox {Spur}\,(Z^{1/2}X Z^{1/2})\\= & {} \hbox {Spur}\,((X^{1/2}Z^{1/2})^T(X^{1/2}Z^{1/2}))\\= & {} \Vert X^{1/2}Z^{1/2}\Vert ^2_F\ge 0. \end{aligned}$

Für den Beweis der Umkehrung möge $\langle X, Z\rangle \ge 0$ für alle $Z\succeq 0$ gelten. Zu jedem Eigenvektor v von X zu einem Eigenwert $\lambda$ von X folgt mit $Z:=vv^T\succeq 0$ , dass

$0\le \langle X, Z\rangle = \hbox {Spur}\,(XZ) = \hbox {Spur}\,(Xvv^T) = \hbox {Spur}\,(v^TXv) = \lambda \Vert v\Vert ^2$

d. h. dass $\lambda \ge 0$ gilt. Somit ist X positiv semidefinit. $\square$

Es ist leicht zu sehen, dass der Kegel $\mathcal{K}:=\mathcal{S}^n_+$ ein nichtleeres Inneres besitzt, nämlich den offenen Kegel $\mathcal{K}^o=\mathcal{S}^n_{++}$ der positiv definiten Matrizen.

Nach diesen Vorbereitungen können wir nun semidefinite lineare Programme wie folgt definieren:

$\begin{aligned} (SDP)\qquad \quad \inf \,\{\langle C, X \rangle \mid X\in \mathcal{S}^n: \ \mathcal{A}(X) = b, \ X \succeq 0\}.\qquad \end{aligned}$

(8.5.3)

Hier ist $C\in \mathcal{S}^n$ eine symmetrische Matrix, $b\in \mathbbm {R}^m$ , und $\mathcal{A}:\mathcal{S}^n\rightarrow \mathbbm {R}^m$ eine lineare Abbildung von $\mathcal{S}^n$ nach $\mathbbm {R}^m$ . Konkret wird die lineare Abbildung $\mathcal{A}$ durch m symmetrische Matrizen $A^{(i)}$ ( $1\le i\le m$ ) gegeben, die jede für sich eine lineare Abbildung $A^{(i)}:\mathcal{S}^n\rightarrow \mathbbm {R}$ , definiert, $\mathcal{S}^n\ni X \mapsto \langle A^{(i)}, X\rangle$ . Dann ist $\mathcal{A}(X)$ gegeben durch

$\begin{aligned} \mathcal{A}(X):=\left( \begin{array}{c}\langle A^{(1)},X \rangle \\ \vdots \\ \langle A^{(m)}, X \rangle \end{array}\right) . \end{aligned}$

(8.5.4)

Wir zeigen, dass (SDP) ein konisches Programm ist. Dazu sei

$\mathcal{L}:= \{X\in \mathcal{S}^n\mid \mathcal{A}(X)=0\}$

der Nullraum der linearen Abbildung $\mathcal{A}$ , und $B\in \mathcal{S}^n$ eine Matrix mit $\mathcal{A}(B)=b$ (falls es keine solche Matrix gibt, ist (SDP) unlösbar, weil es keine zulässigen Lösungen besitzt). Dann hat (SDP) die Form (P) (8.4.2) eines konischen Programms:

$\inf \,\{\langle C, X\rangle \mid X\in \mathcal{S}^n_{+},\ X\in \mathcal{L}+B\}$

Wir bestimmen das dazu duale Problem. Dazu benötigen wir die adjungierte Abbildung $\mathcal{A}^*:\mathbbm {R}^m\rightarrow \mathcal{S}^n$ , die durch die Eigenschaft

$\langle y,\mathcal{A}(X)\rangle :=y^T\mathcal{A}(X) = \langle \mathcal{A}^*(y), X\rangle \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} X\in \mathcal{S}^n,\ y\in \mathbbm {R}^m$

definiert ist. Man bestätigt sofort, dass $\mathcal{A}^*(y)$ durch die symmetrische Matrix

$\mathcal{A}^*(y):=A^{(1)}y_1+\cdots +A^{(m)}y_m$

gegeben ist. Ferner ist

$\mathcal{L}^\perp = \{ S\mid S=\mathcal{A}^*(y), \ \ y\in \mathbbm {R}^m\}.$

Für $S\in \mathcal{L}^\perp$ und $X\in \mathcal{L}$ gilt dann offenbar

$\langle S,X\rangle = \langle \mathcal{A}^*(y),X\rangle = \langle y,\mathcal{A}(X)\rangle = \langle y, 0\rangle =0,$

wie gefordert. Damit ist

$\mathcal{L}^\perp +C=\{\mathcal{A}^*(y)+C\mid y\in \mathbbm {R}^m\}.$

Also ist das zu (SDP) duale konische Programm (vgl. (8.4.3)) durch

$\begin{aligned} \inf \,\{\langle B, S\rangle \mid S=\mathcal{A}^*(y)+C,\ S\succeq 0, \ y\in \mathbbm {R}^m\} \end{aligned}$

(8.5.5)

gegeben.

Sofern (SDP) eine Optimallösung $$X^*$$

besitzt und die Slater-Bedingung für (SDP) erfüllt ist, d. h. hier also, sofern eine Matrix $X\succ 0$ mit $\mathcal{A}(X)=b$ existiert, folgt aus dem Dualitätssatz 8.4.4, dass dann auch (8.5.5) eine Optimallösung $$S^*$$

besitzt und für die Optimalwerte gilt

$\begin{aligned} \langle C,X^* \rangle + \langle B,S^* \rangle = \langle B, C \rangle . \end{aligned}$

(8.5.6)

Wegen

$\begin{aligned} \langle B,S \rangle =\langle B,\mathcal{A}^*(y) + C \rangle= & {} \langle B,\mathcal{A}^*(y) \rangle +\langle B, C \rangle \\= & {} \langle \mathcal{A}(B), y \rangle +\langle B, C \rangle =b^Ty+\langle B, C \rangle \end{aligned}$

kann man als duales Problem von (SDP) auch das konische Problem

$\begin{aligned} \inf \{b^Ty \mid S = \mathcal{A}^*(y) + C, \ S \succeq 0\} \end{aligned}$

(8.5.7)

ansehen. Man beachte, dass sich für (8.5.7) der additive Term $\langle B, C \rangle$ in der Dualitätsbeziehung (8.5.6) weghebt, d. h. der Optimalwert von (8.5.7) stimmt bis auf das Vorzeichen mit dem von (SDP) überein. Ersetzen wir schließlich y durch $$-y$$

erhalten wir aus (8.5.7) das Maximierungsproblem

$\begin{aligned} (DSDP)\quad \sup \{ b^Ty \mid \mathcal{A}^*(y)+S=C, \, S \succeq 0\}\equiv \sup \{ b^Ty \mid \mathcal{A}^*(y)\preceq C\},\qquad \ \end{aligned}$

(8.5.8)

das in der Literatur wegen seiner Analogie zum dualen Problem der linearen Programmierung (vgl. (3.7.1)) als das eigentliche duale Programm zu (SDP) bezeichnet wird. Aus Satz 8.4.4 folgt sofort

Satz 8.5.9

Für die dualen Programme (SDP) und (DSDP) gilt immer

$\inf \ \{ \langle C, X\rangle \mid \mathcal{A}(X)=b,\ X\succeq 0\} \ \ge \ \sup \ \{ b^Ty \mid \mathcal{A}^*(y)+S=C, \ S \succeq 0\},$

sofern eines der beiden Probleme eine zulässige Lösung besitzt. Falls (SDP) strikt zulässige Lösungen besitzt, $\{X\succ 0\mid \mathcal{A}(X)=b\}\ne \emptyset$ , und sein Optimalwert

$\alpha :=\inf \,\{\langle C, X\rangle \mid \mathcal{A}(X)=b, X\succeq 0\}\in \mathbbm {R}$

endlich ist, dann besitzt (DSDP) eine Optimallösung und es gilt

$\alpha =\inf \ \{ \langle C, X\rangle \mid \mathcal{A}(X)=b,\ X\succeq 0\} \ = \ \max \ \{ b^Ty \mid \mathcal{A}^*(y)+S=C, \ S \succeq 0\}.$

Falls (SDP) und (DSDP) strikt zulässige Lösungen besitzen, besitzen sie auch Optimallösungen und es gilt

$\min \ \{ \langle C, X\rangle \mid \mathcal{A}(X)=b,\ X\succeq 0\} \ = \ \max \ \{ b^Ty \mid \mathcal{A}^*(y)+S=C, \ S \succeq 0\}.$

Wenn die Matrix X eine Diagonalmatrix ist, d. h. wenn die linearen Gleichungen $\mathcal{A}(X)=b$ nur für Diagonalmatrizen X erfüllbar sind, dann kann man (SDP) als eine komplizierte Art auffassen, um ein lineares Programm zu formulieren. Der Dualitätssatz stimmt dann mit dem der linearen Programmierung überein (man überlege kurz, dass das wirklich so ist!); allerdings gilt die hier hergeleitete Dualität nur unter der Voraussetzung der Slater-Bedingung. Wir werden später noch auf dieses Paar dualer Programme zurückkommen.

8.6 Übungsaufgaben

1.
Gegeben sei die Menge
$\mathcal{S} := \left\{ x\in \mathbbm {R}^2\mid g_1(x):= x_1^2-x_2\le 0,\ g_2(x):= x_2-x_1 \le 0\right\} .$
Gesucht ist der Punkt $\bar{x}\in \mathcal{S}$ , der zum Punkt den kürzesten Euklidischen Abstand hat.
1. a)
  Lösen Sie die Aufgabe graphisch.
2. b)
  Lösen Sie die Aufgabe durch Auswertung der KKT-Bedingungen.
2.
Sei $\mathcal{K}\not =\emptyset$ eine abgeschlossene, konvexe Teilmenge des $\mathbbm {R}^n$ . Man zeige die folgenden Eigenschaften der Orthogonalprojektion $\bar{x}:=P_{\mathcal{K}}(x)$ von x auf K:
1. a)
  Zu jedem $x\in \mathbbm {R}^n$ gibt es genau ein $\bar{x}\in \mathcal{K}$ mit der Eigenschaft
  $(*)\qquad \qquad \Vert x-\bar{x}\Vert _2 \le \Vert x-y\Vert _2 \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} y\in \mathcal{K}.$
  $\bar{x}$ definiert die Orthogonalprojektion von x auf $\mathcal{K}$ , $P_{\mathcal{K}}(x):=\bar{x}$ .
2. b)
  Bedingung ist äquivalent zu
  $(x-\bar{x})^T(y-\bar{x})\le 0\quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} y\in \mathcal{K}.$
  Hinweis: Man betrachte $\varphi (\lambda ):=\Vert x-\lambda \bar{x} - (1-\lambda ) y\Vert ^2$ .
3. c)
  Es ist
  $\Vert P_{\mathcal{K}}(x)-P_{\mathcal{K}}(y) \Vert _2 \le \Vert x-y\Vert _2 \quad {\text {f}}{\ddot{\text {u}}}{\text {r alle }} x,\, y\in \mathbbm {R}^n.$
  Hinweis: Man setze $P_{\mathcal{K}}(y)$ und $P_{\mathcal{K}}(x)$ geeignet in b) ein und nutze die Cauchy-Schwarzsche Ungleichung aus.
4. d)
  Die (Abstands-)Funktion $\rho (x):=\Vert x-P_{\mathcal{K}}(x)\Vert _2$ ist konvex.
5. e)
  Es gilt $|\rho (x)-\rho (y)|\le \Vert x-y\Vert _2$ für alle $x,\, y\in \mathbbm {R}^n$ .
6. f)
  Falls $\rho$ in einem Punkt $x\in \mathbbm {R}^n\setminus \mathcal{K}$ differenzierbar ist, so gilt
  $\nabla \rho (x)={x-P_{\mathcal{K}}(x)\over \Vert x-P_{\mathcal{K}}(x)\Vert _2}.$
  Hinweis: Man untersuche die Richtungsableitung in Richtung
  $z:=P_{\mathcal{K}}(x)-x$ und nutze Teil e), um die Norm von $\nabla \rho (x)$ abzuschätzen.
3.
Sei $\mathcal{S}:=\{x\in \mathbbm {R}^n\mid f_i(x)\le 0 \ \ (1\le i\le p), \quad a_j^Tx+b_j=0 \ \ (p+1\le j\le m)\}$ mit konvexen Funktionen $f_i:\mathbbm {R}^n\rightarrow \mathbbm {R}$ ( $1\le i\le p$ ) und festen $a_j\in \mathbbm {R}^n,\ b_j\in \mathbbm {R}$ ( $p+1\le j\le m$ ). Sei
$\hat{\mathcal{K}}:= \{(x, x_{n+1})\in \mathbbm {R}^{n+1}\mid x_{n+1}>0,\ \ {x\over x_{n+1}}\in \mathcal{S}\}$
und $\mathcal{K}:=\bar{\hat{\mathcal{K}}}=\overline{\mathrm{cone}}\,\{(x, 1)\mid x\in \mathcal{S}\}$ wie in Abschn. 8.4. Man zeige:
1. a)
  $x\in \mathcal{S}\Longleftrightarrow (x, 1)\in \hat{\mathcal{K}}\Longleftrightarrow (x, 1)\in \mathcal{K}$ .
2. b)
  Die Menge $\hat{\mathcal{K}}\cup \{0\}$ ist genau dann abgeschlossen, wenn $\mathcal{S}$ beschränkt ist.
3. c)
  Sei $x_{n+1}>0$ und $x\in \mathbbm {R}^n$ . Dann ist $(x/x_{n+1}, 1)\in \mathcal{K}$ genau dann, wenn für alle i mit $1\le i\le p$ und alle j mit $p+1\le j\le m$ gilt
  $x_{n+1} f_i\Bigl ({x\over x_{n+1}}\Bigr )\le 0,\quad a_j^Tx+b_j\, x_{n+1} =0.$
4. d)
  Mit ist auch die Funktion $\tilde{f}_i:\{(x, x_{n+1})\in \mathbbm {R}^{n+1}\mid x_{n+1}>0\}\rightarrow \mathbbm {R}$ mit $\tilde{f}_i(x, x_{n+1}):= x_{n+1}f_i({x/x_{n+1}})$ konvex.
4.
Sei $Z\succeq 0$ (d. h. symmetrisch und positiv semidefinit). Man zeige, dass es eine symmetrische Matrix $Z^{1/2}\succeq 0$ gibt (die symmetrische Wurzel von Z) mit $(Z^{1/2})^2=Z$ . (Man nutze die Normalform mit einer unitären Matrix U und einer Diagonalmatrix $D\succeq 0$ .)
5.
Seien konvexe Funktionen $f_i:\mathbbm {R}^n\rightarrow \mathbbm {R}$ für $1\le i\le m$ gegeben. Für $\tilde{x}:= (x^T, t)^T\in \mathbbm {R}^n\times \mathbbm {R}$ definieren wir die Funktionen $\tilde{f}_i:\mathbbm {R}^{n+1}\rightarrow \mathbbm {R}$ durch $\tilde{f}_i(\tilde{x}):=tf_i(x/t)$ . Man zeige, dass auch die $\tilde{f}_i$ konvex sind. Man schreibe das Problem
$\hbox {minimiere}\ c^Tx\ \mid \ f_i(x)\le 0 \ \ {\text {f}}{\ddot{\text {u}}}{\text {r}}\ \ 1\le 1\le m$
mit Hilfe der Funktionen $\tilde{f}_i$ als konisches konvexes Programm.
6.
Sei $\mathcal{K}:= \{x\in \mathbbm {R}^3 \mid x_1\ge \sqrt{x_2^2+x_3^2} \}$ , $\mathcal{L}:=\{ x\in \mathbbm {R}^3\mid x_1=0,\ x_2=x_3\}$ , $c:=0\in \mathbbm {R}^3$ , $b:=(\sqrt{2}, 1,-1)^T$ . Man betrachte das primal-duale Paar von Problemen der Form (8.4.2), (8.4.3)
$(P)\qquad \qquad \min \{c^Tx\mid x\in (b+\mathcal{L})\cap \mathcal{K}\}$
und
$(D)\qquad \qquad \min \{b^Ts\mid s\in (c+\mathcal{L}^\perp )\cap \mathcal{K}^D\}.$
1. a)
  Man zeige $\mathcal{K}=\mathcal{K}^D$ .
2. b)
  Man zeige, dass (P) die Slaterbedingung verletzt.
3. c)
  Man zeige, dass beide Probleme trotzdem eine endliche Optimallösung besitzen und die Optimalwerte sich zu Null addieren. (Vgl. Satz 8.4.4)
4. d)
  Man gebe ein Paar konischer konvexer Programme an, für das das primale Problem und das duale Problem beide die Slaterbedingung verletzen aber beide trotzdem endliche Optimallösungen besitzen, deren Optimalwerte sich zu Null addieren.