3.6. Nicht-differenzierbare Optimierung

Mit Hinblick auf (3.39) stellen wir fest, dass die dortige Zielfunktion zwar nicht differenzierbar ist, aber eine besondere Gestalt hat:

\[F(x) = G(x) + H(x),\]

mit einer stetig differenzierbaren Funktion \(G \colon \R^n \rightarrow \R\) und einer konvexen, nicht notwendigerweise differenzierbaren Funktion \(H \colon \R^n \rightarrow \R\).

Da \(\nabla H\) im Allgemeinen nicht existiert, müssen wir uns Gedanken darüber machen, wie wir Stationarität bzw. Optimalität in diesem Kontext sinnvoll formulieren können. Dies führt auf die folgende

Definition 3.16 (Subdifferential und Subgradient)

Sei \(H: \R^n \rightarrow \R\) eine konvexe Funktion. Dann ist das Subdifferential an der Stelle \(x \in \R^n\) definiert durch

\[\partial H(x) \ \coloneqq \{ p \in \R^n ~|~ H(x) + \langle p, y-x \rangle \leq H(y) \quad \forall~y \in \R^n \}.\]

Ein Element des Subdifferentials nennen wir Subgradient.

Man sieht ein, dass ein globales Minimum der konvexen Funktion \(H\) durch die Bedingung \(\vec{0} \in \partial H(x^*)\) charakterisiert wird, denn mit Definition 3.16 erhalten wir in diesem Fall:

(3.40)\[\vec{0} \in \partial H(x^*) \ \Leftrightarrow \ H(x^*) + \underbrace{\langle \vec{0} , y-x^* \rangle}_{=\, 0} \leq H(y) \quad \forall y \in \R^n.\]

Folgendes Beispiel illustriert das Subdifferential einer nicht differenzierbaren, eindimensionalen Funktion.

Beispiel 3.6 (Subdifferential der Betragsfunktion)

Wir betrachten die eindimensionale Betragsfunktion \(H(x) \coloneqq \vert x \vert\). In diesem Fall ist das Subdifferential von \(H\) für alle Punkte \(x \neq 0\) gegeben als

\[\partial H(x) \ = \ \{\operatorname{sgn}(x)\}.\]

Im Punkt \(x=0\), in dem die Betragsfunktion bekanntlich nicht differenzierbar ist, gilt für das Subdifferential hingegen

\[\partial H(0) \ = \ [-1,1].\]

Basierend auf dieser Beobachtung im Eindimensionalen können wir auch das Subdifferential der \(\ell^1\)-Norm im \(\R^n\) im folgenden Beispiel ausrechnen.

Beispiel 3.7 (Subdifferential der \ell^1-Norm)

Wir betrachten die \(\ell^1\)-Norm, die durch die konvexe Funktion \(H(x) = \Vert x \Vert_{\ell^1}\) gegeben ist. Dann können wir das Subdifferential der \(\ell^1\)-Norm für alle Punkte \(x \in \R^n\) angeben als

\[\partial H(x) \ = \ \{ p \in [-1,1]^n ~|~ p_i = \operatorname{sgn}(x_i) \text{ für } x_i \neq 0\}.\]

Basierend auf der Optimalitätsbedingung für die konvexe Funktion \(H\) in (3.40) können wir eine entsprechende notwendige Bedingung für ein lokales Minimum für die Summe einer differenzierbaren Funktion \(G\) und einer konvexen Funktion \(H\) herleiten, wie das folgende Lemma besagt.

Lemma 3.6 (Optimalitätsbedingung)

Sei \(F \colon \R^n \rightarrow \R\) eine Zielfunktion, die sich schreiben lässt als \(F=G+H\), wobei \(G\) stetig differenzierbar und \(H\) konvex ist. Sei außerdem \(x^* \in \R^n\) ein lokaler Minimierer von \(F\).

Dann gilt \(\vec{0} \in \nabla G(x^*) + \partial H(x^*)\), d.h., es existiert ein Subgradient \(p \in \partial H(x^*)\) mit \(\nabla G(x^*) + p = \vec{0}\).

Proof. Sei \(x^* \in \R^n\) ein lokaler Minimierer von \(F\). Dann gilt für jeden Punkt \(x \in \R^n\) in einer lokalen Umgebung des Minimierers \(x^*\) mit einer Taylor-Entwicklung erster Ordnung der Funktion \(G\) schon

\[\begin{split}\begin{split} G(x^*) + H(x^*) \ &= \ F(x^*) \ \leq \ F(x) \ = \ G(x) + H(x)\\ &= \ G(x^*) + \langle \nabla G(x^*),x-x^* \rangle + r(x)\Vert x-x^*\Vert + H(x) \end{split}\end{split}\]

mit einem Fehlerterm \(r \colon \R^n \rightarrow \R\) für den gilt \(r(x) \rightarrow 0\) wenn \(x \rightarrow x^*\). Wählen wir nun den speziellen Vektor \(p = -\nabla G(x^*)\) und stellen die Gleichung um, so gilt also

\[\frac{H(x^*) + \langle p, x - x^* \rangle - H(x)}{\Vert x-x^* \Vert} \ \leq \ r(x).\]

Dann können wir unter Ausnutzung der Konvexität von \(H\) folgende Abschätzung treffen

\[\begin{split}\begin{split} 0 \ = \ \limsup_{x \rightarrow x^*} r(x) \ &\geq \ \limsup_{x \rightarrow x^*} \frac{H(x^*) + \langle p, x - x^* \rangle - H(x)}{\Vert x-x^* \Vert} \\ &\geq \ \lim_{\lambda \rightarrow 0} \frac{H(x^*) + \langle p, \lambda(x - x^*) \rangle - H((1-\lambda)x^* + \lambda x)}{\lambda \Vert x-x^* \Vert}\\ &\geq \ \lim_{\lambda \rightarrow 0} \frac{H(x^*) + \lambda \langle p, x - x^* \rangle - (1-\lambda)H(x^*) - \lambda H(x)}{\lambda \Vert x-x^* \Vert}\\ &= \ \lim_{\lambda \rightarrow 0} \frac{\langle p, x - x^* \rangle + H(x^*) - H(x)}{\Vert x-x^* \Vert} \ = \ \frac{\langle p, x - x^* \rangle + H(x^*) - H(x)}{\Vert x-x^* \Vert}. \end{split}\end{split}\]

Durch Umstellen erhalten wir schließlich

\[H(x^*) + \langle p, x - x^* \rangle \ \leq \ H(x).\]

Dies bedeutet aber schon nach Definition 3.16, dass \(p \in \partial H(x^*)\) gilt. ◻

Basierend auf Lemma 3.6 könnten wir also von der notwendigen Optimalitätsbedingung \(\nabla G(x^*) + p = 0\) ausgehen und damit ein Analogon zum Gradientenabstiegsverfahren aus Gradientenabstiegsverfahren aufstellen mit

\[x_{k+1} = x_k - \tau_k( \nabla G(x_k) + p_k), \qquad p_k \in \partial H(x_k).\]

Allerdings ist nicht klar welchen Subgradienten \(p_k \in \partial H(x_k)\) wir in jeder Iteration auswählen sollen (falls mehr als einer existiert) oder ob überhaupt ein Subgradient existiert. Deshalb werden wir im Folgenden eine Variante betrachten bei der automatisch Iterationsschritte \(x_{k+1} \in \R^n\) mit nichtleerem Subdifferential und ebenso ein \(p_{k+1} \in \partial H(x_{k+1})\) ausgewählt werden.