U 01.2 – Gradient, Hesse-Matrix und Minimalstelle

 

Es sei

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

wobei c \in \mathbb{R}, \vec b \in {\mathbb{R}^n} und A \in {\mathbb{R}^{n \times n}} symmetrisch und positiv definit sei.

  1. Berechnen Sie Gradienten \nabla f\left( {\vec x} \right) und Hesse-Matrix {H_f}\left( {\vec x} \right)

  2. Zeigen Sie, dass für ein \hat {\vec x} mit \nabla f\left( {\hat {\vec x}} \right) = 0 gilt:

    f\left( {\vec x} \right) = f\left( {\hat {\vec x}} \right)+\frac{1}{2}{\left( {\vec x-\hat {\vec x}} \right)^T}A\left( {\vec x-\hat {\vec x}} \right)\quad \forall \vec x \in {\mathbb{R}^n}

  3. Folgern Sie aus b), dass \hat {\vec x} mit \nabla f\left( {\hat {\vec x}} \right) = 0 eine globale Minimalstelle von f ist.

Lösung

a)

Zunächst schreiben wir die Funktion umgeformt auf:

f\left( {\vec x} \right) = \frac{1}{2}{{\vec x}^T}A\vec x-{{\vec b}^T}\vec x+c

f\left( {\vec x} \right) = \frac{1}{2}\left( {{x_1}\; \ldots \;{x_n}} \right)\left( {\begin{array}{*{20}{c}}{{a_{11}}}& \ldots &{{a_{1n}}} \\   \vdots & \ddots & \vdots \\ {{a_{n1}}}& \ldots &{{a_{nn}}}  \end{array}} \right)\left( {\begin{array}{*{20}{c}}{{x_1}} \\   \vdots \\ {{x_n}}  \end{array}} \right)-\left( {{b_1}\; \ldots \;{b_n}} \right)\left( {\begin{array}{*{20}{c}}{{x_1}} \\   \vdots \\ {{x_n}}  \end{array}} \right)+c

\quad \Rightarrow \quad f\left( {\vec x} \right) = \frac{1}{2}\sum\limits_{i,j = 1}^n {{a_{ij}}{x_i}{x_j}} -\sum\limits_{i = 1}^n {{b_i}{x_i}} +c

Nun bilden wir die erste Ableitung:

\frac{{\partial f}}{{\partial {x_k}}}\left( {\vec x} \right) = \frac{1}{2}\frac{\partial }{{\partial {x_k}}}\left( {\sum\limits_{k \ne j = 1}^n {\sum\limits_{k \ne i = 1}^n {{a_{ij}}{x_i}{x_j}} } +\sum\limits_{k \ne j = 1}^n {{a_{kj}}{x_k}{x_j}} +\sum\limits_{k \ne i = 1}^n {{a_{ik}}{x_i}{x_k}} +{a_{kk}}x_k^2} \right)-{b_k}+0

\quad \Rightarrow \quad \frac{{\partial f}}{{\partial {x_k}}}\left( {\vec x} \right) = \frac{1}{2}\left( {0+\sum\limits_{k \ne j = 1}^n {{a_{kj}}{x_j}} +\sum\limits_{k \ne i = 1}^n {{a_{ik}}{x_i}} +2{a_{kk}}{x_k}} \right)-{b_k}

Wegen Symmetrie gilt {a_{jk}} = {a_{kj}}. Die beiden Summen sind also identisch. Der letzte Term in der Klammer ergänzt die Summen jeweils um das fehlende Element. Es folgt für die partielle Ableitung in Richtung k:

\frac{{\partial f}}{{\partial {x_k}}}\left( {\vec x} \right) = \frac{1}{2}\left( {\sum\limits_{k \ne j = 1}^n {{a_{kj}}{x_j}} +\sum\limits_{k \ne i = 1}^n {{a_{ik}}{x_i}} +2{a_{kk}}{x_k}} \right)-{b_k} = \sum\limits_{j = 1}^n {{a_{kj}}{x_j}} -{b_k}

Daraus können wir nun den Gradienten bilden:

\nabla f\left( {\vec x} \right) = \left( {\begin{array}{*{20}{c}}{\sum\limits_{j = 1}^n {{a_{1j}}{x_j}} } \\   \vdots \\ {\sum\limits_{j = 1}^n {{a_{nj}}{x_j}} }  \end{array}} \right)-\left( {\begin{array}{*{20}{c}}{{b_1}} \\   \vdots \\ {{b_n}}  \end{array}} \right) = A\vec x-\vec b

Um die Hesse-Matrix zu erhalten, müssen wir alle zweiten Ableitungen bilden. Wir erhalten:

{H_f}\left( {\vec x} \right) = \operatorname{grad} \left( {\nabla f\left( x \right)} \right) = \frac{{\partial \left( {\nabla f\left( x \right)} \right)}}{{\partial {x_j}}} = A

b)

Da wir den Gradienten bereits kennen, wissen wir auch:

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

Alle Ableitungen von f mit Ordnung größer 2 sind gleich 0. Dies wissen wir, da die zweiten Ableitungen (Hesse-Matrix) konstant sind. Wir schreiben nun die Funktion als Taylorreihe auf:

f\left( {\vec x} \right) = {T_{2,\hat {\vec x}}}\left( {\vec x} \right)

Dabei ist {T_{2,\hat {\vec x}}}\left( {\vec x} \right) das Taylorpolynom zweiter Ordnung von f mit Entwicklungspunkt \hat {\vec x}.

Wir erhalten:

f\left( {\vec x} \right) = f\left( {\hat {\vec x}} \right)+\underbrace {\nabla f{{\left( {\hat {\vec x}} \right)}^T}\left( {\vec x-\hat {\vec x}} \right)}_{ = 0}+\frac{1}{2}{\left( {\vec x-\hat {\vec x}} \right)^T}\underbrace {{H_f}\left( {\hat {\vec x}} \right)}_{ = A}\left( {\vec x-\hat {\vec x}} \right)+0

\quad \Rightarrow \quad f\left( {\vec x} \right) = f\left( {\hat {\vec x}} \right)+\frac{1}{2}{\left( {\vec x-\hat {\vec x}} \right)^T}A\left( {\vec x-\hat {\vec x}} \right)

Damit ist die Aussage bewiesen.

c)

Aus b) folgt:

f\left( {\vec x} \right)-f\left( {\hat {\vec x}} \right) = \frac{1}{2}{\left( {\vec x-\hat {\vec x}} \right)^T}A\left( {\vec x-\hat {\vec x}} \right) > 0, falls \vec x \ne \hat {\vec x}

Dies folgt aus der positiven Definitheit der Matrix A, denn:

x \ne 0\quad \Rightarrow \quad {x^T}Ax > 0\quad \Leftrightarrow \quad pos.\;def.