Benutzer:Stepri2005/Kurs:Optimierung/Optimalitätskriterien für linear restringierte Optimierungsprobleme

3.1 Das Farkas-Lemma und Folgerungen

Das Hauptziel dieses Kapitels ist es, Optimalitätsbedingungen für lokale Minimalpunkte linear restringierter Optimierungsprobleme bereit zu stellen. Dazu benötigen wir das sog. Farkas-Lemma sowie Folgerungen aus diesem Lemma, das bzw. die wir in diesem Abschnitt beweisen wollen. Für den Beweis des Farkas-Lemmas benötigen wir die folgende Aussage, deren Beweis man überspringen mag. Dabei ist

$\mathbb {R} _{+}^{r}:=\{x\in \mathbb {R} ^{r}{\big |}x\geq 0\}.$

Lemma 3.1

Sei $B\in \mathbb {R} ^{n\times r}$. Dann ist die Menge

(3.1) $D:=\left\{x\in \mathbb {R} ^{n}{\big |}x:=Bz,z\in \mathbb {R} _{+}^{r}\right\}$

nichtleer, konvex und abgeschlossen.

Beweis.

Offenbar ist $x=0$ Element von $D$. Für $x,y\in D$ gilt weiter $x=Bz^{x}$ und $y=Bz^{y}$ mit gewissen $z^{x},z^{y}\in \mathbb {R} _{+}^{r}$. Für $t\in [0,1]$ hat man daher $tz^{x}+(1-t)z^{y}\in \mathbb {R} _{+}^{r}$ sowie

$tx+(1-t)y=tBz^{x}+(1-t)Bz^{y}=B(tz^{x}+(1-t)z^{y}).$

Folglich ist $D$ konvex. Den Beweis der Abgeschlossenheit von $D$ führen wir mittels vollständiger Induktion über die Spaltenzahl von $B$.

Für $B\in \mathbb {R} ^{n\times i}$ setzen wir

$D_{i}(B):=\left\{x\in \mathbb {R} ^{n}{\big |}x:=Bz,\quad z\in \mathbb {R} _{+}^{i}\right\}.$

Für $i=1$ erhalten wir dann mit $B\in \mathbb {R} ^{n\times 1}$ die Halbgerade

$D_{1}(B)=\{y_{1}B{\big |}y_{1}\geq 0\},$

welche, wie man sich leicht klarmacht, abgeschlossen ist. Wir nehmen nun an, dass die Menge $D_{i}(B)$ bei beliebigem $B\in \mathbb {R} ^{n\times i}$ für jedes $i\in \{1,\ldots ,r-1\}$ abgeschlossen ist.

Sei $B\in \mathbb {R} ^{n\times r}$ und $\{x^{l}\}$ eine Folge in $D_{r}(B)$ mit $\lim _{l\to \infty }x^{l}=x^{*}$ für ein $x^{*}$. Insbesondere gilt also $x^{l}=Bz^{l}$ mit einem $z^{l}\geq 0$. Weil die Menge

$\{Bz\in \mathbb {R} ^{n}{\big |}z\in \mathbb {R} ^{r}\}$

ein linearer Teilraum des $\mathbb {R} ^{n}$ und ein solcher abgeschlossen ist, gibt es weiter ein ${\hat {z}}\in \mathbb {R} ^{r}$ mit $x^{*}=B{\hat {z}}$. Da anderenfalls alles gezeigt wäre, nehmen wir an, dass $x^{*}\notin D_{r}(B)$, d. h. ${\hat {z}}\not \geq 0$ für alle ${\hat {z}}\in \mathbb {R} ^{r}$ mit $x^{*}=B{\hat {z}}$ gilt.

Sei nun

$v(t):=t{\hat {z}}+(1-t)z^{l}=z^{l}+t({\hat {z}}-zl)\in \mathbb {R} ^{r},\quad t\in [0,1],$

wobei $z^{l}\geq 0$ und nach unserer Annahme ${\hat {z}}\not \geq 0$ ist. Für jedes $j$ mit ${\hat {z}}_{j}\geq 0$ hat man dann $v(t)_{j}\geq 0$ für alle $t\in [0,1]$ und für jedes $j$ mit ${\hat {z}}_{j}<0$ gilt für $t_{j}:=z_{j}^{l}/(z_{j}^{l}-{\hat {z}}_{j})\in [0,1)$

$v(t_{j})_{j}=0;\quad v(t)_{j}\geq 0,\quad t\in [0,t_{j}].$

Ist weiter

$t_{l}:=\min \left\{{\frac {z_{j}^{l}}{z_{j}^{l}-{\hat {z}}_{j}}}{\Big |}1\leq j\leq r,\quad {\hat {z}}_{j}<0\right\}$

und $v^{l}:=v(t_{l})$, so folgt

(3.2) $v^{l}=t_{l}{\hat {z}}+(1-t_{l})z^{l}\geq 0,\quad v_{j(l)}^{l}=0$ für ein $j(l)\in \{1,\ldots ,r\}$.

Sind $B_{j(l)}\in \mathbb {R} ^{n\times (r-1)}$ und ${\tilde {v}}^{j(l)}\in \mathbb {R} ^{r-1}$ die Matrix und der Vektor, die aus $B$ und $v^{l}$ durch Streichung der $j(l)$-ten Spalte bzw. Komponente hervorgehen, so erhalten wir schließlich

(3.3) ${\tilde {x}}^{l}:=B_{j(l)}{\tilde {v}}^{j(l)}=Bv^{l}=B\left[t_{l}{\hat {z}}+(1-t_{l})z^{l}\right]=t_{l}x^{*}+(1-t_{l})x^{l}=x^{l}+t_{l}(x^{*}-x^{l}).$

Die unendliche Folge $\{j(l)\}$ muss mindestens ein ${\hat {j}}\in \{1,\ldots ,r\}$ unendlich oft enthalten, so dass ${\tilde {x}}^{l_{i}}=B_{\hat {j}}{\tilde {v}}^{\hat {j}}$ mit ${\tilde {x}}^{l_{i}}\in D_{r-1}(B_{\hat {j}})$ für eine Teilfolge $\{{\tilde {x}}^{l_{i}}\}$ von $\{{\tilde {x}}^{l}\}$ folgt. Mit $\lim _{l\to \infty }x^{l}=x^{*}$ ergibt sich aus (3.3) $\lim _{i\to \infty }{\tilde {x}}^{l_{i}}=x^{*}$. Da die Menge $D_{r-1}(B_{\hat {j}})$ nach der Induktionsannahme abgeschlossen ist, erhalten wir $x^{*}\in D_{r-1}(B_{\hat {j}})$, was wegen $D_{r-1}(B_{\hat {j}})\subseteq D_{r}(B)$ der Annahme $x^{*}\notin D_{r}(B)$ widerspricht.

q.e.d.

Das Farkas-Lemma lautet nun:

Lemma 3.2 (Farkas)

Es seien $B\in \mathbb {R} ^{n\times q}$ und $b\in \mathbb {R} ^{n}$ gegeben. Dann besitzt das System

(3.4) $Bx=b,\quad x\geq 0,$

genau dann eine Lösung $x\in \mathbb {R} ^{q}$, wenn das System

(3.5) $B^{T}y\leq 0,\quad b^{T}y>0,$

keine Lösung $y\in \mathbb {R} ^{n}$ hat.

Beweis.

Existiert ein $x\in \mathbb {R} ^{q}$, welches (3.4) erfüllt, so folgt $x^{T}B^{T}y=b^{T}y$ und damit wegen $x\geq 0$ im Fall $B^{T}y\leq 0$ notwendig $b^{T}y\leq 0$. Also hat dann das System (3.5) keine Lösung.

Wir beweisen nun umgekehrt: Besitzt das System (3.4) keine Lösung, d. h. ist $b$ nicht Element der Menge

$D:=\{v\in \mathbb {R} ^{n}{\big |}v:=Bx,\quad x\in \mathbb {R} _{+}^{q}\},$

so hat das System (3.5) eine Lösung. Wir zeigen dazu insbesondere, dass für $b\notin D$ ein Vektor $y\in \mathbb {R} ^{n}$ existiert mit

$v^{T}y\leq 0,\quad v\in D;\quad b^{T}y>0.$

Denn mit $v=Bx$ hat man dann

$v^{T}y=x^{T}B^{T}y\leq 0$

für alle $v\in D$ bzw. für alle $x\geq 0$, woraus man $B^{T}y\leq 0$ erschließt. Nach Lemma 3.1 ist die Menge $D$ nichtleer, konvex und abgeschlossen.

Sei also $b\notin D$. Nach Beispiel 2.34 ist die Zielfunktion des quadratischen Optimierungsproblems

$\min _{v\in D}\|v-b\|^{2}$

gleichmäßig konvex, so dass dieses Problem gemäß Satz 2.41 eine eindeutige Lösung ${\hat {v}}\in D$ besitzt. Weiter ist $\lambda {\hat {v}}\in D$ für alle $\lambda \geq 0$. Wegen der Minimaleigenschaft von ${\hat {v}}$ nimmt die Funktion

$s(\lambda ):=\|\lambda {\hat {v}}-b\|^{2}=\lambda ^{2}{\hat {v}}^{T}{\hat {v}}-2\lambda {\hat {v}}^{T}b+b^{T}b,\quad \lambda \geq 0$

ihr Minimum für $\lambda =1$ an, so dass gilt:

(3.6) $2{\hat {v}}^{T}{\hat {v}}-2{\hat {v}}^{T}b=0$ bzw. ${\hat {v}}^{T}({\hat {v}}-b)=0$.

Sei nun $v\in D$. Dann ist auch ${\hat {v}}+\theta (v-{\hat {v}})\in D$ für alle $\theta \in (0,1)$ und folglich wegen der Optimalität von ${\hat {v}}$

$\|{\hat {v}}-b\|^{2}\leq \|[{\hat {v}}+\theta (v-{\hat {v}})]-b\|^{2},\quad \theta \in (0,1).$

Letzteres impliziert nach Ausmultiplikation der Normen und Streichung identischer Terme auf beiden Seiten der Ungleichung

$0\leq \theta ^{2}(v-{\hat {v}})^{T}(v-{\hat {v}})+2\theta ({\hat {v}}-b)^{T}(v-{\hat {v}}),\quad \theta \in (0,1)$

und somit nach Division durch $2\theta$, Grenzübergang für $\theta \to 0+$ und Anwendung von (3.6):

$0\leq ({\hat {v}}-b)^{T}v.$

Für $y:=b-{\hat {v}}$ bekommt man demnach $v^{T}y\leq 0$ für alle $v\in D$. Mit (3.6) folgt ferner

$b^{T}y=b^{T}(b-{\hat {v}})=(b-{\hat {v}})^{T}(b-{\hat {v}})=y^{T}y\geq 0.$

Da $b\notin D$ und ${\hat {v}}\in D$ ist, ist ${\hat {v}}\neq b$ und daher $y\neq 0$, was schließlich $b^{T}y>0$ impliziert.

q.e.d.

Eine Aussage vom Typ des Farkas-Lemmas bezeichnet man als Alternativsatz. Ein solcher Satz macht eine Aussage der Art, dass ein lineares System genau dann gelöst werden kann, wenn ein anderes lineares System nicht lösbar ist. Eine weitere solche Alternativaussage und eine Folgerung daraus, welche wir brauchen werden, wollen wir als nächstes aus dem Farkas-Lemma ableiten. Mit $(x,y)$ für $x\in \mathbb {R} ^{q}$ und $y\in \mathbb {R} ^{r}$ meinen wir dabei einen Spaltenvektor $(x,y)\in \mathbb {R} ^{q+r}$.

Korollar 3.3

Es seien $B_{1}\in \mathbb {R} ^{n\times q},B_{2}\in \mathbb {R} ^{n\times r}$ und $b\in \mathbb {R} ^{n}$ gegeben. Dann besitzt das System

(3.7) $B_{1}x^{1}+B_{2}x^{2}=b,\quad x^{1}\geq 0$

genau dann eine Lösung $(x^{1},x^{2})\in \mathbb {R} ^{q+r}$, wenn das System

(3.8) $B_{1}^{T}y\leq 0,\quad B_{2}^{T}y=0,\quad b^{T}y>0$

keine Lösung $y\in \mathbb {R} ^{n}$ hat.

Beweis.

Für den Vektor $x^{2}=((x^{2})_{1},\ldots ,(x^{2})_{r})^{T}$ definiere man Vektoren $u\in \mathbb {R} ^{r}$ und $v\in \mathbb {R} ^{r}$ durch

${\begin{array}{lll}u_{i}:=(x^{2})_{i},&v_{i}:=0,&{\text{falls }}(x^{2})_{i}\geq 0,\\u_{i}:=0,&v_{i}:=-(x^{2})_{i},&{\text{falls }}(x^{2})_{i}<0\end{array}}$

für $i=1,\ldots ,r$. Dann gilt $x^{2}=u-v$ mit $u\geq 0,v\geq 0$. Wegen

$b=B_{1}x^{1}+B_{2}x^{2}=B_{1}x^{1}+B_{2}u-B_{2}v={\begin{pmatrix}B_{1}&B_{2}&-B_{2}\end{pmatrix}}\left(x^{1},u,v\right)$

ist das System (3.7) somit äquivalent mit dem System für $x\in \mathbb {R} ^{q+2r}$

${\begin{pmatrix}B_{1}&B_{2}&-B_{2}\end{pmatrix}}x=b,\quad x\geq 0.$

Nach dem Farkas-Lemma besitzt letzteres System genau dann eine Lösung, wenn das System

${\begin{pmatrix}B_{1}&B_{2}&-B_{2}\end{pmatrix}}^{T}y\leq 0,\quad b^{T}y>0$

keine Lösung hat. Offenbar ist letzteres System von Ungleichungen gleichbedeutend mit demjenigen in (3.8).

q.e.d.

Korollar 3.4

Es seien $B_{1}\in \mathbb {R} ^{n\times q},B_{2}\in \mathbb {R} ^{n\times r}$ und $b\in \mathbb {R} ^{n}$ und es existiere ein $z\in \mathbb {R} ^{n}$ mit

(3.9) $B_{1}^{T}z<0,\quad B_{2}^{T}z\leq 0.$

Besitzt dann das System

(3.10) $B_{1}^{T}y<0,\quad B_{2}^{T}y\leq 0,\quad b^{T}y>0$

keine Lösung, so hat das System

$B_{1}x^{1}+B_{2}x^{2}=b,\quad x^{1}\geq 0$

eine Lösung.

Beweis.

Es sei $y\in \mathbb {R} ^{n}$, z. B. $y=0$, Lösung des Systems

(3.11) $B_{1}^{T}y\leq 0,\quad B_{2}^{T}y=0$

und $z\in \mathbb {R} ^{n}$ erfülle die Ungleichungen in (3.9). Für jedes $\lambda >0$ folgt dann

$B_{1}^{T}(y+\lambda z)<0,\quad B_{2}^{T}(y+\lambda z)\leq 0.$

Da das System in (3.10) keine Lösung besitzt, muss ferner $b^{T}(y+\lambda z)\leq 0$ gelten. Grenzübergang für $\lambda \to 0+$ liefert $b^{T}y\leq 0$. Wegen (3.11) hat also das System

$B_{1}^{T}y\leq 0,\quad B_{2}^{T}y=0,\quad b^{T}y>0$

keine Lösung. Die Behauptung folgt nun mit Korollar 3.3.

q.e.d.

3.2 Die Karush-Kuhn-Tucker Bedingungen

Wir betrachten nun das allgemeine restringierte Optimierungsproblem

${\begin{array}{lll}({\mathcal {P}}):&{\text{Minimiere}}&f(x)\\&{\text{u. d. N.}}&h_{j}(x)=0\quad (j=1,\ldots ,m),\\&&g_{i}(x)\leq 0\quad (i=1,\ldots ,l).\end{array}}$

Die zulässige Menge von $({\mathcal {P}})$ bezeichnen wir mit

(3.12) $Z:=\{x\in \mathbb {R} ^{n}{\big |}h_{j}(x)=0\quad (j=1,\ldots ,m),\quad g_{i}(x)\leq 0\quad (i=1,\ldots ,l)\}.$

Alle Ungleichungen von $({\mathcal {P}})$, die in $x$ strikt erfüllt sind, d. h. für welche $g_{i}(x)<0$ gilt, sind aufgrund der geforderten Stetigkeit der $g_{i}$ und ihrer endlichen Anzahl auch in einer Umgebung von $x$ erfüllt und können damit „lokal“ vernachlässigt werden. Deshalb interessiert, welche Ungleichungen von $({\mathcal {P}})$ in $x\in Z$ aktiv sind, d. h., für welche Ungleichungen $g_{i}(x)=0$ ist. Entsprechend nennen wir

$I(x):=\{i\in \{1,\ldots ,l\}{\big |}g_{i}(x)=0\}$

die Menge der in $x$ aktiven Indizes. Eine Ungleichung, für welche $g_{i}(x)<0$ in $x\in Z$ ist, bezeichnen wir als inaktiv in $x$. Mit $i\notin I(x)$ meinen wir einen zugehörigen Index $i\in \{1,\ldots ,l\}\setminus I(x)$.

Wir führen nun Bedingungen ein, welchen in der restringierten Optimierung eine zentrale Rolle zukommt.

Definition 3.5

Seien $f,g_{i},h_{j}\in C^{1}(\mathbb {R} ^{n})$. Die folgenden Gleichungen und Ungleichungen in den Veränderlichen $(x,\lambda ,\mu )\in \mathbb {R} ^{n+m+l}$ heißen Karush-Kuhn-Tucker- (KKT-)Bedingungen für Problem $({\mathcal {P}})$:

(3.13) $h_{j}(x)=0\quad (j=1,\ldots ,m),$

(3.14) $g_{i}(x)\leq 0\quad (i=1,\ldots ,l),$

(3.15) $\nabla f(x)+\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)+\sum _{i=1}^{l}\mu _{i}\nabla g_{i}(x)=0,$

(3.16) $\mu _{i}g_{i}(x)=0\quad (i=1,\ldots ,l),$

(3.17) $\mu _{i}\geq 0\quad (i=1,\ldots ,l).$

Einen Punkt $x$, zu dem Vektoren $\lambda$ und $\mu$ existieren, so dass für $(x,\lambda ,\mu )$ die KKT-Bedingungen erfüllt sind, nennt man einen KKT-Punkt (von $({\mathcal {P}})$).

Die Bedingungen (3.13) und (3.14) sind gleichbedeutend mit der Forderung, dass $x$ ein zulässiger Punkt für Problem $({\mathcal {P}})$, d. h., dass $x\in Z$ ist. Die Gleichung (3.15) drückt aus, dass sich der Gradient von $f$ als Linearkombination der Gradienten der $g_{i}$ und $h_{j}$ schreiben lässt, wobei die Koeffizienten vor den Gradienten der Funktionen, die zu den Ungleichungsrestriktionen gehören, gemäß (3.17) nichtnegativ sein und der Bedingung (3.16) genügen müssen. Diese Bedingung (3.16) bezeichnet man auch als Komplementaritätsbedingung, weil sie impliziert, dass - also in gewissem Sinne komplementär - mindestens einer der beiden Faktoren $\mu _{i}$ und $g_{i}(x)$ identisch Null sein muss. Man spricht von strikter Komplementaritätsbedingung, wenn zusätzlich $\mu _{i}-g_{i}(x)>0$ gilt, also genau einer der beiden Faktoren in (3.16) für jedes $i$ identisch Null ist.

In Abschnitt 3.3 werden wir zeigen, dass jeder lokale Minimalpunkt $x^{*}$ von Problem $({\mathcal {P}})$ im Fall, dass alle Restriktionen in $({\mathcal {P}})$ linear sind, ein KKT-Punkt von $({\mathcal {P}})$ ist. Für linear restringierte Optimierungsprobleme des Typs $({\mathcal {P}})$ sind also die KKT-Bedingungen notwendige Optimalitätsbedingungen erster Ordnung. (Wie man beweisen kann, sind sie dieses auch für Probleme mit beliebigen Funktionen $f,g_{i},h_{j}\in C^{1}(\mathbb {R} ^{n})$, sofern das zulässige Gebiet $Z$ von $({\mathcal {P}})$ eine sog. Constraint Qualification erfüllt.)

Manche Autoren nennen die Bedingungen (3.13)–(3.17) auch Kuhn-Tucker-Bedingungen und nehmen dabei Bezug auf einen Satz aus dem Jahre 1951 von Kuhn und Tucker. Man stellte später jedoch fest, dass diese Bedingungen bereits 1939 in einer Master-Thesis von Karush angegeben worden waren, so dass man dessen Namen heute zumeist in ihrer Benennung mit einbezieht.

Die Komponenten der Vektoren $\lambda$ und $\mu$ in den KKT-Bedingungen bzw. auch diese Vektoren selbst werden als (Lagrange-)Multiplikatoren bezeichnet. Lagrange hatte schon Optimierungsprobleme mit Nebenbedingungen untersucht, allerdings nur solche mit Gleichungsnebenbedingungen. Deshalb wird auch manchmal nur bei $\lambda$ von Lagrange-Multiplikatoren gesprochen.

Einige Beobachtungen im Zusammenhang mit den KKT-Bedingungen fassen wir in der folgenden Bemerkung zusammen.

Bemerkung 3.6

(i) Wenn keine Restriktionen vorliegen, d. h., wenn $l=m=0$ in Problem $({\mathcal {P}})$ ist, reduzieren sich die Bedingungen (3.13)–(3.17) auf die bekannte Bedingung $\nabla f(x)=0$.

(ii) Da für die $\lambda _{j}$ kein Vorzeichen festgelegt ist, kann man in (3.15) statt $\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)$ auch $-\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)$ schreiben.

(iii) Erfüllt $(x,\lambda ,\mu )$ die KKT-Bedingungen, so ist die Komplementaritätsbedingung

(3.18) $\mu _{i}g_{i}(x)=0\quad (i=1,\ldots ,l)$

in (3.16) wegen $g_{i}(x)\leq 0$ und $\mu _{i}\geq 0$ äquivalent mit der Bedingung

$\sum _{i=1}^{l}\mu _{i}g_{i}(x)=0.$

(iv) Die Funktion

(3.19) $L(x,\lambda ,\mu ):=f(x)+\sum _{j=1}^{m}\lambda _{j}h_{j}(x)+\sum _{i=1}^{l}\mu _{i}g_{i}(x)$

bezeichnet man als Lagrange-Funktion. Mit ihr lässt sich die Beziehung für $\nabla f(x)$ in (3.15) auch schreiben in der Form

$\nabla _{x}L(x,\lambda ,\mu )=0.$

(v) Im Fall $l=0$, d. h. im Fall, dass keine Ungleichungsrestriktionen in $({\mathcal {P}})$ vorliegen, reduzieren sich die KKT-Bedingungen auf das Gleichungssystem

$h_{j}(x)=0\quad (j=1,\ldots ,m),$

$\nabla f(x)+\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)=0.$

Dieses Gleichungssystem, welches aus $n+m$ Gleichungen in den $n+m$ Unbekannten $(x,\lambda )\in \mathbb {R} ^{n+m}$ besteht, lässt sich - nach Streichung von $\mu$ in $L$ - auch in der folgenden Form darstellen:

(3.20) $\nabla _{x}L(x,\lambda )=0,\quad \nabla _{\lambda }L(x,\lambda )=0.$

(vi) Weil $g_{i}(x)=0$ $(i\in I(x))$ gilt, kann man die Komplementaritätsbedingung (3.18) durch die Forderung „$\mu _{i}=0$ $(i\notin I(x))$“ ersetzen. Folglich sind die KKT-Bedingungen (3.13)–(3.17) äquivalent mit dem System

$h_{j}(x)=0\quad (j=1,\ldots ,m),$

$g_{i}(x)\leq 0\quad (i=1,\ldots ,l),$

(3.21) $\nabla f(x)+\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)+\sum _{i\in I(x)}\mu _{i}\nabla g_{i}(x)=0,$

$\mu _{i}\geq 0\quad (i\in I(x)).$

Man beachte aber, dass bei dieser Schreibweise die Anzahl der Summenglieder $\mu _{i}\nabla g_{i}(x)$ von $x$ abhängt und sich daher die Bedingung in (3.21) nicht durch den Gradienten der Funktion

${\tilde {L}}(x,\lambda ,\mu ):=f(x)+\sum _{j=1}^{m}\lambda _{j}h_{j}(x)+\sum _{i\in I(x)}\mu _{i}g_{i}(x)$

ausdrücken lässt, da diese Funktion möglicherweise in $x$ nicht differenzierbar ist.

Für eine konvexe Funktion $f\in C^{1}(\mathbb {R} ^{n})$ ist die Bedingung $\nabla f(x^{*})=0$ hinreichend dafür, dass $x^{*}$ ein (globaler) Minimalpunkt von $f$ ist. Diese Aussage können wir nun als erstes im folgenden Sinne auf restringierte konvexe Optimierungsprobleme verallgemeinern.

Satz 3.7

Es seien $f,g_{i}\in C^{1}(\mathbb {R} ^{n})$ konvexe und die $h_{j}$ affin-lineare Funktionen. Ist $x^{*}$ ein KKT-Punkt von Problem $({\mathcal {P}})$, so ist $x^{*}$ (globale) Lösung von $({\mathcal {P}})$.

Beweis.

Die $h_{j}$ seien dargestellt in der Form $h_{j}(x):=(a^{j})^{T}x-b_{j}$ und $(x^{*},\lambda ^{*},\mu ^{*})$ erfülle die KKT-Bedingungen von $({\mathcal {P}})$. Unter den gegebenen Voraussetzungen ist die zulässige Menge $Z$ von $({\mathcal {P}})$ gemäß Lemma 2.27 konvex. Insbesondere gilt $x^{*}\in Z$. Daher schließt man unter Berücksichtigung von Satz 2.28 und Bemerkung 3.6 (vi) für alle $x\in Z$:

$f(x)-f(x^{*})\geq \nabla f(x^{*})^{T}(x-x^{*})=-\sum _{j=1}^{m}\lambda _{j}^{*}\nabla h_{j}(x^{*})^{T}(x-x^{*})-\sum _{i\in I(x^{*})}\mu _{i}^{*}\nabla g_{i}(x^{*})^{T}(x-x^{*})$

$=\sum _{j=1}^{m}\lambda _{j}^{*}[\underbrace {(a^{j})^{T}x^{*}-b_{j}} _{=0}+\underbrace {b_{j}-(a^{j})^{T}x} _{=0}]-\sum _{i\in I(x^{*})}\underbrace {\mu _{i}^{*}} _{\geq 0}[\underbrace {g_{i}(x)} _{\leq 0}-\underbrace {g_{i}(x^{*})} _{=0}]\geq 0.$

Also ist $x^{*}$ optimal für Problem $({\mathcal {P}})$.

3.3 Abstiegsrichtung und zulässige Richtung

Da wir daran interessiert sind, im Rahmen von Verfahren zur Minimierung einer Funktion den Funktionswert zu verkleinern, führen wir die nachstehende Definition ein.

Definition 3.8

Ein Vektor $p\in \mathbb {R} ^{n}$ heißt Abstiegsrichtung für $f:\mathbb {R} ^{n}\to \mathbb {R}$ in $x\in \mathbb {R} ^{n}$, falls ein $t_{1}>0$ existiert, so dass gilt:

(3.22) $f(x+tp)<f(x),\quad t\in (0,t_{1}].$

Das folgende Lemma stellt eine einfache Bedingung bereit, mit deren Hilfe leicht Abstiegsrichtungen in einem vorgegebenen Punkt angegeben werden können.

Lemma 3.9

Es sei $f\in C^{1}(\mathbb {R} ^{n})$. Gilt für $p$

$\nabla f(x)^{T}p<0,$

so ist $p$ Abstiegsrichtung für $f$ in $x$.

Beweis.

Die Definition der Richtungsableitung von $f$ bei $x$ in Richtung $p$ liefert

(3.23) $\lim _{t\to 0+}{\frac {f(x+tp)-f(x)}{t}}=\nabla f(x)^{T}p<0.$

Folglich gilt für ein $t_{1}>0$

${\frac {f(x+tp)-f(x)}{t}}<0,\quad t\in (0,t_{1}].$

Somit ist (3.22) richtig.

Bemerkung 3.10

Im Fall $\nabla f(x)\neq 0$ ist offenbar

$p:=-\nabla f(x)$

gemäß Lemma 3.9 eine Abstiegsrichtung für $f$ in $x$.

Nach (3.23) hat man für alle genügend kleinen $t\geq 0$

$f(x+tp)-f(x)=t\nabla f(x)^{T}p+\varepsilon (t)$

mit $\varepsilon (t)/t\to 0$ für $t\to 0+$. Speziell folgt im Fall einer linearen Funktion, also im Fall $f(x):=c^{T}x$ für ein $c\in \mathbb {R} ^{n}$, dass $\varepsilon (t)=0$ ist, denn in diesem Fall hat man $\nabla f(x)=c$ und somit

$c^{T}(x+tp)-c^{T}x=t\nabla f(x)^{T}p.$

Im Hinblick auf einen möglichst großen Abstieg für $f$ in $x$, also einen möglichst kleinen Wert $f(x+tp)-f(x)$, macht es demnach Sinn, nach einer auf 1 normierten Richtung $p$ zu fragen, welche im Fall $\nabla f(x)\neq 0$ das Problem

(3.24) ${\begin{array}{ll}{\text{Minimiere}}&\nabla f(x)^{T}p\\{\text{u. d. N.}}&\|p\|=1\end{array}}$

löst. Die eindeutige Lösung dieses Problems ist

$p^{*}:=-\nabla f(x)/\|\nabla f(x)\|.$

(Denn mit der Cauchy-Schwarz-Ungleichung kann man den Zielfunktionswert von Problem (3.24) für alle zulässigen $p$ durch

(3.25) $\nabla f(x)^{T}p\geq -\|\nabla f(x)\|\|p\|=-\|\nabla f(x)\|$

nach unten abschätzen, wobei die untere Schranke offenbar gerade für $p^{*}$ angenommen wird und damit den Minimalwert des Problems definiert. Die Eindeutigkeit von $p^{*}$ folgt aus der Tatsache, dass man $\nabla f(x)\neq 0$ und $p\neq 0$ hat und daher Gleichheit in der Cauchy-Schwarz-Ungleichung in (3.25) genau dann vorliegt, wenn $p=\lambda \nabla f(x)$ für ein $\lambda \neq 0$ ist. Mit (3.25) ergibt sich für $\lambda$ als einzige mögliche Wahl $\lambda :=-1/\|\nabla f(x)\|$.)

Die Richtung $p:=-\nabla f(x)$ nennt man daher auch die Richtung des steilsten Abstiegs für $f$ in $x$. Man kann sie lokal - und im linearen Fall auch global - als „beste“ Abstiegsrichtung ansehen. Für nichtlineare Funktionen muss sie dies jedoch global gesehen nicht sein. Auch im Gebirge ist ja die Richtung, die vom Standpunkt aus - vielleicht nur für ein kleines Stück - den steilsten Abstieg liefert, global gesehen nicht notwendig die beste Richtung für einen Abstieg ins Tal.

Im Fall linearer Restriktionen stellen wir nun die $h_{j}$ und $g_{i}$ mit Vektoren $a^{j},c^{i}\in \mathbb {R} ^{n}$ und Zahlen $b_{j},d_{i}\in \mathbb {R}$ dar in der Form

(3.26) $h_{j}(x):=(a^{j})^{T}x-b_{j},\quad g_{i}(x):=(c^{i})^{T}x-d_{i}.$

In diesem Fall lautet die zulässige Menge von $({\mathcal {P}})$

(3.27) $Z:=\left\{x\in \mathbb {R} ^{n}{\big |}(a^{j})^{T}x-b_{j}=0\quad (j=1,\ldots ,m),\qquad (c^{i})^{T}x-di\leq 0\quad (i=1,\ldots ,l)\right\}$

und hat man

(3.28) $\nabla h_{j}(x)=a^{j},\quad \nabla g_{i}(x)=c^{i}.$

Lineare Ungleichungs- und Gleichungsrestriktionen gibt man oft auch in Matrix-Vektor-Schreibweise an. Sind $A\in \mathbb {R} ^{m\times n}$ und $C\in \mathbb {R} ^{l\times n}$ die Matrizen mit den Zeilen $(a^{j})^{T}$ bzw. $(c^{i})^{T}$ und $b\in \mathbb {R} ^{l}$ und $d\in \mathbb {R} ^{m}$ die Vektoren mit Komponenten $b_{j}$ bzw. $d_{i}$, so bekommt Problem $({\mathcal {P}})$ die Gestalt

${\begin{array}{ll}{\text{Minimiere}}&f(x)\\{\text{u. d. N.}}&Ax=b,\\&Cx\leq d.\end{array}}$

Insbesondere hat man also

(3.29) $A^{T}={\begin{pmatrix}a^{1}&a^{2}&\ldots &a^{m}\end{pmatrix}},\quad C^{T}={\begin{pmatrix}c^{1}&c^{2}&\ldots &c^{l}\end{pmatrix}}.$

Für Verfahren, die eine Folge von zulässigen Punkten für $({\mathcal {P}})$ generieren (viele Verfahren tun dies nicht), ist es erforderlich, in einem Punkt $x\in Z$ diejenigen Richtungen zu kennen, in die man sich ein Stück von $x$ aus weg bewegen kann, ohne $Z$ zu verlassen und in die man den Funktionswert von $f$ gleichzeitig reduzieren kann. Wir definieren daher weiter:

Definition 3.11

Eine Richtung $p\in \mathbb {R} ^{n}$ heißt zulässige Richtung für $Z$ in $x\in Z$, wenn ein $t_{2}>0$ existiert, so dass gilt:

(3.30) $x+tp\in Z,\quad t\in [0,t_{2}].$

Eine solche Richtung heißt zulässige Abstiegsrichtung für $({\mathcal {P}})$ in $x\in Z$, wenn $p$ auch Abstiegsrichtung für $f$ in $x$ ist.

In diesem Zusammenhang machen wir die folgende Beobachtung.

Lemma 3.12

Die $h_{j}$ und $g_{i}$ seien affin-lineare Funktionen wie in (3.26) und es sei $x\in Z$. Dann ist $p\in \mathbb {R} ^{n}$ genau dann eine zulässige Richtung in $x$, wenn $p$ folgendes System löst:

(3.31) $(a^{j})^{T}p=0\quad (j=1,\ldots ,m),\qquad (c^{i})^{T}p\leq 0\quad (i\in I(x)).$

Beweis.

Sei $x\in Z$ und $p\in \mathbb {R} ^{n}$ Lösung von (5.3). Dann gilt

(3.32) $j=1,\ldots ,m:\quad (a^{j})^{T}(x+tp)-b_{j}=t(a^{j})^{T}p=0,\quad t>0,$

(3.33) $i\in I(x):\quad (c^{i})^{T}(x+tp)-d_{i}=t(c^{i})^{T}p\leq 0,\quad t>0.$

Ferner hat man mit hinreichend kleinen $\tau _{i}>0$

$i\notin I(x):\quad (c^{i})^{T}(x+tp)-d_{i}=\overbrace {(c^{i})^{T}x-d_{i}} ^{<0}+t(c^{i})^{T}p\leq 0,\quad t\in (0,\tau _{i}].$

Also impliziert (5.3) die Bedingung (3.30) mit $t_{2}:=\min _{i\notin I(x)}\tau _{i}$. Umgekehrt schließt man sofort mit der Bedingung (3.30), dass (3.32) und (3.33) gültig und damit die Beziehungen in (5.3) erfüllt sind.

q.e.d.

Erfüllt $p$ also die Bedingungen in (5.3) und ist zusätzlich $\nabla f(x)^{T}p<0$, so ist $p$ offenbar zulässige Abstiegsrichtung für Problem $({\mathcal {P}})$ im linear restringierten Fall.

3.4 Optimalitätsbedingungen für Probleme mit linearen Restriktionen

Wir betrachten nun den Fall eines linear restringierten Optimierungsproblems. Die Nebenbedingungen und der zulässige Bereich haben also die Form wie in (3.26) und (3.27). Für diesen Fall können wir die folgende wichtige Aussage beweisen.

Satz 3.13

Sei $f\in C^{1}(\mathbb {R} ^{n})$ und seien die $g_{i}$ und $h_{j}$ affin-linear. Ist $x^{*}$ lokale Lösung von $({\mathcal {P}})$, dann ist $x^{*}$ ein KKT-Punkt von $({\mathcal {P}})$.

Beweis.

Die $g_{i}$ und $h_{j}$ seien wie in (3.26) dargestellt. Da $x^{*}$ eine lokale Lösung des Problems $({\mathcal {P}})$ ist, ist $x^{*}\in Z$ und kann es keine zulässige Abstiegsrichtung für $f$ in $x^{*}$ bezüglich $Z$ geben. Mit Lemma 3.12 können wir somit schließen, dass das System

$(a^{j})^{T}p=0\quad (j=1,\ldots ,m),\qquad (c^{i})^{T}p\leq 0\quad (i\in I(x^{*})),\qquad -\nabla f(x^{*})^{T}p>0$

keine Lösung besitzt. Korollar 3.3 garantiert daher die Existenz von Multiplikatoren $\lambda _{j}^{*}$ und $\mu _{i}^{*}\geq 0$, so dass mit (3.28) gilt:

(3.34) $\sum _{j=1}^{m}\lambda _{j}^{*}a^{j}+\sum _{i\in I(x^{*})}\mu _{i}^{*}c^{i}=\sum _{j=1}^{m}\lambda _{j}^{*}\nabla h_{j}(x^{*})+\sum _{i\in I(x^{*})}\mu _{i}^{*}\nabla g_{i}(x^{*})=-\nabla f(x^{*}).$

Setzen wir $\mu _{i}^{*}:=0$ für $i\notin I(x^{*})$, so folgt die Behauptung.

q.e.d.

Die KKT-Bedingungen sind also notwendige Optimalitätsbedingungen erster Ordnung für das Optimierungsproblem $({\mathcal {P}})$, wenn alle Nebenbedingungen darin linear sind. Man beachte aber, dass ein lokaler Minimalpunkt von $({\mathcal {P}})$ kein KKT-Punkt von $({\mathcal {P}})$ sein muss, wenn mindestens ein $g_{i}$ eine nichtlineare konvexe Funktion ist. Für linear restringierte konvexe und somit insbesondere für konvexe quadratische Probleme können wir aber noch aus den Sätzen 3.7 und 3.13 zusammenfassend schließen:

Korollar 3.14

Sei $f\in C^{1}(\mathbb {R} ^{n})$ konvex und seien die $g_{i}$ und $h_{j}$ affin-linear. Es ist $x^{*}$ genau dann Lösung von Problem $({\mathcal {P}})$, wenn $x^{*}$ ein KKT-Punkt von $({\mathcal {P}})$ ist.

Beispiel 3.15

Berechnen Sie den eindeutigen KKT-Punkt und den zugehörigen eindeutigen Multiplikator des Problems

${\begin{array}{ll}{\text{Minimiere}}&f(x_{1},x_{2},x_{3}):=-x_{1}x_{2}-x_{2}x_{3}-x_{1}x_{3}\\{\text{u. d. N.}}&h(x_{1},x_{2},x_{3}):=x_{1}+x_{2}+x_{3}-3=0.\end{array}}$

Die KKT-Bedingungen (3.13)–(3.17) lauten in diesem Fall

${\begin{matrix}&-x_{2}&-x_{3}&+\lambda &=0,\\-x_{1}&&-x_{3}&+\lambda &=0,\\-x_{1}&-x_{2}&&+\lambda &=0,\\x_{1}&+x_{2}&+x_{3}&&=3.\end{matrix}}$

Dieses Gleichungssystem hat die eindeutige Lösung $x_{1}^{*}=x_{2}^{*}=x_{3}^{*}=1,\lambda ^{*}=2$. Die Zielfunktion $f$ des Problems kann mit

(3.35) $Q:={\begin{pmatrix}0&-1&-1\\-1&0&-1\\-1&-1&0\end{pmatrix}}$

in der Form $f(x)={\frac {1}{2}}x^{T}Qx,x\in \mathbb {R} ^{3}$, geschrieben werden. Da $Q$, wie man ausrechnet, die Eigenwerte $-2,1,1$ hat, ist $f$ nicht konvex und sind somit die KKT-Bedingungen für dieses Problem keine hinreichenden Optimalitätsbedingungen. Der Punkt $x^{*}=(1,1,1)^{T}$ kann somit zunächst nur als ein Punkt identifiziert werden, der mit $\lambda ^{*}$ die Optimalitätsbedingungen erster Ordnung erfüllt und somit ein Kandidat für einen lokalen Minimalpunkt des Problems ist.

---

Wir wollen uns noch weitere Beispiele anschauen.

Beispiel 3.16

(1) Es sei $Q\in \mathbb {R} ^{n\times n}$ symmetrisch und es seien $c\in \mathbb {R} ^{n},A\in \mathbb {R} ^{m\times n}$ und $b\in \mathbb {R} ^{m}$. Man betrachte das quadratische Optimierungsproblem

(3.36) ${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&Ax=b,\\&x\geq 0.\end{array}}$

Schreibt man

${\begin{array}{ll}h_{j}(x):=(a^{j})^{T}x-b_{j}&(j=1,\ldots ,m),\\g_{i}(x):=-x_{i}=-(e^{i})^{T}x&(i=1,\ldots ,n),\end{array}}$

wobei $e^{i}$ die $i$-te Spalte der Einheitsmatrix und $a^{j}$ die $j$-te Spalte von $A^{T}$ ist (vgl. (3.29)), so ergibt sich

$\sum _{j=1}^{m}\lambda _{j}\nabla h_{j}(x)+\sum _{i=1}^{n}\mu _{i}\nabla g_{i}(x)=\sum _{j=1}^{m}\lambda _{j}a^{j}-\sum _{i=1}^{n}\mu _{i}e^{i}=A^{T}\lambda -\mu .$

Verwendet man, wie es häufig getan wird, die Variablen $y_{j}:=-\lambda _{j}$ und $s_{i}:=\mu _{i}$ und berücksichtigt man, dass die Komplementaritätsbedingung $\mu _{i}(-x_{i})=0$ $(i=1,\ldots ,n)$ wegen $x\geq 0$ und $\mu \geq 0$ mit der Gleichung $\mu ^{T}x=0$ äquivalent ist, so gelangt man zu der folgenden Form der KKT-Bedingungen in den Variablen $(x,y,s)$:

(3.37) ${\begin{array}{rl}Ax=b,&x\geq 0,\\Qx+c-A^{T}y-s=0,&s\geq 0,\\x^{T}s=0.&\end{array}}$

Wenn $Q$ positiv semidefinit ist, ist das Problem (3.36) konvex, so dass $x^{*}$ nach Korollar 3.14 genau dann eine Lösung des Problems ist, wenn $y^{*}$ und $s^{*}$ existieren, so dass $(x^{*},y^{*},s^{*})$ das System (3.37) löst.

(2) Wie zuvor seien $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix, $c\in \mathbb {R} ^{n},A\in \mathbb {R} ^{m\times n}$ und $b\in \mathbb {R} ^{m}$ und gegeben sei jetzt das nur gleichungsrestringierte quadratische Optimierungsproblem

(3.38) ${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&Ax=b.\end{array}}$

Mit $y_{j}:=-\lambda _{j}$ lauten die KKT-Bedingungen (3.13)–(3.17) in diesem Fall

${\begin{array}{r}Qx+c-A^{T}y=0,\\Ax=b.\end{array}}$

Dies ist ein lineares Gleichungssystem mit $n+m$ Gleichungen und $n+m$ Unbekannten $(x,y)\in \mathbb {R} ^{n+m}$, welches sich nach Multiplikation der zweiten Gleichung mit $-1$ in der folgenden Matrix-Vektor-Form mit einer symmetrischen Systemmatrix darstellen lässt:

(3.39) ${\begin{pmatrix}Q&-A^{T}\\-A&0\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}=-{\begin{pmatrix}c\\b\end{pmatrix}}.$

Für positiv semidefinites $Q$ ist das Problem (3.38) konvex, so dass $x^{*}$ dieses Problem gemäß Korollar 3.14 genau dann löst, wenn ein $y^{*}$ existiert, so dass $(x^{*},y^{*})$ eine Lösung von (3.39) ist.

Ist $Q$ positiv definit und $\operatorname {Rang} (A)=m$, so ist die Lösungsmenge des Systems $Ax=b$ nichtleer und besitzt das Problem (3.38) genau eine Lösung $x^{*}$ (vgl. Beispiel 2.42). Diese Lösung und den zugehörigen, in diesem Fall eindeutigen Lagrange-Multiplikator kann man explizit angeben, was zumindest für theoretische Zwecke hilfreich ist. Und zwar liefert die erste Gleichung in (3.39) die Identität

(3.40) $x=Q^{-1}A^{T}y-Q^{-1}c.$

Eingesetzt in die zweite Gleichung von (3.39) ergibt sich die Beziehung

$AQ^{-1}A^{T}y-AQ^{-1}c=b.$

Da die Matrix $AQ^{-1}A^{T}$ gemäß Lemma 2.21 invertierbar ist, erhalten wir

(3.41) $y^{*}=\left(AQ^{-1}A^{T}\right)^{-1}\left(b+AQ^{-1}c\right).$

Setzen wir $y^{*}$ in (3.40) ein, so bekommen wir schließlich

(3.42) $x^{*}=Q^{-1}AT\left(AQ^{-1}A^{T}\right)^{-1}\left(b+AQ^{-1}c\right)-Q^{-1}c.$

(3) Seien $A\in \mathbb {R} ^{m\times n}$ mit $\operatorname {Rang} (A)=m$ und $b\in \mathbb {R} ^{m}$ gegeben. Möchte man unter den Lösungen von $Ax=b$ eine hervorheben, so wählt man häufig diejenige, welche unter allen Lösungen die kleinste $l_{2}$-Norm bzw., was äquivalent damit ist, die kleinste quadrierte $l_{2}$-Norm besitzt, welche also das Problem

(3.43) ${\begin{array}{ll}{\text{Minimiere}}&\|x\|^{2}\\{\text{u. d. N.}}&Ax=b\end{array}}$

löst. Dieses Problem ist offenbar ein Spezialfall des Problems (3.38) mit $c:=0$ und der symmetrischen, positiv definiten Matrix $Q:=2I$. Somit ist

$x^{*}=A^{T}\left(AA^{T}\right)^{-1}b$

die eindeutige Lösung von Problem (3.43) und

$y^{*}=2\left(AA^{T}\right)^{-1}b$

der zugehörige Multiplikator. Da die Matrix $A^{T}\left(AA^{T}\right)^{-1}$ eine (spezielle) Lösung des Systems $Ax=b$ liefert und im Fall $m=n$ mit $A^{-1}$ identisch ist, bezeichnet man sie als (Moore-Penrose-)Pseudoinverse von $A$.

Um $x^{*}$ im Einzelfall zu erhalten, bestimmt man den Vektor $v^{*}:=\left(AA^{T}\right)^{-1}b$, indem man die eindeutige Lösung des linearen Gleichungssystems $\left(AA^{T}\right)v=b$ berechnet. Da die Matrix $AA^{T}$ nach Lemma 2.21 positiv definit ist, bietet sich dafür eine Cholesky-Zerlegung an.

---