3.4. Restringierte Optimierung

In diesem Abschnitt kehren wir zum allgemeinen restringierten Optimierungsproblem (3.1) zurück.Auch hier beginnen wir zunächst mit der Formulierung von Optimalitätsbedingungen, die uns bei der Konstruktion effizienter Optimierungsalgorithmen als Orientierung dienen sollen. Um uns etwas Schreibarbeit zu sparen, nehmen wir in diesem Kapitel, falls nicht ausdrücklich anders gesagt, stets an, dass die Funktionen \(f,g,h\) stetig differenzierbar sind.

Wir stellen allerdings schnell fest, dass Optimalitätsbedingungen im restringierten Fall deutlich anders aussehen, als im unrestringierten Fall, wie das folgende Beispiel zeigt:

Beispiel 3.4

Wir betrachten das restringierte Optimierungsproblem

\[\begin{split}\begin{aligned} \min_{x\in\R}\quad & \sin(x),\\ \text{s.t.}\quad & -x\le0,\\ & x - 2\pi \le 0. \end{aligned}\end{split}\]

Dieses Problem besitzt das globale Minimum \(x^\ast=\tfrac{3\pi}{2}\), für das \(f^\prime(x^\ast)=0\) gilt. Diese Minimum ist also, wie aus der unrestringierten Optimierung bekannt, ein stationärer Punkt. Allerdings ist auch \(\overline{x}=0\) ein lokales Minimum des Problems, denn \(\sin(x)\ge0\) für alle \(x\in[0,\varepsilon)\), \(\varepsilon>0\). Hier gilt jedoch \(f^\prime(\overline{x})=1\neq0\). Das bedeutet, in restringierten Optimierungsproblemen können Minima auch an Stellen auftreten, an denen der Gradient der Zielfunktion nicht verschwindet.

Wir erinnern uns zurück an die Optimalitätsbedingungen für unrestringierte Optimierungsprobleme. Hier haben wir mithilfe einer Taylor-Entwicklung der Zielfunktion gezeigt, dass \(x_k\in\R^n\) mit \(\nabla f(x_k)\neq0\) kein lokales Minimum sein kann, weil wir entlang der Richtung \(-\nabla f(x_k)\) kleinere Funktionswerte erreichen können. In Beispiel 3.4 sehen wir, dass für die restringierte Optimierung eine interessante Konstellation entstehen kann: Der Gradient von \(f\) ist zwar nicht Null, zeigt aber aus der zulässigen Menge heraus. Auf diese Art erhalten wir ein lokales Minimum, in dem der Gradient der Zielfunktion nicht verschwindet.

Um diesen Gedanken formal festhalten zu können, brauchen wir die folgende

Definition 3.11

Eine Menge \(K\subseteq\R^n\) heißt Kegel, wenn

\[x\in K \quad \Longrightarrow \quad \lambda x\in K \quad \text{für alle }\lambda\ge 0.\]

Für eine nichtleere Menge \(\Omega\subseteq\R^n\) bezeichnen wir mit

\[T(\Omega,x) := \left\{ d\in\R^n\,:\, \exists t_k>0,\, x_k\in\Omega:\, \lim_{k\to\infty} x_k=x,\, \lim_{k\to\infty} t_k(x_k-x)=d \right\}\]

den Tangentialkegel an \(\Omega\) im Punkt \(x\).

Bemerkung 3.13

Für \(x\in\partial\Omega\) können wir \(T(\Omega,x)\) als Menge aller Richtungen auffassen, die von \(x\) gesehen in \(\Omega\) hinein zeigen, oder tangential zu \(\Omega\) verlaufen (daher der Name Tangentialkegel). Diese Anschauung deckt sich mit der Beobachtung, dass \(T(\Omega,x)=\R^n\) für \(x\in\operatorname{int}(\Omega)\).

Mithilfe des Tangentialkegels erhalten wir unsere erste Optimalitätsbedingung.

Satz 3.12

Ist \(x^\ast\in X\) ein lokales Minimum von (3.1), dann gilt

\[\nabla f(x^\ast)^\top d \ge 0\quad\text{für alle }d\in T(X,x^\ast).\]

Proof. Seien \((x_k)_{k\in\N}\), \((t_k)_{k\in\N}\) wie in Definition 3.11 und

\[d_k := t_k(x_k-x^\ast) \to d.\]

Weil \(x^\ast\) ein lokales Minimum von \(f\) auf \(X\) ist, gilt \(f(x_k)\ge f(x^\ast)\) für \(k\in\N\) groß genug. Eine Taylor-Entwicklung liefert demnach

\[\begin{split}\begin{aligned} 0 &\le t_k\big(f(x_k)-f(x^\ast)\big) \\ &= t_k \nabla f(x^\ast)^\top(x_k-x^\ast) + t_ko\big(\Vert x_k-x^\ast\Vert\big)\\ &= \nabla f(x^\ast)^\top d_k + \Vert d_k\Vert\frac{o\big(\Vert x_k-x^\ast\Vert\big)}{\Vert x_k-x^\ast\Vert} \to \nabla f(x^\ast)^\top d. \end{aligned}\end{split}\]

◻

Dieses Kriterium ist leider überhaupt nicht praxistauglich, da wir den Tangentialkegel nur in den wenigsten Fällen wirklich konstruieren können. Wir hätten lieber eine etwas anschaulichere Bedingung, die auch die Funktionen \(g\) und \(h\) explizit mit einbezieht.

Definition 3.12 (Aktive und inaktive Ungleichungen)

Für \(x\in X\) definieren wir die Indexmenge der aktiven Ungleichungsnebenbedingungen \(\mathcal{A}(x)\) und die Indexmenge der inaktiven Ungleichungsnebenbedingungen \(\mathcal{I}(x)\) als

\[\begin{split}\begin{aligned} \mathcal{A}(x) &:= \big\{ i = 1,\ldots,m\,:\, g_i(x)=0\big\},\\ \mathcal{I}(x) &:= \big\{ i = 1,\ldots,m\,:\, g_i(x)<0\big\} = \{1,\ldots,m\}\setminus \mathcal{A}(x). \end{aligned}\end{split}\]

Bemerkung 3.14

Ersetzen wir für den Punkt \(\overline{x}\in X\) die Nebenbedingungen in (3.1) durch Taylor-Approximationen 1. Ordnung (sog. Linearisierungen), so erhalten wir die polyedrische Menge

\[X_l(\overline{x}) := \big\{ x\in\R^n\,:\, g(\overline{x})+\nabla g(\overline{x})^\top(x-\overline{x})\le 0, \, h(\overline{x})+\nabla h(\overline{x})^\top(x-\overline{x})= 0 \big\}.\]

Für diese Menge lässt sich der zugehörige Tangentialkegel \(T(X_l(\overline{x}),\overline{x})\) direkt bestimmen:

\[T(X_l(\overline{x}),\overline{x}) = \left\{ d\in\R^n\,:\, \nabla g_{\mathcal{A}(\overline{x})}(\overline{x})^\top d\le 0, \, \nabla h(\overline{x})^\top d = 0 \right\}.\]

Definition 3.13 (Linearisierter Tangentialkegel)

Für \(x\in X\) bezeichnen wir mit

\[T_l(g,h,x) := \left\{ d\in\R^n\,:\, \nabla g_{\mathcal{A}(x)}(x)^\top d\le 0, \, \nabla h(x)^\top d = 0 \right\}\]

den linearisierten Tangentialkegel.

Es ist äußert wichtig, dass wir im Hinterkopf behalten, dass der linearisierte Tangentialkegel, im Gegensatz zum tatsächlichen Tangentialkegel, von der Darstellung der Menge \(X\) durch \(g\) und \(h\) abhängig ist. Eine Optimalitätsbedingung, die \(T_l\) statt \(T\) benutzt kann also nur dann sinnvoll sein, wenn wir bei der Wahl der Funktionen \(g\) und \(h\) nicht zu viel falsch machen. Dies führt auf den Begriff der Constraint Qualification, den wir hier nur anreißen können.

Definition 3.14 (Polarkegel und GCQ)

Für einen nichtleeren Kegel \(K\subseteq\R^n\) definieren wir den Polarkegel als

\[K^\circ := \big\{ v\in\R^n\,:\, v^\top d\le 0\;\text{für alle }d\in K \big\}.\]

Wir sagen, dass für einen Punkt \(x\in X\) die Guignard Constraint Qualification gilt, wenn

(3.37)\[T_l(g,h,x)^\circ = T(X,x)^\circ.\tag{GCQ}\]

Bemerkung 3.15

Es gibt unzählige praxistaugliche Anforderungen an \(g\) und \(h\), die (3.37) implizieren. Zu den bekanntesten zählen z.B. die Positive Linear Independence Constraint Qualification (PLICQ) oder die Mangasarian-Fromowitz Constraint Qualification (MFCQ). Wir verweisen an dieser Stelle auf die Nichtlineare Optimierung, in der CQ genauer untersucht werden und beschränken uns im Folgenden der Einfachheit halber auf die Nutzung von (3.37).

Korollar 3.2

Ist \(x^\ast\in X\) ein lokales Minimum von (3.1) in dem (3.37) erfüllt ist. Dann gilt

\[\nabla f(x^\ast)^\top d\ge 0 \quad\text{für alle }d\in T_l(g,h,x^\ast).\]

Proof. Aus Satz 3.12 wissen wir, dass

\[\nabla f(x^\ast)^\top d \ge 0\quad\text{für alle }d\in T(X,x^\ast),\]

was äquivalent ist zu \(-\nabla f(x^\ast)\in T(X,x^\ast)^\circ\). Wegen (3.37) haben wir also

\[-\nabla f(x^\ast)\in T_l(g,h,x^\ast)^\circ,\]

was wiederum äquivalent zu der zu zeigenden Aussage ist. ◻

Wir haben mittlerweile eingesehen, dass lokale Minimalstellen für restringierte Optimierungsprobleme keine stationären Punkte der Zielfunktion sein müssen, weil wir bei diesem Ansatz die Nebenbedingungen ignorieren würden. Wenn wir Zielfunktion und Nebenbedingungen jedoch geschickt in einer Funktion kombinieren, können wir aber vielleicht wieder eine Stationaritätsaussage treffen. Dieser Gedanke führt uns auf die folgende

Definition 3.15

Die Funktion \(\mathcal{L}:\R^n\times\R^m\times\R^p\to\R\) mit

\[\mathcal{L}(x,\lambda,\mu) := f(x) + \langle \lambda,g(x)\rangle + \langle\mu,h(x)\rangle\]

heißt Lagrange-Funktion für Problem (3.1).

Die Lagrange-Funktion liefert eine elegante Möglichkeit, Problem (3.1) zu reformulieren, denn

\[\begin{split}\sup_{\lambda\in\R^m_{\ge0},\mu\in\R^p} \mathcal{L}(x,\lambda,\mu) = \begin{cases}f(x), & x\in X\\ +\infty,& x\not\in X. \end{cases}\end{split}\]

Das bedeutet, (3.1) ist äquivalent zu

\[\min_{x\in\R^n}\sup_{\lambda\in\R^m_{\ge0},\mu\in\R^p} \mathcal{L}(x,\lambda,\mu).\]

Bevor wir mithilfe von \(\mathcal{L}\) eine finale Optimalitätsbedingung angeben können, brauchen wir noch ein Hilfsresultat.

Lemma 3.5 (Alternativlemma)

Seien \(A\in\R^{n\times m}\), \(B\in\R^{n\times p}\) und \(c\in\R^n\). Dann sind folgende Aussagen äquivalent:

1. Für alle \(d\in\R^n\) mit \(A^\top d\le 0\) und \(B^\top d=0\) gilt \(c^\top d\le0\).

2. Es gibt \(u\in\R^m_{\ge0}\) und \(v\in\R^p\) mit \(c=Au+Bv\).

Proof. Übung. ◻

Damit haben wir alles zusammen, um die wohl bekannteste Form der Optimalitätsbedingungen für restringierte Optimierungsprobleme zu beweisen.

Satz 3.13 (KKT-Bedingungen)

Sei \(x^\ast\in X\) ein lokales Minimum von (3.1), in der (3.37) erfüllt ist. Dann gelten die Karush-Kuhn-Tucker-Bedingungen, d.h. es existieren Lagrange-Multiplikatoren \(\lambda^\ast\in\R^m\) und \(\mu^\ast\in\R^p\) mit

1. \(\nabla f(x^\ast) + \nabla g(x^\ast)\lambda^\ast + \nabla h(x^\ast)\mu^\ast = 0\) (Stationarität)

2. \(g(x^\ast)\le 0\), \(h(x^\ast)=0\) (Zulässigkeit)

3. \(\lambda^\ast\ge0\), \(\langle\lambda^\ast,g(x^\ast)\rangle = 0\)(Komplementarität)

In diesem Fall bezeichnen wir \((x^\ast,\lambda^\ast,\mu^\ast)\) als KKT-Tripel.

Proof. Die Zulässigkeitsbedingung ist klar. Weiterhin wissen wir aus Korollar 3.2, dass

\[-\nabla f(x^\ast)^\top d \le 0\quad \text{für alle }d\in T_l(g,h,x^\ast),\]

also für alle \(d\in\R^n\), die

\[\nabla g_i(x^\ast)^\top d \le 0,\quad i\in\mathcal{A}(x^\ast)\]

und

\[\nabla h(x^\ast)^\top d = 0\]

erfüllen. Wählen wir im Alternativlemma jetzt \(c=-\nabla f(x^\ast)\), \(A=\nabla g_{\mathcal{A}(x^\ast)}(x^\ast)\) und \(B=\nabla h(x^\ast)\) so folgt, dass \(u\in\R^m_{\ge0}\) und \(v\in\R^p\) existieren mit \(c=Au+Bv\). Setzen wir

\[\lambda^\ast_{\mathcal{A}(x^\ast)} = u,\quad \lambda^\ast_{\mathcal{I}(x^\ast)} = 0 \quad\text{und}\quad \mu^\ast = v,\]

erhalten wir die Stationaritätsbedingung. Die Komplementaritätsbedingung ist durch diese Wahl von \(\lambda^\ast\) ebenfalls erfüllt. ◻

Die Stationaritätsbedingung lässt sich mithilfe der Lagrange-Funktion auch kompakt als \(\nabla_x\mathcal{L}(x^\ast,\lambda^\ast,\mu^\ast)=0\) formulieren. Nutzen wir nun die Komplementaritätsbedingung aus, so stellen wir fest, dass

\[-\nabla f(x^\ast) = \sum_{i\in\mathcal{A}(x^\ast)} \lambda_i^\ast\nabla g_i(x^\ast) + \sum_{i=1}^p \mu_i^\ast\nabla h(x^\ast).\]

Anschaulich gesehen bedeutet das, dass der negative Gradient der Zielfunktion in dem Kegel liegt, der von den Gradienten aktiver Nebenbedingungen aufgespannt wird.

Beispiel 3.5

Wir suchen alle KKT-Tripel des folgenden Optimierungsproblems:

\[\begin{split}\begin{aligned} \min\quad& x+y\\ \text{s.t.}\quad& x^2 + y^2 \le 4\\ & \cos\left(\tfrac{\pi}{2}(x+y)\right) \le 0. \end{aligned}\end{split}\]

In diesem Beispiel ist (3.37) in jedem \(x\in X\) erfüllt. Der zulässige Bereich \(X\) ist in Abb. 3.5 dargestellt. Wir suchen die KKT-Tripel systematisch anhand der Anzahl aktiver Ungleichungsbedingungen.

1. Keine Ungleichung ist aktiv, also \(\mathcal{A}=\emptyset\). Wegen

   \[\begin{split}\nabla f(x,y) = \begin{pmatrix}1\\1\end{pmatrix} \neq 0\quad \forall (x,y)\in\R^2\end{split}\]

   gibt es in diesem Fall kein KKT-Tripel.

2. Eine Ungleichung ist aktiv.

   1. \(\mathcal{A}=\{1\}\). Aus der Stationaritätsbedingung

      \[\begin{split}\begin{pmatrix}1\\1\end{pmatrix}+\lambda_1\begin{pmatrix}2x\\2y \end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}\end{split}\]

      folgt damit \(x=y\). Eingesetzt in die Nebenbedingung \(x^2+y^2=4\) (aktiv!) liefert also die Kandidaten \(x=y=\pm\sqrt{2}\). Das Vorzeichen von \(\lambda_1\) (Komplementarität) schließt \(x,y>0\) aber aus, womit wir in diesem Fall genau ein KKT-Tripel \(\big((-\sqrt{2},-\sqrt{2}),(\tfrac{1}{2\sqrt{2}},0),-\big)\) erhalten (beachte: dieser Punkt ist zulässig!).

   2. \(\mathcal{A}=\{2\}\). In diesem Fall gilt

      \[\cos\left(\tfrac{\pi}{2}(x+y)\right) = 0 \quad \Longrightarrow \quad \sin\left(\tfrac{\pi}{2}(x+y)\right) = \pm 1.\]

      Kombinieren wir die Stationaritätsbedingung

      \[\begin{split}\begin{pmatrix}1\\1\end{pmatrix}-\frac{\pi\lambda_2}{2}\begin{pmatrix}\sin\left(\tfrac{\pi}{2}(x+y)\right)\\\sin\left(\tfrac{\pi}{2}(x+y)\right) \end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}\end{split}\]

      mit der Komplementarität, also \(\lambda_2\ge0\), so folgt \(\sin\left(\tfrac{\pi}{2}(x+y)\right) = 1\). Schränken wir diese Bedingung auf den zulässigen Bereich ein, so folgt sofort \(x+y=1\) und \(x^2+y^2\le4\). Alle diese Punkte sind KKT-Punkte mit einheitlichem Multiplikator \(\lambda=(0,\tfrac{2}{\pi})\).

3. Alle NB sind aktiv, also \(\mathcal{A}=\{1,2\}\). In Abb. 3.5 sehen wir, dass es genau vier solcher Punkte gibt. Zwei davon haben wir bereits als KKT-Punkte identifiziert (Ecken des oberen Kreissegments). Bei den beiden anderen Punkten kann es sich nicht um KKT-Punkte handeln, denn dazu müsste \(\lambda\ge0\in\R^2\) existieren mit

   \[\begin{split}\begin{pmatrix}1\\1\end{pmatrix}+\lambda_1\begin{pmatrix}2x\\2y \end{pmatrix}-\frac{\pi\lambda_2}{2}\begin{pmatrix}\sin\left(\tfrac{\pi}{2}(x+y)\right)\\\sin\left(\tfrac{\pi}{2}(x+y)\right) \end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}.\end{split}\]

   Aus unseren Überlegungen zu \(\vert\mathcal{A}\vert=1\) wissen wir bereits, dass in diesen beiden Punkten \(\sin\left(\tfrac{\pi}{2}(x+y)\right)=-1\) gilt. In Abb. 3.5 sehen wir weiterhin, dass \(x>0,y<0\) oder \(x<0,y>0\) gilt. Somit kann die Stationaritätsbedingung nicht für erfüllt werden, wenn wir \(\lambda\ge0\) fordern.

Geometrisch betrachtet erscheinen unsere Ergebnisse offensichtlich: Da der negative Gradient der Zielfunktion konstant in Richtung \((-1,-1)^\top\) zeigt, sind KKT-Punkte genau die Stellen, an denen dieser Vektor senkrecht auf dem Rand der zulässigen Menge steht und nach außen zeigt (bzw. im Polarkegel liegt, falls wir uns in einer Ecke befinden).

Abb. 3.5 Der zulässige Bereich für Beispiel 3.5.