03-optimization_tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mRCQfI4o9f0k"
   },
   "source": [
    "Optimization with autograd\n",
    "===================================\n",
    "\n",
    "An differentiable optimization problem can be solved with a gradient descent. \n",
    "\n",
    "Gradient descent is based on the observation that if the multi-variable function $F(\\mathbf{x})$ is  differentiable function in a neighborhood of a point $\\mathbf{a}$, then $F(\\mathbf{x})$ decreases ''fastest'' if one goes from $\\mathbf{a}$ in the direction of the negative gradient of $F$ at $\\mathbf{a}$,  $-\\nabla F(\\mathbf{a})$. It follows that, if\n",
    "\\begin{equation}\n",
    "\\mathbf{a}_{n+1} = \\mathbf{a}_n-\\gamma\\nabla F(\\mathbf{a}_n)\n",
    "\\end{equation}\n",
    "\n",
    "for $\\gamma \\in \\mathbb{R}_{+}$ small enough, then  $F(\\mathbf{a_n})\\geq F(\\mathbf{a_{n+1}})$. In other words, the term $\\gamma\\nabla F(\\mathbf{a})$ is subtracted from $\\mathbf{a}$ because we want to move against the gradient, toward the minimum. With this observation in mind, one starts with a guess $\\mathbf{x}_0$ for a local minimum of $F$, and considers the sequence $\\mathbf{x}_0, \\mathbf{x}_1, \\mathbf{x}_2, \\dots$ such that\n",
    "\n",
    "\\begin{equation}\n",
    "\\mathbf{x}_{n+1}=\\mathbf{x}_n-\\gamma_n \\nabla F(\\mathbf{x}_n),\\ n \\ge 0.\n",
    "\\end{equation}\n",
    "\n",
    "We have a monotonic sequence\n",
    "\n",
    "\\begin{equation}\n",
    "F(\\mathbf{x}_0)\\ge F(\\mathbf{x}_1)\\ge F(\\mathbf{x}_2)\\ge \\cdots\n",
    "\\end{equation}\n",
    "\n",
    "(from Wikipedia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# In low dimension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import torch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A function to visualize a 2D -> 1D function as contours "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_with_contours(f):     \n",
    "    delta = 0.1\n",
    "    xsteps = np.arange(-4.0, 4.0, delta)\n",
    "    ysteps = np.arange(-3.0, 3.0, delta)\n",
    "    Z = np.array([[f(torch.tensor([x, y])) for x in xsteps] for y in ysteps])\n",
    "    X, Y = np.meshgrid(xsteps, ysteps)\n",
    "    plt.contour(X, Y, Z, levels=np.arange(Z.min(), Z.max(), 0.05 * (Z.max() - Z.min())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A complex function to minimize (convention: we always minimize rather than maximize)\n",
    "\n",
    "Note that the function is not necessarily differentiable everywhere..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x): \n",
    "    return torch.sin(x[0] + 1.1) + torch.sin(x[1]) + 0.4  * (torch.abs(x[0] - 2.5) + torch.abs(x[1] + .5))\n",
    "\n",
    "plot_with_contours(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# starting point\n",
    "x = torch.tensor([0.0, 0.0])\n",
    "\n",
    "# set the learning rate\n",
    "learning_rate = 0.5\n",
    "\n",
    "objectives = []\n",
    "points = []\n",
    "for it in range(20):    \n",
    "    points.append(x.numpy())   # logging \n",
    "    \n",
    "    # we will need a gradient wrt. x\n",
    "    x.requires_grad = True\n",
    "    \n",
    "    # call the function, record dependencies for the gradient\n",
    "    y = f(x)\n",
    "        \n",
    "    print(it, y.item())\n",
    "    objectives.append(y.item()) # logging\n",
    "    \n",
    "    # compute gradients\n",
    "    y.backward()    \n",
    "    \n",
    "    # update current solution\n",
    "    x = x.data - learning_rate * x.grad\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(objectives)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "points = np.array(points)\n",
    "plot_with_contours(f)\n",
    "plt.plot(points[:, 0], points[:, 1], 'ro-')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercices**\n",
    "\n",
    "- Observations: is this a global minimum? \n",
    "\n",
    "- Try changing the initial value to something else to get a better objective value\n",
    "\n",
    "- Try changing the learning rate to 2 and to 0.02. What happens?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "collapsed_sections": [],
   "default_view": {},
   "name": "autograd_tutorial.ipynb",
   "provenance": [],
   "version": "0.3.2",
   "views": {}
  },
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}