Nichtlineare Optimierung: Konvexität, Gradientenverfahren, KKT

Die lineare Optimierung löst Probleme, in denen Zielfunktion und Nebenbedingungen linear sind. Viele Aufgaben sind das nicht: Man will den Abstand eines Punktes zu einer Menge minimieren, die Parameter eines Modells an Daten anpassen oder die Kosten einer Produktion bei gekrümmten Kostenfunktionen senken. Dann hilft die nichtlineare Optimierung. Ihr Hauptwerkzeug sind Verfahren, die sich schrittweise dem Minimum nähern, und Bedingungen, die ein Minimum kennzeichnen.

Du brauchst partielle Ableitungen und die Hesse-Matrix aus der mehrdimensionalen Analysis, positiv definite Matrizen aus Bilinearformen und die Lagrange-Multiplikatoren von Extrema mit Nebenbedingungen.

Konvexe Funktionen

Anschaulich liegt der Graph unterhalb jeder Sehne. Eine zweimal stetig differenzierbare Funktion ist genau dann konvex, wenn ihre Hesse-Matrix überall positiv semidefinit ist. Zum Beispiel ist $f(x,y)=x^2+xy+y^2$ konvex, denn die Hesse-Matrix $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ hat die Eigenwerte $1$ und $3$, beide positiv. Die Funktion $f(x)=x^4-2x^2$ ist dagegen nicht konvex: $f^{\prime }(x)=12x^2-4$ ist bei $x=0$ negativ.

Beweis. Sei $x^{\ast }$ ein lokales Minimum, aber $f(y)<f(x^{\ast })$ für ein $y$. Auf der Strecke von $x^{\ast }$ nach $y$ gilt $f(\lambda y+(1-\lambda )x^{\ast })\le \lambda f(y)+(1-\lambda )f(x^{\ast })<f(x^{\ast })$ für alle $\lambda \in (0,1]$. Für kleines $\lambda$ liegen diese Punkte beliebig nah an $x^{\ast }$, im Widerspruch zum lokalen Minimum. Für die zweite Aussage benutzt man die Tangentenungleichung $f(y)\ge f(x)+\nabla f{(x)}^{\top }(y-x)$ der konvexen differenzierbaren Funktionen: Bei $\nabla f(x^{\ast })=0$ folgt $f(y)\ge f(x^{\ast })$ für alle $y$. $\square$

Optimalitätsbedingungen ohne Nebenbedingungen

In einem lokalen Minimum $x^{\ast }$ ist $\nabla f(x^{\ast })=0$ (stationärer Punkt), und die Hesse-Matrix $H={\nabla }^{2}f(x^{\ast })$ ist positiv semidefinit. Ist $\nabla f(x^{\ast })=0$ und $H$ positiv definit, dann ist $x^{\ast }$ ein striktes lokales Minimum. Beim Sattelpunkt ist $H$ indefinit. Beim Beispiel $f(x,y)=x^2+xy+y^2-3x$ ist $\nabla f=(2x+y-3,x+2y)$. Aus $x+2y=0$ folgt $x=-2y$, damit $-4y+y-3=0$ und $y=-1$, $x=2$. Das Minimum liegt bei $(2,-1)$ mit $f=4-2+1-6=-3$, und es ist global, weil $f$ konvex ist.

Bei vielen Variablen und komplizierten Funktionen lässt sich $\nabla f=0$ nicht mehr exakt lösen. Dann sucht man das Minimum iterativ.

Das Gradientenverfahren

Der Gradient $\nabla f(x)$ zeigt in die Richtung des steilsten Anstiegs, also zeigt $-\nabla f(x)$ in die Richtung des steilsten Abstiegs. Das Gradientenverfahren (Verfahren des steilsten Abstiegs) macht daher in jedem Schritt einen Schritt entgegen dem Gradienten:

Die Schrittweite $t_k>0$ ist entscheidend. Ist sie zu groß, springt das Verfahren über das Minimum hinweg, ist sie zu klein, kommt es kaum voran. Eine Möglichkeit ist die Liniensuche: Man wählt $t_k$ als Minimum von $f$ entlang der Geraden oder, einfacher, durch Halbieren (Backtracking), bis $f(x_k-t\nabla f(x_k))\le f(x_k)-ct\Vert \nabla f(x_k){\Vert }^2$ gilt (Armijo-Bedingung).

Quadratische Funktionen. Sei $f(x)=\frac{1}{2}{x}^{\top }Ax-b^{\top }x$ mit symmetrischer, positiv definiter Matrix $A$ und Eigenwerten ${\lambda }_{\min }\le \dots \le {\lambda }_{\max }$. Das Minimum $x^{\ast }$ löst $A{x}^{\ast }=b$. Wegen $\nabla f(x)=Ax-b=A(x-x^{\ast })$ ist

Die Matrix $I-tA$ hat die Eigenwerte $1-t\lambda$. Der Fehler schrumpft also mindestens um den Faktor $\max |1-t\lambda |$ pro Schritt. Dieser Faktor ist am kleinsten bei $t=\frac{2}{{\lambda }_{\min }+{\lambda }_{\max }}$, nämlich $\frac{{\lambda }_{\max }-{\lambda }_{\min }}{{\lambda }_{\max }+{\lambda }_{\min }}=\frac{\kappa -1}{\kappa +1}$ mit der Konditionszahl $\kappa =\frac{{\lambda }_{\max }}{{\lambda }_{\min }}$. Im Beispiel ist $A=\mathrm{diag}(2,8)$, $\kappa =4$, und der Faktor $\frac{3}{5}=\mathrm{0,6}$ stimmt. Bei $\kappa =100$ wäre er $\frac{99}{101}\approx \mathrm{0,98}$, und man braucht über hundert Schritte für eine Stelle Genauigkeit. Das erklärt, warum das Verfahren bei „schmalen Tälern“ zickzackt und warum die Kondition entscheidend ist (siehe Numerik-Grundlagen).

Das Verfahren geht auf Augustin-Louis Cauchy zurück, der es 1847 vorschlug. Verbessert wird es durch das Verfahren der konjugierten Gradienten, das bei quadratischen Funktionen in höchstens $n$ Schritten ans Ziel kommt (siehe Numerische Lineare Algebra).

Das Newton-Verfahren

Wenn man die zweiten Ableitungen kennt, kann man besser vorgehen. Das Newton-Verfahren für die Optimierung wendet das Newton-Verfahren auf die Gleichung $\nabla f(x)=0$ an: $x_{k+1}=x_k-H{(x_k)}^{-1}\nabla f(x_k)$ mit der Hesse-Matrix $H$. Bei einer quadratischen Funktion ist $H=A$ konstant, und ein einziger Schritt genügt: $x_1=x_0-A^{-1}(A{x}_0-b)=A^{-1}b=x^{\ast }$. Allgemein konvergiert das Verfahren in der Nähe eines Minimums mit positiv definiter Hesse-Matrix quadratisch. Der Preis: In jedem Schritt muss ein lineares Gleichungssystem gelöst werden.

Nebenbedingungen und die KKT-Bedingungen

Bei Gleichungsnebenbedingungen $h(x)=0$ helfen die Lagrange-Multiplikatoren: Im Optimum ist $\nabla f+\lambda \nabla h=0$. Bei Ungleichungen $g_i(x)\le 0$ gibt es eine Verallgemeinerung.

Die letzte Bedingung heißt Komplementarität: Eine Nebenbedingung hat nur dann einen Multiplikator ${\mu }_i>0$, wenn sie am Optimum scharf ist ($g_i=0$). Inaktive Bedingungen spielen keine Rolle. Das Vorzeichen ${\mu }_i\ge 0$ hat eine Bedeutung: Die Abstiegsrichtung $-\nabla f$ zeigt am Optimum in den verbotenen Bereich, man würde die Nebenbedingung gern verletzen. Der Multiplikator misst, wie viel man dadurch gewinnen würde (Schattenpreis).

Für lineare $f$ und $g_i$ ergeben die KKT-Bedingungen die Optimalitätsbedingungen der linearen Optimierung: zulässiges Primal- und Dualproblem und komplementärer Schlupf. Bei konvexen Problemen mit vielen Nebenbedingungen kommen heute Innere-Punkte-Verfahren zum Einsatz, die sich im Inneren des zulässigen Bereichs dem Optimum nähern.

Übungen

Immer neue Aufgaben mit Lösungen gibt es auf dem Blatt Gradientenverfahren, Newton und KKT.

Geschichte: von Cauchy zum maschinellen Lernen

Augustin-Louis Cauchy schlug 1847 vor, ein Gleichungssystem durch schrittweises Absteigen entlang des Gradienten zu lösen. Jacques Hadamard schlug 1907 unabhängig ein ähnliches Verfahren vor, und Haskell Curry untersuchte 1944 die Konvergenz für nichtlineare Probleme. Die Bedingungen für Ungleichungsnebenbedingungen stehen in der Masterarbeit von William Karush von 1939. Sie blieb unveröffentlicht und wurde vergessen, bis Harold Kuhn und Albert Tucker die Bedingungen 1951 auf einer Konferenz unabhängig vorstellten. Deshalb heißen sie KKT- oder Kuhn-Tucker-Bedingungen. Das Gradientenverfahren in seiner stochastischen Variante ist heute das Standardverfahren, um neuronale Netze zu trainieren: Die Funktion $f$ ist dann der Fehler des Netzes, die Variablen sind seine Millionen Gewichte. 1988 veröffentlichten Barzilai und Borwein ihre nach ihnen benannte Schrittweitenwahl.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Gradientenverfahren
• Wikipedia: Karush-Kuhn-Tucker-Bedingungen
• Wikipedia (englisch): William Karush
• Stephen Boyd, Lieven Vandenberghe: Convex Optimization, Cambridge University Press.
• Jorge Nocedal, Stephen Wright: Numerical Optimization, Springer, New York.