{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "from matplotlib import cm\n",
    "\n",
    "a, c = (10, 1)\n",
    "def f(x):\n",
    "    phi = np.array([np.sin(a*x[0]), np.sin(a*c*x[1]), 2*x[0], 2*c*x[1]])\n",
    "    return phi.T@phi\n",
    "\n",
    "def grad_f(x):\n",
    "    phi = np.array([np.sin(a*x[0]), np.sin(a*c*x[1]), 2*x[0], 2*c*x[1]])\n",
    "    Jphi = np.array([[a*np.cos(a*x[0]), 0],\n",
    "                     [0, a*c*np.cos(a*c*x[1])],\n",
    "                     [2, 0],\n",
    "                     [0, 2*c]])\n",
    "    return 2*Jphi.T@phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# visualize the real function, f\n",
    "%matplotlib notebook\n",
    "%matplotlib notebook\n",
    "\n",
    "nx1, nx2 = (50, 50)\n",
    "x1 = np.linspace(-1, 1, nx1)\n",
    "x2 = np.linspace(-1, 1, nx2)\n",
    "x1v, x2v = np.meshgrid(x1, x2)\n",
    "\n",
    "fx_s = np.zeros_like(x1v)\n",
    "for i in range(nx1):\n",
    "    for j in range(nx2):\n",
    "        x = np.array([x1[i], x2[j]])\n",
    "        fx_s[i,j] = f(x)\n",
    "\n",
    "fig = plt.figure(figsize=(8,4))\n",
    "ax1 = fig.add_subplot(121, projection=\"3d\")\n",
    "surf = ax1.plot_surface(x1v,x2v,fx_s,cmap=cm.coolwarm)\n",
    "fig.colorbar(surf)\n",
    "ax1.set_xlabel('x1')\n",
    "ax1.set_ylabel('x2')\n",
    "ax1.set_zlabel('f')\n",
    "ax2 = fig.add_subplot(122)\n",
    "surf2 = plt.contour(x1v,x2v,fx_s,levels=20,cmap=cm.coolwarm)\n",
    "fig.colorbar(surf2)\n",
    "ax2.set_xlabel('x')\n",
    "ax2.set_ylabel('y')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradDescentBacktraking(x, f, grad_f):\n",
    "    alpha = 1\n",
    "    fx = f(x)\n",
    "    x_path = [x.copy()]\n",
    "    fx_path = [fx.copy()]\n",
    "    while True:\n",
    "        grad_fx = grad_f(x)\n",
    "        delta = -grad_fx/np.linalg.norm(grad_fx)\n",
    "        \n",
    "        while f(x+alpha*delta) > fx + 0.5*grad_fx.T@(alpha*delta):\n",
    "            alpha *= 0.5\n",
    "            \n",
    "        x += alpha*delta\n",
    "        fx = f(x)\n",
    "        \n",
    "        x_path.append(x.copy())\n",
    "        fx_path.append(fx.copy())\n",
    "        \n",
    "        alpha = min(1.2*alpha, np.inf)\n",
    "        if np.linalg.norm(alpha*delta) < 1e-10:\n",
    "            break\n",
    "            \n",
    "    \n",
    "    return x, fx, np.stack(x_path), np.stack(fx_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.random.rand(2)*2-1 # uniformly sample from [-1,1]^2\n",
    "x, fx, x_path, fx_path = gradDescentBacktraking(x, f, grad_f)\n",
    "\n",
    "fig = plt.figure(figsize=(5,5))\n",
    "ax2 = fig.add_subplot(111)\n",
    "surf2 = plt.contour(x1v,x2v,fx_s,levels=20,cmap=cm.coolwarm)\n",
    "fig.colorbar(surf2)\n",
    "ax2.plot(x_path[:,0], x_path[:,1], 'o-', ms=2)\n",
    "ax2.plot(x[0], x[1], 'ro', ms=5)\n",
    "ax2.set_xlabel('x')\n",
    "ax2.set_ylabel('y')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5,5))\n",
    "ax2 = fig.add_subplot(111)\n",
    "surf2 = plt.contour(x1v,x2v,fx_s,levels=20,cmap=cm.coolwarm)\n",
    "fig.colorbar(surf2)\n",
    "for i in range(100):\n",
    "    x = np.random.rand(2)*2-1 # uniformly sample from [-1,1]^2\n",
    "    x, fx, x_path, fx_path = gradDescentBacktraking(x, f, grad_f)\n",
    "    ax2.plot(x_path[:,0], x_path[:,1], 'o-', ms=2)\n",
    "    ax2.plot(x[0], x[1], 'ro', ms=5)\n",
    "\n",
    "ax2.set_xlabel('x')\n",
    "ax2.set_ylabel('y')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}