10_Gradient_Descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Überblick"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir betrachten das Gradient-Descent Verfahren \n",
    "\\begin{equation*}\n",
    "x_{t+1} = x_t - \\gamma_t f'_t,\n",
    "\\end{equation*}\n",
    "untersuchen Konvergenz, d.h.\n",
    "\\begin{equation*} \n",
    "f_t - f_\\ast \\xrightarrow{t\\to\\infty} 0\n",
    "\\end{equation*}\n",
    "bzw.\n",
    "\\begin{equation*} \n",
    "\\|x_t - x_\\ast\\| \\xrightarrow{t\\to\\infty} 0\n",
    "\\end{equation*}  \n",
    "und versuchen das asymptotische Verhalten genauer zu analysieren.\n",
    "  \n",
    "Für den Rest des Kapitels setzen wir $f\\in C^1(\\mathbb{R}^d)$ konvex und $\\gamma_t = \\gamma$ konstant voraus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vorüberlegungen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ist\n",
    "  $f\\in C^1(\\mathbb{R}^d)$, \n",
    "  $x_\\ast = \\mathrm{argmin}_{x\\in\\mathbb{R}}f(x)$, \n",
    "  $x_{t+1} = x_t - \\gamma f'_t$, dann gilt\n",
    "  \\begin{equation*} \n",
    "  \\begin{aligned}\n",
    "  \\|x_{t+1}-x_{*}\\|_{2}^{2} \n",
    "  &=\\|x_{t}-x_{*}-\\gamma f_{t}^{\\prime}\\|_{2}^{2} \\\\\n",
    "  &=\\|x_{t}-x_{*}\\|_{2}^{2}+\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}-2\n",
    "  \\gamma f_{t}^{\\prime}(x_{t}-x_{*})\n",
    "  \\end{aligned}\n",
    "  \\end{equation*}\n",
    "  und somit\n",
    "  \\begin{equation*} \n",
    "  f'_{t}(x_{t}-x_{*}) \n",
    "  =\\frac{1}{2 \\gamma}\\big(\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "  +\\|x_{t}-x_{*}\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big).\n",
    "  \\end{equation*}\n",
    "\n",
    "Für konvexes $f$  ist\n",
    "  \\begin{equation*} \n",
    "  f(y) \\geq f(x) + f'(x)(y-x)\n",
    "  \\end{equation*}\n",
    "  und mit $y=x_\\ast$, $x=x_t$\n",
    "  \\begin{equation*} \n",
    "  f_\\ast \\geq f_t + f'_t (x_\\ast-x_t)\n",
    "  \\end{equation*}\n",
    "  bzw.\n",
    "  \\begin{align*} \n",
    "  0 \n",
    "  \\leq f_t - f_\\ast\n",
    "  &\\leq f'_t(x_t - x_\\ast)\\\\\n",
    "  &= \\frac{1}{2 \\gamma}\\big(\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "+\\|x_{t}-x_{*}\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big).\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aufsummiert erhält man\n",
    "\\begin{align*} \n",
    "\\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "& \\leq \\sum_{t=0}^{T-1} f'_t(x_t - x_\\ast)\\\\\n",
    "&   =   \\frac{1}{2 \\gamma}\n",
    "        \\ \\sum_{t=0}^{T-1} \n",
    "         \\big( \\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "                +\\|x_{t}-x_\\ast\\|_{2}^{2}\n",
    "                -\\|x_{t+1}-x_{*}\\|_{2}^{2}\n",
    "          \\big)\n",
    "\\end{align*}\n",
    "bzw.\n",
    "\\begin{align*} \n",
    "\\underbrace{\\frac{1}{T}\\sum_{t=0}^{T-1} (f_t - f_\\ast)}_{\\text{''mittlere Abweichung von } f_\\ast  \\text{''}}\n",
    "& \\leq \n",
    "  \\frac{\\gamma}{2}\n",
    "  \\underbrace{\\frac{\\sum_{t=0}^{T-1} \\|f_{t}^{\\prime}\\|_{2}^{2}}{T}}_\\text{''mittlerer Gradient''} \n",
    "\\\\\n",
    "& \\quad +\n",
    "  \\frac{1}{2 \\gamma}\n",
    "  \\underbrace{\\frac{\\|x_{0}-x_\\ast\\|_{2}^{2}-\\left\\|x_{T}-x_{*}\\right\\|_{2}^{2}}{T}}_{\\leq \\frac{\\|x_{0}-x_\\ast\\|_{2}^{2}}{T} = \\mathcal{O}(\\frac{1}{T})\\ \\text{''Startfehler''}}.\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mit $\\hat{t} = \\mathrm{argmin}_{t\\in\\{0,\\ldots,T-1\\}}(f_t - f_\\ast)$ ($\\hat{t}$ nicht notwendig gleich $T-1$) folgt\n",
    "  \\begin{equation*} \n",
    "  f_{\\hat{t}} - f_\\ast \\leq \\frac{1}{T}\\sum_{t=0}^{T-1} (f_t - f_\\ast).\n",
    "  \\end{equation*}\n",
    "Der Anteil \n",
    "  \\begin{equation*} \n",
    "  \\frac{1}{2 \\gamma}\\frac{\\|x_{0}-x_\\ast\\|_{2}^{2}-\\|x_{T}-x_{*}\\|_{2}^{2}}{T}\n",
    "  \\end{equation*} \n",
    "  war zu erwarten.\n",
    "Das Ziel ist es nun\n",
    "  \\begin{equation*} \n",
    "  \\frac{\\gamma}{2T} \\sum_{t=0}^{T-1} \\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "  \\end{equation*}\n",
    "  zu kontrollieren.\n",
    "Dazu muss $f$ zusätzliche Voraussetzungen erfüllen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lipschitz-Stetigkeit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im letzten Abschnitt haben wir  $f\\in C^1(\\mathbb{R}^d)$ konvex vorausgesetzt.\n",
    "Jetzt fordern wir zusätzlich Lipschitz-Stetigkeit von $f$, d.h.\n",
    "\\begin{equation*} \n",
    "|f(y) - f(x)| \\leq L_f \\|y - x\\| \\quad \\forall x,y\\in\\mathbb{R}^d.\n",
    "\\end{equation*}\n",
    "Dies ist äquivalent zur Beschränktheit des Gradienten, wie das folgende\n",
    "Ergebnis aus der Analysis zeigt."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lemma:** $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\rightarrow \\mathbb{R}$ differenzierbar\n",
    "(nicht notwendig konvex), $X\\subset\\mathrm{dom}(f)$ offen, konvex.\n",
    "Dann ist\n",
    "\\begin{equation*} \n",
    "|f(x) -f(y)| \\leq L_f \\|x-y\\| \\quad \\forall x,y\\in X\n",
    "\\end{equation*}\n",
    "äquivalent zu\n",
    "\\begin{equation*} \n",
    "\\|f'(x)\\| \\leq L_f \\quad \\forall x\\in X,\n",
    "\\end{equation*}\n",
    "wobei bei $f'$ die induzierte Operatornorm benutzt wird."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "\"$\\Rightarrow$\"\n",
    "\n",
    "- für $f$ gelte\n",
    "    \\begin{equation*} \n",
    "    |f(x) -f(y)| \\leq L_f \\|x-y\\| \\quad \\forall x,y\\in X\n",
    "    \\end{equation*}\n",
    "\n",
    "- da $X$ offen ist gibt es für jedes $x\\in X$ eine Kugel\n",
    "$B_r(x)$ mit ${B}_r(x)\\subset X$\n",
    "\n",
    "- für beliebiges $v\\in\\mathbb{R}^d$ mit $\\|v\\|=1$ ist deshalb die Funktion\n",
    "    \\begin{equation*} \n",
    "    g(t) = f(x + tv), \\quad t \\in (-r,r)\n",
    "    \\end{equation*}\n",
    "  wohldefiniert\n",
    "\n",
    "- mit $f$ ist auch $g$ differenzierbar mit\n",
    "    \\begin{equation*} \n",
    "    g'(t) = f'(x + tv)v\n",
    "    \\end{equation*}\n",
    "  und somit gilt für alle $v\\in\\mathbb{R}^d$ mit $\\|v\\|=1$\n",
    "    \\begin{align*}\n",
    "    \\|f'(x)v\\|\n",
    "    &= |g'(0)| \\\\\n",
    "    &= \\big| \\lim_{t\\to 0} \\frac{g(t) - g(0)}{t}  \\big| \\\\\n",
    "    &= \\lim_{t\\to 0}  \\big| \\frac{f(x + tv) - f(x)}{t}  \\big| \\\\\n",
    "    &\\leq L_f \\lim_{t\\to 0}  \\big\\| \\frac{x + tv - x}{t}  \\big\\| \\\\\n",
    "    & = L_f \\|v\\|,\n",
    "    \\end{align*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    \\|f'(x)\\| \\leq L_f \n",
    "    \\end{equation*}\n",
    "\n",
    "\"$\\Leftarrow$\"\n",
    "\n",
    "- für $f$ gelte\n",
    "    \\begin{equation*} \n",
    "    \\|f'(x)\\| \\leq L_f \\quad \\forall x\\in X\n",
    "    \\end{equation*}\n",
    "\n",
    "- da $X$ konvex ist, ist für alle $x,y\\in X$ und $t\\in[0,1]$ die Funktion\n",
    "    \\begin{equation*} \n",
    "    g(t) = f\\big(x+ t(y-x)\\big)\n",
    "    \\end{equation*}\n",
    "  wohldefiniert und es gilt\n",
    "    \\begin{equation*} \n",
    "    g(0) = f(x),\n",
    "    \\quad\n",
    "    g(1) = f(y)\n",
    "    \\end{equation*}\n",
    "\n",
    "- mit $f$ ist auch $g$ differenzierbar mit\n",
    "    \\begin{equation*} \n",
    "    g'(t) = f'\\big(x+ t(y-x)\\big)(y-x)\n",
    "    \\end{equation*}\n",
    "\n",
    "- durch Anwendung des Mittelwertsatzes folgt\n",
    "    \\begin{align*}\n",
    "    |f(x) - f(y)| \n",
    "    & = |g(1) - g(0)| \\\\\n",
    "    & = |g'(\\tau)|\\\\\n",
    "    & = |f'\\big(\\underbrace{x+ \\tau (y-x)}_{\\xi}\\big)(y-x)| \\\\\n",
    "    & \\leq \\|f'(\\xi)\\| \\ \\|y-x\\| \\\\\n",
    "    & \\leq L_f \\|x-y\\| \n",
    "    \\end{align*}\n",
    "\n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setzen wir dies in die summierte Abschätzung von oben ein, so erhalten wir\n",
    "  \\begin{align*}\n",
    "  \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  &\\leq \\sum_{t=0}^{T-1}f'_t(x_t - x_\\ast)\\\\\n",
    "  & = \\frac{1}{2 \\gamma}\n",
    "      \\ \\sum_{t=0}^{T-1} \n",
    "   \\big(\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}+\\|x_{0}-x_\\ast\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big)\\\\\n",
    "  & \\leq \\frac{\\gamma}{2}T L_f^2 \n",
    "  + \\frac{1}{2\\gamma} \n",
    "  \\big( \n",
    "  \\underbrace{\\|x_{0}-x_{*}\\|_{2}^{2}}_{e_0^2}\n",
    "  -\n",
    "  \\underbrace{\\|x_{T}-x_{*}\\|_{2}^{2}}_{\\geq 0}\n",
    "  \\big)\\\\\n",
    "  &\\leq \\frac{\\gamma T L_f^2}{2} + \\frac{e_0^2}{2\\gamma},\\\\\n",
    "  \\end{align*}\n",
    "also\n",
    "  \\begin{align*} \n",
    "  \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "  \\leq \\frac{1}{T} \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  \\leq \\frac{\\gamma L_f^2}{2} + \\frac{e_0^2}{2\\gamma T}.\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wann verschwindet die rechte Seite für $T\\to\\infty$ ?\n",
    "Beide Summanden auf der rechten Seite sind $\\geq 0$, so dass\n",
    "  \\begin{equation*} \n",
    "  \\frac{\\gamma L_f^2}{2}\\xrightarrow{T\\to\\infty}0,\n",
    "  \\quad\n",
    "  \\frac{e_0^2}{2\\gamma T}\\xrightarrow{T\\to\\infty}0\n",
    "  \\end{equation*}\n",
    "gelten muss, also\n",
    "  \\begin{equation*} \n",
    "  \\gamma \\xrightarrow{T\\to\\infty}0, \\quad \\gamma T \\xrightarrow{T\\to\\infty}\\infty.\n",
    "  \\end{equation*}\n",
    "Mit dem Ansatz\n",
    "  \\begin{equation*} \n",
    "  \\gamma = \\frac{c}{T^\\omega}, \\quad c,\\omega > 0\n",
    "  \\end{equation*}\n",
    "gilt immer $\\gamma \\xrightarrow{T\\to\\infty}0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für den zweiten Teil erhalten wir \n",
    "  $\\gamma T = c T^{1-\\omega}\\xrightarrow{T\\to\\infty}\\infty$\n",
    "falls  $1-\\omega>0$, also \n",
    "  \\begin{equation*} \n",
    "  \\omega < 1\n",
    "  \\end{equation*}\n",
    "ist.\n",
    "Oben eingesetzt folgt\n",
    "  \\begin{align*} \n",
    "  \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "  &\\leq \\frac{\\gamma L_f^2}{2} + \\frac{e_0^2}{2\\gamma T} \\\\ \n",
    "  & = \n",
    "  \\frac{c L_f^2}{2}\\frac{1}{T^\\omega} + \\frac{e_0^2}{2c} \\frac{1}{T^{1-\\omega}} \\\\\n",
    "  &= \\mathcal{O}\\Big(\\big(\\frac{1}{T}\\big)^{\\min(\\omega,1-\\omega)}\\Big).\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die obere Schranke\n",
    "  \\begin{equation*} \n",
    "  g(\\gamma) = \\frac{\\gamma L_f^2}{2} + \\frac{e_0^2}{2\\gamma T}\n",
    "  \\end{equation*}\n",
    "wird wegen\n",
    "  \\begin{equation*} \n",
    "  g'(\\gamma) = \\frac{ L_f^2}{2} - \\frac{e_0^2}{2\\gamma^2 T},\n",
    "  \\quad\n",
    "  g''(\\gamma) =  \\frac{e_0^2}{\\gamma^3 T} \\geq 0\n",
    "  \\end{equation*}\n",
    "minimal für\n",
    "  \\begin{equation*} \n",
    "  \\gamma_{\\min} = \\frac{e_0}{L_f\\sqrt{T}}\n",
    "  \\end{equation*}\n",
    "mit\n",
    "  \\begin{equation*} \n",
    "  g_{\\min} = g(\\gamma_{\\min}) = \\frac{ L_f e_0}{\\sqrt{T}}.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Damit erhalten wir das folgende Ergebnis.\n",
    "\n",
    "\n",
    "**Satz:** $f:\\mathbb{R}^d\\to \\mathbb{R}$, konvex, $C^1$, L-stetig mit Konstante $L_f$\n",
    "und es existiere $x_\\ast = \\mathrm{argmin}_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "\n",
    "Mit $\\gamma = \\frac{c}{T^\\omega}$, $\\omega\\in(0,1)$, gilt\n",
    "\\begin{align*} \n",
    "\\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "&\\leq \\frac{1}{T} \\sum_{t=0}^{T-1} (f_t - f_\\ast)\\\\\n",
    "&= \\mathcal{O}\\Big(\\big(\\frac{1}{T}\\big)^{\\min(\\omega,1-\\omega)}\\Big)\n",
    "\\quad \n",
    "\\text{für}\n",
    "\\quad\n",
    "T\\to\\infty.\n",
    "\\end{align*}\n",
    "\n",
    "Die optimale Ordnung ist $\\frac{1}{2}$ bei $\\omega=\\frac{1}{2}$.\n",
    "\n",
    "Mit $e_0 = \\|x_0 - x_\\ast\\|_2$, $\\gamma = \\frac{e_0}{L_f\\sqrt{T}}$ gilt außerdem\n",
    "\\begin{equation*} \n",
    "\\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "\\leq \\frac{1}{T} \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "\\leq \\frac{ L_f e_0}{\\sqrt{T}}.\n",
    "\\end{equation*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- $\\min_{t=0,\\ldots,T-1}(f_t - f_\\ast) \\leq \\varepsilon$ gilt damit sicher, falls\n",
    "    \\begin{equation*} \n",
    "    \\frac{ L_f e_0}{\\sqrt{T}} \\leq \\varepsilon\n",
    "    \\end{equation*}\n",
    "  bzw.\n",
    "    \\begin{equation*} \n",
    "    T \\geq \\big(\\frac{e_0}{L_f \\varepsilon}\\big)^2\n",
    "    \\end{equation*}\n",
    "\n",
    "- für $\\min_{t=0,\\ldots,T-1}(f_t - f_\\ast) \\leq \\varepsilon$ benötigen \n",
    "  wir damit höchstens $\\mathcal{O}(\\frac{1}{\\varepsilon^2})$ Schritte\n",
    "\n",
    "- in der Praxis gibt man $\\varepsilon$ vor, bestimmt $T$ und das zugehörige (feste) \n",
    "    \\begin{equation*} \n",
    "    \\gamma = \\frac{e_0}{L_f\\sqrt{T}}\n",
    "    \\end{equation*}  und führt dann (maximal) $T-1$ Schritte des Verfahrens durch\n",
    "\n",
    "- für $\\varepsilon\\to 0$ gilt $T\\to\\infty$ und \n",
    "    \\begin{equation*} \n",
    "    \\gamma = \\frac{e_0}{L_f\\sqrt{T}} \\to 0\n",
    "    \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $L$-Glattheit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ist $f$ konvex und $C^1$, dann gilt\n",
    "\\begin{equation*} \n",
    "f(y) \\geq f(x) + f'(x)(y-x),\n",
    "\\end{equation*}\n",
    "d.h. der Graph von $f$ verläuft oberhalb seiner Tangenten.\n",
    "Zur Abschätzung nach oben führen wir den folgenden Begriff ein.\n",
    "\n",
    "\n",
    "**Definition:**\n",
    "$f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$ (nicht notwendig konvex),\n",
    "$X\\subset \\mathrm{dom}(f)$. \n",
    "$f$ heißt $L$-glatt auf $X$ falls ein $L>0$ existiert, mit\n",
    "\\begin{equation*} \n",
    "f(y) \\leq f(x) + f'(x)(y-x) + \\frac{1}{2}L \\|y-x\\|_2^2\n",
    "\\quad \\forall x,y\\in X.\n",
    "\\end{equation*}\n",
    "\n",
    "  \n",
    "**Bemerkung:** Ist $f$ $L$-glatt, so verläuft der Graph von $f$ unterhalb der\n",
    "quadratischen Approximation \n",
    "\\begin{equation*} \n",
    "q_{L,x}(y) = f(x) + f'(x)(y-x) + \\frac{1}{2}L\\|y-x\\|_2^2.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-09-24T09:33:30.717935Z",
     "iopub.status.busy": "2021-09-24T09:33:30.717555Z",
     "iopub.status.idle": "2021-09-24T09:33:31.432435Z",
     "shell.execute_reply": "2021-09-24T09:33:31.432720Z"
    },
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAf8ElEQVR4nO3dd5iV1fX28e+aGapSFDSKqIhGFFEUQQ1KxG5sKEawgwRjSZREY4vIw+NrTKLG9CIajQ1LEg2K3ejYMIoIEgho1B8CIgrEIGWos94/9kPRoA4w59nnnLk/13WuQc8wsxiYe/bZZW1zd0REJB8VsQsQEWlIFLoiIjlS6IqI5EihKyKSI4WuiEiOChK6ltoAS80ttWHrfge7GjPHrE8hPr+I1DOzxpi9gdkHmG0eu5xCstSOy/LrV4X4+IUa6d6RPVJL7bh1PH8NMAEYgVnbAtUgIvXnKmAP4Nu4/yd2MYViqe0C3AW8BlxWkM9RqH26lloz4AVgZ2AfT3zqp9/BdgfGAaOAfmjDsEhxMusBvAzchfvAyNUUjKXWCngVaA1098RnFOTzFDLrLLVtCcH6MSF453/6Hexy4MfAKbjfW7BCRGTDmDUlfA+3Arrg/t+4BRWGpVZBGAAeCRziiT9fqM9V0IW07CfFN4GOwN3ZH2xtNwD/AH6H2daFrEVENkgKdAYGl2vgZoYDxwBDChm4kMPuhewPMAQ4mvAXuNaTvgIYADQFbsbMCl2PiNSR2QHAD4BbcH88djmFYqn1JcxZ/xH4fcE/Xx5TqZaaATcD3wJO9MQf+PQ72IXAL4Gzcb+l4AWJyBcza01Y7F4B7IX7gqj1FIilthvwCvBPoLcnvrTgnzOv9StLrQlQDewO7OeJT1rzpFUATwH7At1wfyuXokRk3czuBvoD++P+SuxyCsFS25wQuJsCe3vis/L4vLkdjsh+gpwIfAI8bKltueZJryVMMywFRmLWOK+6ROQzzE4DTgWGl3HgNgL+DGxHePWdS+BCzifSsj9YH2Ar4IFs9Js96TOBwcDewNV51iUiGbMdgN8BLxJ2FpWdbLrz18DBwGBPfEyenz/3Y8Ce+FjgTGB/4ObsC5A96Q8CI4BLMTsk79pEGjSzKuDO7L/OwH1lzHIK6ELgHODHnvidX/bO9S1K7wVP/M/AMOAM/vfUx0XAm8AdmLXJuzaRBuwKwmDoPNynRa6lICy1bwA3Ag8CQ6PUEOsgWDbCvRs4BejriT+45knbizDB/QjQV6fVRArMbD/ClMK9uJ8eu5xCsNS6AGOAt4FenviiKHXEzLPsqPCzhB0NB3ji49c8aRcBPwPOxf2mOBWKNABmLQjbwyqBrvhnTo6WgWzh/hXCmYAenvjMaLXEHkRaalsRzjtXEI4Kh1XEsI3sMaAXsDfuU6IVKVKubPUrzv7Agbi/GLmiepct2P+dsEj/9WxdKZro/XQ98dmE43etCVvJNg1PeC0wEFgE3ItZs0glipSzbxOm+K4q08CtAG4lzFUPiB24UAShC+CJTwT6AXsC91lqVeEJ/4Cw02EPwhYPEakvYe3kl8ATwE8iV1Mo1xD2HP/QE78/djFQJKEL4Ik/CpwHHAX8dvVWMvfHgB8B38JsQLwKRcqIWUvgfmAuYXtYbeSK6p2ldg5hR8YIiuiHStGELoAnPgK4lvCS5/K1nhpOOEL8e8y65F+ZSBmx1b1QdgBOxn1O5IrqnaV2DOGQx6PAdzwpnh1QRRW6maGEif1rLbXTgFXdyE4B5gN/yVZbRWTDnEeYzruyTOdxuwP3AeOB/p74isglfUr03QvrYqk1Bh4HDgCO8MSfDU9Yb8Iq5P3Aqdq/K7KezLoRboF4Gji23KYVLLUdCH++JYTGWrMjl/Q/ijJ0ASy11oTN2u2B/T3xyeEJ+yFhjvd83Ave+1KkbJi1Al4HGhPaNc6NXFG9yrqGvQR8hZAZRbnNtGhDF8BS245ws8RKoKcnPiPbv/swcCih7dxrMWsUKQnh++YBwvbMr+P5NnkpNEutOfAk0AM4rNC3P2yMYpzTXc0Tnw58A2gBPGmptc1eDp0JfAj8Wf0ZROpkKKHD30VlGLiNCFOOPYHTizlwochDF8ATfwM4FugAPGqptcB9HuHutXbAfVl3JBFZF7NjCVdl3UGZ7Xdf6/DD0cB5WTOtolb0oQvgib9AWG3txqo+vO6vAucChwDXxaxPpGiZdQLuItzoe245LT5ne/l/BpwODPWkNHq0lEToAnjiDxPuWDsUuNNSq8T9NsJP7u9jdkbUAkWKTTgA8TfCjSx9ca+JW1C9uwL4HuFU3bVxS6m7ol5IWxdL7WLC1e03Aef5cKoIE+hfAw7QwpoIn104OxT36rgF1S9L7duEDLiL0FOhZLa+lcxIdxVP/GfATwmd36/GfTlh6mE28CBmX4lZn0iRWHvhrDpyLfXKUvsm8AfCabNBpRS4UIKhm7mCcEf9UEvt0uwY4/FAG+CvuthSGrTyXjg7ChhJOABxkie+PHJJ663kphdWsdQqCS8tTgaGeOK/wuxk4B7gJtzPjVqgSAxmexAOCLwJ9CqneVxL7VBgNDAZOMQT/2/cijZMyW618sRXWmpnAk2AX1pqNe5+c9au7lLMJuNeVj/lRb6Q2daEUJoP9CmzwO0FjALeAg4v1cCFEh7prpJ1hX8QOBI404dzD2sWEI7H/eGY9YnkwmwTQie+XQkLyhOi1lOPLLV9CL0i3gd6e+IfRi5po5R86MLqu9ZGA72Bk304jwLPEf4B9sL99YjliRRW2KnwF8LCWR/cR0euqN5YansBzwD/IVy1837kkjZaWYQugKW2CaEz2X7AiT6csYS+DY2AfXGfEbM+kYIx+ylwKfA93H8Zu5z6YqntRhg8LSbc3vte5JLqRdmELoCl1pLwMqQrcIIPZzphUeE9wkuuT2LWJ1LvzM4m3IzwO+C75XLizFLrTBjh1hJGuG9HLqnelFXoAlhqmwFPEe5VO9GHs4Swn+/vhP6hJbfFRGSdzA4l3Ji9qjduUTXr3lCWWhfC92stcHCxtmjcUGUXurA6eJ8gXHTZ34ezOXAL2Sm2chkNSANm1pXw0nsGocVpWbyKs9T2IATucuAgT/zNyCXVu1I9HPGFPPGPgcMITT7ut+HMB35MOMV2RczaRDaaWUfC+sUC4OgyCty9gGcJvSIOLMfAhTINXQBPfD5wBPAKcG/jq5hIuHvtR5idE7U4kQ0Vjrk/Sbj94Qjcp0euqF5YansTRrgLCYH778glFUzZhi6AJ/4JYf/uS8srubvlFTwBPEK4VfikuNWJrKfQNewxYGvCCPdfkSuqF9k+3L8TDnUc6Im/E7mkgirr0AXwxBcCRwHPLWjCn7a+mIcJOxruxuzwuNWJ1JFZU0Kbxt2BE3H/R9yC6oeltj9h4Xse4eDDtLgVFV7Zhy6AJ76IcELt6dkt+EPHITwKTCF0JdsvbnUiX8KskjA1dhAwAPfHI1dULyy1IwmBO5sQuGWxD/fLNIjQBfDEFwPHAX/9v824tsv5PO3wAfAoZrtFLk9k3cyMsAe3L+Hww8jIFdULS60f8BBZYx5PGs7hpQYTugCe+FJCV7JbJ2/JRfuczYsOS4AnMesQtzqRz7DV19F8G7i2XE6bWWpnA/cSFrkP8sQ/ilxSrhpU6AJ44iuAwcCNr23DgIMH8JpDc+AZzLaLXJ5IEAL3p8D3CdfRDI1bUP2w1C4hnKB7AjiilLuFbaiyPBxRF9mldj8ErjnibZ5/7C66WjaZrz4NElUI3B8R9pT/Frig1A/0ZN9v1wKXA/cBZ3riy+JWFUeDDd1VLLXvAL85+F3GP3UHO1bAXBS8EpNZCgwjnKA8Hy+t62g+y1KrAn5PeIU5AjjfE18Zt6p4GnzoAlhqpwC3f30aM5/9E20r4CNC8M6MXZs0MGZXAVcTrqP6dhkE7qbA/cA3CCPdoZ407NBR6GYstYOAB/efzvLnbqNppfMhCl7Jk9nlhOPqtwODyiBwtyIcRtoTOM8THxG3ouKg0F1L1t3osZ7T2fy526DKmUUI3pJvnCxFzNasLxD24w7AS/vlt6XWidAfYkugvyfl01h9YzW43QtfxBOfBOw3Zjve7jWIJssqaA88h9kOsWuTMrVml8I1wJ3AwDII3P2BMYRdQb0VuJ+m0P2M7DqQXv/Ylmd7DaLp4iraObyoAxRS78JJs5uASwi7FAaWek9cS+0kQh+FecDXPPGxkUsqOppe+ByWWmPg5t0+5Mznb6NmsyXUGByF+yuxa5MyYNaIMLLtT9gedlUpbwvLtoRdBaSEUW4fT3xu3KqKk0L3C2T/kC7b4WOurb6NZe0/YWVFuGH4qdi1SQkzawb8GTgauBT36yNXtFEstebAbUA/4A7gHE98SdyqipdCtw4stT5bLWDk03fQeNc5UAGn4P6X2HVJCQrtGR8GehFuMbkpckUbxVLbBhgFdAMuA25o6FvCvoxCt44stT3aLGb0qHvY5mszsAo4B/ebY9clJcSsPTAa2A04E/d7Ile0UbI+uH8DWgCneuIPx62oNGghrY488YnzmtP9yNP5x+M7YcCIWrNrMNPXUL6c2Z6EBi8dCZdIlnrgnkK4o20pYcFMgVtHGumuJ0utSZPl/OHXjzHw7Nehpoq/NVvBqbjXxK5NipTZUYRTWR8TbnyYGLmiDWapNQKuB4YALwAneuJz4lZVWjRKW0+e+NKljRh07jGcf+lhrGyyguM/acwr2d1VIp9mdj5hDvctYN8SD9x2hIsjhxA6nx2iwF1/GuluBEtt336TeOTWUbSpNea1WMZBuP8zdl1SBMIe3OuAiwjzuKfgvjBuURvOUjuQ0B1sU2CwJ35v5JJKlkJ3I1lqWxw4jdF3/5V9Nq9h+eJGnNhmsea3GjSzVoT+CX2A3xBufCjJU2bZtsmLgZ8AbxOmEybHraq0aXphI3nic57rQM+jT+NXU9rSqPUSHnpnc/txdrxTGppwcvFVwp18Q3C/oIQDtzVhP/H1hF0K+yhwN55GuvVopyHW76dPcdeJU2j09ma8ttPHHIY3vM74DZZZf0JLxoVAP9yfj1zRBrPUegIjgfaExuM/0/7b+qHQrWdNh9r2l7/Es1c+zw7zmrHgw005outsfzl2XVJA4Ujvqqt1xgAn4T4rblEbxlKrJNxYMRyYTth/WxbXvRcLTS/UsyXX+Htpb3b+1nHcurKCFp3m8lJ1B0ti1yUFEnatPEUI3F8DB5Vw4LYnNKv5f4QtbnspcOufRroFdMQZ1mfo89zXazpNxrTnlU2XcfAeH/ri2HVJPTE7jLBg1ppwy8NdcQvacJZaH+BWoAnwXeB2TScUhkK3wL56obW9/EVe/NZ4Or27GYvGtqNf/0n+aOy6ZCOYNSXc8PA9YApwcqnuv7XUWhKueR8MjAdO9sTfiltVeVPo5sBSs6uqufG81xjSZjH2+E480HIp/XpPK81V7QbNbHfC7Q67E7aDXVqqpxEttUMJo9ttgBuAYZ740rhVlT+Fbo4GH2d79pvME4e/y5YTt+TjF7bnmO+86mNi1yV1EHpsXEjYr/pf4CzcH4ta0wbKLou8DjgPeBMYqLnb/Ch0c9avn1XsP51bB0xgQFUt/G1Xbn17MwYPr9ZfRNEy255wdfjhhCO9g3H/KG5RGyY7WXYb0AH4OeF23pIcqZcqhW4kPzzUDugzldH7vk+rl9szZ8y2nHjxGH8hdl2yFrMqwuj26uz/XAyMKMUbHiy1VoQr0M8H3gHO8kT/3mJQ6EZ0zrFW1XMG9/WdQt+qWhi9M4/Pbc43zxvri2LX1uCZ7U0Y3XYj9E74Lu7vxS1q/WXHeE8iNKjZkrCt7UpP9G8sFoVuERje23p0msvDB8zgK8sqWfp0Ry465zX/Xey6GiSzTQn7VC8EPsze/rVER7cdCRdeHgm8TrhG57W4VYlCt0hYatVtF9HhtRG0334+lc904K2pbTnm/LH+79i1NQi2ekR4A+Ho6x+AK3CfH7WuDZBdqnoxMAxYAQwFfutJad80XC4UukUi277D919m4j4zeajvFPZdUoVXd2DU1gs5s8f7viB2jWXL7ABC2O4LTCTcXVaSu0ostW8ANwK7AA8AQzzxmXGrkrUpdIvUsIPthIP+j1sOmsbmHzVnxetb86sj3+EyXKOVemPWibAF7HhgFmFEeEcpdgWz1DoTDjkcCfwbuMgTHx23KlkXhW6RyObf8MTfXev/2ZXPc2WfqQztMYsmM1qy8L1WXHHADH5binOMRSP0SxgGnAMsJjSr+Tleeke0LbW2hOY05xK6m6WEqYRlMeuSz6fQLRKWWjWAJ977s89te5E1HTCBEaf9k9N2nUvFu62ZvbKCS776H0biXpt3rSXLrANwCTAIaATcBKSluOfWUmtKONwwDGhJmIMerutzip9Ct0hkm9bxxJ/7vPfZaYi1P+MNRg6YQK8O8+Gj5swzSLZYzC24jm9+rtBY/HLgFKCW0KTmOrz0FimziyHPAq4iLPg9RZhKmBS1MKkzhW4J2vJS63rqPxlx5gT26TYbFjRmQYVz/SbL+bWapmfCboSewKXAccAiwsj2Rtzfj1nahsj63J5CmErYkXCd+5We+N9j1iXrT6FbJCy1TgCe+Jt1/T2NhtneJ0zh998aT48j3oFlFSwF7mpcy83Aqw1y3tesDXAGcDbQGfgP8CvgN7jPi1nahrDUKoATCKfiOgNvEBb8HlHrxdKk0C0SXzSnW4ff22v/6fx88Dj27vcvvPlybKUxtdK5BbgL9w/rudziEka1BxKC9kRCT9hXCSfK7ivFW3izvbanEUbquxAa0wwD/uKJ5vFLmUK3SGR3UuHJhu0PzY57HrT5Yn54whQOGfw6K/d7n0qHFRaOsd4DPFGKm/3XKXT96gH0JQTtjsB84E7g5hLub9uC8MPjIkLLxYmE3RX363BDeVDoliFLrRtw6a5zOGnQeHzwOJa1XkozYDlQDTwEPFxyvQTCXWQHEl5uHw+0I5y4eha4C/hLKW77ArDUtiY0o/ku4SaKakLYPqFphPKi0C0SlloXgPpchbbUdgR+UFnLWfvOpMlZE5j+zclUtl7KNtm7TAQeB14CXsaLbLtRCNluQK/s8XVCINUQ6n4QGI37x7FK3BjZq5OvE8K2L1BJuOr8p574KxFLkwJS6BaJjZnTrcPH3pKwN/VcYPtd5/DRJS8x/uRJtGq2gr0Je1YhnGR6mXCj7avAW3hO3ajMKoEdgF2BvQhh9DWgefYebwPPE/rZPlmqI1pYfUXO6YSw3Q34mNDj9g+elN42Nlk/Ct0iYan1APDExxbwc1QC3wC+QzguunKTZYz+3su8cuULeLMV7AvsD2yx1m+bCbyVPd4k9GKdA8wj7Az4b52OzYZ7xbYgtBfcInt0IKzIdwY6ERbAAJwwCn9h9cP9gw3+gxeBbBdCL8LOiv7ApsA4Qhew+zwp3R8isn4Uug1UNvVwLiEEvkIYbd1XtZI7F/2IjxrX0g34KiEMd87etl7Hh3LC9TUfAyuBiuxha/26FdDic37vNMLljv/61NsyWfCz1HYhfI1PA7Yn7Bf+M/B7T/zVmLVJHArdImGp7QngiU/I+fNWAYcSguEEoBnwLuHyxQeBCZ64Z9uy2hB2CbQBNs8ea//aCCe+PHu76tefAB8RRshrv51VytMEnyfro3E84TBDd8LX4UnCYt/f1EC8YVPoFolCzumuRw0tCAs6ZwAHE0J0OjCKsMDzgie+PFZ9xSpbENuLELTHE24KhnCl+Z3APZ747CjFSdFR6BaJWCPdz5Mtvh0D9CFcyNiUMIXwKOG8/zOe+Ix4FcZlqW0O9AYOAY4FtiWMaF8k/IAatXbHOJFVFLrypSy1TYDDCKO4o4G22VP/Bp7JHs+Wc4er7NryXoRXAAcTRrZGmKN9ivBqYLQnPjdakVISFLpFIo/dC/UhW4Xvwprw6c2aRbK3gbGE7WZjgfGluCqfdfLqQjjxturRhbCPdhlhS92qHzZj1btW1odCt0gUw5zuhsgW4vYGDgL2IQRU++zplcBkQpOWqYQtZ1OBtz2J34oy20LXgdDbYBfCDo3dgT0J0ykQplTGZo9qYEwp/iCR4qHQLRKFOJEWS3akde1RYmfCnOcqtYQdEu8A7xOuyln77YeEPgqLNqS5S7aw1ZwwAt+ScFx4m+yx6tcdCFvhGq/1W+cQtq29xpqgfVfHcKU+KXQlF9mc6M6sGVXuQjiB1g7YirCfd10WAgsI284WEgL7fz48sAkhZFc9Pu/jzSUE+3TCqHvV401PSq/1o5QehW6R2NguY6Usm6LYkjUj0a34dIC2zN5uSgjYdVlMCOYFrAnpBawJ2VnAB8UwrSENW1XsAmS1a7O3vWMWEUPWsnBW9hApawrd4nFO7AJEpPA0vSAikqPPW2yQnFlqB666EVhEypemF4pHmr3tHbMIESkshW7xGBS7ABEpPM3piojkSHO6RcJSO9RSOzR2HSJSWJpeKB5Ds7dPR61CRApKoVs8zohdgIgUnuZ0RURypDndImGpHWmpHRm7DhEpLE0vFI/Ls7ePR61CRApKoVs8To5dgIgUnuZ0RURypDndImGpHWupHRu7DhEpLE0vFI+Ls7cPR61CRApKoVs8vhm7ABEpPM3piojkSHO6RcJS62up9Y1dh4gUlqYXiseF2dsHolYhIgWl0C0efWIXICKFV5A5XTP7BbBnvX9gEZH8THD379X3B9WcbrHozhZ0Z4vYZYhIYWn3QpGw1KoBPPHecSsRkULSnG7xOCp2ASJSeBrpiojkSHO6RcJSO91SOz12HSJSWJpeKB6Ds7d3Ra1CRApKoVs8DotdgIgUnuZ0RURypDndImGpDbTUBsauQ0QKS6FbPAZmDxEpY5peEBHJkUa6IiI5UuiKiORIoSsikiOFbmRmdp2ZPbjWf19vZn83s0Yx6xKRwtBCWmRm1gZ4B+gN7Ad8BzjA3efHrEtECkOhWwTMbDjQF2hFCNwZcSsSkULR9EJxGA/sDlyhwBUpbxrpRmZmuwNPAE8C7d390MgliUgBaaQbkZltAzwMnAucD+xuZr1j1iQihaXQjcTMWgKPAje6+0Puvhi4HvhR3MpEpJA0vSAikiONdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHCl0RkRwpdEVEcqTQFRHJkUJXRCRHVbELkPU3bty4xlVVVTcDBwCVseuRKGrNbPaKFSvSbt26PRG7GKk7c/fYNch6Gj9+/JDWrVtfsP3228+vqKjQX2ADVFtbazU1NU2nTZvWeOnSpd9V8JYOTS+UoMrKyrPatWu3SIHbcFVUVPgmm2xS06FDh2VVVVVJ7Hqk7hS6JcjdWzVu3Hh57DokvmbNmi1x961i1yF1p9AtTWZmsWuQIpC92tH3cQnRX5aISI4UuiIiOVLoSkHMmjWrqmfPnl9t2bLlnv369ds+dj0ixUL7dKUghg0btlXHjh2Xjhkz5t+xaxEpJhrpSkE8//zzLfv37/9x7DpiWblyJVdcccVWW2+99e6bbbZZ15/85CdbVFVVdZs1a5YGOg2c/gFIvVqyZIltscUWXRcuXFjZv3//ndq3b7/0rbfe+lfsuvJ2ySWXtKuurm753HPPvdmmTZuVBx988Fdbt269sl27diti1yZxKXRL3KBRg7ad9NGk5oX8HF227LL41j63zqjL+zZt2tSrq6unHn744Z3mzZv3RiHr+pRBg7ZlUmG/DnTpsphbv/zrMGvWrKoRI0Z8Zdy4cZN33nnnZQCHH374/JdeemnT7Nc73nDDDTP32GOPpQWtV4qSphek3o0dO7b5Lrvssjh2HbGMHj26RceOHWs6deq0bNX/mzdvXlXnzp1rAN57770mnTt3VuA2UBrplri6jkDzNGHChOZdunSpyfWT1mEEmpe5c+dWtWnTZvU0wvLly3nqqada/eAHP/hg8eLFVlVV5VVVn/+tt2TJEttnn306jRkz5s1Ro0a1fOSRR1qNHDlyei7FS8FppCv1btKkSc26du3aYEe6nTt3XvL6669vOnXq1MZz5sypPOOMM7afOXNmkz333LNmwoQJTXfcccclX/T7mzZt6gMHDpx79tlnb/enP/2p7e23367ALSMKXal3U6dObd69e/d8R7pF5Pjjj19w9NFHf9y9e/fdevTosWuXLl1qKioq6Nat25IJEyY023XXXb/0a3PggQcuvP/++9uOGDFieqNGjfIoW3Ki0JV6NX369KpPPvmksmvXrl84mit3I0eOfG/hwoXjp02bNqlz585L2rdvv7RFixa1kydPbtalS5f/+dq88847q5N19uzZlRdccMF2l1122ft//OMfN8+3cik0ha7Uq+22227FsmXLXm/SpInaTmYmT57ctFOnTjUAU6ZMaXbddddt3bNnz5179uy58+zZsyuXL19Ov379OgLU1NTYySefvMMvfvGLGWmazn7ooYc2mz9/vr5Py4gW0kQKbMqUKU1X7Vx45pln3v7s888++2zzU089dR5As2bNvLq6evX7TJw4cWp+lUoedHNECXrjjTemde3adW7sOqQ4vPHGG227du3aIXYdUjd62SIikiOFrohIjhS6IiI5UuiWJtdcvEC4FRiojV2H1J1CtwSZ2fxly5Zpx7xQU1PT1Mxmx65D6k6hW4JWrlx526xZszbJRjnSANXW1tqiRYuaTZs2rfGKFSvS2PVI3WnLWAkaN25c46qqqpuBA4DK2PVIFLVmNnvFihVpt27dnohdjNSdQldEJEeaXhARyZFCV0QkRwpdEZEcKXRFRHKk0BURyZFCV0QkRwpdEZEcKXRFRHKk0BURyZFCV0QkRwpdEZEc/X+XCbxzzqhJhQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import sympy as sy\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "fsize = 12\n",
    "\n",
    "x = sy.symbols('x')\n",
    "f  = sy.Lambda(x, x*x/2 + 1/2)\n",
    "f1 = sy.Lambda(x, f(x).diff(x))\n",
    "\n",
    "L  = 3/4\n",
    "x0 = -1\n",
    "\n",
    "ql = sy.Lambda(x, f(x0) + f1(x0)*(x-x0) + L*(x-x0)**2)\n",
    "\n",
    "ql = sy.lambdify(x, ql(x))\n",
    "f  = sy.lambdify(x, f(x))\n",
    "\n",
    "x = np.linspace(-2,2)\n",
    "xmin = x.min()\n",
    "xmax = x.max()\n",
    "plt.plot(x, f(x) , 'g', label = '$f$')\n",
    "plt.plot(x, ql(x), 'r', label = '$q_{L,x}$')\n",
    "plt.axis('off')\n",
    "#\n",
    "tic = 0.2\n",
    "plt.plot([xmin, xmax], [0,0], 'k')\n",
    "#\n",
    "plt.text(x0, -tic, '$x$', ha = 'center', va = 'top', fontsize=fsize)\n",
    "plt.plot([x0,x0], [-tic,f(x0)], 'g:')\n",
    "#\n",
    "plt.legend(loc='lower center', ncol=3, fontsize=fsize)\n",
    "plt.ylim(xmin, f(xmin));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$L$-Glattheit ist eng verknüpft mit der  Lipschitz-Stetigkeit\n",
    "des Gradienten $f'$.\n",
    "\n",
    "\n",
    "**Lemma:**\n",
    "$f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$ \n",
    "sei differenzierbar (nicht notwendig konvex).\n",
    "Ist $f'$  Lipschitz-stetig, d.h.\n",
    "\\begin{equation*} \n",
    "\\|f'(y) - f'(x)\\| \\leq L \\|y-x\\| \\quad \\forall x,y,\n",
    "\\end{equation*}\n",
    "dann gilt\n",
    "\\begin{equation*} \n",
    "\\big(f'(y)-f'(x)\\big)(y-x) \\leq L \\|y-x\\|^2.\n",
    "\\end{equation*}\n",
    "  \n",
    "**Beweis:**\n",
    "Da $f'(x), f'(y)$ lineare stetige Operatoren sind gilt\n",
    "\\begin{align*} \n",
    "\\big(f'(y)-f'(x)\\big)(y-x)\n",
    "&\\leq \\big|\\big(f'(y)-f'(x)\\big)(y-x) \\big|\\\\\n",
    "&\\leq \\|f'(y)-f'(x)\\| \\ \\|y-x\\|\\\\\n",
    "&\\leq L \\|y-x\\|^2\n",
    "\\end{align*}\n",
    "\n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lemma:**\n",
    "$f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$ \n",
    "sei differenzierbar (nicht notwendig konvex),\n",
    "$\\mathrm{dom}(f)$ konvex.\n",
    "Dann ist\n",
    "\\begin{equation*} \n",
    "\\big(f'(y)-f'(x)\\big)(y-x) \\leq L \\|y-x\\|^2\n",
    "\\quad \\forall x,y\n",
    "\\end{equation*}\n",
    "äquivalent zu\n",
    "\\begin{equation*} \n",
    "f(y) \\leq f(x) + f'(x)(y-x) + \\frac{1}{2} L \\|y-x\\|^2\n",
    "\\quad \\forall x,y.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "\"$\\Rightarrow$\"\n",
    "\n",
    "- mit\n",
    "    \\begin{equation*} \n",
    "    g(t) = f\\big(x+t(y-x)\\big)\n",
    "    \\end{equation*}\n",
    "  folgt\n",
    "    \\begin{equation*} \n",
    "    g'(t) = f'\\big(x+t(y-x)\\big)(y-x)\n",
    "    \\end{equation*}    \n",
    "  und für $t>0$\n",
    "    \\begin{align*}\n",
    "    g'(t) - g'(0)\n",
    "    & = \\big( f'\\big(x+t(y-x)\\big) - f'(x) \\big) (y-x) \\\\\n",
    "    & = \\frac{1}{t} \\big( f'\\big(x+t(y-x)\\big) - f'(x) \\big) t(y-x) \\\\\n",
    "    &\\leq \\frac{1}{t}  L \\|t(y-x)\\|^2 \\\\\n",
    "    & = tL \\|y-x\\|^2 \n",
    "    \\end{align*}\n",
    "\n",
    "- damit erhalten wir\n",
    "    \\begin{align*}\n",
    "    f(y)\n",
    "    &= g(1) \\\\\n",
    "    &= g(0) + \\int_0^1g'(\\tau)\\:d\\tau\\\\\n",
    "    &\\leq f(x)  + \\int_0^1 g'(0) + \\tau L \\|y-x\\|^2  \\:d\\tau\\\\\n",
    "    & = f(x) +  f'(x)(y-x) + \\frac{1}{2} L \\|y-x\\|^2\n",
    "    \\end{align*}\n",
    "\n",
    "\"$\\Leftarrow$\"\n",
    "\n",
    "- nach Voraussetzung ist\n",
    "    \\begin{equation*} \n",
    "    f(y) \\leq f(x) + f'(x)(y-x) + \\frac{1}{2} L \\|y-x\\|^2\n",
    "    \\end{equation*}\n",
    "  bzw.\n",
    "    \\begin{equation*} \n",
    "    f(x) \\leq f(y) + f'(y)(x-y) + \\frac{1}{2} L \\|x-y\\|^2\n",
    "    \\end{equation*}\n",
    "\n",
    "- Addition der beiden Ungleichungen liefert\n",
    "    \\begin{equation*} \n",
    "    f(y) + f(x) \\leq f(x) + f(y) + \\big(f'(x)-f'(y)\\big) (y-x) +  L \\|y-x\\|^2,\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    \\big(f'(y)-f'(x)\\big)(y-x) \\leq L \\|y-x\\|^2\n",
    "    \\end{equation*}\n",
    "\n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "Ist $f'$ Lipschitz-stetig, dann ist $f$  L-glatt.\n",
    "  \n",
    "Ist $f$ konvex, $\\mathrm{dom}(f)=\\mathbb{R}^d$ und existiert \n",
    "ein $x_\\ast \\in \\mathrm{dom}(f)$ mit $f(x_\\ast)=\\inf_{x}f(x)$,\n",
    "dann gilt auch die Umkehrung."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lemma:**\n",
    "$f:\\mathbb{R}^d  \\to \\mathbb{R}$ sei differenzierbar (nicht notwendig konvex) und\n",
    "es existiere $x_\\ast$ mit \n",
    "$f(x_\\ast)=\\inf_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "Ist $f$ L-glatt mit Konstante $L$, dann gilt\n",
    "\\begin{equation*} \n",
    "\\frac{1}{2L}\\|f'(x)\\|_2^2 \\leq f(x) - f(x_\\ast) \\leq \\frac{L}{2}\\|x - x_\\ast\\|_2^2\n",
    "\\end{equation*}\n",
    "und $f'$ ist Lipschitz-stetig mit Konstante $L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- Abschätzung nach oben:\n",
    "  \n",
    "  - da $x_\\ast$ globaler Minimierer ist muss $f'(x_\\ast)=0$ sein und somit\n",
    "      \\begin{align*} \n",
    "      f(x) \n",
    "      &\\leq f(x_\\ast) + f'(x_\\ast)(x-x_\\ast) + \\frac{1}{2} L \\|x-x_\\ast\\|_2^2\\\\\n",
    "      &= f(x_\\ast) + \\frac{1}{2} L \\|x-x_\\ast\\|_2^2\n",
    "      \\end{align*}\n",
    "    \n",
    "- Abschätzung nach unten: \n",
    "  \n",
    "  - wir benutzen\n",
    "      \\begin{align*} \n",
    "      f(x_\\ast) &= \\inf_y f(y) \\leq \\inf_y u(y),\n",
    "      \\\\\n",
    "      u(y) &= f(x) + f'(x)(y-x) + \\frac{1}{2} L \\|y-x\\|_2^2\n",
    "      \\end{align*}\n",
    "    und minimieren die quadratische Funktion $u$\n",
    "  \n",
    "  - für die Ableitungen erhalten wir\n",
    "      \\begin{equation*} \n",
    "      u'(y) = f'(x) + L(y-x),\n",
    "      \\quad\n",
    "      u''(y) = L I\n",
    "      \\end{equation*}\n",
    "\n",
    "  - $u$ ist (strikt) konvex mit globalem Minimierer $y_\\ast$ mit\n",
    "      \\begin{equation*} \n",
    "      0 = u'(y_\\ast) \\quad \\Leftrightarrow \\quad y_\\ast - x = -\\frac{1}{L}f'(x)\n",
    "      \\end{equation*}\n",
    "    und Minimum\n",
    "      \\begin{align*}\n",
    "      u_\\ast = u(y_\\ast) \n",
    "      &=  f(x) + f'(x)(y_\\ast-x) + \\frac{1}{2} L \\|y_\\ast-x\\|_2^2\\\\\n",
    "      &=  f(x) - \\frac{1}{L}\\|f'(x)\\|_2^2 + \\frac{1}{2} L \\|\\frac{1}{L}f'(x)\\|_2^2\\\\\n",
    "      &=  f(x) - \\frac{1}{2L} \\|f'(x)\\|_2^2\n",
    "      \\end{align*}\n",
    "      \n",
    "  - somit folgt\n",
    "      \\begin{equation*} \n",
    "      f(x_\\ast) \\leq f(x) - \\frac{1}{2L} \\|f'(x)\\|_2^2\n",
    "      \\end{equation*}\n",
    "\n",
    "- Lipschitz-Stetigkeit von $f'$:\n",
    " \n",
    "  - wir betrachten die Funktion\n",
    "      \\begin{equation*} \n",
    "      g(y) = f(y) - f'(x)y\n",
    "      \\end{equation*}\n",
    "  \n",
    "  - mit $f$ ist auch $g$ konvex und differenzierbar mit Ableitung\n",
    "      \\begin{equation*} \n",
    "      g'(y) = f'(y) - f'(x)\n",
    "      \\end{equation*}\n",
    "  \n",
    "  - damit ist $g'(x)=0$, also ist $y_\\ast = x$ globales Minimum von $g$\n",
    "    \n",
    "  - außerdem folgt aus der $L$-Glattheit von $f$ für beliebiges $z$\n",
    "      \\begin{align*}\n",
    "      g(y) &+ g'(y)(z-y) + \\frac{1}{2} L \\|z-y\\|_2^2 = \\\\\n",
    "      &= f(y) - f'(x)y + \\big( f'(y) - f'(x) \\big)(z-y) + \\frac{1}{2} L \\|z-y\\|_2^2 \\\\\n",
    "      & = f(y) + f'(y)(z-y) + \\frac{1}{2} L \\|z-y\\|_2^2 \n",
    "          - f'(x)y  - f'(x) (z-y) \\\\\n",
    "      & \\geq f(z) - f'(x) z \\\\\n",
    "      & = g(z)\n",
    "      \\end{align*}    \n",
    "      so dass auch $g$ $L$-glatt ist\n",
    "  \n",
    "  - somit können wir die Abschätzung nach unten aus dem vorherigen Teil auf $g$ anwenden\n",
    "      und erhalten wegen $y_\\ast=x$\n",
    "      \\begin{align*}\n",
    "      \\frac{1}{2L} \\|f'(y) - f'(x)\\|_2^2\n",
    "      &=  \\frac{1}{2L}\\|g'(y)\\|_2^2 \\\\\n",
    "      &\\leq g(y) - g(y_\\ast)\\\\\n",
    "      & =   g(y) - g(x)\\\\\n",
    "      &= f(y) - f'(x)y - \\big(f(x) - f'(x)x\\big)\\\\\n",
    "      &= f(y) - f(x) - f'(x)(y-x),\n",
    "      \\end{align*}\n",
    "      also\n",
    "      \\begin{equation*} \n",
    "      f(y) - f(x) - f'(x)(y-x) \\geq \\frac{1}{2L} \\|f'(y) - f'(x)\\|_2^2\n",
    "      \\end{equation*}\n",
    "      bzw. durch vertauschen von $x$ und $y$\n",
    "      \\begin{equation*} \n",
    "      f(x) - f(y) - f'(y)(x-y) \\geq \\frac{1}{2L} \\|f'(y) - f'(x)\\|_2^2\n",
    "      \\end{equation*}\n",
    "\n",
    "  - durch Addition der beiden Ungleichungen erhalten wir\n",
    "      \\begin{equation*} \n",
    "      (f'(y) - f'(x))(y-x) \\geq \\frac{1}{L} \\|f'(y) - f'(x)\\|_2^2\n",
    "      \\end{equation*}\n",
    "    und mit Cauchy-Schwartz\n",
    "      \\begin{align*} \n",
    "      \\|f'(y) - f'(x)\\|_2^2 \n",
    "      &\\leq L \\big(f'(y) - f'(x)\\big)(x-y)\\\\\n",
    "      &\\leq L \\|f'(y) - f'(x)\\|_2 \\|x-y\\|_2,\n",
    "      \\end{align*}\n",
    "    so dass $f'$ Lipschitz-stetig mit Konstante $L$ ist\n",
    "  \n",
    "  $\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:** \n",
    "Sei $f:\\mathbb{R}^d\\to \\mathbb{R}$ konvex, $C^1$ und es existiere $x_\\ast \\in \\mathrm{dom}(f)$ mit \n",
    "$f(x_\\ast)=\\inf_{x}f(x)$. \n",
    "Dann ist äquivalent:\n",
    "\n",
    "- $f$ ist $L$-glatt mit Parameter $L$\n",
    "  \n",
    "- $\\|f'(y)-f'(x)\\|_2 \\leq L \\|y-x\\|_2 \\quad \\forall x,y\\in \\mathbb{R}^d$\n",
    "\n",
    "\n",
    "$L$-Glattheit ist also unter diesen Voraussetzungen äquivalent dazu, \n",
    "dass $f'$ Lipschitz-stetig mit Konstante $L$ ist."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Folgende Operation erhalten die $L$-Glattheit:\n",
    "\n",
    "- für  $i=1,\\ldots,m$ seien $f_i:\\mathbb{R}^d \\supset \\mathrm{dom}(f_i) \\to \\mathbb{R}$, $L$-glatt mit Parameter $L_i$ und $\\lambda_i \\geq 0$. Dann ist\n",
    "    \\begin{equation*} \n",
    "    f = \\sum_{i=1}^m \\lambda_i f_i\n",
    "    \\end{equation*}\n",
    "  $L$-glatt mit Konstante\n",
    "    \\begin{equation*} \n",
    "    L = \\sum_{i=1}^m \\lambda_i L_i\n",
    "    \\end{equation*}\n",
    "  über \n",
    "    \\begin{equation*} \n",
    "    \\mathrm{dom}(f) = \\bigcap_{i=1}^m \\mathrm{dom}(f_i)\n",
    "    \\end{equation*}\n",
    "    \n",
    "- ist $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$ $L$-glatt mit Konstante $L$, $g:\\mathbb{R}^m\\to \\mathbb{R}^d$ affin linear, d.h.\n",
    "  \\begin{equation*} \n",
    "  g(z) = Az + b,\n",
    "  \\end{equation*}\n",
    "  dann ist $f\\circ g$ auch $L$-glatt mit  \n",
    "  \\begin{equation*} \n",
    "  \\tilde{L} = L \\, \\|A\\|_2^2,\n",
    "  \\quad\n",
    "  \\mathrm{dom}(f\\circ g)\n",
    "  =\n",
    "  \\big\\{z \\ | z\\in\\mathbb{R}^m,\\ g(z)\\in \\mathrm{dom}(f)\\big\\}\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für $f$ konvex und $L$-glatt werden wir nun günstigere Konvergenzresultate für Gradient-Descent erhalten.\n",
    "Wir benutzen $L$-Glattheit mit $y=x_{t+1}$, $x=x_t$\n",
    "  \\begin{equation*} \n",
    "  f_{t+1} \\leq f_{t}+f_{t}^{\\prime}(x_{t+1}-x_{t})+\\frac{L}{2}\\|x_{t+1}- x_{t}\\|_{2}^{2}.\n",
    "  \\end{equation*}\n",
    "Mit $x_{t+1}-x_{t}=-\\gamma  f_t$ folgt\n",
    "  \\begin{equation*} \n",
    "  f_{t+1} \n",
    "  \\leq f_{t}-\\gamma\\|f_{t}^{\\prime}\\|_{2}^{2}+\\frac{L}{2} \\gamma^{2}\\|f_{t}^{\\prime} \\|_{2}^{2}\n",
    "  =f_{t}-\\underbrace{\\gamma\\big(1-\\frac{L}{2}\\gamma\\big)}_{=: \\beta}\\|f_{t}^{\\prime}\\|_2^{2}.\n",
    "  \\end{equation*}\n",
    "Für $\\gamma > 0$ ist $\\beta > 0$ genau dann, wenn \n",
    "  \\begin{equation*} \n",
    "  1-\\frac{L}{2}\\gamma > 0,\n",
    "  \\end{equation*}\n",
    "also genau dann, wenn\n",
    "  \\begin{equation*} \n",
    "  0 < \\gamma < \\frac{2}{L}.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Damit folgt\n",
    "\n",
    "\n",
    "**Descent-Lemma:** Ist $f:\\mathbb{R}^d\\to \\mathbb{R}$ $L$-glatt, dann gilt \n",
    "  \\begin{equation*} \n",
    "  f_{t+1} \n",
    "  \\leq f_{t}-\\beta\\|f_{t}^{\\prime}\\|_2^{2},\n",
    "  \\quad\n",
    "  \\beta = \\gamma\\big(1-\\frac{\\gamma L}{2}\\big)\n",
    "  \\end{equation*}\n",
    "und $\\beta > 0$ falls $0 < \\gamma < \\frac{2}{L}$.\n",
    "\n",
    "\n",
    "**Bemerkung:** Für $f$ $L$-glatt und  $0 < \\gamma < \\frac{2}{L}$ fällt $f_t$\n",
    "  also *monoton*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Damit verschärfen wir jetzt unser Konvergenzresultat aus dem vorherigen Abschnitt.\n",
    "Nach den Vorüberlegungen gilt\n",
    "  \\begin{equation*} \n",
    "  \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  \\leq  \\frac{\\gamma}{2} \\sum_{t=0}^{T-1} \\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "  + \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2}\n",
    "  - \\frac{1}{2 \\gamma} \\|x_{T}-x_{*}\\|_{2}^{2}.\n",
    "  \\end{equation*}\n",
    "  \n",
    "Aus dem Descent-Lemma folgt\n",
    "  \\begin{equation*} \n",
    "  \\|f_{t}^{\\prime}\\|_2^{2} \\leq \\frac{1}{\\beta}(f_{t}-f_{t+1})\n",
    "  \\end{equation*}\n",
    "und somit\n",
    "  \\begin{align*}\n",
    "  \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  &\\leq  \\frac{\\gamma}{2\\beta} \\sum_{t=0}^{T-1}(f_{t}-f_{t+1})\n",
    "  + \\frac{1}{2 \\gamma} \\big(\\|x_{0}-x_{*}\\|_{2}^{2} - \\|x_{T}-x_{*}\\|_{2}^{2}\\big)\n",
    "  \\\\\n",
    "  &=  \\frac{\\gamma}{2\\beta} (f_{0}-f_{T}) \n",
    "  + \\frac{1}{2 \\gamma} \\big(\\|x_{0}-x_{*}\\|_{2}^{2} - \\|x_{T}-x_{*}\\|_{2}^{2}\\big).\n",
    "  \\end{align*}\n",
    "Für $\\gamma < \\frac{2}{L}$ ist $f_{t+1}\\leq f_t$, so dass\n",
    "  \\begin{equation*} \n",
    "  f_{T-1} \\leq \\frac{1}{T}\\sum_{t=0}^{T-1}f_t \n",
    "  \\end{equation*}\n",
    "und damit\n",
    "  \\begin{align*} \n",
    "  f_{T-1}-f_\\ast \n",
    "  &\\leq \\frac{1}{T}\\sum_{t=0}^{T-1}(f_t -f_\\ast)\\\\\n",
    "  &\\leq \\frac{1}{T}\n",
    "  \\Big(\n",
    "  \\frac{\\gamma}{2\\beta} (f_{0}-f_{T}) \n",
    "  + \\frac{1}{2 \\gamma} \\big(\\|x_{0}-x_{*}\\|_{2}^{2} - \\|x_{T}-x_{*}\\|_{2}^{2}\\big) \n",
    "  \\Big).\n",
    "  \\end{align*}\n",
    "Mit $\\|x_{T}-x_{*}\\|_{2}\\geq 0$ erhalten wir schließlich\n",
    "  \\begin{equation*} \n",
    "  f_{T-1}-f_\\ast \n",
    "    \\leq \\frac{1}{T}\n",
    "  \\Big(\n",
    "  \\frac{\\gamma}{2\\beta} (f_{0}-f_{\\ast}) \n",
    "  + \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2} \n",
    "  \\Big).\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Satz:** $f:\\mathbb{R}^d\\to \\mathbb{R}$, konvex, $L$-glatt mit Konstante $L$\n",
    "und es existiere $x_\\ast = \\mathrm{argmin}_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "Für  $0 < \\gamma < \\frac{2}{L}$ ist\n",
    "\\begin{align*} \n",
    "f_{T}-f_\\ast \n",
    "&\\leq \\frac{1}{T+1}\n",
    "\\Big(\n",
    "\\frac{\\gamma}{2\\beta} (f_{0}-f_{\\ast}) \n",
    "+ \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2} \n",
    "\\Big)\n",
    "\\\\\n",
    "&= \\mathcal{O}\\big( \\frac{1}{T} \\big)\n",
    "\\quad \\text{für}\\quad  T\\to\\infty.\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- $f_{T} - f_\\ast \\leq \\varepsilon$ gilt damit sicher, falls\n",
    "    \\begin{equation*} \n",
    "    \\frac{1}{T+1}\n",
    "    \\Big(\n",
    "    \\frac{\\gamma}{2\\beta} (f_{0}-f_{\\ast}) \n",
    "    + \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2} \n",
    "    \\Big) \\leq \\varepsilon\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    T \\geq \\frac{1}{\\varepsilon}\n",
    "    \\Big(\n",
    "    \\frac{\\gamma}{2\\beta} (f_{0}-f_{\\ast}) \n",
    "    + \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2} \n",
    "    \\Big) - 1\n",
    "    = \\mathcal{O}\\big(\\frac{1}{\\varepsilon}\\big)\n",
    "    \\end{equation*}\n",
    "  \n",
    "- da $\\gamma < \\frac{2}{L}$ sein muss kann wegen des Terms\n",
    "    \\begin{equation*} \n",
    "    \\frac{1}{2 \\gamma} \\|x_{0}-x_{*}\\|_{2}^{2}\n",
    "    \\end{equation*}\n",
    "  die Asymptotik der oberen Schranke nicht mehr durch\n",
    "  eine $T$-abhängige Wahl von $\\gamma$ verbessert werden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\mu$-Konvexität"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bis jetzt haben wir nur Abschätzungen für $f_t - f_\\ast$ bewiesen.\n",
    "Nun werden wir $\\|x_t - x_\\ast\\|_2$ betrachten.\n",
    "Dazu benötigen wir nochmals stärkere Voraussetzungen, nämlich $\\mu$-Konvexität.\n",
    "Damit werden wir zusätzlich auch eine besseres asymptotisches Verhalten\n",
    "nachweisen können."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f$ ist $\\mu$-konvex falls $f(x)-\\frac{\\mu}{2}\\|x\\|_2^2$ konvex ist.\n",
    "Ist $f$ zusätzlich differenzierbar, so erhalten wir das folgende Ergebnis.\n",
    "\n",
    "\n",
    "**Lemma:** Ist $f$ $\\mu$-konvex und differenzierbar, dann gilt\n",
    "  \\begin{equation*} \n",
    "  f(y) \\geq f(x) + f'(x)(y-x) + \\frac{\\mu}{2}\\|y-x\\|_2^2\n",
    "  \\quad\n",
    "  \\forall x,y\n",
    "  \\end{equation*}\n",
    "und\n",
    "  \\begin{equation*} \n",
    "  \\big(f'(y) - f'(x)\\big)(y-x) \\geq \\mu \\|y-x\\|_2^2\n",
    "  \\quad\n",
    "  \\forall x,y.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- $f$ ist $\\mu$-konvex falls $g(x) = f(x)-\\frac{\\mu}{2}\\|x\\|_2^2$ konvex ist\n",
    "  \n",
    "- mit $f$ ist auch $g$ differenzierbar mit\n",
    "    \\begin{equation*} \n",
    "    g'(x) = f'(x) - \\mu x\n",
    "    \\end{equation*}\n",
    "  \n",
    "- wegen\n",
    "    \\begin{equation*} \n",
    "    g(y) \\geq g(x)+g'(x)(y-x)\n",
    "    \\end{equation*}\n",
    "  ist\n",
    "    \\begin{equation*} \n",
    "    f(y)-\\frac{\\mu}{2}\\|y\\|_{2}^{2} \n",
    "    \\geq \n",
    "    f(x)-\\frac{\\mu}{2}\\|x\\|_2^{2} + \\big(f'(x) - \\mu x\\big)^T(y-x)\n",
    "    \\end{equation*}\n",
    "  bzw.\n",
    "    \\begin{equation*} \n",
    "    f(y) \n",
    "    \\geq f(x)+f'(x)(y-x)\n",
    "    +\\frac{\\mu}{2} \\big(\\underbrace{y^{T} y-x^{T} x-2 x^{T}(y-x)}_{h}\\big)\n",
    "    \\end{equation*}\n",
    "  mit\n",
    "    \\begin{align*} \n",
    "    h \n",
    "    &= y^{T} y - x^{T} x - 2 x^{T}y + 2 x^{T}x\n",
    "    \\\\\n",
    "    &= y^{T} y - 2 x^{T}y + x^{T} x\n",
    "    \\\\\n",
    "    &= \\|y-x\\|_2^2,\n",
    "    \\end{align*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + f'(x)(y-x) + \\frac{\\mu}{2}\\|y-x\\|_2^2\n",
    "    \\end{equation*}\n",
    "    \n",
    "  da $g$ konvex und differenzierbar ist, ist $g'$ monoton,\n",
    "  also\n",
    "    \\begin{align*}\n",
    "    0 \n",
    "    & \\leq \\big(g'(y) - g'(x)\\big)(y-x) \\\\\n",
    "    &=  \\big(f'(y) - \\mu y - f'(x) + \\mu x\\big)(y-x)\\\\\n",
    "    &= \\big(f'(y) - f'(x)\\big)(y-x) - \\mu \\|y-x\\|_2^2\n",
    "    \\end{align*}\n",
    "  und somit\n",
    "    \\begin{equation*} \n",
    "    \\big(f'(y) - f'(x)\\big)(y-x) \\geq \\mu \\|y-x\\|_2^2\n",
    "    \\quad\n",
    "    \\forall x,y\n",
    "    \\end{equation*}\n",
    "    \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- ist $f$ $\\mu$-konvex und $L$-glatt (und damit differenzierbar), so gilt\n",
    "    \\begin{align*}\n",
    "    f(y) &\\leq f(x) + f'(x)(y-x) + \\frac{L}{2}\\|y-x\\|_2^2 =: q_{L,x}(y) \\\\\n",
    "    f(y) &\\geq f(x) + f'(x)(y-x) + \\frac{\\mu}{2}\\|y-x\\|_2^2 =: q_{\\mu,x}(y)\n",
    "    \\end{align*}\n",
    "  \n",
    "- $f$ kann also zwischen den beiden quadratischen Funktionen $q_{\\mu,x}$, $q_{L,x}$\n",
    "  \"eingesperrt\" werden\n",
    "  \n",
    "- $q_{\\mu,x}$, $q_{L,x}$ berühren $f$ im Punkt $x$\n",
    "\n",
    "- es muss immer $\\mu \\leq L$ gelten\n",
    "  \n",
    "- ist $\\mu>0$ so ist $f$ strikt konvex und $x_\\ast$ ist damit eindeutig\n",
    "  \n",
    "- ist $\\mu = L$ dann ist $f = q_{\\mu,x} = q_{L,x}$, d.h. $f$ ist ein quadratisches\n",
    "  Polynom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-09-24T09:33:31.445406Z",
     "iopub.status.busy": "2021-09-24T09:33:31.445089Z",
     "iopub.status.idle": "2021-09-24T09:33:31.557883Z",
     "shell.execute_reply": "2021-09-24T09:33:31.557573Z"
    },
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAbUAAADnCAYAAACZm8iVAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAA37UlEQVR4nO3dd3gU5fbA8e9JAoQaukgXFQRDESmKBbBybSgieBWviGLBrqCiVzeLYi9c+w9F1ItdxN4LIGLhIoggoCIIiihNEAglyfn98b7BNQYIIdnZnT2f55kneXdnd89sNnN23jnzvqKqGGOMMWGQFnQAxhhjTFmxpGaMMSY0LKkZY4wJDUtqxhhjQsOSmjHGmNCwpFYGJCoXSFRUojLgr3fIXohsQeThgEIzJv5EshBZgcj7iEjQ4ewMiUpricpmicp/g47FlI4ltbIxGvgMGCVRqbf1VtXvgYeAwYi0CSg2Y+LtKqAOcDVJdM2QREVw/6/rgCsDDseUkiW1MqARzQfOAWoA/yly9wjgD+D2eMdlTNyJNAIuB55BdXrQ4eyks4HuwNUa0d+CDsaUjiW1MqIRnQPcBPxTonLcn3foCmAkcCwihwcUnjHxkgNkANcFHMdOkag0Au4CJgJjgo3G7ApJot6BhCdRqQhMB2oBbTSia90dkgnMA1YD+6NaEFiQxpQX18X+NXAfqpcFHE2J+W7HV4HDgbYa0QUBh2R2gR2plSGN6GZcF8buwG1/3qEbgeFAB2BAcY81JgRuwZ2PuinoQHbSP4HjgOssoSU/O1IrBxKVu4ArgO4a0cnuRknDFZPsDrRCdUNwERpTxkQOBj4GrkP15qDDKSmJSn3gG+A74GB/ftwkMTtSKwMiVBFhUMxNNwALgUclKpUBfJfjUKAxcFm8YzSm3Liy/TuAX4BRwQaz0+4FqgNnp3JCE+E0EeoEHUdZsKRWNs4GxohwNoBGdD0wGNgbl+Ac1cnAy8BwRHaLf5jGlIvTgQNwR2lJ0wMhUTkR6A/cqBH9JuBwAiPCMcBTwNVBx1IWrPuxDIiQDrwFHAp0U+VLAInKGOBMoKtGfHmzSEtgDvAIqkOCidiYMiJSDZgPLAW6JksRlESlFq7b8Vegs0Z0S8AhBUKE5sCXwGLgQFVyg41o19mRWhlQJR84DVgOvChCLX/XUNw/zRMSlUy/8rfAw8C5iLQOIFxjytJwoCFwSbIkNO8uoB4wKIUTWibwIi4PnByGhAaW1MqMKiuAU3DnzJ4UIU0juhp3Ufa+QDRm9RHAeuCeZBtGyJitRFrgRt4Yh+qnQYdTUhKVo4GzgNs1ol8GHU+ARgH7A2eqEpqqT0tqZUiVz3BVj8fh+6c1om/hhtEaJlE5yK+4HIgARwMnBBKsMbvuLiCPJDoXI1GpDYzFdT2OCDicwIjwL+A84DZVXgk6nrJk59TKmAiCO+naHzhKlQ8kKtWBr4ACoINGdB0iGcAMoBrQBtVQHPqbFCFyBPAecC2qtwQdTklJVJ4B+gJdNKIzgo4nCCK0BT73y5Gq5AUcUpmyI7UypooC5+JOnj8jQiON6B/AQKAFhRdlq+YBFwPNSaJvusb4L2SjgB+Ae4INpuQkKqcCpwI5KZzQsoDxwO/AqWFLaGBJrVyosg7oA1QGXhChor8I+x5giETlSL/iROBZ4Bp/fsKYZHAB7jzxlX60nITnx3Z8EDcAwm07WD2UfC/SY7gv1/1U+TXgkMqFJbVyoso83PVrBwJ3+5v/DcwFHpOo1PS3DcWdl0iab7wmhYnUxZ2Leh+S41yMH9txDFAJ+JdGNHRHJyV0Ne7L9lWqTAk6mPJiSa0cqfI8cCdwoQhna0Rzcdet7U7hFDWqP+N2EicgckxQsRpTQiNwI3BclkRzpZ2PK8oaphH9LuhggiDCP4CbcT1Dof4CbYUi5UyEDOBN3DxN3VX5TKIyArge6KMRnYBIRdzo5mlANqqbgovYmG0Q2R/4AngA1UuCDqckJCp7AzNx41L+QyOpt8MTYW9gGm7ovoNUSZpRX0rDklociFAb96GqDOxPjqwEPsUVibTTiP6MyFHAOyTZgLAmRbjikM9xF1rvg+qagCPaIYlKBi6ZtcJNKfNzwCHFnQg1cOcR6wOdVFkUbETlz7of40CVVcCJ4CuPclRwI5BkAv+VqKSj+i7wEvBvRJoGFqwxxbsI6IgbOSThE5o3HDcm5ZAUTWhpwJNAS1xhyKJgI4oPS2pxosrXuPNpBwL3k6Pf4kr6ewJX+dWuAISQ93mbJCPSBDdH2pu4YZUSnh/oIAI8rRF9Nuh4AnI90Bu4UpUPgw4mXiypxZEqL+JO1p6Du5p/LPA8cKNEpSuqPwI3An0QOTGwQI35q/tw+4oLk6E4xA9W/DSwCHf5QcoRoTeQgztSuzfYaOLLzqnFmR/R/1XgKOAwcuRr3InsfGA/zSEX+B9QFzfSSLJ09Zgwcl+uJgBXoXpHwNHskC/ffxE3/Fw3jei0gEOKOxHa4M5/zgMODctAxSVlR2px5kf0Px03GsNL5Ght326OqyrbgjuSawDcGlScxiBSHbgfmEXyTP55Hu5arOEpmtDqAa8DG4A+qZbQwJJaIFT5HTfocTrwOjk6G3f9zwCJygBUp+F2IucjckhggZpUdyOu2vE8/2UroUlU2uLOR7/DnwMepAwRKuGKzRoCvVVZEnBIgbDuxwCJ0BN4F/iA7tHe9Mx5H+gAdNAclgGzgU1Ah2QZjsiEhEgnXBfWw6heGHQ4OyJRqYLrtq8NtNeIhnIIqG3xQ2CNxRWj/VOVVC2OsSO1IKnyEe5E9tFMityJ64bMA56VHPJwXSmtgOuCi9KkHHdN2v8BvwHXBhxNSY0CWgNnpFpC867GJbRoKic0sKQWOFUexc1LdRE5ejxu8sJOwN3+2rUncQMetw0wTJNariSJrkmTqJwCDAZu04i+F3Q88SbCScAtuCGwojtYPfSs+zEB+IrIl4F/AMeSI0fgBjo+XXN4BzcI8kKgG6r5gQVqwk8kG5gOvAackugl/BKVlrhux2+AQzSS+Of+ypIIHXGjpnwN9EzFwpCiLKklCBGqA1OA5lRddgjDdn8A9225s+bQDngGuBzVUQGGacJMpALuPFpjYF8/Q3vCkqhUxQ0BtTvQUSO6OOCQ4kqEhrjh9/KBLqosCzikhGDdjwlClT+A44Fc1jd4hY9yLgLWAePrXsXrwBvASET2DjJOE2rXAvsB5ydBQhNgNG5et9NSMKFVxx1NZwHHWUL7kyW1BKLKYlxiq8+kyBiWtx4ItFxZhUdyMzgPVwn5X38i35iyI9IRN9/f06i+FHQ4JTAEN37qDRrRd4MOJp5EqIAbiag9bkzHWQGHlFCs+zEBiXAcbgLGd7iu8lQqbLwRuEhzWA48B9yA6o2BBmnCQ6QS7rxUHdzUR6sCjmi7JCoHAJNx16P11ogWBBxS3PjS/UeBQcBgX2hmYtiRWgJS5XXcN9F/MHJ9M1TeAO6RHBYBTwERRDoHGaMJlQiQDZyTBAmtPm4YrJ9ws1inTELzbsAltBstoRXPklqCUuX/gJGQdg63rfgKWAq8eFkvcoBfcN2QVYKM0YSAyAG4a5weQ/XNoMPZHolKOq5gqg5wskZ0dcAhxZUIZ+EGKX4C90XEFMOSWmK7HvgvG2tfy9iPxgL1/nMAj63O5GzcRdm3BRueSWoilYHHgZ9x0x4luhuBw3Dzo80IOph4EuFo4BHgPVy3o5032gZLagnMf3DPAT7gxx7/5oOb7gEOqX0NJ6sb4+4iRI4ONkqTxG7HfTkalOgXWUtU+uMm/XxEIzo26HjiSYT9cF2us4G+qqTUtXg7y5JaglNlM3Ay8A0fX3cx35z8OHBu3atYhLvgdCwidQIM0SQjkZNws1nfg+r7QYezPRKVTrgjyk9wE+umDBH2BN4CVgPHqLI24JASnlU/Jgl/oeUnoNUY3HU2jaYdfN1khtz0IQ/gRiPpn+ijP5gEIdIMN4ffAtwoNZuDDWjbJCqFFxjnAZ01or8FHFLc+P/5KUAN4BBV5gYcUlKwpJZERNgLmAIFeVyydy61f6j1wyge2+N3hgGDUbVqKLN9btSQSbhqx/1QXRBwRNskUamMi7UNcJBG9KuAQ4obEWrjtr05cJgqKTc3XGlZ92MSUeV74GhIq8YD36Sxrn7G3pfQa0saHwH3IdI+6BhNwosCBwLnJnhCK7weqzMwIMUSWlXcRJ8tgRMtoe0cS2pJRpWvgOPIr7Q798/7LX9zjX33uoRchVXAi4jUCDpGk6BEjgSuAR5FNdGnJxmOGzHkOo3oywHHEjcxE312BU5V5YOAQ0o6ltSSkCpTgL5srLUHD89cuLhq5jH/OomPgD2AMYhIwCGaRCPSABiHm/Hh0oCj2S6JyknASOBp3JQqKcHP1vFf4Chc2f6EgENKSpbUkpQqbwJn8nvzFoydvGhcdsbpL7ThVaAvrqrNGEckDTcvXw1cQdGGgCPaJolKR9yO/QvgHI2kxkl/P/zVA8ApwFBVHgs4pKRlSS2JqfI0yMUs7dycp95Yemqf9N4/ZvEFcBciXYOOzySMa4AjcZN+zg46mG2RqOwBvAmsBE7SiKbE3GA+od2Nm+n+FlXuCjikpGbVjyEgwjDgdvaZsLLW8X2rLL27YHVmPnlAR1RXBh2fCZDIMbiig2eB0xP1sg+JSl3cdWj1cZWO3wQcUlz4hHYLbqiy/wCX22ghu8aO1EJAlTuAfzPvpDqr334iv8eZkqnQAHjSdz2ZVCTSEnde6ivcYMUJubOUqFQBXgWaASekSkLzcnAJ7SEsoZUJ2+GFhCojgRv5ekC1z2c+XPXqI9wIBLjxI02qcVWwrwBbgBMT9TyaH6T4aeAA4HSN6McBhxQ3IlyHG3V/DHCRJbSyYUktXCLAbXx5bqU7146qO6EVvwE5iPQLOjATR+7o/ClgL6Avqj8GHFGx/LVo9wG9gUs1ouMDDilu/CmDm3BFMeeqkmpT6JQbS2oh4r/pDQdG6ReXpp9aa2T9r+uzSuEJm38tpYwAjgMuQ3VS0MFsxzXABcAdGtH7gg4mXkS4FDeY9HPAIEtoZcuSWsj4xHYF8ODmz67lsObX1V5ehXyFVxBpHHR8ppyJ9AWuw3VpPRhwNNskURkE3IybH+2agMOJGxEuAUbhLrA+Q5W8YCMKH6t+DCkR0oD7gQv2bXcV/5tzx5ZK+XwtcCiq64OOz5QDkXbAp7jCkJ6obgo4omJJVE7FnUd7HzheI4kZZ1nbWqUME3CjhSTsQNLJzJJaiLlyYb0H5NJj9hrCa98/RBqMB/qhal0eYSKyOy6hVQA6ofpLwBEVS6LSG/cZnAr00khiFrCUNRH+jZvk9DncEZrNiVZOrPsxxFxXpFwOetub3z/I0EangJubbUTAoZmyJJKFm3OrLnBCAie0o4HngenAcamQ0EQQEW7EJbT/AqdbQitfdqSWAtwRW0EOyA2P1OrBOasnA/wL1f8GG5nZZSKVcAntEOBYVN8NOKJiSVQOBd4GvgUO04iuCjikcucvrL4NGIY7x3meKvnBRhV+ltRSiKRvvr5CASPertqRHuvnFKRBb1RfDzouU0qudP8ZoB9wBqrjAo6oWBKVrrjzZz8B3VNhok+f0O7BDR79EO46NOvyjwPrfkwhml/xxi0ZecNPXD+V6ZX2SssTXkKke9BxmVJwMzHcg0toVyVwQuuAO0L7DTgiRRJaOvB/uIQ2CrjQElr82JFaCpJKf1xaZ3PuqI8zOtOiYPGmSgUchOr0oOMyO0HkKlzX1ijgikQcAkui0hl4B1gHHKoRXRRsROVPhEzche99cNPnXG8jhcSXJbUUJZlrzmi8edUTH8tBUi/t1/VV8wo6oTov6LhMCYj8C3gCV0l3WiJWskpUDsKNuL8Kdw5tYcAhlTsRagAvAz2By1T5T7ARpSZLailMMtccs/eWxa9+rD3TK2WsWVtzS167RB1SyXgiJ+NG3J8MHJOI16JJVHoCrwFLgcM1oksCDqnciVAfV7DTDjhLlYTsDk4FltRSnFRe3a193jcTJ+YdU2FTpU2rd9u0aR80/Oc9kpLIKbjCkC+AXqiuDTiiv5Go9MJdXPwD7hxaQl5eUJZEaA68CzQG+voJfE1ArFAkxWluralfVdhn/+MrjttYfVNarcWVq87dUEF2CzouU4QblPoZ4DPg6ARNaL1xU8jMA3qkSELbFzcPXD3gSEtowbOkZtANdb6eUqljm5MqP7K+bm5B7ZXp1Rf8Wk2aBh2X8WTrsFKfAv9A9Y+AI/obiUp/4EVgBu4c2vKAQyp3IhyOS2gCHKrKJwGHZLCkZjxd22jhu2lHND+++kPLszZRdcvmrO+/rVWhddBxpTyRf+Kq6T4hcRPaZfx5FHmkRnR1sBGVPxEG4i5V+Ak4UJWvg43IFLJzauYvRMg8pPajMyesurrV5vSCgq92k4N6/bzqs6DjSkkip+GGVpoMHJdoA1FLVNKAO3CzQkzATfKZG2xU5ctfVD0C+DfugvK+qqwJNioTy47UzF+osvHjVee06d0g50PJr5TWaVnB1NHNW/UOOq6UI3IeLqFNIjETWibu6OwK3ESfp6RAQqsEjMMltDHAMZbQEo8lNfM3qhRM+eXiw09pctmYDQU15JTFv7x8yx4HDAk6rpQgkobIrcDDuBLxRExotXAXVfcDhuJmrQ71mIYi1AHeA04DrgUG28DEicm6H812dW/x72sfXfjMyIb8wr2NO48evmTSeUHHFFoimcDjQH/ceIGXoJpQk0hKVJrhku2ewJka0WcDDqncidAaeAVoBpypSui3OZlZUjM7dGTLy/550w+TnuqaP1MeqnfozF/bTO6YM9E+OGVKpA5uNIqDgauAOxNt6CuJyoG4GZszgRM1opMCDqnciXA8rlAnFzhZlSkBh2R2wJKaKZGDWl/e8pJFs2f13/h+pZerdVnzv90qtrjp+49DP31IXIjsiRtSqhluSqDnA47obyQq5wAPAouB3hrROQGHVK58Qci1uHnQZgAnqhL6kVHCwJKaKbG9299Q8ewl33x/zerxTaZVaJ3/WPM9ej707RsfBx1XUhM5CFc5mIabCiihrnWSqFQE/gOcjzuP9s+wl+yLUA0YC/TFHaUNViXURTBhYoUiZUSiMlGiMtD/XsG3B/h2Fd/u79tZvt3Ht+v69vG+3cC3e/l2E98+wrdb+HZ3327l2918O9u3O/t2B9/u4NudfTvbt7v5divf7u7bLXz7CInKxO/73LjbNatebNrr0AP/d8Xp89NnHvTe5Pb993w+zNssUWni2718u4FvH+/bdX27j29n+XZ/367i2wN8uwJARkTOanGpLMBVN67pcD6jJIdozOdpiETlrZj2pRKVV2PaQyUq42Pa10hUno1pXy9RGRfTHiFRGRvTvkWiMjqmfadE5YGY9ih//4e4hPYlMKcwoUlURktUbolZf6xEZURMe5xE5fqY9rMSlWti2uMlKkNj2q9KVC6Nab8lURkS035fojI4pl0u/28i7EGtBV8wsEdfDrh7NHAGObJ7mD57EpWBEpWJMe/lYInK+4SEJbWSEumByE9Bh5EI3jns0+tn1M1csikdhny75JSbG/xjUuvQjx9RhkTq3vI+lzVdSwvcOapOXzXg16DDKqIBrtJvP1zhymcQ8ilUvhiyPzCNgoyG1PtmFr2ufMGmjUk+4ep+FFFgb1S/L4fn7gGMQ7VxmT93EpKoTKy4qWLW23e1ze65eXrGW1U6rpvWMK3TDd9Nmx90bAlN5GDcKPv1gMuAhxOpIESiIsBFwJ3Az7iCkFnBRlW+RMgAorhzaF/jCkK+CzYqU1qJc6QmkhF0CHFTltsqIogE8Xe8aXOlzcNGtOhWbWTtvj8ctmF2tcELFs27q2nXSACxJD53/dnVwERgI3Agqg8lWEKrD7wO3Iu7JqtzCiS0hriRQa4FHgW6WkJLcqq6/QU6KsxQ+EPhBYXnFG7y9w1UmFJkfVXYy/9+rH/sWoUlCjkx6zX3656tsFhhsr/9BYVlCmsUJivsG/OYxxUeUHjDx/O5wp7+vsn++dYrrFPo728/TmGmwu8KUxXaxTxfQ4XxCssVFipcEnNfZf96qxW+URim8NN23idVuEThB4UVCncopMW8T58o3KOwSuEmhSyFJ/1r/6jw75j10xXu8s+zUOEi//wZ/v6JCiP9c+Yq7KWwj8J7/vnnK/SLie0Yvw1/KPysMNTfXlfhdf/erFL4eGsMO7mc0uyCe+ZIS1XQF+q0nb2kOpmleZ5QLrCnwvv+b/i8Qo3AYyqykMNR5LCMHDaSw0XkuF6cMC+gh4P+Croe9Iyg47GljP6u210BKvod7qUKFRT6KGzeiaTWQ6GtQppCO4VfFU709xUmtScVqipU9rcPUqiuUElhlMLMmOd+3O98uyhkKDyl8Gyxr+3aHRV+U+jqE8WZCov8c6cpTFe4wW9nC5+QjvaPvdXv5GsrNFGYXYKk9pFfv6nCtwrnxLxPeQoX+7gr++1+xW9rc7/+2X79830SaqxQK2aHGJvUFivs658vS92XhrN8u6NPiPv69X9ROMT/Xkuho//9FoWH/d+2gsIhSsl2ZuTQghxaxN7WptXILg9m9tuooN9UbLjprd3rHB30BzzQxX2uhqv74rFW4bySvr/xWsihIjncSQ5KDnPIifnSF9IFNB00AloAOge0TdAx2VKGf9/trgCHqvtmLzG3TSlxUvv7841SuMf/XpjUWmzn9Wv6dbJ8+3GFR2PuP0Zh3jZfGx5SuLHIc85X6O4T3eIi9w1XGOt//0GhV8x955YgqcWuP0Thg5j3aXHMfekKmxTaxNx2nsJE//uHCufF3HdEMUltRMz9/RU+LhLP/ylE/O+L/fPXKLLOCJ9Yi/97be+Dk8NEcny8sbfXnVPh1PrDv/qF3TQf0U9q1Z+qUC/oD3rcF+im8LX/u72o0CjwmP7+N2xDDtN9QnuQHP/FMsQLaHPQye7Pok+CVg06pkRZQK8FfbScnnsR6BHx2I4dndtpCPzsoypU8gsQRboCtwLZQEWgEvBCkbWWxKyfDowETsGdSC/w99SFrQOHLot57Aag2nYiaAacicjFMbdVxG1XPtAQkd9j7ksHCq+7ashft/XH7bxOoaLrN9zGfXV9HD8WWb/RNl67uPc89rZmQNci25KBGxAX4GTcIKy3IjILuAbVT3EjrOcA7yICMBrVW7exbUVFirtRl7fZAje336NF86GXLP7ytotWjzlwbXqlZWuqp9/QZF3BbSTYsE9lTqQmcAuuDH4JcAKqrwUaUxESlUrANbjzSOuAkzSiLwcaVDnzF1MPAO7HzX92JvBfVatuLKTKzUHHUBZ2VGDwC9AIcXs8r0nM7+uBKltb4q6jiPE0bibcJqhm4QZplSLrxH6oTgN6A0cAWUDzwmfeQZzbsgQYiWrNmKUKqs/4+xYWua86qsf4x/5SZFtLMmlm0fWXxrRjt3MFsAWXjGLX/znmtWOrLGOft7jnWwJMKrIt1VC9wK2p01DtDdTHDcX0vL/9D1SvRLUFcDxwBSKHl2A70YhO2t4wSQt/OPfOK+pc1KRLracXfJ5/SFqTdQU3La9U4cf8NOlZkudPOiJVELkS+BY4F7gHaJOACe1A3DVnOcB4oHUKJLTauIrTJ4FZQDtVnrSEFk47Smqf4o5oLkIkA5HeQJeY+78C9kWkgx+MNafI46sDq1DdiEgXXNLanurAJmAlLlnu7DeHX4EWMe1HgPMR6eqrBKsiciwi1YEvgLWIXI1IZUTSEclG3AWUuB3/cERqIdIYuJgdG+bXbwJcCjxX7Fqq+f75RyJSHZFmuCk8Ci+WfR64FJFG/pv/1Tt43deBloicgUgFv3RGpDUiFRE5HZEsVLcAa3F/UxA5DpG9/JeWwttLNNq6vwC11fbW0V+zl85cfcrevRrcfEOftGcK1m3evWG68uG6ivKeH0kj+bnPzmXAD7gy+K+ALqhegeq6QGOLIVGpLlG5DzfZaHXgWI3oaRrR3wIOrVz52alnAX1wR6Y9VFkUaFClIMIiEYaJMEuE9SKMEWE3Ed4S4Q8R3hehll/3BRGWibBGhMki7OtvryjCTBG3LxMhXYRPRLjBt3NE3D5IhOYiqAhnibBEhNUinC9CZx/D7yLcHxPfniJ8KMJKEVaI8JQINeP+RkGJqh87qaseXKeuMvElhetj7r/OFyUsURjwl/Na0Fddockf6qrs7lcY5+8rPKeWEfNc1fw5nj/84/5V5Pke33o+z7V7/OU8lyuw+EVdNV8/f1svhWn+tl/8NlT39zVUeEZdteVqhc8UjvD3VVFXzPG77nz140p11Yvp/r7izj3WUhinrvpxibqClcLqxwx1lZIr1VU/Xq6wRQvPbbpzaucUeb5W6qpCl/vHfajQQV2xwtt++9b69+Jg/5jL1RXOrFf46S9/1x31kW/jnNo2189c1apKtfmLhzNSl6dXUwXNE6aqq04tVcVloAtkqiv8Wer/9h9sfV8TaCEHIYcTyWEJORSQw3/I8Z//EC+g1UD/48+dzQXdP+iYdnF7FoF+BrobaCPQ30C/BN0PtBLoh6ARv+4g0Or+9lGgM2OeJxt0NWhr0Ov8c6b7+3JAx/nfm/v37mHQTNCjQDeCvgxaPyaG7n79vUCP9K9Zz5+3HFUk/ricU9v5B7ky+rOC/iMn3LK9Apldf+5/KPwY+DbGLOTQjRy67dRj0ArU+PGeqvxecFGFkfpj5ar56krQZvsvMBWC3q4S/C1aqCuw+dn/zScp9Ag8ruL/Rvv7Lx9KDl+TwwFBxxSX7XY74EW+uvFe0CpBx1QG27QI9PSY9njQh2LaF4O+XMzjavrklBVz25Wg83xy2zvm9uKSWqOY+1eC9i8Sw2XbiPdE0BlF4o9LUtvxRbsi3RFp4LsfzwTaAW/v4gGi2R7XpXWMf88b4YoyJgQdViyN6FSN6NSdeoyyRdc0vXw9We3vTx8yb8/c1WkDGlzO91kZLYAngMWI/AeRA4ucxw2W+3ucjsgHwAJc0c3XwOFAD1QnBhleUeLGzXwS+B/QBrgA2E8j+lmwkZUvEWqL8Dhu4OVc4BBVLlFlQ7CRlZnYodRyi2lX812Kt4qwQIS1sLWrtW7Muk/g6hXe1B1faL7D1wQQob4Iz4rws3/dcUVeM25KMhJFK9x5gjXAlUBfVH8p16iM4IbtWY2b9mIuuH7vROEHcc0uzWNV+ZqNNbPzRIY+9dttm1ttWJF5bOde+kljNhW4qsGpwEJEbkNkv0ASnDv/2guRB3GFO+OAPXB/h2ao9kL1Q/81NCH482Y34YpV+uEqj/fSiD6skfBWnYogIvTF/Z+cjqug3k+VhJrxIE5KUmz3IO48/NEiHFxGr3sLrnitnSo1cJWmgXwx3fFwTaqjgdE7XC/VqZbdH1B1A9B5h+sFq/AkcY/SPFiVfMi4S4SXlcpj35z21iFvNp3ctMbZFxRctPCbj6/6hIKsTVyBmzBzASIf4wqXPgW+wRXblB2RCrgiqMNxO4QDgAq4Ia3GA48BE1Et2OZzBESiUhO4EDeWZF1c1fG1GtGSXIaS1ETYAxgFnICr6jxalZlBxhSw7RbbiXAGsD/QHveePSFCe1V2taipOu7A53cRGgHDdvH5Si11xls0Za1MPrSqLBCp2B04m8UH3772sVk1b+78QLebL4tIk02/j3/1Gb7u8CtdcJccDPQPW4vIF7iR4xfiLp1YijuiWrndxCNSA9gb2Cvm5164f/JquG+bM3Al+R8AU/yXjITjx2q8HJfQqgNvACM0ol8EGlgciFAZVxV8Ne561quBu1UJ7RFpCT0JHI27PGgVcD2u+xkRmuK/APgk9rQIvXGf9cHFPlvJRf1rrwG+x10je/kuPmfpBH0CNDSLq0gc6H+v4NsDfLuKbxeOR5nl2318u65vH+/bDXy7l2838e3CyswWvt3dt1v5djffzvbtzr7dwbc7+HZn38727W6+3cq3u/t2C98+wreb+HYv327g28f7dl3f7uPbWb7d37er+PYA367g2wMVJoLWAX1oMP9X8IEcks8JgzZxQ1rBTYcw7bcqfLopjb19QckUdWOD5vtijdhls7qK1XXqqkqXqasGXatuuKqi6//sY3lQXbVuncA/SztYyKEJOdxLDrm+ovE5cvzfNuQLqPgihIX+T/gsaOOg47IlcRY7UjOlsqYS1YYcy75P/XWEl12iykrggk/kiRXpmn8xr47JYvJ1S5e17tn2fw0XVzpmAM8DD665mVdqbGYVbuSZ3XHnejvjut0aAkcCdYCPgM24C90Ll5XAd375AdX1ZRV/eZKopOO+gQ/GHbUq7pvxbRrRb4OMLV5EaImbhbsXMAc4TJWPgo3KJJpwzadm4qZw5lyNaI9yeX4hDTgDuB20Hrt99QWn9KtB3e9a4y4UfwJ4SCM6tzxeP1H42Y8HAWfjRpb5DXgceEAjujjA0OJGhPq4Ap3zcEPjRYAHVNkSaGAmIVlSM6VSOFW9RnRmub6OkAUMBy4FTaPO/Jf411EZZC05ATd+5pe48URf0IguKM9Y4kWiUgs4FjgV+AeuSvldXMHWaxrRzQGGFzciVMeNtDMUqIwbISiqWna9AyZ8LKmZpCBCY9zJ6IHAOqr8dh8XZq+j6vITga5+tRn8meDKfvbzciRRaYQrxT4JV1GagSt+eRwYoxH9IbDg4kyECrhu1ghuvNIXgetUSYluVrNrLKmZUpGoGyNTIzotrq/rxrG7GVeO/AtwK4MOepumU4/HnWMrTHDf4maZnghM1EhiXVspUamBu2zgYOAo/hr3BL9M00jiXUJQXnwyOx13cfuewGTgKlU+DzSwBCGCAnurUu5f2ER4C3hWlSfK+Hmb4yqWK6iSVx6vY0nNlEp5n1Pb4eu7i0ZvBg7BjXJwF/AQOVIbN3jt4cChQA3/kPm4BPcprshgrkbiUyTiizyaAZ1wSexg3CUEabhy9OnAK7hENlcjqfVPKUIl3BH4NbiLhWfiEtubqjaSfqHySmoi5AB7qTKgLJ93G6/VnJikVuS+gcA5qrt2QbhVP5rSuijIF1dlCnCoCIfidoC3A9eQo/cA96kyyieT/XDdeT1woy2cV/gUEpWFwGxckvsWV8n5K64Y4zeNaIkKEfzr1MJVXNbBzRSxD240nn1w18NV8qtvwF1fdxMwBfhMI/pH6d6F5CZCFeAc3AX2jYDPcZ8rS2am1OxIzYSCCAcA1wHH4S4A/T/gQdU/J2L1yWdP3KS12cC+/mdLiv+Ctwo3910e7ogqdgE3DFEdKHaKjXzcdDTz/TIPNwXKjJImy7Dy1Yzn4RJYfVw3443AB2FPZn6y0rtx3ayVcJMDn6bKbBEmAuNUedSvO5CYIxd/pHYpbuSYGsBY4GpVCny18LW4c5GVcePzXqzKmpijo/Nw04MJcKcqd4nQCzfnpeBGIlmgSvvYWHwcg3HTdZ2F+78YgPu/udFvx7DCLkQRjsV9adsT9784RtVNS1ZM9+NE3BB0n+DOiVfAjSmZh7s053WgUeFRnQgnA9er0mFb77EdqZlSkah0AzewcdCxAKjyGXC8CPvhqiWHAkNFmADcC3ysbmitb/3yUuFjJSoVceXyuxVZ6uOSVjquq7Au7p9/jW/Px133thL3j174cxGwIFWqFEtKhI7AJcA/cZWrbwO3qDI50MDi6yhct3hL3OdoH+D3nXj8Sbhu7GrA+7jP4KO47tuBQE9cT8OTuKHszoh5bE9cr0EL4EMRvlLlbRFuZsfdj13969TBFWw9C7yGG42nOzBehPHqRipZD/wL1wOSDbwnwkxVXt7Wk6syV4TzKdL9KMJKXHJ7y980ADdayTZZUjOlVTimXI8ggyhKlRlAPz8k0IW4b5gnAzNFuBd4RpWNf3mMSz4L/LJN/jyiakSPL4/Yw0iEDNyO+BLcucT1uJ3jfarMCzK2gGzBDWm2D/CFKjt7neVtqqwCVokwCvcF4VHckd/dqvwAIMJwYLYIZ8U8NqrKeuBrEcb6x75fwtddqMpY/9zP4XpFRqiyCXhXhM24BDdTlYkxj5slwjO4xPfyTm4ruOtRBwBv+RnMjwaGbO8BJRml35jinMef56cSjiqLVbkaaIyLswJuUOKlIjwgQiffFbQzEnqbE4kIbUS4A/gJN5N7Y9zIL41VuTBFExqqfIg7gnoA+FWE0SJbi5lKYknM7z/iRtDB//yxyH0ZuB6HHT22JIpOOYPqNqeh6SrCRyIsF2ENbuaN0k5DMw7XA1MNN/PEx6pst5LZkpopFY3ofI3o/KDj2BFVNqgyGmiLG33/HdzoHNNw3yKvEPnLP/62nytJtjkoItQU4XwRPsd1PV2OK/44Ede9dbfqTnW1hZIq96qyP+6cbkv+HBx8PW5k/UINinl4k5jfm+KuZcT/bFbkvjz+moy29diyPo/5NO48XRNVsoCHKdk0NH+LQ5WfcRXLJ+G6Urfb9QiW1EwpSVS6S1S6Bx1HSfmxTj9Q5Z+4ncUFuErEu4CfRHhNhDNFqLWt50i2bY4HEaqJ0M93Sf0CPARUxZ3TbKRKb1VeUaVspwpKUiJ09kcyFXBJbCNsfW9mAn1EqCLCXrgvX0UNE6GWCE1wRSPP+dufAS4XYQ9/VHMz8FyRsvnr/XPviyv4KHzsr0BzX2xSFqoDq1TZKEIXXNVxSfwKNBahYpHbn8RVyLalBJMlW1IzpRX1S9JR5XdVHlalK+7b8j2468YeB34T4R0RzvVVerGSdpvLkj8iGyDCy8By3M6xJ657tzPQVpW7inRPGacGbriv1bguwJXAnf6+e3ADcP+KO5f0VDGPfwV3XeNM3FRDY/ztj+GOYibjqgs3AhcXeewk3LQwH+CqH9/1t7/gf64U4cvSb9pWQ4ARIvyBG7Pz+RI+7kPcEf4yEVbE3D4BdxQ6wZ8T3C4r6TelIlFpARCW4Zv8+bXOuKKSk3HlyAW4a8neBt7jqjq/U2VVQVi2uaT8e5ON6749GjgMd47yZ1wV6Xhgih2NJabtXfCcLERYAJynuuPCFktqxhThd+LtcMntBNxRHLhy/Q+A94D3VFkUSIBxIEJDXBI70v8sPL8zH1fKPR5XvZcyw3glq2RPav7atNuAliX5vFlSM6UiUTkCQCNa0pLgpOULSQ6n3ZNnsqHu/nx/TB1/11Lc6CCf++V/JekeSTQiZOJGXunqlwNww1WBu/j8ff5M5EuKew6TuJI5qfmLs9sAZ6jyTokeY0nNlEbQYz8GQaIyEQWiOgQ3tuQBuCSwp18lHzfs1kxgLvCN/7kwEbrmfCFAE9xOorX/2Q7ogOtOBFf2XZikPwC+sqMxk0zs4mtTWmfseJXQOQMBf7TyDXAfgAj1gC78eaRzJHBmzOM2iTAfd5L+J7/8HPNzGbBhV4aI8l2mmbjrkhrhrguL/bknLpHFlowvxyXhu/GJTHVrmbcxyUl9rbMttthSdgtoFugBoGeB3gH6Bug3oGtAtZglD3QV6CLQWaBTQN8GfTNmWQn6lb99Cug60N9AV4Bu3sbzbgSdD/oh6BLQ+0EPBm0NOhG0l4+3iW8f4dstfLu7b7fy7W6+ne3bnX27g2938O3Ovp3t2918u5Vvd/ftFr59hG838e1evt3At4/37bq+3ce3s3y7v29X8e0Bvl3BtweCToz5+wwGfT+mPQT0rZj2paCvxrSHgo6PaV8D+mxM+3rQcTHtEaBjY9q3gI6Oad8J+kBMexToqJj2A6B3xrRHg94S0x4LOiKmPQ70+pj2s6DXxLTHgw6Nab8KemlMe+u2J/tiR2qmVCQqvQA0om8HHUu87Mw2q7IGd77ts789jxtBohF/Hkk1wF3bU6PIUou/XrRawa+3iT+vcZoPfIW75q4vbobsCbhxBe/EDZ30kgh1cZNtvqPKFJFiL+w1JunZOTVTKil7To3U2mZjko0dqZnSOjXoAAKQittsTFKxIzVjjDGhYcNkmVKRqBwvUUmpKVhScZuNSTbW/WhK60r/87VAo4ivVNxmY5KKJTVTWn2DDiAAqbjNxiQVO6dmjDEmNOycmikViUofiUqfoOOIp1TcZmOSjXU/mtK6xP98KdAo4isVt9mYpGJJzZRW76ADCEAqbrMxScXOqZUBERmFG+ncGGOS1UxVvSzoIHaVnVMzpdOJenSiXtBhxFUqbrMxSca6H8tAGL7d7Kyt4yBOS51xEFNxm41JNpbUTGkdE3QAAUjFbTYmqdg5NWOMMaFh59RMqUhUBkhUBgQdRzyl4jYbk2ys+9GU1jn+57hAo4ivVNxmY5KKJTVTWkcGHUAAUnGbjUkqdk7NGGNMaNg5NVMqEpWBEpWBQccRT6m4zcYkG0tqprQG+iWVDCT1ttmYpGLdj8YYY0LDjtSMMcaEhiU1Y4wxoWFJzRhjTGhYUjM7RURuF5EJMe07ROQDEakQZFzGGANWKGJ2kojUARYAPYADgAuBg1V1TZBxGWMMWFIzpSAiOUAfIAuX0JYEG1H5EJHbgb1V9STfvgPoCPRS1S2BBmeMKZYNk2VKYwYQAU4Pa0LzbgMWiEgH3FFpL1wSt4RmTIKyIzWzU0SkLfAO8C7QWFWPCDikclXcUamI1PLtHsArqro6uAiNMbGsUMSUmIg0Al4DzgeGAG1FpEeQMcXBDKAtMDzmqHR/4GLgOKBvUIEZY/7OkpopERGpAbwJ3K2qr6rqBuAOYGSwkZUff1T6EPAEMKjo3fGPyBizI9b9aEwx/FHpJ8AlwPvAQqC/qk607kdjEpclNWOK8EelHwNjVPVef9tQ4CRVPSjQ4Iwx22VJzRhjTGjYOTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoSGJTVjjDGhYUnNGGNMaFhSM8YYExqW1IwxxoRGRtABmGBNnz69YkZGxiPAwUB60PEYk8QKRGRZXl5etGPHju8EHUyqElUNOgYToBkzZlxas2bNi5s1a7YmLS3NPgzGlFJBQYHk5uZmLlq0qOKmTZsussQWDOt+THHp6elnNWzYcL0lNGN2TVpamlatWjW3efPmmzMyMiJBx5OqLKmlOFXNqlix4pag4zAmLCpXrrxRVRsEHUeqsqRmRESCjsGY0PC9HrZvDYi98cYYY0LDkpoxxpjQsKRmEt7SpUszunXrtneNGjU69OvXr1nQ8RhjEpddp2YS3g033NCgRYsWm6ZOnfpd0LEYYxKbHamZhDd58uQa/fv3Xx10HCa55efnM3z48Aa7775721q1arW/9dZb62VkZHRcunSpfbkPEUtqJmFt3LhRqlev3uG7776r3L9//71atmzZJuiYgmA747IxbNiwhu+8807NSZMmzf/+++9nP/PMM3Vq1qyZ37Bhw7ygYzNlx/4pzFaDXhnUZPZvs6uU52tk18/e8Fjvx5aUZN3MzEydOHHivKOOOqrVypUrvyrPuGINGkST2bMp3/chmw2PPUaJ3odhw4Y1nDhxYo1JkybNr1OnTv5hhx22d1LsjAcNasLs8v08kZ29gcd2/HlaunRpxujRo3ebPn36nJYtW24GOOqoo9Z88skn1fzve955550/tWvXblO5xmvKnSU1k9CmTZtWZZ999tkQdBxB2dHO2JTM66+/Xr1Fixa5rVq12lx428qVKzPatGmTC/Djjz9WatOmjSW0ELCkZrYq6RFUPM2cObNKdnZ2bjxfs6RHUPGwo51xQivBEVS8rFixIqNOnTpbj2y3bNnCe++9lzV06NBfNmzYIBkZGZqRse3d4caNG6VLly6tpk6dOv+VV16p8cYbb2Q9/fTTi+MSvNkpdk7NJLTZs2dXbt++fcoeqW1rZ9y2bdvc/Px8unXr1rLwvi5durQq7jk2btwo7dq122fdunXy1FNPZZ122mlN4xF7ImnTps3GL7/8stq8efMqLl++PP2MM85o9tNPP1Xq0KFD7syZMzP33HPPjdt7fGZmpg4cOHDF4MGDmz7++ON1n3jiCUtoCcqSmklo8+bNq9KpU6fEPyopJ9vbGc+dO7dSs2bNNgGsWLEivUaNGsWeY7MdMpx44ol/HHvssas7deq0b+fOnVtnZ2fnpqWl0bFjx40zZ86s3Lp16x1+xrp3777u+eefrzt69OjFFSpUiEfYphQsqZmEtXjx4oy1a9emt2/ffrvfosNsezvjL7/8snLbtm03AHz22WdV9t13323umG2HDE8//fSP69atm7Fo0aLZbdq02di4ceNN1atXL5gzZ07l7Ozsv33GFixYsPWNWrZsWfrFF1/c9Oqrr/55zJgxteMbudkZltRMwmratGne5s2bv6xUqVJKT4uzrZ3xrFmzKterVy8PYMKECTU7dOiQC3/dGYPtkIszZ86czFatWuUCzJ07t/Ltt9++e7du3Vp269at5bJly9K3bNlCv379WgDk5ubKqaeeuseoUaOWRKPRZa+++mqtNWvW2L4zQVmhiDFJJHZnPGfOnMrz5s2r/OKLL9bOz88nPT296oABA1b369evxfTp0+fDX3fI++23X+7++++/z7Bhw5ZnZWUVBLslwZo7d25mYbHNhx9++H3R+z/66KMqp5122kqAypUr68SJE7euM2vWrHnxi9TsLEtqxiSR2J3x77//nvHpp59+G3t/7M4YbIe8LTuqXOzZs+eGnj17pmyBUjKzpGZMEincGW/YsEEqVqz4t6Mt2xmbVGf9wsYkoSpVquikSZP+1m1mTKqzpGaMMSY0LKkZY4wJDUtqRlVTumLemDJVUFAgQEpXlwbJklqKE5E1mzdvTs2rcY0pB7m5uZkisizoOFKVJbUUl5+fP3bp0qVV/bdLY0wpFRQUyPr16ysvWrSoYl5eXjToeFKVWNdTaps+fXrFjIyMR4CDgfSg4zEmiRWIyLK8vLxox44d3wk6mFRlSc0YY0xoWPejMcaY0LCkZowxJjQsqRljjAkNS2rGGGNCw5KaMcaY0LCkZowxJjQsqRljjAkNS2rGGGNCw5KaMcaY0LCkZowxJjQsqRljjAmN/wc6HgbMXwAb3QAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import sympy as sy\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "fsize = 12\n",
    "\n",
    "x = sy.symbols('x')\n",
    "f  = sy.Lambda(x, x*x/2 + 1/2)\n",
    "f1 = sy.Lambda(x, f(x).diff(x))\n",
    "\n",
    "m  = 1/3\n",
    "L  = 3/4\n",
    "x0 = -1\n",
    "\n",
    "qm = sy.Lambda(x, f(x0) + f1(x0)*(x-x0) + m*(x-x0)**2)\n",
    "ql = sy.Lambda(x, f(x0) + f1(x0)*(x-x0) + L*(x-x0)**2)\n",
    "\n",
    "\n",
    "x1 = sy.solve(ql(x).diff(x))[0]\n",
    "x2 = sy.solve(f1(x))[0]\n",
    "x3 = sy.solve(qm(x).diff(x))[0]              \n",
    "\n",
    "qm = sy.lambdify(x, qm(x))\n",
    "ql = sy.lambdify(x, ql(x))\n",
    "f  = sy.lambdify(x, f(x))\n",
    "\n",
    "x = np.linspace(-2,3)\n",
    "xmin = x.min()\n",
    "xmax = x.max()\n",
    "plt.plot(x, f(x) , 'g', label = '$f$')\n",
    "plt.plot(x, qm(x), 'b', label = '$q_{\\mu,x}$')\n",
    "plt.plot(x, ql(x), 'r', label = '$q_{L,x}$')\n",
    "plt.axis('off')\n",
    "#\n",
    "tic = 0.2\n",
    "plt.plot([xmin, xmax], [0,0], 'k')\n",
    "#\n",
    "plt.text(x2, -tic, '$x_{*}$', ha = 'center', va = 'top', fontsize=fsize)\n",
    "plt.plot([x2,x2], [-tic,f(x2)], 'g:')\n",
    "#\n",
    "plt.text(x0, -tic, '$x$', ha = 'center', va = 'top', fontsize=fsize)\n",
    "plt.plot([x0,x0], [-tic,f(x0)], 'g:')\n",
    "plt.plot([xmin,x0], [f(x0),f(x0)], 'g:')\n",
    "#\n",
    "plt.plot([xmin,x1], [ql(x1),ql(x1)], 'r:')\n",
    "#\n",
    "plt.text(xmin-tic, (f(x0)+f(x1)+tic)/2, 'guaranteed progress', color='r', ha = 'center', va = 'center', fontsize=fsize)\n",
    "#\n",
    "#\n",
    "plt.plot([x0,xmax], [f(x0),f(x0)], 'g:')\n",
    "plt.plot([x3,xmax], [qm(x3),qm(x3)], 'b:')\n",
    "plt.text(xmax, (f(x0)+qm(x3))/2, 'maximal\\n suboptimality', color='b', ha = 'center', va = 'center', fontsize=fsize)\n",
    "#\n",
    "plt.legend(loc='lower center', ncol=3, fontsize=fsize)\n",
    "plt.ylim(xmin, f(xmin));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lemma:**\n",
    "$f:\\mathbb{R}^d  \\to \\mathbb{R}$ differenzierbar und\n",
    "es existiere $x_\\ast$ mit \n",
    "$f(x_\\ast)=\\inf_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "Ist $f$ $\\mu$-konvex dann gilt\n",
    "\\begin{equation*} \n",
    "\\frac{\\mu}{2}\\|y-x\\|_2^2\\leq f(x) - f(x_\\ast) \\leq \\frac{1}{2\\mu} \\|f'(x)\\|_2^2. \n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- $f$ ist $\\mu$-konvex, d.h.\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + f'(x)(y-x) + \\frac{\\mu}{2}\\|y-x\\|_2^2  \\quad \\forall x,y\n",
    "    \\end{equation*}\n",
    "\n",
    "- Abschätzung nach unten:\n",
    "  \n",
    "  - da $x_\\ast$ globaler Minimierer ist muss $f'(x_\\ast)=0$ sein und \n",
    "    aus der $\\mu$-Konvexität folgt\n",
    "      \\begin{align*} \n",
    "      f(x) \n",
    "      &\\geq f(x_\\ast) + f'(x_\\ast)(x-x_\\ast) + \\frac{\\mu}{2}  \\|x-x_\\ast\\|_2^2\\\\\n",
    "      &   = f(x_\\ast) + \\frac{\\mu}{2} \\|x-x_\\ast\\|_2^2\n",
    "      \\end{align*}\n",
    "    \n",
    "- Abschätzung nach oben: \n",
    "  \n",
    "  - wir benutzen\n",
    "      \\begin{align*} \n",
    "      f(x_\\ast) &= \\inf_y f(y) \\geq \\inf_y u(y),\n",
    "      \\\\\n",
    "      u(y) &= f(x) + f'(x)(y-x) + \\frac{\\mu}{2}  \\|y-x\\|_2^2\n",
    "      \\end{align*}\n",
    "    und minimieren die quadratische Funktion $u$\n",
    "  \n",
    "  - für die Ableitungen erhalten wir\n",
    "      \\begin{equation*} \n",
    "      u'(y) = f'(x) + \\mu (y-x),\n",
    "      \\quad\n",
    "      u''(y) = \\mu I\n",
    "      \\end{equation*}\n",
    "\n",
    "  - für $\\mu>0$ ist $u$ strikt konvex mit globalem Minimierer $y_\\ast$ mit\n",
    "      \\begin{equation*} \n",
    "      0 = u'(y_\\ast) \\quad \\Leftrightarrow \\quad y_\\ast - x = -\\frac{1}{\\mu}f'(x)\n",
    "      \\end{equation*}\n",
    "    und Minimum\n",
    "      \\begin{align*}\n",
    "      u_\\ast = u(y_\\ast) \n",
    "      &=  f(x) + f'(x)(y_\\ast-x) + \\frac{1}{2} \\mu \\|y_\\ast-x\\|_2^2\\\\\n",
    "      &=  f(x) - \\frac{1}{\\mu} \\|f'(x)\\|_2^2 + \\frac{1}{2} \\mu \\|\\frac{1}{\\mu}f'(x)\\|_2^2\\\\\n",
    "      &=  f(x) - \\frac{1}{2\\mu} \\|f'(x)\\|_2^2\n",
    "      \\end{align*}\n",
    "      \n",
    "  - somit folgt\n",
    "      \\begin{equation*} \n",
    "      f(x_\\ast) \\geq  f(x) - \\frac{1}{2\\mu} \\|f'(x)\\|_2^2.\n",
    "      \\end{equation*}\n",
    "    bzw.\n",
    "      \\begin{equation*} \n",
    "      f(x) - f(x_\\ast) \\leq \\frac{1}{2\\mu} \\|f'(x)\\|_2^2 \n",
    "      \\end{equation*}\n",
    "      \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aus $x_{t+1} = x_t - \\gamma f'_t$ hatten wir in den Vorüberlegungen\n",
    "  \\begin{equation*} \n",
    "  \\|x_{t+1}-x_{*}\\|_{2}^{2} \n",
    "  =\\|x_{t}-x_{*}\\|_{2}^{2}+\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}-2\n",
    "  \\gamma f_{t}^{\\prime}(x_{t}-x_{*})\n",
    "  \\end{equation*}\n",
    "erhalten.\n",
    "$\\mu$-Konvexität liefert mit $y=x_\\ast$, $x=x_t$\n",
    "  \\begin{equation*} \n",
    "  f_\\ast \\geq f_t + f'_t(x_\\ast-x_t) + \\frac{\\mu}{2} \\|x_\\ast-x_t\\|_2^2\n",
    "  \\end{equation*}\n",
    "bzw.\n",
    "  \\begin{equation*} \n",
    "  -f'_t(x_t - x_\\ast)  \\leq  f_\\ast - f_t - \\frac{\\mu}{2} \\|x_t - x_\\ast\\|_2^2.\n",
    "  \\end{equation*}\n",
    "Eingesetzt erhalten wir\n",
    "  \\begin{align*}\n",
    "  \\|x_{t+1}-x_{*}\\|_{2}^{2} \n",
    "  & =\\|x_{t}-x_{*}\\|_{2}^{2}+\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "     + 2 \\gamma \\big( f_\\ast - f_t - \\frac{\\mu}{2} \\|x_t - x_\\ast\\|_2^2 \\big)\\\\\n",
    "  & \\leq\n",
    "  (1-\\gamma\\mu) \\|x_{t}-x_{*}\\|_{2}^{2}+\\gamma^{2}\\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "   + 2 \\gamma (f_\\ast - f_t).\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Descent-Lemma aus dem vorherigen Kapitel liefert\n",
    "  \\begin{equation*} \n",
    "  f_\\ast - f_t \n",
    "  \\leq f_{t+1} - f_{t}\n",
    "  \\leq -\\beta\\|f_{t}^{\\prime}\\|_2^{2},\n",
    "  \\quad\n",
    "  \\beta = \\gamma\\big(1-\\frac{\\gamma L}{2}\\big)\n",
    "  \\end{equation*}\n",
    "mit $\\beta > 0$ für $0 < \\gamma < \\frac{2}{L}$, so dass\n",
    "  \\begin{equation*} \n",
    "  \\|x_{t+1}-x_{\\ast}\\|_{2}^{2}\n",
    "  \\leq \n",
    "  (1-\\gamma\\mu) \\ \\|x_{t}-x_{*}\\|_{2}^{2}\n",
    "  +(\\gamma^{2} -  2 \\gamma \\beta)  \\ \\|f_{t}^{\\prime}\\|_{2}^{2}\n",
    "  \\end{equation*}\n",
    "gilt.\n",
    "  \n",
    "Für den Vorfaktor des letzten Terms gilt wegen $\\gamma>0$, $\\beta = \\gamma\\big(1-\\frac{\\gamma L}{2}\\big)$,\n",
    "  \\begin{align*}\n",
    "  \\gamma (\\gamma - 2  \\beta) \\leq 0\n",
    "  & \\quad\\Leftrightarrow \\quad \\gamma \\leq 2  \\beta = \\gamma(2 - \\gamma L) \\\\\n",
    "  & \\quad\\Leftrightarrow \\quad 1 \\leq 2 - \\gamma L \\\\\n",
    "  & \\quad\\Leftrightarrow \\quad \\gamma \\leq \\frac{1}{L} .\n",
    "  \\end{align*}\n",
    "Somit folgt für $0<\\gamma \\leq \\frac{1}{L}$\n",
    "  \\begin{equation*} \n",
    "  \\|x_{t+1}-x_{*}\\|_{2}^2 \\leq \\rho \\|x_{t}-x_{*}\\|_{2}^2,\n",
    "  \\quad\n",
    "  \\rho = 1-\\gamma\\mu \n",
    "  \\end{equation*}\n",
    "bzw.\n",
    "  \\begin{equation*} \n",
    "  \\|x_{T}-x_{*}\\|_{2}^2 \\leq \\rho^T \\|x_{0}-x_{*}\\|_{2}^2.\n",
    "  \\end{equation*}\n",
    "Wegen $0<\\mu\\leq L$ und $0<\\gamma\\leq \\frac{1}{L}$ ist \n",
    "  \\begin{equation*} \n",
    "  0<\\gamma\\mu\\leq \\gamma L \\leq 1\n",
    "  \\end{equation*} \n",
    "und somit\n",
    "  \\begin{equation*} \n",
    "  0 \\leq \\rho < 1,\n",
    "  \\end{equation*}\n",
    "also $|\\rho|< 1$ und wir erhalten Konvergenz für $x_T$.\n",
    "\n",
    "Für $f_T$ ergibt sich direkt aus der $L$-Glattheit\n",
    "  \\begin{equation*} \n",
    "  f_T \\leq f_\\ast + f'_\\ast(x_T - x_\\ast) + \\frac{L}{2} \\|x_T - x_\\ast\\|_2^2\n",
    "  \\end{equation*}\n",
    "und wegen $f'_\\ast=0$\n",
    "  \\begin{equation*} \n",
    "  f_T - f_\\ast  \n",
    "  \\leq \\frac{L}{2} \\|x_T - x_\\ast\\|_2^2\n",
    "  \\leq \\frac{L}{2} \\rho^T \\|x_{0}-x_{*}\\|_{2}^2.\n",
    "  \\end{equation*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insgesamt haben wir damit das folgende Ergebnis bewiesen.\n",
    "\n",
    "\n",
    "**Satz:** $f:\\mathbb{R}^d\\to \\mathbb{R}$, $\\mu$-konvex mit $\\mu>0$, $L$-glatt mit Konstante $L$\n",
    "und es existiere $x_\\ast = \\mathrm{argmin}_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "  \n",
    "Für  $0 < \\gamma \\leq \\frac{1}{L}$ folgt\n",
    "\\begin{equation*} \n",
    "\\|x_{t+1}-x_{*}\\|_{2}^2 \\leq \\rho \\|x_{t}-x_{*}\\|_{2}^2\n",
    "\\end{equation*}\n",
    "und\n",
    "\\begin{equation*} \n",
    "f_T - f_\\ast \\leq \\frac{L}{2} \\rho^T \\|x_{0}-x_{*}\\|_{2}^2\n",
    "\\end{equation*}\n",
    "mit\n",
    "\\begin{equation*} \n",
    "\\rho = 1-\\gamma\\mu \\in [0,1).\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- $f_{T} - f_\\ast \\leq \\frac{L}{2} \\rho^T \\|x_{0}-x_{*}\\|_{2}^2 \\leq\\varepsilon$ \n",
    "  gilt sicher, falls\n",
    "    \\begin{equation*} \n",
    "    \\rho^T \\leq \\frac{2\\varepsilon}{L \\|x_{0}-x_{*}\\|_{2}^2}\n",
    "    \\end{equation*}\n",
    "\n",
    "- für $\\rho = 0$ gilt das für alle $\\varepsilon\\ge 0$\n",
    "  \n",
    "- für $0 < \\rho < 1$  folgt\n",
    "    \\begin{equation*} \n",
    "    T\\log(\\rho) \\leq \\log\\big(\\frac{2\\varepsilon}{L \\|x_{0}-x_{*}\\|_{2}^2}\\big), \n",
    "    \\quad \\log(\\rho)<0\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{align*}\n",
    "    T \n",
    "    &\\geq \n",
    "    \\frac{1}{ \\log(\\rho) } \\log\\big(\\frac{2\\varepsilon}{L \\|x_{0}-x_{*}\\|_{2}^2}\\big)\\\\\n",
    "    &=\n",
    "    \\frac{1}{|\\log(\\rho)|} \\log\\big(\\frac{L \\|x_{0}-x_{*}\\|_{2}^2}{2\\varepsilon}\\big)\\\\\n",
    "    &=\n",
    "    \\frac{1}{|\\log(\\rho)|}\n",
    "    \\Big(\n",
    "    \\log\\big(\\frac{L}{2} \\|x_{0}-x_{*}\\|_{2}^2\\big)\n",
    "    +\n",
    "    \\log\\big(\\frac{1}{\\varepsilon}\\big)\n",
    "    \\Big)\n",
    "    \\end{align*}\n",
    "  und somit\n",
    "    \\begin{equation*} \n",
    "    T = \\mathcal{O}\\Big( \\log\\big(\\frac{1}{\\varepsilon}\\big) \\Big)\n",
    "    \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusammenfassung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für Gradient-Descent bei *nicht restringierten Optimierungsproblemen* haben wir folgendes \n",
    "  Konvergenzverhalten nachgewiesen:\n",
    "\n",
    "- $f$ konvex und Lipschitz-stetig, $\\gamma = \\frac{c}{\\sqrt{T}}$, $c>0$:\n",
    "    \\begin{equation*} \n",
    "    \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast) \\leq \\varepsilon\n",
    "    \\quad \\Rightarrow\\quad\n",
    "    T = \\mathcal{O}\\big(\\frac{1}{\\varepsilon^2}\\big)\n",
    "    \\end{equation*}\n",
    "    \n",
    "- $f$ konvex und $L$-glatt, $0 < \\gamma < \\frac{2}{L}$:\n",
    "    \\begin{equation*} \n",
    "    f_{T}-f_\\ast \\leq \\varepsilon\n",
    "    \\quad \\Rightarrow\\quad\n",
    "    T =\\mathcal{O}\\big( \\frac{1}{\\varepsilon} \\big)\n",
    "    \\end{equation*}  \n",
    "\n",
    "- $f$ $\\mu$-konvex mit $\\mu>0$ und $L$-glatt, $0 < \\gamma \\leq \\frac{1}{L}$:\n",
    "    \\begin{equation*} \n",
    "    f_{T}-f_\\ast \\leq \\varepsilon\n",
    "    \\quad \\Rightarrow\\quad\n",
    "    T = \\mathcal{O}\\Big( \\log\\big(\\frac{1}{\\varepsilon}\\big) \\Big)\n",
    "    \\end{equation*}\n",
    "    \n",
    "Ist $f(x)$ eine $L$-glatte Funktion, dann ist für alle $\\mu > 0$\n",
    "  \\begin{equation*} \n",
    "  f_R(x) = f(x) + \\mu \\|x\\|_2^2\n",
    "  \\end{equation*}\n",
    "auch $\\mu$-konvex, d.h. Tikhonov(Ridge)-Regularisierung kann die\n",
    "Konvergenz von Gradient-Descent beschleunigen."
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  },
  "nbTranslate": {
   "displayLangs": [
    "fr",
    "en"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": false,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}