{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Methods for finding the minima (extrema) of functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Golden section search (see lecture notes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "\n",
    "phi = (math.sqrt(5) + 1) / 2\n",
    "\n",
    "# Iterative implementation\n",
    "def gss(f, a, b, accuracy=1e-7):\n",
    "    c = b - (b - a) / phi\n",
    "    d = a + (b - a) / phi\n",
    "    while abs(b - a) > accuracy:\n",
    "        if f(c) < f(d): \n",
    "            b = d\n",
    "        else:\n",
    "            a = c\n",
    "\n",
    "        c = b - (b - a) / phi\n",
    "        d = a + (b - a) / phi\n",
    "\n",
    "    return (b + a) / 2\n",
    "\n",
    "# Recursive implementation\n",
    "def gss_recursive(f, a, b, accuracy=1e-7):\n",
    "    if (abs(b - a) <= accuracy):\n",
    "        return (b + a) / 2\n",
    "    \n",
    "    c = b - (b - a) / phi\n",
    "    d = a + (b - a) / phi\n",
    "    if f(c) < f(d): \n",
    "        return gss_recursive(f, a, d, accuracy)\n",
    "    else:\n",
    "        return gss_recursive(f, c, b, accuracy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Golden secton search:\n",
      "The minimum of sin(x) over the interval ( 0.0 , 6.283185307179586 ) is at x = 4.712388990891052\n"
     ]
    }
   ],
   "source": [
    "def f(x):\n",
    "    return np.sin(x)\n",
    "xleft = 0.\n",
    "xright = 2. * math.pi\n",
    "print(\"Golden secton search:\")\n",
    "print(\"The minimum of sin(x) over the interval (\",xleft,\",\",xright,\") is at x =\",gss(f,xleft,xright, 1.e-10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Newton method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton_extremum(f, df, d2f, x0, accuracy=1e-7, max_iterations=100):\n",
    "    xprev = xnew = x0\n",
    "    for i in range(max_iterations):\n",
    "        xnew = xprev - df(xprev) / d2f(xprev)\n",
    "\n",
    "        if (abs(xnew-xprev) < accuracy):\n",
    "            return xnew\n",
    "    \n",
    "        xprev = xnew\n",
    "    \n",
    "    print(\"Newton method failed to converge to a required precision in \" + str(max_iterations) + \" iterations\")\n",
    "    \n",
    "    return xnew   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "An extremum of sin(x) using Newton's method starting from x0 =  5.0  is ( 0.0 , 6.283185307179586 ) is at x = 4.71238898038469\n"
     ]
    }
   ],
   "source": [
    "def f(x):\n",
    "    return np.sin(x)\n",
    "\n",
    "def df(x):\n",
    "    return np.cos(x)\n",
    "\n",
    "def d2f(x):\n",
    "    return -np.sin(x)\n",
    "\n",
    "x0 = 5.\n",
    "print(\"An extremum of sin(x) using Newton's method starting from x0 = \",x0,\" is (\",xleft,\",\",xright,\") is at x =\",newton_extremum(f,df,d2f, x0, 1.e-10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Gradient descent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradient_descent(f, df, x0, gam = 0.01, accuracy=1e-7, max_iterations=100):\n",
    "    xprev  = x0\n",
    "    for i in range(max_iterations):\n",
    "        xnew = xprev - gam * df(xprev)\n",
    "\n",
    "        if (abs(xnew-xprev) < accuracy):\n",
    "            return xnew\n",
    "    \n",
    "        xprev2 = xprev\n",
    "        xprev = xnew\n",
    "    \n",
    "    print(\"Gradient descent method failed to converge to a required precision in \" + str(max_iterations) + \" iterations\")\n",
    "    \n",
    "    return xnew     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "An extremum of sin(x) using gradient descent (gam =  0.1 ) starting from x0 =  5.0  is ( 0.0 , 6.283185307179586 ) is at x = 4.712397537576874\n"
     ]
    }
   ],
   "source": [
    "def f(x):\n",
    "    return np.sin(x)\n",
    "\n",
    "def df(x):\n",
    "    return np.cos(x)\n",
    "\n",
    "x0 = 5.\n",
    "gam = 0.1\n",
    "print(\"An extremum of sin(x) using gradient descent (gam = \", gam, \") starting from x0 = \",x0,\" is (\",xleft,\",\",xright,\") is at x =\",gradient_descent(f,df,x0, gam, 1.e-6))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}