4_unconstrained/FONCs_SOSCs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# First order necessary conditions (multivariate version)\n",
    "\n",
    "A local minimizer is defined as \n",
    "\n",
    "$$ f(\\mathbf{x}^*) \\le f\\left(\\mathbf{x}^* + \\alpha\\mathbf{d}\\right)~\\forall~\\mathrm{small}~\\alpha > 0$$\n",
    "\n",
    "where $\\mathbf{d}$ is the direction vector which points away from $\\mathbf{x}^*$. We define a new function $g$ in terms of $\\alpha$\n",
    "\n",
    "$$g(\\alpha) = f\\left(\\mathbf{x}^* + \\alpha\\mathbf{d}\\right) - f(\\mathbf{x}^*) \\ge 0$$\n",
    "\n",
    "**Background: The mean-value theorem:**\n",
    "\n",
    "if $f$ is a continuous function on the closed interval $[a,b]$ and differentiable on the open interval $(a,b)$, then there exists a point $c\\in(a,b)$ such that the tangent at $c$ is parallel to the secant line through the endpoints $(a,f(a))$ and $(b,f(b))$, that is,\n",
    "\n",
    "$$f'(c)={\\dfrac {f(b)-f(a)}{b-a}}$$\n",
    "\n",
    "Visually, this is represented below:\n",
    "\n",
    "<p style=\"text-align:center;\">\n",
    "    <img src=\"./meanvalue.png\" alt=\"beam 1\" title=\"mean value theorem\" width=\"350px\" align=\"center\" style=\"background-color:white;\"/>\n",
    "</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use the mean value theorem to write the following on the interval $[0,\\alpha]$\n",
    "\n",
    "\\begin{equation}\\tag{1}\n",
    "g(\\alpha) = g(0) + g'(\\beta)\\alpha = g'(\\beta)\\alpha \\ge 0\n",
    "\\end{equation}\n",
    "\n",
    "where $\\beta\\in(0,\\alpha)$\n",
    "\n",
    "we can write $g'(\\beta)$ as a function of a function $v$:\n",
    "\n",
    "$$g(\\beta) = f\\left(\\mathbf{x}^* + \\beta\\mathbf{d}\\right) - f(\\mathbf{x}^*) = f\\left(v(\\beta)\\right) - f(\\mathbf{x}^*)$$\n",
    "\n",
    "using the chain rule for multivariate calculus that states for $f(v(\\beta))$ its derivative is given by $\\nabla f\\cdot v'(\\beta) = \\sum_{i=1}^n \\dfrac{\\partial f}{\\partial x_i}(v(\\beta))v'_i(\\beta)$. We can therefore write:\n",
    "\n",
    "\\begin{equation}\\tag{2}\n",
    "g'(\\beta) = \\sum_{i=1}^n \\dfrac{\\partial f}{\\partial x_i}\\left(\\mathbf{x}^* + \\beta\\mathbf{d}\\right)d_i\n",
    "\\end{equation}\n",
    "\n",
    "since $f(\\mathbf{x}^{*})$ is a constant. Substituting (2) in (1) we get\n",
    "\n",
    "$$g(\\alpha) = \\alpha\\sum_{i=1}^n \\dfrac{\\partial f}{\\partial x_i}\\left(\\mathbf{x}^* + \\beta\\mathbf{d}\\right)d_i \\ge 0$$\n",
    "\n",
    "As $\\beta \\rightarrow 0$ and since $\\alpha > 0$ we get:\n",
    "\n",
    "$$\\sum_{i=1}^n \\dfrac{\\partial f}{\\partial x_i}\\left(\\mathbf{x}^*\\right)d_i \\ge 0~\\forall~\\mathbf{d}\\in\\mathbb{R}^n$$\n",
    "\n",
    "For the above condition to hold, we need\n",
    "\n",
    "$$\\nabla f(\\mathbf{x}^*) = \\mathbf{0}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Second order sufficient conditions (multivariate version)\n",
    "\n",
    "To derive the second order sufficient conditions, we write the second order taylor series expansion of a continuous function $f$ about the point $\\mathbf{x}^* + \\mathbf{d}$\n",
    "\n",
    "$$f\\left(\\mathbf{x}^* + \\mathbf{d}\\right) = f(\\mathbf{x}^*) + \\nabla^\\mathrm{T}f(\\mathbf{x}^*)\\mathbf{d} + \\dfrac{1}{2}\\mathbf{d}^\\mathrm{T}\\nabla^2f(\\mathbf{x}^*)\\mathbf{d} + \\mathrm{O}\\left(\\left|\\left|\\mathbf{d}\\right|\\right|^2\\right)$$\n",
    "\n",
    "since we established from FONCs that $\\nabla f(\\mathbf{x}^*) = \\mathbf{0}$. This gives\n",
    "\n",
    "$$f\\left(\\mathbf{x}^* + \\mathbf{d}\\right) - f(\\mathbf{x}^*) = \\dfrac{1}{2}\\mathbf{d}^\\mathrm{T}\\nabla^2f(\\mathbf{x}^*)\\mathbf{d} + \\mathrm{O}\\left(\\left|\\left|\\mathbf{d}\\right|\\right|^2\\right)$$\n",
    "\n",
    "A special property of positive-definite matrices $\\mathbf{A}$ is that $\\mathbf{x}^\\mathrm{T}\\mathbf{A}\\mathbf{x} \\ge \\dfrac{1}{2}\\lambda_\\mathrm{min}(\\mathbf{A})\\left|\\left|\\mathbf{x}\\right|\\right|^2$, where $\\lambda_\\mathrm{min}$ is the smallest eigenvalue of $\\mathbf{A}$. We can now write as $\\left|\\left|\\mathbf{d}\\right|\\right| \\rightarrow 0$:\n",
    "\n",
    "\\begin{align}\n",
    "    f\\left(\\mathbf{x}^* + \\mathbf{d}\\right) - f(\\mathbf{x}^*) \\ge \\dfrac{1}{2}\\lambda_\\mathrm{min}\\left(\\nabla^2f(\\mathbf{x}^*)\\right)\\left|\\left|\\mathbf{d}\\right|\\right|^2 + \\mathrm{O}\\left(\\left|\\left|\\mathbf{d}\\right|\\right|^2\\right) \\\\\n",
    "    f\\left(\\mathbf{x}^* + \\mathbf{d}\\right) - f(\\mathbf{x}^*) \\ge \\left|\\left|\\mathbf{d}\\right|\\right|^2 \\left(\\dfrac{1}{2}\\lambda_\\mathrm{min}\\left(\\nabla^2f(\\mathbf{x}^*)\\right) + \\dfrac{\\mathrm{O}\\left(\\left|\\left|\\mathbf{d}\\right|\\right|^2\\right)}{\\left|\\left|\\mathbf{d}\\right|\\right|^2}\\right) \\rightarrow 0\n",
    "\\end{align}\n",
    "\n",
    "since the error $\\mathrm{O}\\left(\\left|\\left|\\mathbf{d}\\right|\\right|^2\\right)$ decays to zero much faster than $\\left|\\left|\\mathbf{d}\\right|\\right|^2$.\n",
    "\n",
    "We finally have\n",
    "\n",
    "$$f\\left(\\mathbf{x}^* + \\mathbf{d}\\right) - f(\\mathbf{x}^*) \\ge 0~\\forall~(\\mathrm{small})~\\mathbf{d}\\in\\mathbb{R}^n$$\n",
    "\n",
    "which means that $\\mathbf{x^*}$ is a local minimizer if and only if the matrix $\\nabla^2f(\\mathbf{x}^*)$ is positive definite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convex functions and sets\n",
    "\n",
    "A function $f : \\mathcal{S} \\rightarrow \\mathbb{R}$ defined on a nonempty convex set $\\mathcal{S} \\subseteq \\mathbb{R}$ is (strictly) convex if and only if for every pair of points $\\mathbf{x},\\mathbf{y} \\in \\mathcal{S}$\n",
    "\n",
    "\\begin{equation}\\tag{3}\n",
    "f(\\mathbf{x}) = f(\\alpha\\mathbf{x} + (1-\\alpha)\\mathbf{y}) \\le \\alpha f(\\mathbf{x}) + (1-\\alpha)f(\\mathbf{y})~\\forall~\\alpha \\in [0,1]\n",
    "\\end{equation}\n",
    "\n",
    "This is visually represented below:\n",
    "\n",
    "<p style=\"text-align:center;\">\n",
    "    <img src=\"./convex_function.png\" alt=\"beam 1\" title=\"a convex function\" width=\"350px\" align=\"center\" style=\"background-color:white;\"/>\n",
    "</p>\n",
    "\n",
    "**Theorem 1:** if $f$ is a convex function defined on a convex set $\\mathcal{S} \\subseteq \\mathbb{R}$ then a stationary point $\\mathbf{x^*}$ is a global minimizer\n",
    "\n",
    "**Proof:** Suppose $\\mathbf{x*}$ is **not** a global minimum, then $\\exists~\\mathbf{y} \\in \\mathcal{S}$ such that \n",
    "\n",
    "\\begin{equation}\\tag{4}\n",
    "f(\\mathbf{y}) < f(\\mathbf{x^*})\n",
    "\\end{equation}\n",
    "\n",
    "(3) tells us that for $f(\\mathbf{y})$ we have:\n",
    "\n",
    "\\begin{align}\\tag{5}\n",
    "f(\\alpha\\mathbf{y} + (1-\\alpha)\\mathbf{x^*}) \\le \\alpha f(\\mathbf{y}) + (1-\\alpha)f(\\mathbf{x^*})\\\\\n",
    "f(\\mathbf{y}) \\le \\alpha f(\\mathbf{y}) + (1-\\alpha)f(\\mathbf{x^*}) < f(\\mathbf{x}^*)\n",
    "\\end{align}\n",
    "\n",
    "we can rewrite (5) as \n",
    "\n",
    "\\begin{equation}\n",
    "f(\\mathbf{x^*} + \\alpha(\\mathbf{y} - \\mathbf{x}^*)) < f(\\mathbf{x^*})\n",
    "\\end{equation}\n",
    "\n",
    "For this to hold true, for all $\\alpha$, $\\mathbf{x}^*$ cannot be a local minimum\n",
    "\n",
    "**Theorem 2:** The first order taylor series expansion underestimates a convex function $f$\n",
    "\n",
    "* $f(\\mathbf{y}) \\ge f(\\mathbf{x}) +\\nabla^\\mathrm{T}f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x})$\n",
    "* $f(\\mathbf{y}) > f(\\mathbf{x}) +\\nabla^\\mathrm{T}f(\\mathbf{y} - \\mathbf{x})$, if strictly convex\n",
    "\n",
    "This graphically shown below:\n",
    "\n",
    "<p style=\"text-align:center;\">\n",
    "    <img src=\"./convex_function_taylor.png\" alt=\"beam 1\" title=\"a convex function with taylor series approximation\" width=\"350px\" align=\"center\" style=\"background-color:white;\"/>\n",
    "</p>\n",
    "\n",
    "**Proof:** Suppose $f$ is a convex function\n",
    "\n",
    "\\begin{align*}\n",
    "f(\\mathbf{x} + \\alpha(\\mathbf{y} - \\mathbf{x})) & = f((1-\\alpha)\\mathbf{x} + \\alpha\\mathbf{y})\\\\\n",
    "                                                & \\le (1-\\alpha) f(\\mathbf{x}) + \\alpha f(\\mathbf{y})\n",
    "\\end{align*}\n",
    "\n",
    "we have\n",
    "\n",
    "$$ \\dfrac{f(\\mathbf{x} + \\alpha(\\mathbf{y} - \\mathbf{x})) - f(\\mathbf{x})}{\\alpha} \\le f(\\mathbf{y}) - f(\\mathbf{x})$$\n",
    "\n",
    "from the definition of the derivative, as $\\alpha \\rightarrow 0$ we have\n",
    "\n",
    "$$ \\nabla^\\mathrm{T}f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x}) \\le f(\\mathbf{y}) - f(\\mathbf{x})$$\n",
    "\n",
    "rearranging\n",
    "\n",
    "$$ f(\\mathbf{y}) \\ge f(\\mathbf{x}) + \\nabla^\\mathrm{T}f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x})$$\n",
    "\n",
    "**Theorem 3:** $f$ is\n",
    "\n",
    "* convex if and only if $\\nabla^2f(\\mathbf{x}) \\ge 0~\\forall~\\mathbf{x}\\in\\mathcal{S}$\n",
    "* strictly convex if and only if $\\nabla^2f(\\mathbf{x}) > 0~\\forall~\\mathbf{x}\\in\\mathcal{S}$\n",
    "\n",
    "**Proof:** The second order taylor series expansion of $f$ about $\\mathbf{y}$ is\n",
    "\n",
    "$$\n",
    "f(\\mathbf{y}) = f(\\mathbf{x}) + \\nabla^\\mathrm{T}f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x}) + \\dfrac{1}{2}(\\mathbf{y} - \\mathbf{x})^\\mathrm{T}\\nabla^2f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x})\n",
    "$$\n",
    "\n",
    "from theorem 2 we have\n",
    "\\begin{align*}\n",
    "f(\\mathbf{y}) & \\le f(\\mathbf{y}) + \\dfrac{1}{2}(\\mathbf{y} - \\mathbf{x})^\\mathrm{T}\\nabla^2f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x})\\\\\n",
    "0 & \\le \\dfrac{1}{2}(\\mathbf{y} - \\mathbf{x})^\\mathrm{T}\\nabla^2f(\\mathbf{x})(\\mathbf{y} - \\mathbf{x})~\\forall~\\mathbf{x},\\mathbf{y}\\in\\mathcal{S}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "The above is a property of positive definite matrices. \n",
    "Reminder: A square, symmetric matrix  $A \\in \\mathbb{R}^{n\\times n}$ is positive definite if the quadratic form $x^{\\mathrm{T}}Ax$ can be shown to be positive  $\\forall~~ x \\in \\mathbb{R}^n$."
   ]
  }
 ],
 "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.8.10"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  },
  "vscode": {
   "interpreter": {
    "hash": "222976e2ab69f3c3e71eef83592af0a5f998b8dfe881aa23eb5e4321225b3133"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}