Benutzer:Stepri2005/Kurs:Optimierung II/Optimalitätskriterien für nichtlineare Optimierungsprobleme mit Nebenbedingungen

In diesem Kapitel wollen wir Optimalitätsbedingungen erster und zweiter Ordnung für die nichtlineare Optimierung unter Nebenbedingungen bereit stellen. Dazu gehören vor allem wieder die Karush-Kuhn-Tucker- (KKT-)Bedingungen, die ja in der Optimierung mit Restriktionen eine ähnlich wichtige Rolle für Algorithmen spielen, wie es die Bedingung $\nabla f(x^{*})=0$ in der unrestringierten Optimierung tut.

9.1 Das restringierte Optimierungsproblem

Von jetzt an betrachten wir das folgende Optimierungsproblem mit endlich vielen Gleichungs- und Ungleichungsnebenbedingungen, wobei wieder über $x\in \mathbb {R} ^{n}$ zu minimieren ist:

${\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

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

Wir gehen hier der Einfachheit halber davon aus, dass die Funktionen $f,g_{i}$ und $h_{j}$ mindestens einmal und erforderlichenfalls auch zweimal stetig auf dem $\mathbb {R} ^{n}$ differenzierbar sind.

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)$. In diesem Zusammenhang hat man die folgende intuitiv einleuchtenden Aussagen.

Lemma 9.1

(i) $x^{*}$ ist genau dann ein lokaler Minimalpunkt von $({\mathcal {P}})$, wenn $x^{*}$ ein lokaler Minimalpunkt von

${\begin{array}{ll}\left({\mathcal {P}}^{\#}\right):&Minimiere\ f(x)\ {\ddot {u}}ber\ alle\ x\in Z^{\#}\end{array}}$

ist für

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

(ii) Ist $x^{*}$ ein lokaler Minimalpunkt von $({\mathcal {P}})$, so ist $x^{*}$ auch ein lokaler Minimalpunkt von

${\begin{array}{ll}({\mathcal {P}}^{*}):&Minimiere\ f(x)\ {\ddot {u}}ber\ alle\ x\in Z^{*}\end{array}}$

für

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

Beweis.

Übung!

Würde man die in einer lokalen Lösung von $({\mathcal {P}})$ aktiven Restriktionen kennen, so könnte man also die für diese Lösung inaktiven Restriktionen von Vorneherein im Problem streichen. Im Hinblick auf die Erfüllung notwendiger Optimalitätsbedingungen könnte man sogar alle anderen Ungleichungen als Gleichungen behandeln. Da die Anzahl der mit Gleichheit in einem Punkt x^* erfüllten Nebenbedingungen typischerweise kleiner oder gleich der Zahl der Variablen des Problems ist, also hier typischerweise $|I(x^{*})|+m\leq n$ angenommen werden kann, übersteigt die Zahl der Ungleichungsrestriktionen, die keine Rolle für die gefundene Lösung spielen, die Zahl der aktiven Restriktionen in der Praxis oft beträchtlich. Es bietet sich daher zumindest für Probleme mit sehr vielen Ungleichungsnebenbedingungen an, Lösungsstrategien zu entwickeln, die in der aktuellen Näherung nur die aktiven Restriktionen oder nur eine kleine Teilmenge von Restriktionen verwenden, welche z. B. die aktiven und fast aktive Restriktionen umfasst.

Die zulässige Menge $Z$ von Problem $({\mathcal {P}})$ kann auch dann konvex sein, wenn unter den $g_{i}$ und $h_{j}$ nichtkonvexe Funktionen sind. Zumeist ist aber in einem solchen Fall die Konvexität von $Z$ nicht erkennbar, so dass man ein derartiges Problem als ein nichtkonvexes Problem behandeln muss. Abweichend von der in Optimierung I gegebenen Definition, dass ein Optimierungsproblem konvex heißt, wenn $f$ eine konvexe Funktion und $Z$ eine konvexe Menge ist und Bezug nehmend auf Lemma 2.27 aus Optimierung I nennen wir daher der Einfachheit halber von nun an das Problem $({\mathcal {P}})$ konvex, wenn gilt:

(9.2) $f,g_{i}$ sind konvex und $h_{j}$ sind affin-linear.

Anderenfalls sprechen wir bei $({\mathcal {P}})$ von einem (nichtkonvexen) nichtlinearen Problem.

In Übereinstimmung mit der in Optimierung I gegebenen Definition sagen wir weiter, dass $({\mathcal {P}})$ ein quadratisches Optimierungsproblem ist im Fall

$f$ ist quadratisch und $g_{i},h_{j}$ sind affin-linear.

Von besonderem Interesse sind bekanntlich konvexe quadratische Optimierungsprobleme, d. h. quadratische Optimierungsprobleme mit konvexer Zielfunktion $f$. Schließlich heißt das Problem $({\mathcal {P}})$ ja ein lineares Optimierungsproblem, wenn gilt:

$f,g_{i},h_{j}$ sind affin-linear.

Die $g_{i}$ und $h_{j}$ haben dann mit Vektoren $a^{j},c^{i}\in \mathbb {R} ^{n}$ und Zahlen $b_{j},d_{i}\in \mathbb {R}$ die Form

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

mit Gradienten

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

9.2 Die Karush-Kuhn-Tucker Bedingungen

Die folgende Definition war in Optimierung 1 gegeben worden.

Definition 9.2

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}})$:

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

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

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

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

(9.9) $\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}})$).

Für Erläuterungen zu den KKT-Bedingungen und für Beispiele, für die wir die KKT-Bedingungen aufgestellt hatten, verweisen wir auf die Optimierung I. Dort findet man auch den folgenden Satz, den wir wegen seiner Bedeutung für die Betrachtungen hier wiederholen.

Satz 9.3

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}})$.

In Optimierung I war weiter gezeigt und verwendet worden, dass die KKT-Bedingungen für linear restringierte nichtlineare Optimierungsprobleme notwendige Optimalitätsbedingungen erster Ordnung darstellen:

Satz 9.4

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}})$.

Für linear restringierte konvexe Optimierungsprobleme konnten wir schließen, indem wir die letzten beiden Sätze kombinierten:

Korollar 9.5

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.

Wenn $({\mathcal {P}})$ ein lineares oder konvexes Problem ist, spricht man bei lokalen Lösungen auch einfach von Lösungen des Problems.

Das folgende Beispiel zeigt nun, dass die KKT-Bedingungen ohne eine Zusatzvoraussetzung an das Problem keine notwendigen Optimalitätsbedingungen für allgemeine nichtlineare Probleme darstellen müssen.

Beispiel 9.6

Man betrachte die folgende Aufgabe:

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

Offenbar ist $x^{*}:=(1,0)^{T}$ die globale Lösung dieses Problems und gilt $I(x^{*})=\{1,3\}$. Die Bedingung (9.7) der KKT-Bedingungen lautet in diesem Fall

(9.10) ${\begin{pmatrix}-1\\0\end{pmatrix}}+\mu _{1}^{*}{\begin{pmatrix}0\\1\end{pmatrix}}+\mu _{3}^{*}{\begin{pmatrix}0\\-1\end{pmatrix}}={\begin{pmatrix}0\\0\end{pmatrix}}.$

Das lineare Gleichungssystem (9.10) besitzt offenbar keine Lösung. Somit ist $x^{*}$ in diesem Fall kein KKT-Punkt.

---

Es existieren eine Reihe unterschiedlicher Annahmen, die zum Ziel haben, eine Situation wie sie im letzten Beispiel auftritt, auszuschließen. Da sich diese in irgendeiner Weise auf die Restriktionen bzw. das durch sie definierte zulässige Gebiet beziehen, spricht man in der englischsprachigen Literatur bei einer solchen Annahme von einer Constraint Qualification (CQ) („Qualification“ heißt Vorbedingung). Die am häufigsten verwendete Bedingung ist die in der folgenden Definition angegebene, die in Beispiel 9.6 offenbar nicht erfüllt ist.

Definition 9.7

Es seien $g_{i},h_{j}\in C^{1}(\mathbb {R} ^{n})$. Die Linear-Independence-Constraint-Qualification (LICQ) ist in $x\in Z$ erfüllt, wenn gilt:

(9.11) $\nabla h_{j}(x)\quad (j=1,\ldots ,m),\quad \nabla g_{i}(x)\quad (i\in I(x))$ sind linear unabhängig.

Im Fall, dass die LICQ erfüllt ist, hat man:

Lemma 9.8

Sind $f,g_{i},h_{j}\in C^{1}(\mathbb {R} ^{n})$ und ist $x^{*}$ ein Punkt, in dem die LICQ gilt und für den mit Multiplikatoren $\lambda ^{*}$ und $\mu ^{*}$ die KKT-Bedingungen erfüllt sind, dann sind $\lambda ^{*}$ und $\mu ^{*}$ eindeutig.

Beweis.

Übung!

Man kann nun mit einigem Aufwand beweisen (siehe [GeiKa02]):

Satz 9.9

Seien $f,g_{i},h_{j}\in C^{1}(\mathbb {R} ^{n})$. Ist $x^{*}$ lokale Lösung von Problem $({\mathcal {P}})$ und ist die LICQ in $x^{*}$ erfüllt, dann ist $x^{*}$ ein KKT-Punkt von $({\mathcal {P}})$.

Ob die LICQ tatsächlich in einem mit einem Verfahren berechneten Punkt erfüllt ist, prüft man zumeist nicht nach.

Im Hinblick auf die Berechnung eines KKT-Punktes für nichtlineare Probleme untersuchen wir als nächstes ein Beispiel.

Beispiel 9.10

Wir betrachten das Problem

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

Mit Lemma 1.13 prüft man leicht nach, dass $f$ gleichmäßig konvex ist und dass die $g_{i}$ konvex sind. Weiter ist $g_{i}(0)<0$ $(i=1,2)$. Also ist das zulässige Gebiet des Problems nichtleer. Insbesondere hat somit das Problem eine eindeutige Lösung $x^{*}\in \mathbb {R} ^{2}$ (Satz 1.9).

Weiter ist ein Punkt $x^{*}$ ein KKT-Punkt des Problems und damit nach Satz 9.3 Lösung des Problems, wenn $x^{*}$ zulässig ist und Multiplikatoren $\mu _{1}^{*}\geq 0$ und $\mu _{2}^{*}\geq 0$ existieren, so dass $(x^{*},\mu _{1}^{*},\mu _{2}^{*})$ das folgende System löst:

(9.12) $\nabla f(x)+\mu _{1}\nabla g_{1}(x)+\mu _{2}\nabla g_{2}(x)=0,$

(9.13) $\mu _{i}g_{i}(x)=0\quad (i=1,2).$

Dieses System besteht aus 4 Gleichungen in 4 Unbekannten und lautet ausgeschrieben wie folgt:

${\begin{array}{r}4x_{1}+2x_{2}-10+2\mu _{1}x_{1}+3\mu _{2}=0,\\2x_{1}+2x_{2}-10+2\mu _{1}x_{2}+\mu _{2}=0,\\\mu _{1}\left(x_{1}^{2}+x_{2}^{2}-5\right)=0,\\\mu _{2}(3x_{1}+x_{2}-6)=0.\end{array}}$

Man hat nun zumindest eine Lösung $(x^{*},\mu ^{*})$ dieses Systems zu berechnen, für die $x^{*}$ zulässig und $\mu ^{*}$ nichtnegativ ist. (Zum Beispiel ist auch $x^{*}=(0,5)^{T}$ und $\mu ^{*}=(0,0)^{T}$ eine Lösung des Systems, aber $x^{*}$ ist nicht zulässig.) Bei einem so kleinen Problem kann man sich die Arbeit etwas erleichtern, indem man versuchsweise einzelne oder alle $\mu _{i}$ gleich 0 setzt. (Typischerweise liegt eine Lösung des Problems auf dem Rand des zulässigen Gebietes, d. h., ist mindestens eine Restriktion in ihr aktiv.) Wie man durch Einsetzen von $x^{*}$ und $\mu ^{*}$ für den Fall $\mu _{2}=0$ erkennt, besitzt das resultierende System die Lösung $x^{*}=(1,2)^{T}$ und $\mu ^{*}=(1,0)^{T}$, wobei $x^{*}$ offenbar zulässig und damit die (globale) Lösung des Problems ist. (Man hat $I(x^{*})=\{1\}$ und $\nabla g_{1}(x^{*})=(2,4)^{T}$, so dass die LICQ in $x^{*}$ erfüllt ist und folglich die KKT-Bedingungen auch notwendige Optimalitätsbedingungen für die Lösung $x^{*}$ sind.)

In der Praxis stellt die hier aufgezeigte Vorgehensweise aber keine effiziente Methode zur Bestimmung einer Lösung eines nichtlinearen Optimierungsproblems dar. So ist es insbesondere sinnvoll, während des Lösungsprozesses zu untersuchen, ob die erzeugten Näherungen zulässig sind oder ob zumindest der Grad der Verletztheit der Restriktionen abnimmt.

---

9.3 Optimalitätsbedingungen zweiter Ordnung

In der Theorie numerischer Verfahren für nichtlineare restringierte Optimierungsprobleme spielen auch Optimalitätsbedingungen zweiter Ordnung für Problem $({\mathcal {P}})$ eine wichtige Rolle, in der Praxis ist ihre Überprüfung aber meist zu aufwändig. Solche Bedingungen enthalten im Allgemeinen eine Bedingung für die Hesse-Matrix bezüglich $x$ der Lagrange-Funktion zu $({\mathcal {P}})$. Diese lautet

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

und ihre Hesse-Matrix bezüglich $x$ ist im Fall $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$ gegeben durch

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

Es gibt nun zahlreiche Varianten solcher Bedingungen zweiter Ordnung. Hier wollen wir im Fall notwendiger Optimalitätsbedingungen solche angeben, welche die LICQ als Constraint Qualification voraussetzen (s. [GeiKa02]):

Satz 9.11

Seien $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$. Ist $x^{*}$ lokale Lösung von Problem $({\mathcal {P}})$ und ist die LICQ in $x^{*}$ erfüllt, dann ist $x^{*}$ ein KKT-Punkt von $({\mathcal {P}})$ und es gilt mit den zu $x^{*}$ gehörigen Multiplikatoren $\lambda ^{*}$ und $\mu ^{*}$

$s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s\geq 0,\quad s\in {\hat {\Sigma }}$

für

${\hat {\Sigma }}:=\left\{s\in \mathbb {R} ^{n}{\big |}\nabla h_{j}(x^{*})^{T}s=0\ (j=1,\ldots ,m),\quad \nabla g_{i}(x^{*})^{T}s=0\ (i\in I(x^{*}))\right\}.$

Um zu hinreichenden Optimalitätsbedingungen zweiter Ordnung für beliebige Probleme des Typs $({\mathcal {P}})$ mit Funktionen $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$ zu gelangen, genügt es nicht, statt der positiven Semidefinitheit bezüglich $x$ auf ${\hat {\Sigma }}$ die positive Definitheit der Hesse-Matrix der Lagrange-Funktion auf ${\hat {\Sigma }}$ vorauszusetzen, sondern man hat diese auf einem Oberraum ${\tilde {\Sigma }}$ von ${\hat {\Sigma }}$ zu fordern. Da wir den folgenden Satz weiter unten benötigen, wollen wir ihn auch beweisen.

Satz 9.12

Es seien $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$. Ist $x^{*}$ ein KKT-Punkt von Problem $({\mathcal {P}})$ und gilt für zugehörige Multiplikatoren $\lambda ^{*}$ und $\mu ^{*}$

$s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s>0,\quad s\in {\tilde {\Sigma }}$

mit

${\tilde {\Sigma }}:=\left\{s\in \mathbb {R} ^{n}{\big |}\nabla h_{j}(x^{*})^{T}s=0\ (j=1,\ldots ,m),\quad \nabla g_{i}(x^{*})^{T}s=0\ (i\in J(x^{*}))\right\}$

und

$J(x^{*}):=\{i\in I(x^{*}){\big |}\mu _{i}^{*}>0\},$

so ist $x^{*}$ strikt lokale Lösung von $({\mathcal {P}})$.

Beweis.

Nach Voraussetzung genügt $(x^{*},\lambda ^{*},\mu ^{*})$ den KKT-Bedingungen von $({\mathcal {P}})$ und ist damit $x^{*}\in Z$. Sei $x^{*}$ keine strikt lokale Lösung von $({\mathcal {P}})$. Dann ist $x^{*}$ insbesondere kein isolierter Punkt von $Z$ und es existiert daher eine Folge $\left\{y^{k}\right\}$ mit

$y^{k}\in Z,\quad f(y^{k})\leq f(x^{*}),\quad \lim _{k\to \infty }y^{k}=x^{*}.$

Wir schreiben nun $y^{k}$ in der Form

$y^{k}:=x^{*}+\delta _{k}s^{k},\quad s^{k}\in \mathbb {R} ^{n}{\text{ mit }}\left\|s^{k}\right\|=1,\quad \delta _{k}>0.$

Offenbar ist $\lim _{k\to \infty }\delta _{k}=0$ und gibt es wegen der Kompaktheit der Einheitskugel eine Teilfolge $\left\{s^{k_{p}}\right\}$ von $\left\{s^{k}\right\}$ mit $\lim _{p\to \infty }s^{k_{p}}=s^{*}$ für ein $s^{*}\in \mathbb {R} ^{n}$ mit $\left\|s^{*}\right\|=1$. Ohne Beschränkung der Allgemeinheit gelte $\lim _{k\to \infty }s^{k}=s^{*}$.

Für jedes $j\in \{1,\ldots ,m\}$ hat man nun

$0=h_{j}(y^{k})-h_{j}(x^{*})=\left[h_{j}(x^{*}+\delta _{k}s^{*}+\delta _{k}(s^{k}-s^{*}))-h_{j}(x^{*}+\delta _{k}s^{*})\right]+[h_{j}(x^{*}+\delta _{k}s^{*})-h_{j}(x^{*})].$

Dividiert man diese Gleichung durch $\delta _{k}$ und bildet man den Grenzübergang für $k\to \infty$, so konvergiert die erste eckige Klammer gegen 0, wie man unter Anwendung des Satzes von Taylor schließt, so dass man insgesamt erhält:

$\nabla h_{j}(x^{*})^{T}s^{*}=0\quad (j=1,\ldots ,m).$

Analog folgt aus

$f(y^{k})-f(x^{*})\leq 0,\quad g_{i}(y^{k})-\underbrace {g_{i}(x^{*})} _{=0}\leq 0\quad (i\in I(x^{*})),$

dass gilt:

$\nabla f(x^{*})^{T}s^{*}\leq 0,\quad \nabla g_{i}(x^{*})^{T}s^{*}\leq 0\quad (i\in I(x^{*})).$

Für jedes ${\hat {j}}\in J(x^{*})$, sofern ein solches existiert, muss ferner $\nabla g_{\hat {j}}(x^{*})^{T}s^{*}=0$ gelten, da die Beziehung $\nabla g_{\hat {j}}(x^{*})^{T}s^{*}<0$ unter Ausnutzung der Bedingung (9.7)

$\nabla f(x^{*})^{T}s^{*}=-\sum _{j=1}^{m}\lambda _{j}^{*}\underbrace {\nabla h_{j}(x^{*})^{T}s^{*}} _{=0}-\sum _{i\in I(x^{*})\setminus \{{\hat {j}}\}}\underbrace {\mu _{i}^{*}} _{\geq 0}\underbrace {\nabla g_{i}(x^{*})^{T}s^{*}} _{\leq 0}-\underbrace {\mu _{\hat {j}}^{*}} _{>0}\underbrace {\nabla g_{\hat {j}}(x^{*})^{T}s^{*}} _{<0}>0$

einen Widerspruch zu $\nabla f(x^{*})^{T}s^{*}\leq 0$ implizieren würde. Also ist $s^{*}\in {\tilde {\Sigma }}$.

Anwendung des Satzes von Taylor liefert als nächstes, dass für alle $j$ und $i\in I(x^{*})$ Vektoren $\eta _{j}^{k},\vartheta _{i}^{k}\in \mathbb {R} ^{n}$ auf der Verbindungsstrecke von $x^{*}$ und $y^{k}$ existieren, so dass gilt:

(9.16) $0\geq f(y^{k})-f(x^{*})=\delta _{k}\nabla f(x^{*})^{T}s^{k}+{\frac {\delta _{k}^{2}}{2}}\left(s^{k}\right)^{T}\nabla ^{2}f(\eta _{0}^{k})s^{k},$

(9.17) $0=h_{j}(y^{k})-h_{j}(x^{*})=\delta _{k}\nabla h_{j}(x^{*})^{T}s^{k}+{\frac {\delta _{k}^{2}}{2}}\left(s^{k}\right)^{T}\nabla ^{2}h_{j}(\eta _{j}^{k})s^{k},$

(9.18) $0\geq g_{i}(y^{k})-g_{i}(x^{*})=\delta _{k}\nabla g_{i}(x^{*})^{T}s^{k}+{\frac {\delta _{k}^{2}}{2}}\left(s^{k}\right)^{T}\nabla ^{2}g_{i}(\vartheta _{i}^{k})s^{k}.$

Multiplikation von (9.17) mit $\lambda _{j}^{*}$, von (9.18) mit $\mu _{i}^{*}$ und anschließende Addition von (9.16), von (9.17) über $j$ und von (9.18) über $i\in I(x^{*})$ führt weiter unter Ausnutzung der KKT-Bedingungen für $(x^{*},\lambda ^{*},\mu ^{*})$ und insbesondere der Tatsache, dass $\mu _{i}^{*}=0$ für alle $i\notin I(x^{*})$ gilt, zu der Beziehung

$0\geq {\frac {\delta _{k}^{2}}{2}}(s^{k})^{T}\left(\nabla ^{2}f(\eta _{0}^{k})+\sum _{j=1}^{m}\lambda _{j}^{*}\nabla ^{2}h_{j}(\eta _{j}^{k})+\sum _{i=1}^{l}\mu _{i}^{*}\nabla ^{2}g_{i}(\vartheta _{i}^{k})\right)s^{k}.$

Division dieser Ungleichung durch $\delta _{k}^{2}/2$ und anschließender Grenzübergang für $k\to \infty$ liefern wegen $\lim _{k\to \infty }\eta _{j}^{k}=\lim _{k\to \infty }\vartheta _{i}^{k}=x^{*}$ schließlich

$0\geq s^{*T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s^{*}.$

Da $s^{*}\in {\tilde {\Sigma }}$ gezeigt wurde, widerspricht dies aber der vorausgesetzten positiven Definitheit von $\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})$ auf ${\tilde {\Sigma }}$.

q.e.d.

Man beachte, dass für die Mengen ${\hat {\Sigma }}$ und ${\tilde {\Sigma }}$ aus den Sätzen 9.11 und 9.12 die Inklusion ${\tilde {\Sigma }}\supseteq {\hat {\Sigma }}$ gilt. Als Beispiel betrachten wir nochmals Beispiel 3.15 aus der Optimierung I.

Beispiel 9.13

Gegeben sei das Problem

${\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 Zielfunktion $f$ des Problems kann offenbar mit der Matrix

(9.19) $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. Die KKT-Bedingungen sind in diesem Fall ein lineares Gleichungssystem von 4 Gleichungen und 4 Unekannten, das die eindeutige Lösung

$x_{1}^{*}=x_{2}^{*}=x_{3}^{*}=1,\quad \lambda ^{*}=2$

besitzt (vgl. Beispiel 3.15 aus der Optimierung I). Da $Q$, wie man ausrechnet, die Eigenwerte $-2,1,1$ hat, ist $f$ nicht konvex (und somit insbesondere Satz 9.3 hier nicht anwendbar). Der Punkt $x^{*}=(1,1,1)^{T}$ kann daher zunächst nur als ein Kandidat für einen lokalen Minimalpunkt des Problems identifiziert werden.

Man berechnet nun weiter

$\nabla _{xx}^{2}L(x^{*},\lambda ^{*})=-{\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}}+2{\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}=-{\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}}.$

Die Matrix $\nabla _{xx}^{2}L(x^{*},\lambda ^{*})$ entspricht also der Matrix $Q$ in (9.19). Da sie die Eigenwerte $-2,1,1$ hat, ist sie bezüglich des ganzen Raumes $\mathbb {R} ^{n}$ weder positiv noch negativ definit. Mit

${\tilde {\Sigma }}:=\left\{s\in \mathbb {R} ^{3}{\big |}s_{1}+s_{2}+s_{3}=0\right\}$

ist aber für alle $s\in {\tilde {\Sigma }}\setminus \{0\}$

$s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*})s=-s_{1}(s_{2}+s_{3})-s_{2}(s_{1}+s_{3})-s_{3}(s_{1}+s_{2})=+s_{1}^{2}+s_{2}^{2}+s_{3}^{2}>0.$

Nach Satz 9.12 ist also $x^{*}:=(1,1,1)^{T}$ eine strikt lokale Lösung des Problems.

---