---
fontsize: 8pt
format:
    beamer:
        include-in-header: "11_Header.tex"
bibliography: 11_Referenzen.bib
---

#  {.plain}

\center
```{r, echo = FALSE, out.width = "20%", fig.align = "center"}
knitr::include_graphics("11_Abbildungen/mv_11_otto.png")
```
\vspace{2mm}

\huge
Multivariate Verfahren
\vspace{4mm}

\large
MSc Psychologie | MSc Klinische Psychologie und Psychotherapie   

WiSe 2023/24

\vspace{4mm}
\normalsize
Prof. Dr. Dirk Ostwald

#  {.plain}
\vfill
\center
\huge
\textcolor{black}{(11) Nichtlineare Optimierung}
\vfill

# 
Motivation

\footnotesize

* Viele Verfahren der Prädiktiven Modellierung oder, wie heutzutage auch oft gesagt wird, der "Künstlichen Intelligenz", z.B. Neuronale Netze als generalisierte logistische Regression oder Support-Vektor-Maschinen, basieren auf mathematisch recht überschaubaren Modellen.

* Ihre momentane breite Verwendung verdanken diese Verfahren im Wesentlichen den verbesserten Computer-Hardware-Komponenten der letzten 15 Jahre, die zum Lernen ihrer Parameter ("Trainieren") 
genutzt werden, weniger wesentlichen neuen theoretischen Einsichten. Für einen aktuellen Überblick, 
siehe zum Beispiel @prince2023 und @murphy2023.

* Das Lernen von Parametern von Modellen der Prädiktiven Modellierung enstpricht der 
Optimierung von Funktionen, wie wir in (12) Logistische Regression und (13) 
Neuronale Netze sehen werden,  insbesondere der Minimierung sogenannter *Loss Functions*.

* Zur Optimierung von Funktionen werden in diesem Bereich insbesondere und im einfachsten   Fall sogenannten *Gradientenverfahren* eingesetzt. In diesem Abschnitt wollen wir
deshalb zunächst ein Grundverständnis von Gradientenverfahren erarbeiten.
  

#
\vfill
\large
\setstretch{3}

Multivariate Differentialrechnung

Grundlagen der nichtlinearen Optimierung

Gradientenverfahren

Selbstkontrollfragen
\vfill


#
\vfill
\large
\setstretch{3}

**Multivariate Differentialrechnung**

Grundlagen der nichtlinearen Optimierung

Gradientenverfahren

Selbstkontrollfragen
\vfill


# Multivariate Differentialrechnung
\small
\begin{definition}[Multivariate reellwertige Funktion]
Eine Funktion der Form
\begin{equation}
f : \mathbb{R}^n \to \mathbb{R}, x \mapsto f(x) = f(x_1,...,x_n) 
\end{equation}
heißt \textit{multivariate reellwertige} Funktion. 
\end{definition}

Beispiel für $n:= 2$
\begin{equation}
f : \mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := x_1^2 + x_2^2
\end{equation}  

```{r, echo = F, eval = F}

# Funktionsdefinitionen
# -----------------------------------------------------------------------------
# Zielfunktion
f = function(x) {
  return(x[1]^2 + x[2]^2)                 # f(x) := x_1^2 + x_2^2
}
# Gradient der Zielfunktion
nabla_f = function(x) {
  return(matrix(c(2*x[1],2*x[2]),         # \nabla f(x) := (2x_1, 2x_2)^T
                nrow = 2))
}

pdf(
file        = "11_Abbildungen/mv_11_bivariate_funktion.pdf",
width       = 8,
height      = 4)
par(
family      = "sans",
mfcol       = c(1,2),
pty         = "s",
bty         = "l",
lwd         = 1,
las         = 1,
xaxs        = "i",
yaxs        = "i",
font.main   = 1,
cex         = 1,
cex.main    = 1.2)


# Bivariate reellwertige Funktion 1
x_min  = -2                                                                     # x_i Minimum
x_max  =  2                                                                     # x_i Maximum
x_res  = 1e2                                                                    # x_i Auflösung
x_1    = seq(x_min, x_max, length.out = x_res)                                  # x_1 Raum
x_2    = seq(x_min, x_max, length.out = x_res)                                  # x_2 Raum
X      = expand.grid(x_1,x_2)                                                   # X = (x_1,x_2)^T Raum
fX     = matrix(as.matrix(f(X)),nrow = x_res )                                  # f(x)
persp(
x_1,
x_2,
fX,
col    = "gray60",
border = NA,
theta  = 30,
phi    = 30,
ltheta = -120,
shade  = 0.75,
zlab   = "",
main   = TeX("$f(x) := x_1^2 + x_2^2$"))

# Bivariate reellwertige Funktion 2
contour(
x_1,
x_2,
fX,
xlim      = c(x_min,x_max),
ylim      = c(x_min,x_max),
xlab      = TeX("$x_1$"),
ylab      = TeX("$x_2$"),
levels    = c(.1,.5, 1:8),
main      = TeX("$f(x) := x_1^2 + x_2^2$"))
g         = grid()
dev.off()
```

\center
```{r, echo = FALSE, out.width = "85%"}
knitr::include_graphics("11_Abbildungen/mv_11_bivariate_funktion.pdf")
```

# Multivariate Differentialrechnung
\footnotesize
\begin{definition}[Partielle Ableitung]
Es sei $D \subseteq \mathbb{R}^n$ eine Menge und
\begin{equation}
f : D \to \mathbb{R}, x \mapsto f(x)
\end{equation}
eine multivariate reellwertige  Funktion.
$f$ heißt in $x \in D$ \textit{nach $x_i$ partiell differenzierbar}, wenn der Grenzwert
\begin{equation}
\frac{\partial}{\partial x_i}f(x) := \lim_{h\to 0} \frac{f(x + he_i)-f(x)}{h}
\end{equation}
existiert. $\frac{\partial}{\partial x_i}f(x)$ heißt dann die \textit{ partielle Ableitung von $f$ nach $x_i$
an der Stelle $x$}. Wenn $f$ für alle $x \in D$, nach $x_i$  partiell differenzierbar ist,
dann heißt $f$ \textit{nach $x_i$  partiell differenzierbar} und die Funktion
\begin{equation}
\frac{\partial}{\partial x_i} f: D \to \mathbb{R}, x \mapsto \frac{\partial}{\partial x_i}f(x)
\end{equation}
heißt \textit{partielle Ableitung von $f$ nach $x_i$}.
\vspace{2mm}

$f$ heißt \textit{partiell differenzierbar in $x \in D$}, wenn $f$ für alle $i = 1,...,n$
in $x \in D$ nach $x_i$ partiell differenzierbar ist, und  $f$ heißt partiell differenzierbar,
wenn $f$ für alle  $i = 1,...,n$ in allen $x \in D$ nach $x_i$ partiell differenzierbar ist.
\end{definition}

# Multivariate Differentialrechnung
\small
\setstretch{1.8}
Bemerkungen

* $e_i \in \mathbb{R}^n$ bezeichnet den $i$ten Einheitsvektor.
* $\frac{f(x + he_i)-f(x)}{h}$  misst die Änderung $f(x+he_i)-f(x)$ von $f$ pro Strecke $h$ in Richtung $e_i$.
* Für $h\to 0$ misst der Differenzquotient die Änderungs\underline{rate} von $f$ in $x$ in Richtung $e_i$.
* $\frac{\partial}{\partial x_i}f(x)$ ist eine Zahl, $\frac{\partial}{\partial x_i}f$ ist eine Funktion.
* Praktisch berechnet man $\frac{\partial}{\partial x_i}f$ als die (einfache) Ableitung
\begin{equation}
\frac{d}{dx_i}\tilde{f}_{x_1,...x_{i-1},x_{i+1}, ...,x_n}(x_i)
\end{equation}
der univariaten reellwertigen Funktion
\begin{equation}
\tilde{f} : \mathbb{R} \to \mathbb{R}, x_i \mapsto \tilde{f}_{x_1,...x_{i-1},x_{i+1}, ...,x_n}(x_i) := f(x_1,...,x_i, ...,x_n).
\end{equation}
* Man betrachtet alle $x_j$ mit $j \neq i$ also als Konstanten.

# Multivariate Differentialrechnung
Beispiel (1)
\footnotesize

Wir betrachten die Funktion
\begin{equation}
f:\mathbb{R}^2\to \mathbb{R}, x\mapsto f(x):=x_1^2+x_2^2.
\end{equation}
Weil die Definitionsmenge dieser Funktion zweidimensional ist, kann man zwei
partielle Ableitungen berechnen
\begin{equation}\label{eq:pdex_1}
\frac{\partial }{\partial x_1}f:\mathbb{R}^2 \to \mathbb{R},
x\mapsto \frac{\partial}{\partial x_{1}} f(x)
\mbox{ und }
\frac{\partial}{\partial x_2} f:\mathbb{R}^2\to \mathbb{R},
x\mapsto \frac{\partial }{\partial x_2}f(x).
\end{equation}
Um die erste dieser partiellen Ableitungen zu berechnen, betrachtet man die Funktion
\begin{equation}
f_{x_2}:\mathbb{R} \to \mathbb{R}, x_1 \mapsto f_{x_2}(x_1):=x_1^2+x_2^2,
\end{equation}
wobei $x_2$ hier die Rolle einer Konstanten einnimmt. Um explizit zu machen, dass $x_2$
kein Argument der Funktion ist, die Funktion aber weiterhin von $x_2$ abhängt haben
wir die Subskriptnotation $f_{x_2}(x_1)$ verwendet. Um nun die partielle Ableitung
zu berechnen, berechnen wir die (einfache) Ableitung von $f_{x_2}$,
\begin{equation}
f_{x_2}'(x)=2x_{1}.
\end{equation}
Es ergibt sich also
\begin{equation}
\frac{\partial}{\partial x_1}f:\mathbb{R}^2\to \mathbb{R},
x\mapsto \frac{\partial}{\partial x_1}f(x)
=\frac{\partial}{\partial x_1}(x_1^2+x_2^2)
=f_{x_2}'(x)=2x_1.
\end{equation}
Analog gilt mit der entsprechenden Formulierung von $f_{x_1}$, dass
\begin{equation}
\frac{\partial}{\partial x_2}f:\mathbb{R}^2\to \mathbb{R},
x\mapsto \frac{\partial}{\partial x_2}f(x)
=\frac{\partial}{\partial x_2}(x_1^2+x_2^2)
=f_{x_1}'(x)=2x_2.
\end{equation}

# Multivariate Differentialrechnung
\small
\begin{definition}[Zweite partielle Ableitungen]
$f: \mathbb{R}^n \to \mathbb{R}$ sei eine multivariate reellwertige Funktion und
$\frac{\partial}{\partial x_i}f$  sei die partielle Ableitung von $f$ nach $x_i$.
Dann ist die zweite partielle
Ableitung von $f$ nach $x_i$ und $x_j$ definiert als
\begin{equation}
\frac{\partial^2}{\partial x_j \partial x_i} f(x)
:= \frac{\partial}{\partial x_j}\left(\frac{\partial}{\partial x_i}f\right)
\end{equation}
\end{definition}

\footnotesize
Bemerkungen

* \justifying Wie die zweite Ableitung ist auch die zweite partielle Ableitung rekursiv definiert.
* Zu jeder partiellen Ableitung $\frac{\partial}{\partial x_i}f$ gibt es $n$ zweite partiellen Ableitungen $\frac{\partial^2}{\partial x_j\partial x_i}f, j = 1,...,n$.

# Multivariate Differentialrechnung
\small
\begin{theorem}[Satz von Schwarz]
\justifying
\normalfont
$f: \mathbb{R}^n \to \mathbb{R}$ sei eine partiell differenzierbare multivariate reellwertige Funktion.
Dann gilt
\begin{equation}
  \frac{\partial^2}{\partial x_j\partial x_i}f(x)
= \frac{\partial^2}{\partial x_i\partial x_j}f(x)
	\mbox{ für alle }  1 \le i,j \le n.
\end{equation}
\end{theorem}

\footnotesize
Bemerkungen

* Wir verzichten auf einen Beweis.
* Das Theorem von Schwarz besagt, dass die Reihenfolge des partiellen Ableitens irrelevant ist
* Das Theorem erleichtert die Berechnung von zweiten partiellen Ableitungen.
* Das Theorem hilft, Fehler bei der Berechnung zweiter partieller Ableitungen aufzudecken.

# Multivariate Differentialrechnung

Beispiel (1) (fortgeführt)
\footnotesize

Wir wollen die partiellen Ableitungen zweiter Ordnung der Funktion
\begin{equation}
f:\mathbb{R}^{2}\to \mathbb{R}, x\mapsto f(x):=x_1^2+x_2^2.
\end{equation}
berechnen. Mit den Ergebnissen für die partiellen Ableitungen erster Ordnung dieser Funktion ergibt sich
\begin{align}
\begin{split}
\frac{\partial^2}{\partial x_1 \partial x_1} f(x)
& = \frac{\partial}{\partial x_1}\left(\frac{\partial}{\partial x_1} f(x)\right)
  = \frac{\partial}{\partial x_1}(2x_1)
  = 2
\\
\frac{\partial^2}{\partial x_1 \partial x_2} f(x)
& = \frac{\partial}{\partial x_1}\left(\frac{\partial}{\partial x_2} f(x)\right)
  = \frac{\partial}{\partial x_1}(2x_2)
  = 0
\\
\frac{\partial^2}{\partial x_2 \partial x_1} f(x)
& = \frac{\partial}{\partial x_2}\left(\frac{\partial}{\partial x_1} f(x)\right)
  = \frac{\partial}{\partial x_2}(2x_1)
  = 0
  \\
\frac{\partial^2}{\partial x_2 \partial x_2} f(x)
& = \frac{\partial}{\partial x_2}\left(\frac{\partial}{\partial x_2} f(x)\right)
  = \frac{\partial}{\partial x_2}(2x_2)
  = 2
\end{split}
\end{align}
Offenbar gilt
\begin{equation}
\frac{\partial^2}{\partial x_1 \partial x_2} f(x) = \frac{\partial^2}{\partial x_2 \partial x_1} f(x).
\end{equation}

# Multivariate Differentialrechnung
\vfill
Beispiel (2)
\footnotesize

Wir wollen die partiellen Ableitungen erster und zweiter Ordnung der Funktion
\begin{equation}
f:\mathbb{R}^{3}\to \mathbb{R}, x\mapsto f(x):=x_1^2+x_1x_2+x_2\sqrt{x_3}.
\end{equation}
berechnen.
\vspace{2mm}

Mit den Rechenregeln für Ableitungen ergibt sich für die partiellen Ableitungen erster Ordnung
\begin{align}
\begin{split}
& \frac{\partial}{\partial x_1}f(x)
= \frac{\partial}{\partial x_1}\left(x_1^2+x_1x_2+x_2\sqrt{x_3} \right) = 2x_1+x_2,                   \\
& \frac{\partial}{\partial x_2}f(x)
= \frac{\partial}{\partial x_2}\left(x_1^2+x_1x_2+x_2\sqrt{x_3} \right) = x_1+\sqrt{x_3},             \\
& \frac{\partial}{\partial x_3}f(x)
= \frac{\partial}{\partial x_3}\left(x_1^2+x_1x_2+x_2\sqrt{x_3} \right) = \frac{x_{2}}{2\sqrt{x_3}}.
\end{split}
\end{align}
\vfill

# Multivariate Differentialrechnung
Beispiel (2) (fortgeführt)
\footnotesize

Für die zweiten partiellen Ableitungen hinsichtlich $x_1$ ergibt sich
\begin{align}
\begin{split}
    \frac{\partial^2}{\partial x_1 \partial x_1}f(x)
& = \frac{\partial}{\partial x_1} \left(\frac{\partial}{\partial x_1} f(x) \right)
  = \frac{\partial}{\partial x_1}\left(2x_1+x_2\right) = 2, \\
    \frac{\partial^2}{\partial x_2\partial x_1}f(x)
& = \frac{\partial}{\partial x_2} \left(\frac{\partial}{\partial x_1} f(x) \right)
  = \frac{\partial}{\partial x_2}\left(2x_1+x_2 \right) = 1, \\
    \frac{\partial^2}{\partial x_3\partial x_1} f(x)
& = \frac{\partial}{\partial x_3}\left(\frac{\partial}{\partial x_{1}} f(x) \right)
  = \frac{\partial}{\partial x_3}\left(2x_1+x_2\right)=0.
\end{split}
\end{align}
Für die zweiten partiellen Ableitungen hinsichtlich $x_2$ ergibt sich
\begin{align}
\begin{split}
    \frac{\partial^2}{\partial x_1\partial x_2}f(x)
& = \frac{\partial}{\partial x_1}\left(\frac{\partial}{\partial x_2}f(x) \right)
  = \frac{\partial}{\partial x_{1}}\left(x_1+ \sqrt{x_3} \right) = 1, \\
    \frac{\partial^2}{\partial x_2 \partial x_2}f(x)
& = \frac{\partial}{\partial x_2}\left(\frac{\partial}{\partial x_2}f(x) \right)
  = \frac{\partial}{\partial x_2}\left(x_1 + \sqrt{x_3} \right) = 0, \\
    \frac{\partial^2}{\partial x_3\partial x_2}f(x)
& = \frac{\partial}{\partial x_3}\left(\frac{\partial}{\partial x_2}f(x) \right)
  = \frac{\partial}{\partial x_3}\left(x_1+\sqrt{x_3} \right) =\frac{1}{2\sqrt{x_3}}.
\end{split}
\end{align}

# Multivariate Differentialrechnung
Beispiel (2) (fortgeführt)
\footnotesize

Für die zweiten partiellen Ableitungen hinsichtlich $x_3$ ergibt sich
\begin{align}
\begin{split}
    \frac{\partial^{2}}{\partial x_1\partial x_3}f(x)
& = \frac{\partial}{\partial x_1}\left(\frac{\partial}{\partial x_3} f(x) \right)
  = \frac{\partial}{\partial x_1}\left(\frac{x_2}{2}\sqrt{x_3}\right) = 0, \\
    \frac{\partial^2}{\partial x_2\partial x_3}f(x)
& = \frac{\partial}{\partial x_2}\left(\frac{\partial}{\partial x_3}f(x) \right)
  = \frac{\partial}{\partial x_2}\left(\frac{x_2}{2 \sqrt{x_3}} \right)
  = \frac{1}{2\sqrt{x_3}}, \\
    \frac{\partial^2}{\partial x_3 \partial x_3}f(x)
& = \frac{\partial}{\partial x_3}\left(\frac{\partial}{\partial x_3}f(x) \right)
  = \frac{\partial}{\partial x_3}\left(x_2\frac{1}{2}x_3^{-\frac{1}{2}}\right)
  = -\frac{1}{4}x_2x_3^{-\frac{3}{2}}.
\end{split}
\end{align}
Weiterhin erkennt man, dass die Reihenfolge der partiellen Ableitungen irrelevant ist, denn es gilt
\begin{align}
\begin{split}
& \frac{\partial^{2}}{\partial x_{1}\partial x_{2}}f(x)
= \frac{\partial^{2}}{\partial x_{2}\partial x_{1}}f(x) = 1, \\
& \frac{\partial^{2}}{\partial x_{1}\partial x_{3}}f(x)
= \frac{\partial^{2}}{\partial x_{3}\partial x_{1}}f(x) = 0, \\
& \frac{\partial^{2}}{\partial x_{2}\partial x_{3}}f(x)
= \frac{\partial^{2}}{\partial x_{3}\partial x_{2}}f(x) = \frac{1}{2\sqrt{x_3}}.
\end{split}
\end{align}


# Multivariate Differentialrechnung
\small
\begin{definition}[Gradient]
\justifying
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine multivariate reellwertige Funktion.
Dann ist der \textit{Gradient} $\nabla f(x)$ von $f$ an der Stelle $x \in \mathbb{R}^n$
definiert als
\begin{equation}
\nabla f(x) :=
\begin{pmatrix}
\frac{\partial}{\partial x_1} f(x) 	\\
\frac{\partial}{\partial x_2} f(x) 	\\
\vdots								\\
\frac{\partial}{\partial x_n} f(x) 	\\
\end{pmatrix} \in \mathbb{R}^n.
\end{equation}
\end{definition}

\footnotesize
Bemerkung

* $\nabla f(x)$ fasst die partiellen Ableitungen von $f$ an der Stelle $x \in \mathbb{R}^n$ in einem Vektor zusammen.
* Gradienten sind multivariate vektorwertige Abbildungen der Form $\nabla f: \mathbb{R}^n \to \mathbb{R}^n, x \mapsto \nabla f(x)$.
* Wir zeigen später, dass $-\nabla f(x)$ die Richtung des steilsten Abstiegs von $f$ in $\mathbb{R}^n$ anzeigt.
* Für $n = 1$ gilt $\nabla f(x) = f'(x)$.

# Multivariate Differentialrechnung
Beispiele

\setstretch{1.6}
\small
Für die in Beispiel (1) betrachtete Funktion $f: \mathbb{R}^2 \to \mathbb{R}$ gilt
\begin{equation}
\nabla f(x) :=
\begin{pmatrix}
\frac{\partial}{\partial x_1} f(x) 	\\
\frac{\partial}{\partial x_2} f(x) 	\\
\end{pmatrix}
=
\begin{pmatrix}
2x_1                    \\
2x_2
\end{pmatrix}
\in \mathbb{R}^2.
\end{equation}
\vspace{2mm}

Für die in Beispiel (2) betrachtete Funktion $f: \mathbb{R}^3 \to \mathbb{R}$ gilt
\begin{equation}
\nabla f(x) :=
\begin{pmatrix}
\frac{\partial}{\partial x_1} f(x) 	\\
\frac{\partial}{\partial x_2} f(x) 	\\
\frac{\partial}{\partial x_3} f(x) 	\\
\end{pmatrix}
=
\begin{pmatrix}
2x_1+x_2                    \\
x_1+\sqrt{x_3}              \\
\frac{x_{2}}{2\sqrt{x_3}}   \\
\end{pmatrix}
\in \mathbb{R}^3.
\end{equation}

# Multivariate Differentialrechnung

Beispiel (1) (fortgeführt)
\footnotesize

Gradienten von $f : \mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := x_1^2 + x_2^2$ bei

\center
\textcolor{black}{      $x = \begin{pmatrix}  0.7 \\  0.7 \end{pmatrix}\quad\quad\quad$}
\textcolor{blue}{       $x = \begin{pmatrix} -0.3 \\  0.1 \end{pmatrix}\quad\quad\quad$}
\textcolor{red}{        $x = \begin{pmatrix} -0.5 \\ -0.4 \end{pmatrix}\quad\quad\quad$}
\textcolor{green}{  $x = \begin{pmatrix}  0.1 \\ -1.0 \end{pmatrix}$}
\vspace{-1mm}

```{r, echo = F, eval = F}
# Funktion
f = function(x) {
  return(x[1]^2 + x[2]^2)                 # f(x) := x_1^2 + x_2^2
}
# Gradient
nabla_f = function(x) {
  return(matrix(c(2*x[1],2*x[2]),         # \nabla f(x) := (2x_1, 2x_2)^T
                nrow = 2))
}

x_min  = -2                                                                     # x_i Minimum
x_max  =  2                                                                     # x_i Maximum
x_res  = 1e2                                                                    # x_i Auflösung
x_1    = seq(x_min, x_max, length.out = x_res)                                  # x_1 Raum
x_2    = seq(x_min, x_max, length.out = x_res)                                  # x_2 Raum
X      = expand.grid(x_1,x_2)                                                   # X = (x_1,x_2)^T Raum
fX     = matrix(as.matrix(f(X)),nrow = x_res )                                  # f(x)

# Visualisierung
pdf(
file        = "11_Abbildungen/mv_11_gradientbeispiel.pdf",
width       = 5,
height      = 5)
par(
family      = "sans",
mfcol       = c(1,1),
pty         = "s",
bty         = "l",
lwd         = 1,
las         = 1,
xaxs        = "i",
yaxs        = "i",
font.main   = 1,
cex         = 1.1,
cex.main    = 1.3)

# Funktion
contour(
x_1,
x_2,
fX,
xlim      =  c(x_min,x_max),
ylim      =  c(x_min,x_max),
xlab      = TeX("x_1"),
ylab      = TeX("x_2"),
levels    = c(.1,.5, 1:8),
main      = "")

# Gradientenbeispiele
A         = matrix(c(.7, -.5, -.3, .1,
                     .7, -.4,  .1, -1),
                   nrow   = 2,
                   byrow = T)

cols      = c("black", "red", "blue", "darkgreen")
for(i in 1:ncol(A)){
  points(
  A[1,i],
  A[2,i],
  col     = cols[i]
  )
  arrows(
  x0      = A[1,i],
  y0      = A[2,i],
  x1      = nabla_f(A[,i])[1],
  y1      = nabla_f(A[,i])[2],
  col     = cols[i],
  angle   = 30,
  length  = .1,
  lwd     = 2)
}
dev.off()
```

\vfill
```{r, echo = FALSE, out.width = "50%"}
knitr::include_graphics("11_Abbildungen/mv_11_gradientbeispiel.pdf")
```
\vfill

# Multivariate Differentialrechnung
\small
\setstretch{1.6}
\begin{definition}[Hesse-Matrix]
\justifying
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine multivariate reellwertige Funktion.
Dann ist die \textit{Hesse-Matrix} $\nabla^2 f(x)$ von $f$ an der Stelle $x \in \mathbb{R}^n$
definiert als
\begin{equation}
\nabla^2 f(x) :=
\begin{pmatrix}
	\frac{\partial^2}{\partial x_1 \partial x_1} f(x)
& 	\frac{\partial^2}{\partial x_1 \partial x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_1 \partial x_n} f(x)  \\
	\frac{\partial^2}{\partial x_2 \partial x_1} f(x)
& 	\frac{\partial^2}{\partial x_2 \partial x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_2 \partial x_n} f(x)  \\
	\vdots
& 	\vdots
& 	\ddots
& 	\vdots 									 	\\
	\frac{\partial^2}{\partial x_n \partial x_1} f(x)
& 	\frac{\partial^2}{\partial x_n \partial x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_n \partial x_n} f(x)  \\
\end{pmatrix} \in \mathbb{R}^{n \times n}.
\end{equation}
\end{definition}

\footnotesize
Bemerkung

* $\nabla^2 f(x)$ fasst die partiellen Ableitungen zweiter Ordnung von $f$ in einer Matrix zusammen.
* Hesse-Matrizen sind multivariate matrixwertige Abbildungen der Form $\nabla^2 f: \mathbb{R}^n \to \mathbb{R}^{n\times n}, x \mapsto \nabla^2 f(x)$.
* Für $n = 1$ gilt $\nabla^2 f(x) = f''(x)$.
* Mit $\frac{\partial^2}{\partial x_i\partial x_j}f(x) = \frac{\partial^2}{\partial x_j\partial x_i}f(x)$ für $1 \le i,j\le n$ folgt, dass $\left(\nabla^2f(x)\right)^T = \nabla^2f(x)$.

# Multivariate Differentialrechnung
Beispiel
\setstretch{1.6}
\footnotesize

Für die in Beispiel (1) betrachtete Funktion $f: \mathbb{R}^2 \to \mathbb{R}$ gilt
\begin{equation*}
\nabla^2 f(x) :=
\begin{pmatrix}
\frac{\partial^2}{\partial x_1 \partial x_1} f(x) & \frac{\partial^2}{\partial x_1 \partial x_2}	f(x) \\
\frac{\partial^2}{\partial x_2 \partial x_1} f(x) & \frac{\partial^2}{\partial x_2 \partial x_2}	f(x) \\
\end{pmatrix}
=
\begin{pmatrix}
2 & 0	\\
0 & 2	\\
\end{pmatrix}
\in \mathbb{R}^{2 \times 2}
\end{equation*}
\vspace{1mm}

Für die in Beispiel (2) betrachtete Funktion $f: \mathbb{R}^3 \to \mathbb{R}$ gilt
\setstretch{1.8}
\begin{align*}
\begin{split}
\nabla^2 f(x)
& :=
\begin{pmatrix}
  \frac{\partial^2}{\partial x_1 \partial x_1}  f(x)
& \frac{\partial^2}{\partial x_1 \partial x_2}	f(x)
& \frac{\partial^2}{\partial x_1 \partial x_3}	f(x)
\\
  \frac{\partial^2}{\partial x_2 \partial x_1}  f(x)
& \frac{\partial^2}{\partial x_2 \partial x_2}	f(x)
& \frac{\partial^2}{\partial x_2 \partial x_3}	f(x)
\\
  \frac{\partial^2}{\partial x_3 \partial x_1}  f(x)
& \frac{\partial^2}{\partial x_3 \partial x_2}	f(x)
& \frac{\partial^2}{\partial x_3 \partial x_3}	f(x)
\end{pmatrix}
\\
& :=
\begin{pmatrix}
  2
& 1
& 0
\\
  1
& 0
& \frac{1}{2\sqrt{3}}
\\
  0
& \frac{1}{2\sqrt{3}}
& -\frac{1}{4}x_2x_3^{-3/2}
\end{pmatrix}
\end{split}
\end{align*}

# Multivariate Differentialrechnung

\small
\begin{definition}[Glatte multivariate reellwertige Funktion]
\justifying
Eine multivariate reellwertige Funktion
\begin{equation}
f:\mathbb{R}^n \to \mathbb{R}, x \mapsto f(x)
\end{equation}
heißt \textit{glatt}, wenn ihr Gradient und ihre Hesse-Matrix existieren und für alle $x \in \mathbb{R}^n$ stetig sind.
\end{definition}

\footnotesize
Bemerkungen

* Der Gradient und die Hesse-Matrix einer glatten Funktion könnten überall in $\mathbb{R}^n$ berechnet werden.

# Multivariate Differentialrechnung
\small
\begin{theorem}[Multivariater Mittelwertsatz erster Ordnung]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion und es sei $p \in \mathbb{R}^n$. Dann gibt es
ein $t \in ]0,1[$, so dass gilt
\begin{equation}
f(x + p) = f(x) + \nabla f(x + tp)^T p.
\end{equation}
\end{theorem}

\begin{theorem}[Multivariater Mittelwertsatz zweiter Ordnung]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion und es sei $p \in \mathbb{R}^n$. Dann gibt es
ein $t \in ]0,1[$, so dass gilt
\begin{equation}
f(x + p) = f(x) + \nabla f(x)^T p + \frac{1}{2}p^T \nabla^2 f (x + tp) p.
\end{equation}
\end{theorem}

\footnotesize
Bemerkung

* Wir verzichten auf Beweise.
* @nocedal2006 bezeichnen die Theoreme als "Taylor's Theorem", das ist ein wenig misleading.
* $\nabla f$ und $\nabla^2 f$ werden an einer Stelle zwischen $x$ und $x+p$ evaluiert.


<!-- # Multivariate Differentialrechnung

Univariate visuelle Intuition zum Mittelwertsatz 1. Ordnung

\small
\begin{equation}
\mbox{Es gibt ein }t \in ]0,1[ \mbox{ mit } f(x + p) = f(x) + f'(x + tp)p
\end{equation}
\vspace{1mm}
```{r, echo = FALSE, out.width = "65%", fig.align = "center"}
knitr::include_graphics("11_Abbildungen/mv_11_mittelwertsatz.pdf")
``` 
-->

#
\vfill
\large
\setstretch{3}
Multivariate Differentialrechnung

**Grundlagen der nichtlinearen Optimierung**

Gradientenverfahren

Selbstkontrollfragen
\vfill


# Grundlagen der nichtlinearen Optimierung
\small
\begin{definition}[Optimierungsproblem]
\justifying
Ein \textit{Optimierungsproblem} hat die allgemeine Form
\begin{equation}
\min_{x} f(x),
\end{equation}
wobei $x \in \mathbb{R}^n$ und $f : \mathbb{R}^n \to \mathbb{R}$ eine glatte
multivariate reellwertige Funktion ist. Die Lösung $x^*$ eines Optimierungsproblems wird 
bezeichnet mit
\begin{equation}
x^* = \argmin_{x} f(x).
\end{equation}
\end{definition}

\footnotesize
Bemerkungen

*  Weil gilt, dass $\max_{x} f(x) = \min_{x} -f(x)$ genügt es, sich mit Minimierungsproblemen zu befassen.
* Im Allgemeinen ist die Lösung $x^*$ eines Optimierungsproblems eine Menge. 
* Man denkt bei $\argmin_{x} f(x)$ alllerdings auch einfach an Elemente dieser Menge. 


# Grundlagen der nichtlinearen Optimierung
\small
\begin{definition}[Globale und lokale Minimalstellen/Minima]
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine multivariate reellwertige Funktion.
\begin{itemize}
\justifying
\setlength{\itemsep}{3mm}
\item $x^* \in \mathbb{R}^n$ heißt \textit{globale Minimalstelle} von $f$, wenn
$f(x^*) \le f(x) \mbox{ für alle } x \in \mathbb{R}^n$ gilt.
$f(x^*) \in \mathbb{R}$ heißt dann das \textit{globale Minimum} von $f$.
\item $x^* \in \mathbb{R}^n$ heißt \textit{lokale Minimalstelle} von $f$, wenn
es eine Umgebung $N$ von $x^*$ gibt, so dass $f(x^*) \le f(x)$ für alle
$x \in N \subset \mathbb{R}^n$. $f(x^*) \in \mathbb{R}$ wird dann ein 
\textit{lokales Minimum} von $f$ genannt.
\item  $x^* \in \mathbb{R}^n$ heißt \textit{strikte lokale Minimalstelle} von $f$, wenn
es eine Umgebung $N$ von $x^*$ gibt, so dass $f(x^*) < f(x)$ für alle
$x \in N \subset \mathbb{R}^n$. $f(x^*) \in \mathbb{R}$ wird dann ein
\textit{striktes lokales Minimum} von $f$ genannt.
\end{itemize}
\end{definition}

\footnotesize
Bemerkung

* Eine Umgebung von $x \in \mathbb{R}^n$ ist eine offene Menge, die $x$ enthält.

# Grundlagen der nichtlinearen Optimierung
\small
\begin{theorem}[Notwendige Bedingung erster Ordnung]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion. Wenn $x^*$ eine
lokale Minimalstelle von $f$ ist, dann gilt
\begin{equation}
\nabla f(x^*) = 0_n.
\end{equation}
\end{theorem}

\tiny
\underline{Beweis}
\vspace{1mm}

Wir beweisen das Theorem mithilfe eines indirekten Beweises (Beweis durch Widerspruch).
Dazu nehmen wir an, dass $x^*$ zwar eine lokale Minimalstelle von $f$ ist, aber
$\nabla f(x^*) \neq 0_n$ ist. Dazu definieren wir zunächst $p := - \nabla f(x^*)$.
Dann gilt, dass
\begin{equation}
p^T \nabla f(x^*) = - \nabla f(x^*)^T \nabla f(x^*) = -||\nabla f(x^*)|| < 0.
\end{equation}
Weil $\nabla f$ in einer Umgebung von $x^*$ stetig ist, existiert ein Skalar $T > 0$, so dass auch
\begin{equation}
p^T \nabla f(x^* + tp) < 0 \mbox{ für alle } t \in [0,T].
\end{equation}
gilt. Nun gilt für $\tilde{t} \in ]0,T]$ aber mit dem Mittelwertssatz erster Ordnung, dass
\begin{equation}
f(x^* + \tilde{t}p)
= f(x^*) + \nabla f(x^* + tp)^T \tilde{t}p
= f(x^*) + \tilde{t}p^T \nabla f(x^* + tp)
\mbox{ für ein } t \in ]0,\tilde{t}[.
\end{equation}
Also folgt $f(x^* + \tilde{t}p)<f(x^*)$ für alle $\tilde{t} \in ]0,T]$.
Wir haben also eine Richtung von $x^*$ weg gefunden, in der $f$ abnimmt. Also kann
$x^*$ keine Minimalstelle sein, wenn $\nabla f(x^*) \neq 0_n$ gilt. Dies ist
aber ein Widerspruch, zur Annahme, dass es möglich ist, dass $x^*$ eine lokale Minimalstelle
von $f$ ist und $\nabla f(x^*) \neq 0_n$ gilt. Also muss $\nabla f(x^*)  =  0_n$
gelten, wenn $x^*$ eine lokale Minimalstelle ist.

# Grundlagen der nichtlinearen Optimierung
\small
\begin{theorem}[Notwendige Bedingung zweiter Ordnung]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion.  Wenn $x^*$  eine lokale
Minimalstelle von $f$ ist, dann ist $\nabla f(x^*) = 0_n$ und $\nabla^2 f(x^*)$
ist positiv semidefinit.
\end{theorem}

\tiny
\underline{Beweis}

Wir beweisen das Theorem mithilfe eines indirekten Beweises (Beweis durch Widerspruch).
Wir haben schon gesehen, dass $\nabla f(x^*) = 0_n$ ist, wenn $x^*$ eine lokale Minimalstelle von $f$.
ist. Für einen Widerspruchsbeweis nehmen wir nun an, dass $x^*$ zwar eine lokale
Minimalstelle von $f$ ist, aber dass $\nabla^2 f(x^*)$ nicht positiv semidefinit ist.
Dann ist es möglichen einen Vektor $p$ zu finden, so
dass gilt
\begin{equation}
p^T \nabla^2 f (x^*)p < 0.
\end{equation}
Weil  $\nabla^2 f(x^*)$ in einer Umgebung von $x^*$ stetig ist, existiert ein Skalar $T > 0$,
so dass
\begin{equation}
p^T \nabla^2 f (x^* + tp)p < 0 \mbox{ für alle } t \in [0,T].
\end{equation}
gilt. Mithilfe des Mittelwertsatzes zweiter Ordnung gilt dann für alle $\bar{t} \in ]0,T]$ und ein
$t \in ]0,\bar{t}[$, dass
\begin{equation}
f(x^* + \bar{t}p)
= f(x^*) + \bar{t}p^T\nabla f(x^*) + \frac{1}{2} \bar{t}^2 p^T \nabla^2 f(x^* + tp)p
< f(x^*).
\end{equation}
Wir haben also wieder eine Richtung von $x^*$ weg gefunden, in der $f$ abnimmt. Also kann
$x^*$ keine Minimalstelle sein, wenn $\nabla^2 f(x^*)$ nicht positiv semidefinit ist.
Dies ist aber ein Widerspruch, zur Annahme, dass es möglich ist, dass $x^*$ eine lokale Minimalstelle
von $f$ ist und $\nabla^2 f(x^*)$ nicht positiv semidefinit ist. Also muss $\nabla^2 f(x^*)$
positiv semidefinit sein, wenn $x^*$ eine lokale Minimalstelle ist.


# Grundlagen der nichtlinearen Optimierung
\small
\begin{theorem}[Hinreichende Bedingungen zweiter Ordnung]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion und es seien
$\nabla f(x^*) = 0_n$ und $\nabla^2 f(x^*)$ positiv definit. Dann ist  $x^*$ eine
strikte Minimalstelle von $f$.
\end{theorem}

\tiny
\underline{Beweis}

Wir halten zunächst fest, dass weil die Hesse-Matrix stetig und positiv definit
in $x^*$ ist, wir ein $r>0$ wählen können, so dass $\nabla^2 f(x)$ positiv definit
für alle $x$ in
\begin{equation}
D = \{x | ||x - x^*||<r\}
\end{equation}
ist. Für einen Vektor $p$ mit $||p|| > 0$ und $||p|| < r$ gilt $x^*+ p \in D$.
Für ein $t \in ]0,1[$ gilt dann mit dem Mittelwertssatz zweiter Ordnung, dass
\begin{align}
\begin{split}
f(x^* + p)
& = f(x^*) + \nabla f(x^*) p^T + \frac{1}{2}p^T \nabla^2 f(x^*+ tp) p  \\
& = f(x^*) + \frac{1}{2}p^T \nabla^2 f(x^*+ tp) p.
\end{split}
\end{align}
Weil aber $x^*+ tp \in D$ ist, gilt, dass $p^T \nabla^2 f(x^*+ tp) p > 0$ ist und
somit $f(x^* + p) > f(x^*)$. In jeder Richtung $p$ von $x^*$ weg erhöht sich also
der Wert von $f$ und damit ist $x^*$ eine strikte Minimalstelle.


<!-- # Grundlagen der nichtlinearen Optimierung
\small
\begin{theorem}[Minmalstellen konvexer Funktionen]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine \textit{konvexe Funktion}, das heißt,
für alle $x,y\in \mathbb{R}^n$ gelte
\begin{equation}
f(\lambda x + (1 - \lambda)y)
\le \lambda f(x) + (1 - \lambda) f(y)
\mbox{ für alle } \lambda \in [0,1].
\end{equation}
Dann ist eine lokale Minimalstelle $x^*$ von $f$ auch die globale Minimalstelle von $f$.
\end{theorem}

\tiny
\underline{Beweis}
\vspace{1mm}

Wir beweisen das Theorem mithilfe eines indirekten Beweises (Beweis durch Widerspruch).
Nehmen wir dazu an, $x^*$ sei eine lokale, aber keine globale Minimalstelle. Dann
können wir ein $z \in \mathbb{R}^n$ mit $f(z) < f(x^*)$ finden. Wir betrachten
nun die Strecke, die $x^*$ und $z$ in $\mathbb{R}^n$ verbindet, also
\begin{equation}
x = \lambda z + (1 - \lambda)x^* \mbox{ mit } \lambda \in ]0,1]
\end{equation}
Mit der Konvexität von $f$ folgt dann aber, dass
\begin{equation}
f(x) \le \lambda f(z) + (1 - \lambda)f(x^*) < f(x^*)
\end{equation}
Jede Umgebung $N$ von $x^*$ enthält ein Stück dieser Strecke, also gibt es immer
Punkte $x \in N$ mit $f(x) < f(x^*)$. Also ist $x*$ keine lokale Minimalstelle
und wir haben einen Widerspruch. -->


# Grundlagen der nichtlinearen Optimierung
Zusammenfassung
\vspace{1mm}
\small

Optimierungsproblem
\begin{equation*}
\min_x f(x) = \max_x -f(x) \mbox{ für } f:\mathbb{R}^n \to \mathbb{R}
\end{equation*}
Lokale Minimalstelle
\begin{equation*}
x^* = \argmin_x f(x), x^* \in \mathbb{R}^n
\Leftrightarrow
f(x^*) \le f(x) \mbox{ für alle } x \in N \subset \mathbb{R}^n
\end{equation*}
Notwendige Bedingung erster Ordnung
\begin{equation*}
x^* = \argmin_x f(x) \Rightarrow \nabla f(x^*) = 0_n
\end{equation*}
Notwendige Bedingung zweiter Ordnung
\begin{equation*}
x^* = \argmin_x f(x) \Rightarrow \nabla f(x^*) = 0_n \mbox{ und }\nabla^2 f(x^*) \mbox{ positiv semidefinit }
\end{equation*}
Hinreichende Bedingung zweiter Ordnung
\begin{equation*}
\nabla f(x^*) = 0_n \mbox{ und } \nabla^2 f(x^*) \mbox{ positiv definit }  \Rightarrow x^* = \argmin_x f(x)
\end{equation*}

#
\vfill
\setstretch{3}
\large
Multivariate Differentialrechnung

Grundlagen der nichtlinearen Optimierung

**Gradientenverfahren**

Selbstkontrollfragen
\vfill


# Gradientenverfahren
\setstretch{2.2}

Allgemeine Form von Optimierungsalgorithmen

\small
*Initialisierung*

\noindent 0. Wahl eines Startpunktes $x_0 \in \mathbb{R}^n$.

*Iterationen*

Für $k = 0,1,2,...$

1. Berechnung von $x_{k+1}$ basierend auf Information über $f$ an der Stelle $x_k$.
2. STOP, wenn Minimalstelle gefunden ist oder kein Fortschritt mehr erzielt wird.


# Gradientenverfahren
\small

\begin{definition}[Gradientenverfahren]
\justifying

Es sei $f : \mathbb{R}^n \to \mathbb{R}$ eine multivariate reellwertige Funktion. Dann hat das \textit{Gradientenverfahren} zur Minimierung von $f$ folgende allgemeine Form:
\vspace{2mm}

\textit{Initialisierung}
\vspace{1mm}

0. Wähle einen Startpunkt $x_0 \in \mathbb{R}^n$, eine Lernrate $\alpha > 0$ und ein Konvergenzkriterium $\delta > 0$.

\vspace{2mm}
\textit{Iterationen}
\vspace{1mm}

Für $k = 0,1,2,...$
\vspace{1mm}

$\quad$ 1. Setze $x_{k+1} := x_k - \alpha\nabla f(x_k)$.
\vspace{1mm}

$\quad$ 2. STOP, wenn $||\nabla f(x_{k+1})|| < \delta$, ansonsten gehe zu 1.
\end{definition}

\footnotesize
Bemerkungen

* Die Lernrate $\alpha$ bestimmt, wie weit ein Schritt in Richtung des Gradienten erfolgt.
* Das Konvergenzkriterium bestimmt, wie klein der Gradient sein muss, damit das Verfahren endet.

# Gradientenverfahren

\small
\begin{theorem}[Gradientenverfahren]
\justifying
\normalfont
$f : \mathbb{R}^n \to \mathbb{R}$ sei eine glatte Funktion und es sei $x_k \in \mathbb{R}^n$.
Dann ist die Gradientenrichtung
\begin{equation}
p^G_k := - \nabla f(x_k)
\end{equation}
die Richtung des steilsten Abstiegs von $f$ in $x_k$.
\end{theorem}

\footnotesize
Bemerkungen

* Es gibt unendliche viele mögliche Richtungen $p$ in $x_k$.
* $\nabla f(x) \in \mathbb{R}^n$ ist eine Richtung in der Definitionsmenge von $f$ (Parameterraum).
* Die Gradientenrichtung ist davon die Richtung, in der die Zielfunktion $f$ am schnellsten abnimmt.
* Zum Vergleich von Richtungen genügt es, Richtungen der Länge $||p|| = 1$ zu vergleichen.


# Gradientenverfahren
\footnotesize
\underline{Beweis}


Mit dem Mittelwertsatz zweiter Ordnung gilt für jede Richtung $p$
und Schrittlängenparameter $\alpha$, dass
\begin{equation}
f(x_k + \alpha p) = f(x_k) + \alpha p^T \nabla f(x_k) + \frac{1}{2}\alpha^2 p^T \nabla^2 f(x_k + t p)p
\mbox{ für ein } t \in ]0,\alpha[.
\end{equation}
Die Änderungsrate von $f$ in Richtung $p$ in $x_k$ ist also der Koeffizient von
$\alpha$, also $p^T \nabla f(x_k)$ (man denke an $x = tv$ für einen Ort $x$,
eine Geschwindigkeit $v$ und eine Zeit $t$).
Also gilt, dass die Richtung des steilsten Abstiegs $p$ in $x_k$ mit Länge 1
die Lösung des Optimierungsproblems
\begin{equation}
\min_p p^T \nabla f(x_k)  \mbox{ mit der Nebenbedingung } ||p|| = 1.
\end{equation}
ist. Wir erinnern nun zunächst daran, dass für $x,y \in \mathbb{R}^n$ gilt
der Kosinus des Winkel zwischen $x$ und $y$ durch
\begin{equation}
\cos \alpha = \frac{\langle x,y \rangle}{||x|| ||y||} = \frac{x^Ty}{||x|| ||y||}
\end{equation}
gegeben ist. Damit aber gilt, dass
\begin{equation}
p^T \nabla f(x_k)
= ||p||\cdot ||\nabla f(x_k)|| \cos \theta
= 1\cdot ||\nabla f(x_k)|| \cos \theta
= ||\nabla f(x_k)|| \cos \theta
\end{equation}
und somit liegt hier bei $\cos \theta = -1$ eine Minimalstelle vor.
Dies bedeutet aber, dass die minimierende Länge $p$ exakt antiparallel zu
$\nabla f(x_k)$ und von Länge 1 sein muss. Also ist die Minimalstelle des
Optimierungsproblems
\begin{equation}
p = \frac{-\nabla f(x_k)}{||\nabla f(x_k)||}.
\end{equation}
Damit ist $p^G_k := -\nabla f(x_k)$ aber der Richtungsvektor beliebiger Länge
in der die Abnahme von $f$ maximal ist.

# Gradientenverfahren
\vspace{1mm}
Beispiel

\small
Minimierung von $f:\mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := x_1^2 + x_2^2$
\vspace{1mm}

\setstretch{.90}
\tiny

```{r, echo = T}
# Funktionsdefinitionen
# ------------------------------------------------------------------------------
# Zielfunktion
f = function(x) {
  return(x[1]^2 + x[2]^2)                 # f(x) := x_1^2 + x_2^2
}
# Gradient der Zielfunktion
nabla_f = function(x) {
  return(matrix(c(2*x[1],2*x[2]),         # \nabla f(x) := (2x_1, 2x_2)^T
                nrow = 2))
}
# Gradientenverfahren
# ------------------------------------------------------------------------------
# Parameter
n      = 2                               # Dimension
alpha  = 1e-1                            # Lernrate
delta  = 1e-2                            # Konvergenzkriterium

# Initialisierung
x_k   = matrix(c(.61,.85), nrow = 2)     # Zufälliger Startpunkt in [0,1]^2
x     = x_k                              # Initialisierung Iteranden
fx    = f(x_k)                           # Initialisierung Funktionswerte
crt   = norm(nabla_f(x_k))               # Initialisierung Kriterium

# Iterationen
while(norm(nabla_f(x_k)) > delta){

  # Argumentupdate
  x_k   = x_k - alpha*nabla_f(x_k)

  # Dokumentation
  x    = cbind(x,x_k)
  fx   = c(fx,f(x_k))
  crt  = c(crt, norm(nabla_f(x_k)))
}
```


# Gradientenverfahren
Beispiel

\small
Minimierung von $f:\mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := x_1^2 + x_2^2$

```{r, echo = F, eval = F}
library(latex2exp)
pdf(
file        = "11_Abbildungen/mv_11_gradientenverfahren.pdf",
width       = 12,
height      = 4)
par(
family      = "sans",
mfcol       = c(1,3),
pty         = "s",
bty         = "l",
lwd         = 1,
las         = 1,
xaxs        = "i",
yaxs        = "i",
font.main   = 1,
cex         = 1.1,
cex.main    = 1.3)

# Definitionsmengenraum
x_min  = -1                                           # x_i Minimum
x_max  = 1                                            # x_i Maximum
x_res  = 1e2                                          # x_i Auflösung
x_1    = seq(x_min, x_max, length.out = x_res)        # x_1 Raum
x_2    = seq(x_min, x_max, length.out = x_res)        # x_2 Raum
X      = expand.grid(x_1,x_2)                         # X = (x_1,x_2)^T Raum
fX     = matrix(as.matrix(f(X)),nrow = x_res )      # f(x)
cols   = hcl.colors(10, "YlOrRd")

# Zielfunktion
contour(
x_1,
x_2,
fX,
col       = cols,
xlim      =  c(x_min,x_max),
ylim      =  c(x_min,x_max),
xlab      = TeX("x_1"),
ylab      = TeX("x_2"),
nlevels   = 10,
main      = "f(x)")
points(
x[1,],
x[2,],
type = "o")

plot(
1:length(fx),
fx,
type = "l",
lwd  = 1,
xlab = "k",
ylab = "",
main = TeX("$f(x^k)$"),
ylim = c(0,1)
)

plot(
1:length(crt),
crt,
type = "l",
lwd  = 1,
xlab = "k",
ylab = "",
main = TeX("$||\\nabla f(x^k) ||$"),
ylim = c(0,2))
dev.off()
```
\vspace{1cm}
\vfill
```{r, echo = FALSE, out.width = "100%"}
knitr::include_graphics("11_Abbildungen/mv_11_gradientenverfahren.pdf")
```
\vfill

# Gradientenverfahren
\setstretch{1.7}

Liniensuchverfahren als generalisierte Gradientenverfahren

\small

*Initialisierung*

\noindent 0. Wahl eines Startpunktes  $x_0 \in \mathbb{R}^n$.


*Iterationen*

Für $k = 0,1,2,...$

1. Wahl einer Abstiegsrichtung $p_k$
2. Wahl eines Lernparameters $\alpha_k \approx \min_{\alpha} f(x_k + \alpha p_k)$.
3. Setze $x_{k+1} := x_k + \alpha_k p_k$.
4. Konvergenztest.


$\Rightarrow$ Die Wahl sinnvoller Lernraten $\alpha_k$ ist für eine gute Performanz entscheidend!

\flushright (vgl. @ostwald2016)


# Selbstkontrollfragen
\setstretch{1.8}
\footnotesize
1. Geben Sie die Definition einer multivariaten reellwertigen Funktion wieder.
1. Geben Sie die Definition der partiellen Ableitung wieder.
1. Geben Sie die Definition der zweiten partiellen Ableitung wieder.
1. Geben Sie den Satz von Schwarz wieder.
1. Geben Sie die Definition eines Gradienten einer multivariaten reellwertigen Funktion wieder.
1. Geben Sie die Definition der Hesse-Matrix einer multivariaten reellwertigen Funktion wieder.
1. Geben Sie die allgemeine Form eines Optimierungsproblems wieder.
1. Geben Sie die notwendige Bedingung erster Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
1. Geben Sie die notwendige Bedingung zweiter Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
1. Geben Sie die hinreichende Bedingung zweiter Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
1. Geben Sie die Definition des Gradientverfahrens wieder.
1. Erläutern Sie die Bedeutung der Lernrate und des Konvergenzkriteriums im Gradientenverfahren.
1. Geben Sie das Theorem zum Gradientenverfahren wieder.


# Referenzen
\footnotesize