---
fontsize: 8pt
bibliography: 6_Referenzen.bib
citation_package: natbib
output:
  beamer_presentation:
    keep_tex: true
    includes:
      in_header: 6_header.tex
---


```{r, include = F}
source("6_R_common.R")
```

#  {.plain}
\center
```{r, echo = FALSE, out.width = "20%"}
knitr::include_graphics("6_Abbildungen/mvda_6_otto.png")
```

\vspace{2mm}

\Huge
Multivariate Datenanalyse
\vspace{6mm}

\large
MSc Psychologie WiSe 2021/22

\vspace{6mm}
\large
Prof. Dr. Dirk Ostwald

#  {.plain}

\vfill
\center
\huge
\textcolor{black}{(6) Optimierung}
\vfill

# Multivariate Datenanalyse

\small
\center
\footnotesize
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{lll}
Datum        & Einheit                     & Thema					                        \\\hline
15.10.2021   & Einführung                  & (0) Einführung                         \\
15.10.2021   & Grundlagen                  & (1) Vektoren 		       		            \\
22.10.2021   & Grundlagen                  & (2) Matrizen I            	            \\
29.10.2021   & Grundlagen                  & (3) Matrizen II                        \\
05.11.2021   & Grundlagen                  & (4) Multivariate Normalverteilung      \\
12.11.2021   & Latente Variablenmodelle    & (5) Hauptkomponentenanalyse            \\
19.11.2021   & Latente Variablenmodell     & (6) Faktorenanalyse                    \\
26.11.2021   & Prädiktive Modellierung     & (7) Optimierung                        \\
03.12.2021   & Prädiktive Modellierung     & (8) Lineare Diskriminanzanalyse und Logistische Regression     \\
10.12.2021   & Prädiktive Modellierung     & (9) Support Vektor Maschinen           \\
17.12.2021   & Prädiktive Modellierung     & (10) Neuronale Netze                   \\
             & \textcolor{gray}{Weihnachtspause}                                    \\
07.01.2022   & Frequentistische Inferenz   & (11) T-Tests                           \\
14.01.2022   & Frequentistische Inferenz   & (12) Einfaktorielle Varianzanalyse     \\
21.01.2022   & Frequentistische Inferenz   & (13) Kanonische Korrelationsanalyse I  \\
28.01.2022   & Frequentistische Inferenz   & (14) Kanonische Korrelationsanalyse II \\\hline
22.02.2022   & Klausur                     & 12 - 13 Uhr, G26-H1                    \\
Jul 2022     & Klausurwiederholungstermin
\end{tabular}

#
\vfill
\setstretch{2}
\large
**Prädiktive Modellierung**

Differentialrechnung und Analytische Optimierung

Multivariate Differentialrechnung

Grundlagen der Optimierung

Gradientenverfahren

Grundlagen der Optimierung mit Nebenbedingungen

Selbstkontrollfragen
\vfill

# Prädiktive Modellierung
\setstretch{1.7}
\small

In der Psychologie möchte man gerne Dinge prädizieren, zum Beispiel

* Risiko psychiatrischer Erkrankung basierend auf Fragebogendaten
* Prognose psychiatrischer Erkrankung basierend auf Hirnbildgebungsdaten
* Psychotherapieerfolg basierend auf klinisch-psychologischen Tests
* Subjektive Wahrnehmung (Bewusstsein) basierend auf funktionellen Hirnbildgebungsdaten
* ...
\vspace{2mm}

Prädiktive Modellierung ist ein datenanalytisches Paradigma, das die prädiktive Rhethorik bedient.

* Die Datengrundlage ist hier oft multivariat, die Vorhersage ist oft univariat.
* Prädiktive Modellierung wird oft mit "Maschinellem Lernen" gleichgesetzt oder verwechselt.
* Prädiktive Modellierung wird oft mit "Künstlicher Intelligenz" gleichgesetzt oder verwechselt.
* Prädiktive Modellierung wird oft mit "Deep Learning" gleichgesetzt oder verwechselt.


# Prädiktive Modellierung

Struktur der Prädiktiven Modellierung

\begin{minipage}{.6\textwidth}
```{r, echo = FALSE, out.width = "80%"}
knitr::include_graphics("6_Abbildungen/mvda_6_prädiktive_modellierung_1.pdf")
```
\end{minipage}
\begin{minipage}{.4\textwidth}
```{r, echo = FALSE, out.width = "90%"}
knitr::include_graphics("6_Abbildungen/mvda_6_prädiktive_modellierung_2.pdf")
```
\end{minipage}

\flushright
\tiny
nach @dwyer_2018
\vspace{3mm}

\flushleft
\small
Rhethorik der Prädiktiven Modellierung

\center
\begin{tabular}{ll}
Daten                     & Trainingsdaten und Testdaten                  \\
Statistisches Modell      & Modell, Machine Learning Algorithmus          \\
Schätzen von Parametern   & Trainieren des Modells, Lernen von Parametern, Supervised Learning
\end{tabular}


# Prädiktive Modellierung

Typische Modelle der Prädiktiven Modellierung

```{r, echo = FALSE, out.width = "80%"}
knitr::include_graphics("6_Abbildungen/mvda_6_prädiktive_modellierung_3.pdf")
```


# Prädiktive Modellierung

Modellschätzung- und Modellevaluationsansatz der Prädiktiven Modellierung

```{r, echo = FALSE, out.width = "70%"}
knitr::include_graphics("6_Abbildungen/mvda_6_prädiktive_modellierung_4.pdf")
```

Die theoretische Analyse dieses Ansatzes heißt "Statistische Lerntheorie" [@vapnik_2010]

# Prädiktive Modellierung

Explanatorische Modellierung vs. Prädiktive Modellierung

\vspace{2mm}


```{r, echo = FALSE, out.width = "80%"}
knitr::include_graphics("6_Abbildungen/mvda_6_prädiktive_vs_explanatorische_modellierung.pdf")
```

\small

* Es gibt keinen Grund anzunehmen, dass immer $\tilde{f} = \hat{f}$ gilt.
* Für ein Beispiel mit $\tilde{f} \neq \hat{f}$. , siehe z.B. @shmueli_2010.

# Prädiktive Modellierung

Technik der Prädiktiven Modellierung

\setstretch{1.5}
\small
Das Lernen von Modellparametern ist das zentrale Problem der Prädiktiven Modellierung

* Parameterlernen impliziert die Minimierung einer Zielfunktion (objective function).
* An der Stelle eines Minimums ist die erste Ableitung einer Funktion gleich Null.
* An der Stelle eines Minimums ist die zweite Ableitung einer Funktion positiv.

Optimierungsverfahren identifizieren Parameterwerte, für die diese Minimumsbedingungen gelten.

\center
\begin{tabular}{|l|l|}
\hline
Modell
& Optimierungsverfahren                         \\\hline
Lineare Diskriminanzanalyse
& Analytische Optimierung  	                    \\
Logistische Regression
& Gradientenverfahren                           \\
Support Vektor Maschinen
& Optimierung mit Nebenbedingungen               \\
Neuronale Netze
&  Gradientenverfahren											    \\
\hline
\end{tabular}

\flushleft
Anmerkungen

* In der statistischen Modellierung hat die Zielfunktion meist probabilistische Konnotation.
* Typische Zielfunktionen der statistischen Modellierung sind Likelihood Funktionen.
* Prädiktive Modellierung verzichtet zum Teil auf die Repräsentation von Unsicherheit.

#
\vfill
\large
\setstretch{2}
Prädiktive Modellierung

**Differentialrechnung und Analytische Optimierung**

Multivariate Differentialrechnung

Grundlagen der Optimierung

Gradientenverfahren

Grundlagen der Optimierung mit Nebenbedingungen

Selbstkontrollfragen
\vfill

# Differentialrechung und Analytische Optimierung
\setstretch{1.1}
\small
\begin{definition}[Funktionenarten]
In der statistischen Anwendung unterscheiden wir
\begin{itemize}
\item \textit{univariate reellwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R} \to \mathbb{R}, x \mapsto f(x),
\end{equation}
\item \textit{multivariate reellwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R}^n \to \mathbb{R}, x \mapsto f(x) = f(x_1,...,x_n),
\end{equation}
\item \textit{multivariate vektorwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R}^n \to \mathbb{R}^m, x \mapsto
f(x) =
\begin{pmatrix}
f_1(x_1,...,x_n) 	\\
\vdots				\\
f_m(x_1,...,x_n)
\end{pmatrix}.
\end{equation}
\end{itemize}
\end{definition}
\footnotesize
Bemerkung
\begin{itemize}
\item In der Physik werden multivariate reellwertige Funktionen auch \textit{Skalarfelder} genannt.
\item In der Physik werden multivariate vektorwertige Funktionen auch \textit{Vektorfelder} genannt.
\end{itemize}

\small
\center
**In diesem Abschnitt betrachten wir univariate reellwertige Funktionen.**

# Differentialrechung und Analytische Optimierung

Beispiele

\small
Univariate, reellwertige Funktion
\begin{equation}
f : \mathbb{R} \to \mathbb{R}, x \mapsto f(x) := x^2
\end{equation}
Multivariate (bivariate), reellwertige Funktion
\begin{equation}
f : \mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := x_1^2 + x_2^2
\end{equation}
\vspace{1mm}

```{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))
}


graphics.off()
fdir        =  file.path(getwd(), "6_Abbildungen")
dev.new()
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)

# Univariate reellwertige Funktion
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
plot(
x_1,
x_1^2,
lwd  = 2,
type = "l",
ylim = c(-.1,2),
xlab = TeX("$x$"),
ylab = "",
main = TeX("$f(x) := x^2$")
)
g   = grid()

# Bivariate reellwertige Funktion 1
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.copy2pdf(
file        = file.path(fdir, "mvda_6_funktionenarten.pdf"),
width       = 12,
height      = 4)
```

```{r, echo = FALSE, out.width = "100%"}
knitr::include_graphics("6_Abbildungen/mvda_6_funktionenarten.pdf")
```

# Differentialrechung und Analytische Optimierung
\setstretch{1.2}
\footnotesize
\begin{definition}[Ableitung]
Es sei $I \subseteq \mathbb{R}$ ein Intervall und
\begin{equation}
f : I \to \mathbb{R}, x \mapsto f(x)
\end{equation}
eine univariate reellwertige Funktion.
$f$ heißt in $a \in I$ \textit{differenzierbar}, wenn der Grenzwert
\begin{equation}
f'(a) := \lim_{h\to 0} \frac{f(a+h)-f(a)}{h}
\end{equation}
existiert.
$f'(a)$ heißt dann die \textit{Ableitung von $f$ an der Stelle $a$}.
Ist $f$ differenzierbar für alle $x \in I$, so heißt $f$ \textit{differenzierbar} und die Funktion
\begin{equation}
f' : I \to \mathbb{R}, x \mapsto f'(x)
\end{equation}
heißt \textit{Ableitung von $f$}
\end{definition}

\footnotesize
\setstretch{1.4}
Bemerkungen

* Für $h>0$ heißt $\frac{f(a+h)-f(a)}{h}$ \textit{Differenzquotient}.
* Der Differenzquotient  misst die Änderung $f(a+h)-f(a)$ von $f$ pro Strecke $h$.
* Für $h\to 0$ misst der Differenzquotient die Änderungs\underline{rate} von $f$ in $a$.
* $f'(a)$ ist eine Zahl, $f'$ ist eine Funktion.
* Wir werden keine Grenzwertbildung zur Berechnung von Ableitungen benötigen.


# Differentialrechung und Analytische Optimierung
\setstretch{1.4}
\small
\begin{definition}[Notation für Ableitungen univariater reellwertiger Funktionen]
Es sei $f$ eine univariate reellwertige Funktion. Äquivalente Schreibweisen für
die Ableitung von $f$ und die Ableitung von $f$ an einer Stelle $x$ sind
\begin{enumerate}
\item[(1)] die \textit{Lagrange-Notation} $f'$ und $f'(x)$,
\item[(2)] die \textit{Newton-Notation} $\dot{f}$ und $\dot{f}(x)$,
\item[(3)] die \textit{Leibniz-Notation} $\frac{df}{dx}$ und $\frac{df(x)}{dx}$ und
\item[(4)] die \textit{Euler-Notation} $Df$ und $Df(x)$.
\end{enumerate}

\end{definition}

\footnotesize
Bemerkungen

* Für univariate reellwertige Funktionen benutzen wir $f'$ und $f'(x)$ als Bezeichner.
* In Berechnungen benutzen wir auch die "Operator-Schreibweise" $\frac{d}{dx}f(x)$.
* Wir verstehen  $\frac{d}{dx}f(x)$ als den Auftrag, die Ableitung von $f$ zu berechnen.

# Differentialrechung und Analytische Optimierung
\footnotesize
\begin{definition}[Höhere Ableitungen]
Es sei $f$ eine univariate reellwertige Funktion und
\begin{equation}
f^{(1)} := f'
\end{equation}
sei die Ableitung von $f$. Die $k$-te Ableitung von $f$ ist rekursiv definiert durch
\begin{equation}
f^{(k)} := \left(f^{(k-1)}\right)' \mbox{ für } k \ge 0,
\end{equation}
unter der Annahme, dass $f^{(k-1)}$ differenzierbar ist. Insbesondere ist die
\textit{zweite Ableitung von $f$} definiert durch die Ableitung von $f'$, also
\begin{equation}
f'' := (f')'.
\end{equation}
\end{definition}

\setstretch{1.4}
\footnotesize
Bemerkungen

* Wir schreiben auch $\frac{d^2}{dx^2}f(x)$ für den Auftrag, die zweite Ableitung von $f$ zu bestimmen.
* Die nullte Ableitung $f^{(0)}$ von $f$ ist $f$ selbst.
* Üblicherweise schreibt man für $k < 4$ $f',f'',f'''$ statt $f^{(1)}, f^{(2)}, f^{(3)}$.
* Im Allgemeinen benötigen wir nur $f'$ und $f''$.

# Differentialrechung und Analytische Optimierung
\setstretch{1.1}
\footnotesize
\begin{theorem}[Rechenregeln für Ableitungen]
\justifying
\normalfont
Für $i = 1,...,n$ seien $g_i$ reellwertige univariate differenzierbare Funktionen.
Dann gelten folgende Rechenregeln:
\begin{enumerate}
\item[(1)] Summenregel
\begin{equation}
\mbox{Für } f(x) := \sum_{i=1}^n g_i(x) \mbox{ gilt } f'(x) = \sum_{i=1}^n g_i'(x).
\end{equation}
\item[(2)] Produktregel
\begin{equation}
\mbox{Für } f(x) := g_1(x)g_2(x) \mbox{ gilt } f'(x) = g_1'(x)g_2(x) + g_1(x)g_2'(x).
\end{equation}
\item[(3)] Quotientenregel
\begin{equation}
\mbox{Für } f(x) := \frac{g_1(x)}{g_2(x)} \mbox{ gilt } f'(x) = \frac{g_1'(x)g_2(x) - g_1(x)g_2'(x)}{g_2^2(x)}.
\end{equation}
\item[(4)] Kettenregel
\begin{equation}
\mbox{Für } f(x) := g_1(g_2(x)) \mbox{ gilt } f'(x) = g_1'(g_2(x))g'_2(x).
\end{equation}
\end{enumerate}
\end{theorem}

\footnotesize
Bemerkung

* Für Beweise der Rechenregeln wird auf die einschlägige Literatur verwiesen.

# Differentialrechung und Analytische Optimierung
\footnotesize
\begin{theorem}[Ableitungen elementarer Funktionen]
\justifying
\normalfont
Für einige elementare Funktionen der Datenanalyse ergeben sich folgende Ableitungen:
\vspace{2mm}

\setstretch{1.6}
\begin{table}
\centering
\begin{tabular}{lll}
Name 							            & Definition	    			            & Ableitung								              \\\hline
Polynomfunktionen 				    & $f(x) := \sum_{i=0}^n a_ix^i$     & $f(x)  = \sum_{i=1}^n ia_ix^{i-1}$ 	  \\
$\quad$ Konstante Funktion 		& $f(x) := a$					              & $f'(x) = 0$ 							            \\
$\quad$ Identitätsfunktion  	& $f(x) := x$ 					            & $f'(x) = 1$ 							            \\
$\quad$ Lineare Funktion 		   & $f(x) := ax + b$				          & $f'(x) = a$ 							            \\
$\quad$ Quadratfunktion 		  & $f(x) := x^2$ 				            & $f'(x) = 2x$ 							            \\
Exponentialfunktion				    & $f(x) := \exp(x)$ 			          & $f'(x) = \exp(x)$						          \\
Logarithmusfunktion				    & $f(x) := \ln(x)$ 				          & $f'(x) = \frac{1}{x}$					        \\
\end{tabular}
\end{table}
\end{theorem}

\setstretch{1.4}
\footnotesize
Bemerkung

* Für Beweise wird auf die einschlägige Literatur verwiesen.

# Differentialrechung und Analytische Optimierung

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

# 1 x 3 Plot Layout
dev.new()
library(latex2exp)
par(
mfcol     = c(1,3),
family    = "sans",
pty       = "s",
bty       = "l",
lwd       = 1,
las       = 1,
mgp       = c(2,1,0),
font.main = 1,
cex.main  = 1.2)

# Definitionsmenge
x_min     = -5                                                                   # minimum x-value
x_max     = 5                                                                    # maximum x-value
x_res     = 1e3                                                                  # x space resolution
x         = seq(x_min,x_max,len = x_res)                                         # x space

# Identitätsfunktion
fxdx      = cbind(matrix(x), matrix(rep(1,length(x)), nrow = length(x)))          # f(x) := x, f'(x) = 1
matplot(
x,
fxdx,
type      = "l",
lty       = 1,
lwd       = 2,
col       = c("gray30", "gray70"),
xlim      = c(-x_max,x_max),
ylim      = c(-x_max,x_max),
ylab      = " ",
xlab      = "x",
main      = "Identitätsfunktion" )
grid()
legend(
-2,
-2,
c("f(x)  = x", "f'(x) = 1"),
cex       = 1,
lty       = 1,
col       = c("gray30", "gray70"),
lwd       = 2,
y.intersp = 1,
bty       = "n")

# Lineare Funktion
a         = 1/2
b         = -1
fxdx      = cbind(matrix(a*x + b), matrix(a, nrow = length(x)))                  # f(x) := 2x - 3, f'(x) = 2
matplot(
x,
fxdx,
type      = "l",
lty       = 1,
lwd       = 2,
col       = c("gray30", "gray70"),
xlim      = c(-x_max,x_max),
ylim      = c(-x_max,x_max),
ylab      = " ",
xlab      = "x",
main      = "Lineare Funktion")
grid()
legend(
-4,
-2,
c("f(x) = 0.5x - 1", "f'(x) = 0.5"),
cex       = 1,
lty       = 1,
col       = c("gray30", "gray70"),
lwd       = 2,
y.intersp = 1,
bty       = "n")

# Quadratfunktion
fxdx      = cbind(matrix(x^2),matrix(2*x))                                       # f(x) := x^2 # f'(x) = 2x
matplot(
x,
fxdx,
type      = "l",
lty       = 1,
lwd       = 2,
col       = c("gray30", "gray70"),
xlim      = c(-x_max,x_max),
ylim      = c(-x_max,x_max),
ylab      = " ",
xlab      = "x",
main      = "Quadratfunktion")
grid()
legend(
-2,
-2,
c(TeX("f(x)  = x^2"), "f'(x) = 2x"),
cex       = 1,
lty       = 1,
col       = c("gray30", "gray70"),
lwd       = 2,
y.intersp = 1,
bty       = "n")

# PDF Speicherung
dev.copy2pdf(
file        = file.path(getwd(), "6_Abbildungen", "mvda_6_ableitungen_1.pdf"),
width       = 7,
height      = 3)

```

Ableitungen elementarer Funktionen
\vspace{3mm}
\center
```{r, echo = FALSE, out.width = "100%"}
knitr::include_graphics("6_Abbildungen/mvda_6_ableitungen_1.pdf")
```

# Differentialrechung und Analytische Optimierung

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

# 1 x 2 Plotlayout
dev.new()
library(latex2exp)
par(
mfcol      = c(1,2),
family     = "sans",
pty        = "s",
bty        = "l",
lwd        = 1,
las        = 1,
mgp        = c(2,1,0),
font.main  = 1,
cex        = 0.9,
cex.main   = 1.1)

# Exponentialfunktion
x_min     = -4                                                                   # minimum x-value
x_max     = 2                                                                    # maximum x-value
x_res     = 1e3                                                                  # x space resolution
x         = seq(x_min,x_max,len = x_res)                                         # x space
fxdx      = cbind(matrix(exp(x)),matrix(exp(x)))                                 # f(x) := exp(x), f'(x) = exp(x)
matplot(
x,
fxdx,
type      = "l",
lty       = c(1,2),
lwd       = 2,
col       = c("gray30", "gray70"),
xlim      = c(x_min,x_max),
ylim      = c(-1,6),
ylab      = " ",
xlab      = "x",
main      = "Exponentialfunktion")
grid()
legend(
-4,
6,
c("f(x) = exp(x)", "f'(x) = exp(x)"),
cex       = .9,
lty       = 1,
col       = c("gray30", "gray70"),
lwd       = 2,
y.intersp = 1.5,
bty       = "n")

# Logarithmusfunktion
x_min     = 1e-3                                                                 # minimum x-value
x_max     = 4                                                                    # maximum x-value
x_res     = 1e3                                                                  # x space resolution
x         = seq(x_min,x_max,len = x_res)                                         # x space
fxdx      = cbind(matrix(log(x)), matrix(1/x))                                   # f(x) := ln(x), f'(x) = 1/x
matplot(
x,
fxdx,
type      = "l",
lty       = 1,
lwd       = 2,
col       = c("gray30", "gray70"),
xlim      = c(0,x_max),
ylim      = c(-4,5),
ylab      = " ",
xlab      = "x",
main      = "Logarithmusfunktion")
grid()
legend(
1,
-1,
c("f(x) = ln(x)", "f'(x) = 1/x"),
cex       = .9,
lty       = 1,
col       = c("gray30", "gray70"),
lwd       = 2,
y.intersp = 1.5,
bty       = "n")

# PDF Speicherung
dev.copy2pdf(
file        = file.path(getwd(), "6_Abbildungen", "mvda_6_ableitungen_2.pdf"),
width       = 7,
height      = 3)

```

Ableitungen elementarer Funktionen
\vspace{3mm}
\center
```{r, echo = FALSE, out.width = "100%"}
knitr::include_graphics("6_Abbildungen/mvda_6_ableitungen_2.pdf")
```


# Differentialrechnung und Analytische Optimierung
\setstretch{1.1}
\footnotesize
\begin{definition}[Extremstellen und Extremwerte]
\justifying
Es sei $U \subseteq \mathbb{R}$ und $f : U \to \mathbb{R}$ eine univariate
reellwertige Funktion. Dann hat $f$ an der Stelle $x_0 \in U$
\begin{itemize}
\justifying
\item ein \textit{lokales Minimum}, wenn es ein Intervall $I := ]a,b[$ gibt mit $x_0 \in ]a,b[$ und
\begin{equation}
f(x_0) \le f(x) \mbox{ für alle } x\in I\cap U,
\end{equation}
\item ein \textit{globales Minimum}, wenn gilt, dass
\begin{equation}
f(x_0) \le f(x) \mbox{ für alle } x\in U,
\end{equation}
\item ein \textit{lokales Maximum}, wenn es ein Intervall $I := ]a,b[$ gibt mit $x_0 \in ]a,b[$ und
\begin{equation}
f(x_0) \ge f(x) \mbox{ für alle }  x\in I\cap U,
\end{equation}
\item \textit{lokales Maximum}, wenn gilt, dass
\begin{equation}
f(x_0) \ge f(x) \mbox{ für alle } x\in U.
\end{equation}
\end{itemize}
Der  Wert $x_0 \in U$ der Definitionsmenge von $f$ heißt entsprechend
\textit{lokale} oder \textit{globale Minimalstelle} oder \textit{Maximalstelle},
der Funktionswert $f(x_0) \in \mathbb{R}$ heißt entsprechend \textit{lokales}
oder \textit{globales Minimum} oder \textit{Maximum}. Generell heißt der Wert
$x_0 \in U$ \textit{Extremstelle} und der Funktionswert $f(x_0) \in \mathbb{R}$ \textit{Extremwert}.
\end{definition}

Bemerkungen

* Extremstellen werden auch mit
$\argmin_{x \in I \cap U} f(x)$ oder
$\argmax_{x \in I \cap U} f(x)$
bezeichnet.
* Extremwerte werden auch mit
$\min_{x \in I \cap U} f(x)$ oder
$\max_{x \in I \cap U} f(x)$
bezeichnet.


# Differentialrechnung und Analytische Optimierung
\small
\begin{definition}[Notwendige Bedingung für Extrema]
$f$ sei eine univariate reellwertige Funktion. Dann gilt
\begin{equation}
x_0 \mbox{ ist Extremstelle von } f \Rightarrow f'(x_0) = 0.
\end{equation}
\end{definition}

Bemerkungen

* Wenn $x_0$ eine Extremstelle von $f$ ist, dann ist die erste Ableitung von $f$ in $x_0$ null.
* Sei zum Beispiel $x_0$ eine lokale Maximalstelle von $f$. Dann gilt
    * \small Links von $x_0$ steigt $f$ an, rechts von $x_0$ fällt $f$ ab.
    * In $x_0$ steigt $f$ weder an, noch fällt $f$ ab, also ist $f'(x_0) = 0$.


# Differentialrechnung und Analytische Optimierung
\small
\begin{definition}[Hinreichende Bedingungen für lokale Extrema]
$f$ sei eine zweimal differenzierbare univariate reellwertige Funktion.
\begin{itemize}
\item Wenn für $x_0 \in U \subseteq \mathbb{R}$
\begin{equation}
f'(x_0) = 0 \mbox{ und } f''(x_0) > 0
\end{equation}
gilt, dann hat $f$ an der Stelle $x_0$ ein Minimum.
\item Wenn für $x_0 \in U \subseteq \mathbb{R}$
\begin{equation}
f'(x_0) = 0 \mbox{ und } f''(x_0) < 0
\end{equation}
gilt, dann hat $f$ an der Stelle $x_0$ ein Maximum.
\end{itemize}
\end{definition}

Bemerkung

* Eine Intuition vermittelt nachfolgende Abbildung.

# Differentialrechnung und Analytische Optimierung
\vspace{2mm}

```{r, eval = F, echo = F}
# plot specifications
dev.new()                                                                        # new figure
theta   = par(                                                                   # figure parameters
            mfcol      = c(1,1),                                                 # subplot grid
            family     = "sans",                                                 # font family
            pty        = "s",                                                    # square plots
            bty        = "l",                                                    # plot box, o, l, 7, c, or ]
            lwd        = 1,                                                      # line width
            las        = 1,                                                      # 0: axis parallel, 1: horizontal, 2: axis perpendicular, 3: vertical
            mgp        = c(2,1,0),                                               # margin line in mex unit
            font.main  = 1,                                                      # title font type
            cex.main   = 1.2                                                     # title  magnification factor
)

# Exponentialfunktion
x_min   = -3                                                                     # minimum x-value
x_max   = 4                                                                      # maximum x-value
x_res   = 1e3                                                                    # x space resolution
x       = seq(x_min,x_max,len = x_res)                                           # x space
fxdx    = cbind(matrix((x-1)^2),                                                 # f(x) : = (x-1)^2
                matrix(2*x - 2),                                                 # f'(x)  = 2x - 2
                matrix(rep(2,x_res), nrow = x_res))                              # f''(x) = 2

p   = matplot(                                                                   # multiple line plot
            x,                                                                   # x values
            fxdx,                                                                # f(x) values
            type        = "l",                                                   # line type für alle graphs
            lty         = 1,                                                     # solid and dashed lines
            lwd         = 2,                                                     # linewidth für alle graphs
            col         = c("gray20", "gray50", "gray80"),                       # line colors
            xlim        = c(x_min,x_max),                                        # x-axis limits
            ylim        = c(-2,6),                                               # y-axis limits
            ylab         = " ",                                                  # no y-axis label
            xlab         = "x",                                                  # x-axis label
)
g   = grid()                                                                     # grid lines
l   = legend(-3.3,                                                               # upper left corner x ordinate
             1,                                                                  # upper left corner y ordinate
             c(TeX("f(x)   = $(x-1)^2$"),
                "f'(x) = 2x - 2" ,
                "f''(x) = 2") ,                                                  # labels
             cex = .8,                                                           # size of text multiplier
             lty = 1,                                                            # linetype
             col = c("gray20", "gray50", "gray80"),                              # colors
             lwd = 2,                                                            # line width
             y.intersp = 1.5,                                                    # legend line spacing
             bty = "n")

# PDF Speicherung
dev.copy2pdf(
file        = file.path(getwd(), "6_Abbildungen", "mvda_6_optimierung.pdf"),
width       = 4,
height      = 4)

```
\center
```{r, echo = FALSE, out.width = "50%"}
knitr::include_graphics("6_Abbildungen/mvda_6_optimierung.pdf")
```
\vspace{-3mm}
\footnotesize
Hier ist offenbar $x_0 = 1$ eine lokale Minimalstelle von $f(x) = (x-1)^2$. Man erkennt:

* Links von $x_0$ fällt $f$ ab, rechts von $x_0$ steigt $f$ an.
* In $x_0$ steigt $f$ weder an, noch fällt $f$ ab, also ist $f'(x_0) = 0$.
* Links und rechts von $x_0$ und in $x_0$ ist die Änderung $f''$ von $f'$ positiv.
* Links von $x_0$ schwächt sich die Negativität von $f'$ zu $0$ ab.
* Rechts von $x_0$ verstärkt sich die Positivität von $f'$.


# Differentialrechnung und Analytische Optimierung
\small
\begin{definition}[Standardverfahren der analytischen Optimierung]
\justifying
$f$ sei eine univariate reellwertige Funktion. Lokale Extremstellen von $f$ können
mit folgendem \textit{Standardverfahren der analytischen Optimierung} identifiziert
werden:
\begin{itemize}
\itemsep3mm
\item[(1)] Berechnen der ersten und zweiten Ableitung von $f$.
\item[(2)] Bestimmen von Nullstellen $x^*$ von $f'$ durch Auflösen von $f'(x^*) = 0$ nach $x^*$.

$\Rightarrow$ Nullstellen von $f'$ sind Kandidaten für Extremstellen von $f$.

\item [(3)]  Evaluation von $f''(x^*)$.

$\Rightarrow$ Wenn $f''(x^*) > 0$, dann ist $x^*$ lokale Minimumstelle von $f$.

$\Rightarrow$ Wenn $f''(x^*) < 0$, dann ist $x^*$ lokale Maximumstelle von $f$.

$\Rightarrow$ Wenn $f''(x^*) = 0$, dann ist $x^*$ keine Extremstelle von $f$.
\end{itemize}
\end{definition}


# Differentialrechnung und Analytische Optimierung
Beispiel
\vspace{2mm}
\small

Wir betrachten die Funktion
\begin{equation}
f : \mathbb{R} \to \mathbb{R}, x \mapsto f(x) := (x - 1)^2.
\end{equation}

Die erste Ableitung von $f$ ergibt sich mit der Kettenregel zu
\begin{equation}
f'(x) = \frac{d}{dx}\left((x-1)^2 \right) = 2(x-1)\cdot \frac{d}{dx}(x-1) = 2x - 2.
\end{equation}

Die zweite Ableitung von $f$ ergibt sich zu
\begin{equation}
f''(x) = \frac{d}{dx}f'(x) = \frac{d}{dx}(2x - 2) = 2 > 0 \mbox{ für alle } x \in \mathbb{R}.
\end{equation}

Auflösen von $f'(x^*) = 0$ nach $x^*$ ergibt
\begin{equation}
f'(x^*) = 0
\Leftrightarrow
2x^* - 2 = 0
\Leftrightarrow
2x^* = 2
\Leftrightarrow
x^* = 1.
\end{equation}

$x^* = 1$ ist folglich eine Minimalstelle von $f$ mit zugehörigen Minimalwert $f(1) = 0$.

#
\vfill
\large
\setstretch{2}
Prädiktive Modellierung

Differentialrechnung und Analytische Optimierung

**Multivariate Differentialrechnung**

Grundlagen der Optimierung

Gradientenverfahren

Grundlagen der Optimierung mit Nebenbedingungen

Selbstkontrollfragen
\vfill

# Multivariate Differentialrechnung
\setstretch{1.1}
\small
\begin{definition}[Funktionenarten]
In der statistischen Anwendung unterscheiden wir
\begin{itemize}
\item \textit{univariate reellwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R} \to \mathbb{R}, x \mapsto f(x),
\end{equation}
\item \textit{multivariate reellwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R}^n \to \mathbb{R}, x \mapsto f(x) = f(x_1,...,x_n),
\end{equation}
\item \textit{multivariate vektorwertige Funktionen} der Form
\begin{equation}
f : \mathbb{R}^n \to \mathbb{R}^m, x \mapsto
f(x) =
\begin{pmatrix}
f_1(x_1,...,x_n) 	\\
\vdots				\\
f_m(x_1,...,x_n)
\end{pmatrix}.
\end{equation}
\end{itemize}
\end{definition}

\small
\center

**In diesem Abschnitt betrachten wir multivariate reellwertige Funktionen.**

**Beim Parameterlernen der Prädiktiven Modellierung ist**

**$x \in \mathbb{R}^n$ ein Vektor von Parameterwerten und $f : \mathbb{R}^n \to \mathbb{R}$ eine Zielfunktion**.

# 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 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 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 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 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 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 x_2} f(x) = \frac{\partial^2}{\partial x_2 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*}[r]  0.7 \\  0.7 \end{pmatrix*}\quad\quad\quad$}
\textcolor{blue}{       $x = \begin{pmatrix*}[r] -0.3 \\  0.1 \end{pmatrix*}\quad\quad\quad$}
\textcolor{red}{        $x = \begin{pmatrix*}[r] -0.5 \\ -0.4 \end{pmatrix*}\quad\quad\quad$}
\textcolor{darkgreen}{  $x = \begin{pmatrix*}[r]  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))
}

# Visualisierung
graphics.off()
fdir        =  file.path(getwd(), "6_Abbildungen")
dev.new()
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.copy2pdf(
file        = file.path(fdir, "mvda_6_gradientbeispiel.pdf"),
width       = 5,
height      = 5)

```

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

# Multivariate Differentialrechnung
\small
\setstretch{1.6}
\begin{definition}[Hesse-Matrix]
\justifying
$f : \mathbb{R}^n \to \mathbb{R}$ sei ein 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 x_1} f(x)
& 	\frac{\partial^2}{\partial x_1 x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_1 x_n} f(x)  \\
	\frac{\partial^2}{\partial x_2 x_1} f(x)
& 	\frac{\partial^2}{\partial x_2 x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_2 x_n} f(x)  \\
	\vdots
& 	\vdots
& 	\ddots
& 	\vdots 									 	\\
	\frac{\partial^2}{\partial x_n x_1} f(x)
& 	\frac{\partial^2}{\partial x_n x_2} f(x)
& 	\cdots
& 	\frac{\partial^2}{\partial x_n 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_1x_1} f(x) & \frac{\partial^2}{\partial x_1x_2}	f(x) \\
\frac{\partial^2}{\partial x_2x_1} f(x) & \frac{\partial^2}{\partial x_2x_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_1x_1}  f(x)
& \frac{\partial^2}{\partial x_1x_2}	f(x)
& \frac{\partial^2}{\partial x_1x_3}	f(x)
\\
  \frac{\partial^2}{\partial x_2x_1}  f(x)
& \frac{\partial^2}{\partial x_2x_2}	f(x)
& \frac{\partial^2}{\partial x_2x_3}	f(x)
\\
  \frac{\partial^2}{\partial x_3x_1}  f(x)
& \frac{\partial^2}{\partial x_3x_2}	f(x)
& \frac{\partial^2}{\partial x_3x_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.
* @nocedal_2006 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%"}
knitr::include_graphics("6_Abbildungen/mvda_6_mittelwertsatz.pdf")
```


#
\vfill
\large
\setstretch{2}
Prädiktive Modellierung

Differentialrechnung und Analytische Optimierung

Multivariate Differentialrechnung

**Grundlagen der Optimierung**

Gradientenverfahren

Grundlagen der Optimierung mit Nebenbedingungen

Selbstkontrollfragen
\vfill


# Grundlagen der Optimierung
\small
\begin{definition}[Optimierungsproblem]
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. Weil gilt, dass
\begin{equation}
\max_{x} f(x) = \min_{x} -f(x)
\end{equation}
genügt es, sich mit Minimierungsproblemen zu befassen.
\end{definition}

# Grundlagen der Optimierung
\small
\begin{definition}[Globale und lokale Minimierer, globale und lokale Minima]
$f : \mathbb{R}^n \to \mathbb{R}$ sei ein multivariate reellwertige Funktion.
\begin{itemize}
\justifying
\setlength{\itemsep}{3mm}
\item $x^* \in \mathbb{R}^n$ heißt globaler 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 das globale Minimum von $f$.
\item $x^* \in \mathbb{R}^n$ heißt 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$. In diesem Fall heißt $f(x^*) \in \mathbb{R}$
lokales Minimum von $f$.
\item  $x^* \in \mathbb{R}^n$ heißt 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$. In diesem Fall heißt $f(x^*) \in \mathbb{R}$
striktes lokales Minimum von $f$.
\end{itemize}
\end{definition}

\footnotesize
Bemerkung

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

# Grundlagen der 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 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 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 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 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 \mbox{ und } \nabla^2 f(x) \mbox{ positiv definit }  \Rightarrow x^* = \argmin_x f(x)
\end{equation*}

#
\vfill
\setstretch{2}
\large
Prädiktive Modellierung

Differentialrechnung und Analytische Optimierung

Multivariate Differentialrechnung

Grundlagen der Optimierung

**Gradientenverfahren**

Grundlagen der Optimierung mit Nebenbedingungen

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
\setstretch{1.8}

Gradientenverfahren

\small
**Initialisierung**

\noindent 0. Wahl von Startpunkt $x_0 \in \mathbb{R}^n$, Lernrate $\alpha > 0$, Konvergenzkriteriums $\delta > 0$.


**Iterationen**

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

1. Setze $x_{k+1} := x_k - \alpha\nabla f(x_k)$.
2. STOP, wenn $||\nabla f(x_{k+1})|| < \delta$, ansonsten gehe zu 1.


# 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}
# 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}
graphics.off()
fdir        =  file.path(getwd(), "6_Abbildungen")
dev.new()
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.copy2pdf(
file        = file.path(fdir, "mvda_6_gradientenverfahren.pdf"),
width       = 12,
height      = 4)
```
\vspace{1cm}
\vfill
```{r, echo = FALSE, out.width = "100%"}
knitr::include_graphics("6_Abbildungen/mvda_6_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. @ostwald_2016)

#
\vfill
\setstretch{2}
\large
Prädiktive Modellierung

Differentialrechnung und Analytische Optimierung

Multivariate Differentialrechnung

Grundlagen der Optimierung

Gradientenverfahren

**Grundlagen der Optimierung mit Nebenbedingungen**

Selbstkontrollfragen
\vfill


# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Optimierungsproblem mit Nebenbedingungen]
\justifying
Ein \textit{Optimierungsproblem mit Nebenbedingungen} hat die allgemeine Form
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I,
\end{equation}
wobei $f : \mathbb{R}^n \to \mathbb{R}$ und $c_i : \mathbb{R}^n \to \mathbb{R}, i \in E \cup I$
glatte multivariate reellwertige Funktions und $E,I$ endliche Indexmengen sind.
$f$ heißt \textit{Zielfunktion}, die $c_i, i \in E$ heißen \textit{Gleichungsnebenbedingungen} und
die $c_i, i \in I$ heißen \textit{Ungleichungsnebenbedingungen}. Die Menge
\begin{equation}
\mathcal{X} := \{x \in \mathbb{R}^n| c_i(x) = 0, i \in E \mbox{ und } c_i(x) \ge 0, i \in I \}
\end{equation}
heißt \textit{feasible set}.
\end{definition}

Bemerkung

* \justifying Die notwendigen Bedingungen für Minimalstellen bei Optimierungsproblem
ohne Nebenbedingungen sind für $n = 1$: $f'(x^*) = 0$ und
für $n > 1$: $\nabla f(x^*) = 0_n$. Im Folgenden führen wir analoge notwendige
Bedingungen erster Ordnung für  Minimalstellen bei Optimierungsproblemen mit
Nebenbedingungen ein.


# Grundlagen der Optimierung mit Nebenbedingungen
Beispiel

\footnotesize
\begin{definition}[Quadratisches Programm]
\justifying
Ein \textit{Quadratisches Programm} ist das konvexe Optimierungsproblem mit den
Nebenbedingungen
\begin{equation}
\min_{x \in \mathbb{R}^n} \frac{1}{2}x^T P x + q^T x
\mbox{ u.d.N. }
Ax = b
\mbox{ und }
-Gx + h \ge 0,
\end{equation}
wobei
\begin{itemize}
\item $P \in \mathbb{R}^{n \times n}$ eine positiv definite Matrix ist,
\item $q \in \mathbb{R}^n$, $A \in \mathbb{R}^{p\times n}$, $b \in \mathbb{R}^p$ sind und
\item $G \in \mathbb{R}^{m \times n}$, und  $h \in \mathbb{R}^m$ sind.
\end{itemize}
\end{definition}

Bemerkungen

* Quadratische Programme sind Optimierungsprobleme mit Nebenbedingungen.
* Parameterlernen bei Support Vektor Maschinen  führt auf ein Quadratisches Programm.
* Optimierungstoolboxen enhalten Funktionen zur Lösung Quadratischer Programme.
* In R bietet sich das Paket `quadprog` an.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Lagrange Funktion, Lagrange Multiplikatoren]
\justifying
Es sei
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I,
\end{equation}
ein Optimierungsproblem mit Nebenbedingungen. Dann ist die \textit{Lagrange Funktion}
dieses Problems definiert als
\begin{equation}
L: \mathbb{R}^n \times \mathbb{R}^{|E\cup I|} \to \mathbb{R},
(x,\lambda) \mapsto L(x,\lambda) :=
f(x) - \sum_{i \in E \cup I}\lambda_ic_i(x).
\end{equation}
Hierbei wird $\lambda \in \mathbb{R}^{|E\cup I|}$ \textit{Lagrange-Multiplikatoren Vektor}
genannt und die einzelnen $\lambda_i \in \mathbb{R}$ mit $i \in E\cup I$ werden
\textit{Lagrange Multiplikatoren}genannt.
\end{definition}

Bemerkung

* \justifying Die Lagrange Funktion und die Lagrange Multiplikatoren nehmen in den
notwendigen Bedingungen der Optimierung mit Nebenbedingungen eine zentrale Rolle ein.


# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Notwendige Bedingungen erster Ordnung]
\justifying
$x^*$ sei eine lokale Lösung des Optimierungsproblems
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I.
\end{equation}
Dann gibt es einen Lagrange-Multiplikatoren Vektor $\lambda^* \in \mathbb{R}^{|E\cup I|}$
mit den Komponenten $\lambda_i^*, i \in E \cup I$, so dass die folgenden Bedingungen
an der Stelle $(x^*,\lambda^*) \in \mathbb{R}^{n + |E\cup I|}$ gelten
\begin{align*}
\nabla_x L(x^*,\lambda^*) 	  & =   0 								\\
c_i(x^*) 					            & =   0 \mbox{ für alle } i \in E 		\\
c_i(x^*) 					            & \ge 0 \mbox{ für alle } i \in I 		\\
\lambda_i^* 				          & \ge 0 \mbox{ für alle } i \in I 		\\
\lambda_i^*c_i(x^*)			      & = 0 \mbox{ für alle } i \in E\cup I
\end{align*}
\end{definition}

Bemerkungen

* Die Bedingungen werden auch \textit{Karush-Kuhn-Tucker (KKT)} Bedingungen genannt.
* Für einen Beweis und Reguläritätsbedingungen, siehe @nocedal_2006 Section 12.4.
* Die letzte Bedingung impliziert $\lambda_i^* > 0 \Rightarrow c_i(x^*) = 0$.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Duales Problem]
\justifying
Es sei
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0,
\end{equation}
ein Optimierungsproblem ohne Gleichungsnebenbedingungen, $c(x) := (c_1(x),c_2(x),...,c_m(x))^T$
sei die multivariate vektorwertige Funktion der Ungleichungsnebenbedingungen
und die zugehörige Lagrange Funktion und der Lagrange Multiplikatoren Vektoren $\lambda \in \mathbb{R}^m$
seien durch
\begin{equation}
L: \mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R},
(x,\lambda) \mapsto L(x,\lambda) :=
f(x) - \lambda^T c(x).
\end{equation}
gegeben. Dann ist die \textit{duale Zielfunktion} (auch \textit{duale Lagrange Funktion genannt})
definiert als
\begin{equation}
q : \mathbb{R}^m \to \mathbb{R}, \lambda \mapsto q(\lambda) := \min_x L(x,\lambda),
\end{equation}
und das  \textit{duale Problem} ist definiert als
\begin{equation}
\max_{\lambda \in \mathbb{R}^m} q(\lambda) \mbox{ u.d.N. } \lambda \ge 0.
\end{equation}
\end{definition}
Bemerkung

* Duale Probleme sind manchmal einfacher zu lösen als die (primären) Ausgangsprobleme.
* Duale Probleme sind für das Parameterlernen von Support Vektor Maschinen zentral.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{theorem}[Schwache Dualität]
\justifying
\normalfont
Für jede Lösung $\bar{x}$ von
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0,
\end{equation}
und jedes $\bar{\lambda} \ge 0$ gilt, dass
\begin{equation}
q(\bar{\lambda}) \le f(\bar{x}).
\end{equation}
\end{theorem}

\footnotesize
\underline{Beweis}

Mit den Definitionen von $q$, $\bar{\lambda} \ge 0$, und $c(\bar{x}) \ge 0$,  gilt, dass
\begin{equation}
q(\bar{\lambda})
= \min_x f(x) - \bar{\lambda}^T c(x)
\le f(\bar{x}) - \bar{\lambda}^T c(\bar{x})
\le f(\bar{x}).
\end{equation}

$\hfill \Box$

Bemerkung

* \justifying Das Theorem besagt, dass der optimierte Wert des dualen Problems eine
untere Grenze für den optimalen Wert der Zielfunktion des Ausgangsproblems ist.


# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{theorem}[Starke Dualität]
\normalfont
\justifying
Gegeben seien das Optimierungsproblem
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0
\end{equation}
und seine zugehörigen notwendigen Bedingungen erster Ordnung
\begin{align}
\begin{split}
\nabla f(\bar{x}) - \nabla c(\bar{x})\bar{\lambda} & = 0, \\
c(\bar{x}) & \ge 0, \\
\bar{\lambda} & \ge 0, \\
\bar{\lambda}_i c_i(\bar{x}) & = 0, i = 1,2,...,m,
\end{split}
\end{align}
mit $\nabla c(x) = \left(\nabla c_1(x), \nabla c_2(x), ...,\nabla c_m(x)\right) \in \mathbb{R}^{n \times m}$.
$\bar{x}$ sei eine Lösung des Ausgangsproblems und $f$ sowie $-c_i, i = 1,2,...,m$
konvexe Funktionen auf  $\mathbb{R}^n$, die in $\bar{x}$ differenzierbar sind.
Dann ist jedes $\bar{\lambda}$, für das $(\bar{x},\bar{\lambda})$ die notwendigen
Bedingungen des Ausgangsproblem erfüllt, eine Lösung des dualen Problems
\end{theorem}

Bemerkungen

* Die optimalen Lagrange Multiplikatoren des Ausgangsproblems sind Lösungen des dualen Problems.
* SVM Training als Quadratisches Programm benötigt das Konzept der starken Dualität.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\underline{Beweis}
\vspace{1mm}

Wir nehmen an, dass  $(\bar{x}, \bar{\lambda})$ die notwendigen Bedingungen erster
Ordnung für ein Minimum des Ausgangsproblem erfüllen und dass $L(\cdot ,\bar{\lambda})$
konvex und differenzierbar ist. Dann gilt für jedes  $x \in \mathbb{R}^n$, dass
\begin{equation}
L(x,\bar{\lambda})
\ge L(\bar{x},\bar{\lambda}) + \nabla_x L(\bar{x},\bar{\lambda})(x - \bar{x})
= L(\bar{x},\bar{\lambda}),
\end{equation}
weil $\nabla_x L(\bar{x},\bar{\lambda}) = 0$. Also gilt für die duale Zielfunktion
\begin{equation}
q(\bar{\lambda}) = \inf_{x} L(x,\bar{\lambda}) = L(\bar{x},\bar{\lambda}).
\end{equation}
Mit der letzten der notwendigen Bedingungen erster Ordnung folgt weiterhin
\begin{equation}
q(\bar{\lambda})
= L(\bar{x},\bar{\lambda})
= f(\bar{x}) - \bar{\lambda}^T c(\bar{x})
= f(\bar{x})
\end{equation}
Schließlich gilt mit dem Theorem zur Schwachen Dualität, dass  $q(\lambda) \le f(\bar{x})$
für alle $\lambda \ge 0$. Also folgt mit  $q(\bar{\lambda}) = f(\bar{x})$, dass
$\bar{\lambda}$ eine Lösung des dualen Problems ist.
$\hfill \Box$

#
\vfill
\setstretch{2}
\large
Prädiktive Modellierung

Differentialrechnung und Analytische Optimierung

Multivariate Differentialrechnung

Grundlagen der Optimierung

Gradientenverfahren

Grundlagen der Optimierung mit Nebenbedingungen

**Selbstkontrollfragen**

\vfill

# Selbstkontrollfragen
\footnotesize
\begin{enumerate}
\item Erläutern Sie das allgemeine datenanalytische Vorgehen im Rahmen der Prädiktiven Modellierung.
\item Nennen Sie drei in der Prädiktiven Modellierung typischerweise vewendete Verfahren.
\item Erläutern Sie den Begriff der $k$-fachen Kreuzvalidierung.
\item Erläutern Sie Gemeinsamkeiten und Unterschiede explanatorischer und prädiktiver Modellierung.
\item Warum ist die Kenntnis von Optimierungsprinzipien im Rahmen der Prädiktiven Modellierung wichtig?
\item Definieren Sie die Begriffe der univariat-und multivariat-reellwertigen Funktion.
\item Definieren Sie Begriff der multivariaten vektorwertigen Funktion.
\item Definieren Sie den Begriff der Ableitung $f'(a)$ einer Funktion $f$ an einer Stelle $a$.
\item Definieren den Begriff der Ableitung $f'$ einer Funktion $f$.
\item Erläutern Sie die Symbole $f'(x), \dot{f}(x)$, $\frac{df(x)}{dx}$, und $\frac{d}{dx}f(x)$.
\item Definieren Sie den Begriff der zweiten Ableitung $f''$ einer Funktion $f$.
\item Geben Sie die Summenregel für Ableitungen wieder.
\item Geben Sie die Produktregel für Ableitungen wieder.
\item Geben Sie die Quotientenregel für Ableitungen wieder.
\item Geben Sie die Kettenregel für Ableitungen wieder.
\end{enumerate}

# Selbstkontrollfragen
\footnotesize
\begin{enumerate}
\setcounter{enumi}{15}
\item Bestimmen Sie die Ableitung der Funktion $f(x) := 3x^2 + \exp\left(-x^2\right) - x \ln(x)$
\item Bestimmen Sie die Ableitung der Funktion $f(x) :=\frac{1}{2}\sum_{i=1}^n (x_i - \mu)^2$ für $\mu \in \mathbb{R}$.
\item Definieren Sie die Begriffe des globalen und lokalen Maximums/Minimums einer Funktion.
\item Geben Sie die notwendige Bedingung für ein Extremum einer Funktion wieder.
\item Geben Sie die hinreichende Bedingung für ein lokales Extremum einer Funktion wieder.
\item Geben Sie das Standardverfahren der analytischen Optimierung wieder.
\item Bestimmen Sie einen Extremwert von $f(x) := \exp\left(-\frac{1}{2}(x - \mu)^2\right)$ für $\mu \in \mathbb{R}$.
\item Berechnen Sie die (ersten) partiellen Ableitungen der Funktion 
\begin{equation}
f : \mathbb{R}^2 \to \mathbb{R}, x \mapsto f(x) := \exp\left(-\frac{1}{2}\left(x_1^2 + x_2^2\right)\right)
\end{equation}
\item Berechnen Sie die zweiten partiellen Ableitungen obiger Funktion $f$.
\item Geben Sie den Satz von Schwarz wieder.
\item Definieren Sie den Gradienten einer multivariaten reellwertigen Funktion.
\item Geben Sie den Gradienten obiger Funktion $f$ an und werten Sie ihn in $x = (1,2)^T$ aus.

\end{enumerate}

# Selbstkontrollfragen
\footnotesize
\begin{enumerate}
\setcounter{enumi}{29}
\item Definieren Sie die Hesse-Matrix einer multivariaten reellwertigen Funktion.
\item Geben Sie die Hesse-Matrix obiger Funktion $f$ an und werten Sie sie in $x = (1,2)^T$ aus.
\item Definieren Sie die allgemeine Form eines Optimierungsproblems.
\item Was sind $x$ und $f$ eines Optimierungsproblems in der Prädiktiven Modellierung?
\item Warum betrachtet man in der Theorie der Optimierung nur die Minimierung?
\item Definieren Sie die Begriffe der globalen und lokalen Minimalstellen einer multivariaten reellwertigen Funktion.
\item Geben Sie die notwendige Bedingung erster Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
\item Geben Sie die notwendige Bedingung zweiter Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
\item Geben Sie die hinreichende Bedingung zweiter Ordnung für ein Minimum von $f:\mathbb{R}^n \to \mathbb{R}$ an.
\item Geben Sie das Theorem zu Minimalstellen konvexer Funktionen an.
\item Formulieren Sie den Algorithmus des Gradientenverfahrens.
\item Geben Sie das Theorem zum Gradientenverfahren wieder.
\item Erläutern Sie die Bedeutung der Lernrate $\alpha > 0$ und des Konvergenzkriteriums $\delta > 0$ im Gradientenverfahren.
\end{enumerate}

# References
\footnotesize