U 07 – Gradientenverfahren mit exakter Liniensuche

 

Zeigen Sie, dass das Gradientenverfahren mit exakter Liniensuche das Optimierungsproblem mit der Zielfunktion

f\left( {\vec x} \right): = \frac{1}{2}{\left\| {\vec x} \right\|^2}+{\vec b^T}\vec x\quad ,\quad \vec b \in {\mathbb{R}^n}

für ein beliebiges {x_0} \in {\mathbb{R}^n} in einem Schritt löst.

Lösung

Für das Gradientenverfahren benötigen wir zunächst den Gradienten von f:

\nabla f\left( {\vec x} \right): = \nabla \frac{1}{2}{\left\| {\vec x} \right\|^2}+\nabla {{\vec b}^T}\vec x\quad ,\quad \vec b \in {\mathbb{R}^n}

\nabla \frac{1}{2}{\left\| {\vec x} \right\|^2} = \frac{1}{2}\left( {\begin{array}{*{20}{c}}{\frac{\partial }{{\partial {x_1}}}} \\   \vdots \\ {\frac{\partial }{{\partial {x_n}}}}  \end{array}} \right)\left( {x_1^2+ \ldots +x_n^2} \right) = \frac{1}{2}\left( {\begin{array}{*{20}{c}}{2{x_1}} \\   \vdots \\ {2{x_n}}  \end{array}} \right) = \left( {\begin{array}{*{20}{c}}{{x_1}} \\   \vdots \\ {{x_n}}  \end{array}} \right) = \vec x

\nabla {{\vec b}^T}\vec x = \left( {\begin{array}{*{20}{c}}{\frac{\partial }{{\partial {x_1}}}} \\   \vdots \\ {\frac{\partial }{{\partial {x_n}}}}  \end{array}} \right)\left( {{b_1}{x_1}+ \ldots +{b_n}{x_n}} \right) = \left( {\begin{array}{*{20}{c}}{{b_1}} \\   \vdots \\ {{b_n}}  \end{array}} \right) = \vec b

\quad \Rightarrow \quad \nabla f\left( {\vec x} \right) = \vec x+\vec b

\quad \Rightarrow \quad \nabla f\left( {{{\vec x}_k}} \right) = {{\vec x}_k}+{{\vec b}_k}

Somit haben wir unseren Gradienten und damit die Suchrichtung.

An dieser Stelle sind nun 2 Fälle zu unterscheiden.

Fall 1

{\vec x_0} = -\vec b

In diesem Fall wäre \nabla f\left( {{{\vec x}_0}} \right) = 0. Wir befänden uns also bereits im Extremum.

Fall 2

In diesem Fall gilt es nun, die benötigte Schrittweite zu bestimmen. Dazu machen wir von {x_0} aus einen Schritt in Richtung des negativen Gradienten und betrachten die Funktion in Abhängigkeit der Schrittweite t:

\varphi \left( t \right) = f\left( {{{\vec x}_0}-t\nabla f\left( {{x_0}} \right)} \right) = \frac{1}{2}{\left\| {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right\|^2}+{\vec b^T}\left( {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right)

Hier gilt es nun, das Minimum zu finden. Wir leiten also ab:

\varphi \left( t \right) = \frac{1}{2}{\left\| {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right\|^2}+{\vec b^T}\left( {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right)

Für den ersten Term gilt:

\frac{\partial }{{\partial t}}\left[ {\frac{1}{2}{{\left\| {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right\|}^2}} \right] = \frac{\partial }{{\partial t}}\frac{1}{2}\left[ {{{\left( {{x_{0,1}}-t\left( {{x_{0,1}}+{b_1}} \right)} \right)}^2}+ \ldots +{{\left( {{x_{0,n}}-t\left( {{x_{0,n}}+{b_n}} \right)} \right)}^2}} \right]

\qquad = -\frac{1}{2}\left[ {2\left( {{x_{0,1}}-t\left( {{x_{0,1}}+{b_1}} \right)} \right)\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +2\left( {{x_{0,n}}-t\left( {{x_{0,n}}+{b_n}} \right)} \right)\left( {{x_{0,n}}+{b_n}} \right)} \right]

Für den zweiten Term gilt:

\frac{\partial }{{\partial t}}\left[ {{{\vec b}^T}\left( {{{\vec x}_0}-t\left( {{{\vec x}_0}+\vec b} \right)} \right)} \right] = \frac{\partial }{{\partial t}}\left[ {{b_1}\left( {{x_{0,1}}-t\left( {{x_{0,1}}+{b_1}} \right)} \right)+ \ldots +{b_n}\left( {{x_{0,n}}-t\left( {{x_{0,n}}+{b_n}} \right)} \right)} \right]

\qquad = -\left[ {{b_1}\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +{b_n}\left( {{x_{0,n}}+{b_n}} \right)} \right]

Zusammengesetzt erhalten wir:

\Rightarrow \quad {\varphi ^\prime }\left( t \right) = -\left[ {\left( {{x_{0,1}}-t\left( {{x_{0,1}}+{b_1}} \right)} \right)\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +\left( {{x_{0,n}}-t\left( {{x_{0,n}}+{b_n}} \right)} \right)\left( {{x_{0,n}}+{b_n}} \right)} \right]+

\qquad \qquad \quad -\left[ {{b_1}\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +{b_n}\left( {{x_{0,n}}+{b_n}} \right)} \right]

\Rightarrow \quad {\varphi ^\prime }\left( t \right) = -\left[ {\left( {{x_{0,1}}-t\left( {{x_{0,1}}+{b_1}} \right)+{b_1}} \right)\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +\left( {{x_{0,n}}-t\left( {{x_{0,n}}+{b_n}} \right)+{b_n}} \right)\left( {{x_{0,n}}+{b_n}} \right)} \right]

\Rightarrow \quad {\varphi ^\prime }\left( t \right) = -\left[ {\left( {\left( {{x_{0,1}}+{b_1}} \right)-t\left( {{x_{0,1}}+{b_1}} \right)} \right)\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +\left( {\left( {{x_{0,n}}+{b_n}} \right)-t\left( {{x_{0,n}}+{b_n}} \right)} \right)\left( {{x_{0,n}}+{b_n}} \right)} \right]

\Rightarrow \quad {\varphi ^\prime }\left( t \right) = -\left( {1-t} \right)\left[ {\left( {{x_{0,1}}+{b_1}} \right)+ \ldots +\left( {{x_{0,n}}+{b_n}} \right)} \right]

\Rightarrow \quad {\varphi ^\prime }\left( t \right) = \left( {t-1} \right){\left\| {{{\vec x}_0}+\vec b} \right\|^2}

Für die zweite Ableitung folgt damit:

{\varphi ^{\prime \prime }}\left( t \right) = {\left\| {{{\vec x}_0}+\vec b} \right\|^2}

Für ein Minimum muss gelten:

{\varphi ^\prime }\left( t \right) = \left( {t-1} \right){\left\| {{{\vec x}_0}+\vec b} \right\|^2}\mathop = \limits^! 0\quad \Rightarrow \quad t = 1

{\varphi ^{\prime \prime }}\left( t \right) = {\left\| {{{\vec x}_0}+\vec b} \right\|^2} > 0

Damit ist das Optimierungsproblem tatsächlich in einem Schritt lösbar.

Die erkennt man auch am Funktionsverlauf von f mit {\vec b^T} = \left( {\begin{array}{*{20}{c}}  1&1  \end{array}} \right):

opti-u07-funktionsverlauf

Der negative Gradient der Funktion zeigt an jeder Stelle genau in Richtung Minimum.

    \[\mathcal{J}\mathcal{K}\]