3.7. Proximales Splitting

Die Idee des sogenannten proximalen Splitting, auch Forward-Backward Splitting genannt, ist es den differenzierbaren Teil genauso wie beim Gradientenabstiegsverfahren auszuwerten, d.h., vorwärts ausgehend vom Punkt \(x_k \in \R^n\), während der Subgradient hingegen bezüglich der nächsten Iterierten ausgewertet wird, d.h., rückwärts ausgehend vom Punkt \(x_{k+1} \in \R^n\).

Somit lässt sich die Iterationsvorschrift für das proximale Splitting schreiben als

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

Diese Gleichung können wir nun selbstverständlich nicht mehr explizit auswerten, da der Subgradient \(p_{k+1} \in \partial H(x_{k+1})\) vom bisher unbestimmten Iterationsschritt \(x_{k+1} \in \R^n\) abhängt. Diesem Problem begegnen wir aber nicht zum ersten Mal. Im proximalen Gradientenverfahren hatten wir mit (3.5) eine ganz ähnliche Updateregel.

Wir gehen also möglichst analog vor und schreiben (3.41) weiter um zu

\[\frac{1}{\tau_k} (x_{k+1} - x_k) + \nabla G(x_k) + p_{k+1} \ = \ 0.\]

Erneut suchen wir eine Funktion, deren Ableitung den Ausdruck auf linken Seite der obigen Gleichung liefert. Man sieht ein, dass die obige Gleichung die hinreichende Optimalitätsbedingung für die Minimierung der folgenden strikt konvexen Funktion darstellt

\[F_k(x) \ = \ \frac{1}{2 \tau_k} \Vert x - x_k + \tau_k \nabla G(x_k) \Vert^2 + H(x).\]

Hierbei stellt die Iterierte \(x_{k+1} \in \R^n\) also einen stationären Punkt der Zielfunktion \(F_k(x)\) dar, während \(p_{k+1} \in \R^n\) aus dem Subdifferential \(\partial H(x)\) stammt.

Wir können das Iterationsverfahren in (3.41) also durchführen, wenn wir strikt konvexe Funktionen der Form

\[\Phi(x) \ \coloneqq \ \frac{1}{2\tau} \Vert x - y \Vert^2 + H(x)\]

effizient minimieren können.

Bei der Optimierung der Funktion \(\Phi\) versucht man anschaulich einen Kompromiss einzugehen zwischen dem Ziel die Funktion \(H\) zu minimieren und gleichzeitig nahe dem Punkt \(y \in \R^n\) bezüglich der Euklidischen Norm zu sein. Der Parameter \(\tau > 0\) steuert hierbei die Gewichtung zwischen diesen beiden Kriterien.

Da es sich bei \(\Phi\) um eine strikt konvexe Funktion handelt existiert ein eindeutiges Minimum. Dieses lässt sich erneut durch den Proximaloperator beschreiben, diesmal allerdings ohne die Forderung nach Differenzierbarkeit.

Definition 3.17 (Proximaloperator (nicht-differenzierbarer Fall))

Sei \(H \colon \R^n \rightarrow \R\) eine konvexe, unterhalbstetige Funktion und sei \(\tau > 0\) ein positiver Parameter. Dann definieren wir den Proximaloperator bezüglich der Funktion \(H\) im Punkt \(y\in \R^n\) als

\[\operatorname{prox}_{\tau H}(y) \ \coloneqq \ \underset{x \in \R^n}{\operatorname{arg\,min}} \left \lbrace \frac{1}{2\tau} ||x - y||^2 + H(x) \right\rbrace.\]

Wir wollen zunächst das Konzept des Proximaloperators im folgenden Beispiel für die Betragsfunktion bzw. die \(\ell^1\)-Norm genauer verstehen.

Beispiel 3.8 (Shrinkage-Operator)

Sei \(H(x) = \vert x \vert\) in diesem Beispiel zunächst die Betragsfunktion. Dann ist der Proximaloperator \(z =\operatorname{prox}_{\tau H}(y)\) der eindeutige Minimierer der strikt konvexen Funktion

\[\Phi(x) \ = \ \frac{1}{2\tau} (x - y)^2 + \vert x \vert\]

mit der notwendigen Optimalitätsbedingung 1. Ordnung

(3.42)\[\frac{1}\tau (y-z) \in \partial \vert z\vert.\]

Aus Beispiel 3.6 wissen wir bereits, dass \(\partial |z| = \lbrace{ \operatorname{sgn}(z)}\rbrace = \lbrace -1, 1 \rbrace\) für \(z \neq 0\) gilt und \(\partial |0| = [-1, 1]\) in der Null.

Betrachten wir zunächst den Fall \(z > 0\). Dann ist klar, dass \(\partial |z| = 1\) gilt und somit wird aus der notwendigen Optimalitätsbedingung (3.42)

\[\frac{1}\tau (y-z) \: = \: 1 \quad \Longleftrightarrow \quad z \: = \: y - \tau.\]

Da wir \(z > 0\) angenommen haben, ist dies nur möglich für \(y > \tau > 0\).

Analog gilt für den Fall \(z < 0\), dass \(\partial |z| = -1\) ist und somit erhalten wir aus der notwendigen Optimalitätsbedingung (3.42)

\[\frac{1}\tau (y-z) \: = \: -1 \quad \Longleftrightarrow \quad z \: = \: \tau + y.\]

Dies ist aber für \(z < 0\) nur möglich, wenn \(y < -\tau < 0\) gilt.

Für den letzten Fall mit \(z=0\) lauten die notwendigen Optimalitätsbedingung (3.42)

\[\frac{1}\tau (y-z) \: = \: \frac{y}{\tau} \: \in \: [-1, 1] = \partial |0|.\]

Dies ist äquivalent zu der Bedingung \(-1 \leq \frac{y}{\tau} \leq 1\), die nur dann erfüllt ist wenn \(-\tau \leq y \leq \tau\) gilt.

Somit lässt sich der Proximaloperator \(z =\operatorname{prox}_{\tau H}(y)\) für die Betragsfunktion \(H(x) \coloneqq \vert x \vert\), der auch Shrinkage-Operator genannt wird, wie folgt angeben:

\[\begin{split}\operatorname{prox}_{\tau \vert \cdot \vert}(y) \ = \ \text{shrink}_\tau(y) \ \coloneqq \ \left\{ \begin{array}{ll} y - \tau \quad & \text{falls } y > \tau \\ 0 \quad & \text{falls } y \in [-\tau, \tau] \\ y + \tau \quad & \text{falls } y < - \tau. \end{array}\right.\end{split}\]

Die kontrahierende Wirkung des Shrinkage-Operators wird in fig:shrinkage illustriert.

Analog können wir auch den Proximaloperator für die \(\ell^1\)-Norm \(H(x) = \Vert x \Vert_{\ell^1}\) im \(\R^n\) angeben als

\[\text{prox}_{\tau H}(y) = ( \operatorname{shrink}_\tau(y_i))_{i=1,\ldots,n}.\]

Mit Hilfe des Proximaloperators können wir das proximale Splitting in (3.41) schreiben als

\[x_{k+1} \ = \ \operatorname{prox}_{\tau_k H}(x_k - \tau_k \nabla G(x_k)).\]

Wie wir in Beispiel 3.8 gesehen haben ist der Shrinkage-Operator in gewisser Weise kontraktiv. Diese Beobachtung gilt im Allgemeinen für Proximaloperatoren wie folgendes Lemma feststellt.

Lemma 3.7 (Kontraktivität des Proximaloperators)

Sei \(H\) eine konvexe, unterhalbstetige Funktion. Dann ist der Proximaloperator \(\operatorname{prox}_H\) Lipschitz stetig mit Lipschitz-Konstante \(1\).

Proof. Wir betrachten zunächst die beiden Punkte, die für \(i = 1,2\) gegeben sind durch \(x_i= \operatorname{prox}_H(y_i)\). Dann gilt wegen der Optimalitätsbedingung des Proximaloperators \(x_i + p_i = y_i,\) für einen Subgradienten \(p_i \in \partial H(x_i)\). Subtrahieren wir die beiden Identitäten für \(i=1,2\), so erhalten wir

\[x_1 - x_2 + p_1 - p_2 \ = \ y_1 - y_2.\]

Multiplizieren wir diese Gleichung von links mit dem Zeilenvektor \((x_1-x_2)^T \in \R^n\) so gilt mit Hilfe der Cauchy-Schwarz Ungleichung:

(3.43)\[\Vert x_1 - x_2 \Vert^2 + \langle x_1-x_2, p_1 - p_2 \rangle = \langle x_1-x_2, y_1 -y_2 \rangle \ \leq \ \Vert y_1-y_2 \Vert \cdot \Vert x_1-x_2 \Vert.\]

Wegen Definition 3.16 des Subgradienten können wir festhalten, dass gilt

\[\begin{split}\begin{aligned} \langle p_1, x_1- x_2 \rangle \ &\geq \ H(x_1) - H(x_2) \\ \langle p_2, x_2- x_1 \rangle \ &\geq \ H(x_2) - H(x_1). \end{aligned}\end{split}\]

Addieren wir diese beiden Ungleichungen, so erhalten wir insgesamt \(\langle p_1 - p_2, x_1-x_2 \rangle \geq 0\). Damit können wir die linke Seite der Ungleichung (3.43) weiter abschätzen und erhalten durch Teilen mit dem Wert \(||x_1 - x_2||\) auf beiden Seiten schließlich

\[\Vert x_1 - x_2 \Vert \ \leq \ \Vert y_1 - y_2 \Vert ,\]

was genau die gewünschte Lipschitz-Stetigkeit des Proximaloperators mit Lipschitz-Konstante \(L=1\) bedeutet. ◻

Satz 3.14 (Konvergenz des proximalen Splitting-Verfahrens)

Sei \(F \coloneqq \R^n \rightarrow \R\) eine nach unten beschränkte Zielfunktion, das heißt, dass die Niveaumenge \(K \coloneqq \lbrace x \in \R^n : F(x) \leq F(x_0) \rbrace\) beschränkt ist. Außerdem lasse sich \(F\) als Summe zweier Funktionen schreiben mit \(F(x) = G(x) + H(x)\) für eine zweimal stetig differenzierbare Funktion \(G \colon \R^n \rightarrow \R\) und eine konvexe, unterhalbstetige Funktion \(H \colon \R^n \rightarrow \R\).

Dann konvergiert das proximale Splitting-Verfahren der Form

\[x_{k+1} \ = \ \operatorname{prox}_{\tau_k H}(x_k - \tau_k \nabla G(x_k)).\]

Proof. Wir nutzen zunächst für einen Subgradienten \(p_{k+1} \in \partial H(x_{k+1})\) die explizite Iterationsvorschrift (3.41) für das proximale Splitting

\[\frac{1}{\tau_k} (x_{k+1} - x_k) + \nabla G(x_k) + p_{k+1} \ = \ 0.\]

Multiplizieren wir diese Gleichung von links mit dem Zeilenvektor \((x_{k+1} - x_k)^T \in \R^n\), dann folgt

(3.44)\[\frac{1}{\tau_k} \Vert x_{k+1} - x_k \Vert^2 + \langle x_{k+1} - x_k, \nabla G (x_k) \rangle + \langle x_{k+1} - x_k, p_{k+1} \rangle \ = \ 0.\]

Da die Funktion \(G\) nach Voraussetzung zweimal stetig differenzierbar ist folgt mit einer Taylorapproximation erster Ordnung

\[\langle x_{k+1} - x_k, \nabla G (x_k) \rangle \ = \ G(x_{k+1}) - G(x_k) -r_k.\]

Hierbei lässt sich der Fehlerterm \(r_k\) abschätzen durch

\[r_k \ \leq \ \frac{C_k}2 \Vert x_{k+1} - x_k \Vert^2,\]

wobei \(C_k\) eine obere Schranke für die Norm der Hesse-Matrix von \(G\) in einer Umgebung von \(x_k\) mit Radius \(\Vert x_{k+1} - x_k \Vert\) ist.

Aus Definition 3.16 folgt für den Subgradienten \(p_{k+1} \in \partial H(x_{k+1})\) außerdem

\[\langle p_{k+1}, x_{k+1} - x_k \rangle \ \geq \ H(x_{k+1}) - H(x_k).\]

Nutzen wir diese Abschätzungen nun für die Identität (3.44), so erhalten wir insgesamt

\[\begin{split}\begin{split} 0 \ &= \ \frac{1}{\tau_k} \Vert x_{k+1} - x_k \Vert^2 + \langle x_{k+1} - x_k, \nabla G (x_k) \rangle + \langle x_{k+1} - x_k, p_{k+1} \rangle \\ &\geq \ \frac{1}{\tau_k} \Vert x_{k+1} - x_k \Vert^2 + G(x_{k+1}) - G(x_k) - \frac{C_k}2 \Vert x_{k+1} - x_k \Vert^2 + H(x_{k+1}) - H(x_k) \\ &= \ \left(\frac{1}{\tau_k}-\frac{C_k}{2}\right) \Vert x_{k+1} - x_k \Vert^2 + F(x_{k+1}) - F(x_k) \end{split}\end{split}\]

Theoretisch können wir die Schrittweiten \(\tau_k > 0\) so klein wählen, dass \(\frac{1}{\tau_k}-\frac{C_k}{2} > \epsilon\) für ein beliebiges \(\epsilon > 0\) gilt. Durch Umstellen sehen wir also, dass gilt

\[F(x_k) \ \geq \ \left(\frac{1}{\tau_k}-\frac{C_k}{2}\right) \Vert x_{k+1} - x_k \Vert^2 + F(x_{k+1}) \ > \ \epsilon \cdot \Vert x_{k+1} - x_k \Vert^2 + F(x_{k+1}).\]

Damit ist offensichtlich, dass \(F(x_{k+1}) < F(x_k)\) für alle \(k \in \N\) gilt. Damit haben wir gezeigt, dass das proximale Splitting-Verfahren die Zielfunktion \(F\) in jedem Schritt verkleinert.

Wir sehen ein, dass für die Folge der Iterationsschritte \((x_k)_{k \in \N} \subset K\) gilt und nach dem Satz von Bolzano-Weierstrass eine konvergente Teilfolge besitzt, deren Grenzwert in der kompakten Menge \(K\) liegen muss.

Es gilt ebenfalls

\[\sum_{k=0}^\infty \Vert x_{k+1} - x_k \Vert^2 \: < \: \infty.\]

Da die Iterierten auf einer beschränkten Menge bleiben und \(G\) zweimal stetig differenzierbar ist, ist die Norm der Hesse-Matrix von \(G\) ebenfalls uniform für alle \(k \in \N\) beschränkt für eine Konstante \(C > 0\) mit \(0 < C_k < C\) und somit kann die Folge der Schrittweiten \((\tau_k)_{k\in\N}\) ebenfalls uniform nach unten beschränkt werden.

Aus der Konvergenz

\[0 \ = \ \lim_{k\rightarrow \infty} \frac{1}{\tau_k}( x_{k+1} - x_k) \ = \ \lim_{k\rightarrow \infty} \nabla G(x_k) + p_{k+1}, \qquad p_{k+1} \in \partial H(x_{k+1})\]

können wir schließlich folgern, dass jeder Häufungspunkt die Optimalitätsbedingung aus Lemma 3.6 erfüllt. ◻