{
 "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",
    "n, c = (2, 10)\n",
    "C = np.diag(c**(np.arange(n)/(n-1.)))\n",
    "print(C)\n",
    "\n",
    "f_sq = lambda x: x.T@C@x\n",
    "f_hole = lambda x: 1.-np.exp(-x.T@C@x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%matplotlib notebook\n",
    "%matplotlib notebook\n",
    "\n",
    "def draw_f(x_path_sq = np.empty(0), fx_path_sq = np.empty(0), x_path_hole = np.empty(0), fx_path_hole = np.empty(0)):\n",
    "    x = np.arange(-2, 2, 0.05)\n",
    "    y = np.arange(-2, 2, 0.05)\n",
    "    xv, yv = np.meshgrid(x, y, indexing='ij')\n",
    "    zv_sq = np.zeros_like(xv)\n",
    "    zv_hole = np.zeros_like(xv)\n",
    "    for i in range(x.shape[0]):\n",
    "        for j in range(y.shape[0]):\n",
    "            zv_sq[i,j] = f_sq(np.array([xv[i,j], yv[i,j]]))\n",
    "            zv_hole[i,j] = f_hole(np.array([xv[i,j], yv[i,j]]))\n",
    "            \n",
    "    fig = plt.figure(figsize=(8,8))\n",
    "    ## f_sq\n",
    "    ax1 = fig.add_subplot(221, projection=\"3d\")\n",
    "    surf = ax1.plot_surface(xv,yv,zv_sq,cmap=cm.coolwarm)\n",
    "    if not x_path_sq.size == 0: ax1.plot(x_path_sq[:,0], x_path_sq[:,1], fx_path_sq, 'ko-')\n",
    "    fig.colorbar(surf)\n",
    "    ax1.set_xlabel('x')\n",
    "    ax1.set_ylabel('y')\n",
    "    ax1.set_zlabel('f')\n",
    "\n",
    "    ax2 = fig.add_subplot(222)\n",
    "    surf2 = plt.contourf(xv,yv,zv_sq,cmap=cm.coolwarm)\n",
    "    if not x_path_sq.size == 0: ax2.plot(x_path_sq[:,0], x_path_sq[:,1], 'ko-')\n",
    "    fig.colorbar(surf2)\n",
    "    ax2.set_xlabel('x')\n",
    "    ax2.set_ylabel('y')\n",
    "\n",
    "    ## f_hole\n",
    "    ax3 = fig.add_subplot(223, projection='3d')\n",
    "    surf3 = ax3.plot_surface(xv,yv,zv_hole,cmap=cm.coolwarm)\n",
    "    if not x_path_hole.size == 0: ax3.plot(x_path_hole[:,0], x_path_hole[:,1], fx_path_hole, 'ko-')\n",
    "    fig.colorbar(surf3)\n",
    "    ax3.set_xlabel('x')\n",
    "    ax3.set_ylabel('y')\n",
    "    ax3.set_zlabel('f')\n",
    "\n",
    "    ax4 = fig.add_subplot(224)\n",
    "    surf4 = plt.contourf(xv,yv,zv_hole,cmap=cm.coolwarm)\n",
    "    if not x_path_hole.size == 0: ax4.plot(x_path_hole[:,0], x_path_hole[:,1], 'ko-')\n",
    "    fig.colorbar(surf4)\n",
    "    ax4.set_xlabel('x')\n",
    "    ax4.set_ylabel('y')\n",
    "    \n",
    "    plt.show()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw_f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradDescentBacktraking(x, f, grad_f, C = np.eye(n)):\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",
    "        grad_fx = np.linalg.solve(C, grad_fx)\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)\n",
    "\n",
    "grad_f_sq = lambda x: 2.*C@x\n",
    "grad_f_hole = lambda x: 2.*np.exp(-x.T@C@x)*C@x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "n, c = (2, 10)\n",
    "C = np.diag(c**(np.arange(n)/(n-1.)))\n",
    "\n",
    "x_sq, fx_sq, x_path_sq, fx_path_sq = gradDescentBacktraking(1.5*np.ones(n), f_sq, grad_f_sq)\n",
    "plt.figure()\n",
    "plt.plot(fx_path_sq)\n",
    "plt.grid()\n",
    "\n",
    "x_hole, fx_hole, x_path_hole, fx_path_hole = gradDescentBacktraking(1.5*np.ones(n), f_hole, grad_f_hole)\n",
    "plt.figure()\n",
    "f2 = plt.plot(fx_path_hole)\n",
    "plt.grid()\n",
    "\n",
    "draw_f(x_path_sq, fx_path_sq, x_path_hole, fx_path_hole)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "x_sq, fx_sq, x_path_sq, fx_path_sq = gradDescentBacktraking(1.5*np.ones(n), f_sq, grad_f_sq, C)\n",
    "plt.figure()\n",
    "plt.plot(fx_path_sq)\n",
    "plt.grid()\n",
    "\n",
    "x_hole, fx_hole, x_path_hole, fx_path_hole = gradDescentBacktraking(1.5*np.ones(n), f_hole, grad_f_hole, C)\n",
    "plt.figure()\n",
    "f2 = plt.plot(fx_path_hole)\n",
    "plt.grid()\n",
    "\n",
    "draw_f(x_path_sq, fx_path_sq, x_path_hole, fx_path_hole)"
   ]
  },
  {
   "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
}