3.c Optimization-Scipy-NewtonCG.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scipy Optimization [Source](https://docs.scipy.org/doc/scipy/reference/optimize.html#module-scipy.optimize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SciPy optimize provides functions for minimizing (or maximizing) objective functions, possibly subject to constraints. It includes solvers for nonlinear problems (with support for both local and global optimization algorithms), linear programing, constrained and nonlinear least-squares, root finding and curve fitting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Scalar Functions Optimization\n",
    "2. Local (Multivariate) Optimization\n",
    "```\n",
    "    ‘Nelder-Mead’ ,‘Powell’ ,‘CG’ ,‘BFGS’ ,‘Newton-CG’ \n",
    "    ‘L-BFGS-B’  ,‘TNC’  ,‘COBYLA’  ,‘SLSQP’  ,‘trust-constr’ \n",
    "    ‘dogleg’  ,‘trust-ncg’  ,‘trust-exact’  ,‘trust-krylov’  \n",
    "```\n",
    "3. Global Optimization\n",
    "4. Least-squares and Curve Fitting\n",
    "5. Root finding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Newton's Cojugate Gradient Method (Local Optimization)\n",
    "\n",
    "Method Newton-CG uses a Newton-CG algorithm [5] pp. 168 (also known as the truncated Newton method). It uses a CG method to the compute the search direction. See also TNC method for a box-constrained minimization with a similar algorithm. Suitable for large-scale problems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.linalg as la\n",
    "import scipy.optimize as sopt\n",
    "from scipy.optimize import minimize\n",
    "\n",
    "import matplotlib.pyplot as pt\n",
    "from mpl_toolkits.mplot3d import axes3d\n",
    "%matplotlib inline\n",
    "import seaborn as sns\n",
    "sns.set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The minimum value of this function is 0 which is achieved when x =1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](img/0.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rosen(x):\n",
    "    \"\"\"The Rosenbrock function\"\"\"\n",
    "    return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](img/1.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 269,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rosen_der(x):\n",
    "    xm = x[1:-1]\n",
    "    xm_m1 = x[:-2]\n",
    "    xm_p1 = x[2:]\n",
    "    der = np.zeros_like(x)\n",
    "    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)\n",
    "    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])\n",
    "    der[-1] = 200*(x[-1]-x[-2]**2)\n",
    "    return der"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](img/2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](img/3.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 270,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rosen_hess(x):\n",
    "    x = np.asarray(x)\n",
    "    H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)\n",
    "    diagonal = np.zeros_like(x)\n",
    "    diagonal[0] = 1200*x[0]**2-400*x[1]+2\n",
    "    diagonal[-1] = 200\n",
    "    diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]\n",
    "    H = H + np.diag(diagonal)\n",
    "    return H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 271,
   "metadata": {},
   "outputs": [],
   "source": [
    "x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimization terminated successfully.\n",
      "         Current function value: 0.000000\n",
      "         Iterations: 24\n",
      "         Function evaluations: 33\n",
      "         Gradient evaluations: 56\n",
      "         Hessian evaluations: 24\n"
     ]
    }
   ],
   "source": [
    "res = minimize(rosen, x0, method='Newton-CG',jac=rosen_der, hess=rosen_hess,\n",
    "                options={'xtol': 1e-8, 'disp': True})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.        , 1.        , 1.        , 0.99999999, 0.99999999])"
      ]
     },
     "execution_count": 274,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res.x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. https://andreask.cs.illinois.edu/cs357-s15/public/demos/12-optimization/Steepest%20Descent.html\n",
    "2. https://scipy-lectures.org/advanced/mathematical_optimization/auto_examples/plot_gradient_descent.html\n",
    "3. https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html\n",
    "4. https://scipy-cookbook.readthedocs.io/index.html\n",
    "5. http://folk.ntnu.no/leifh/teaching/tkt4140/._main000.html"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}