lec/jupyter/2020-04-24.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture notes for 2020-04-24\n",
    "\n",
    "## Broadening the Basin\n",
    "\n",
    "All the methods we have so far discussed for solving nonlinear equations\n",
    "or optimization problems have the form \n",
    "$$\n",
    "x_{k+1} = x_k + \\alpha_k p_k\n",
    "$$\n",
    "where $\\alpha_k$ is a *step size* and $p_k$ is a *search direction*.\n",
    "We have described a wide variety of methods for choosing\n",
    "the search directions $p_k$. We have also analyzed several of these\n",
    "methods (or at least pointed to their analysis) under the assumption\n",
    "that the step sizes were chosen to be $\\alpha_k = 1$ (or, in our\n",
    "analysis of gradient descent, $\\alpha_k = \\alpha$ some constant). But so\n",
    "far, our analyses have all come with the caveat that convergence is only\n",
    "assured for initial guesses that are “good enough.” We call the set of\n",
    "initial guesses for which a nonlinear solver or optimizer converges to a\n",
    "given solution $x_*$ the *basin of convergence* for $x_*$. In a\n",
    "previous lecture, we have already discussed some features that make the\n",
    "basin of convergence large or small for Newton and modified Newton\n",
    "iterations. Today we begin our discussion of *globalization* methods\n",
    "that allow us to guarantee convergence even if we lack a good enough\n",
    "initial guess to make our unguarded iterations converge.\n",
    "\n",
    "In our discussion today, it will be convenient to focus on globalization\n",
    "by *line search methods* that make intelligent, adaptive choices of\n",
    "the step size. Informally, these methods work with any “reasonable”\n",
    "method for choosing search directions $p_k$ (which should at least be\n",
    "descent directions). An *exact line search* method seeks to minimize\n",
    "$g(\\alpha) = \\phi(x_k + \\alpha p_k)$ by a one-dimensional optimization;\n",
    "but it turns out that the work required for exact line search usually\n",
    "does not justify the benefit. Instead, we consider *inexact line search*\n",
    "methods that choose step sizes $\\alpha_k$ such that the methods:\n",
    "\n",
    "-   Make significant progress in the downhill direction ($\\alpha_k$ not\n",
    "    too small).\n",
    "\n",
    "-   But don’t step so far they go back uphill ($\\alpha_k$ not too big).\n",
    "\n",
    "We need to tighten and formalize these conditions a little bit in order\n",
    "to obtain formal convergence results, but this is the right intuition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using LinearAlgebra\n",
    "using Plots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A series of unfortunate examples\n",
    "\n",
    "In order to illustrate the conditions we will require – and the limits\n",
    "of our approach – we will first consider three illustrative examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The long march to infinity\n",
    "\n",
    "Consider the one-dimensional objective function\n",
    "$$\n",
    "\\phi(x) = x \\tan^{-1}(x) - \\frac{1}{2} \\log(1+x^2).\n",
    "$$ \n",
    "The first and\n",
    "second derivatives of $\\phi$ are \n",
    "$$\\begin{aligned}\n",
    "  \\phi'(x) &= \\tan^{-1}(x) \\\\\n",
    "  \\phi''(x) &= \\frac{1}{1+x^2}.\n",
    "\\end{aligned}$$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ϕ1(x) = x*atan(x) - log(1+x^2)/2\n",
    "dϕ1(x) = atan(x)\n",
    "Hϕ1(x) = 1/(1+x^2)\n",
    "\n",
    "xx = range(-3, 3, length=100)\n",
    "plot(xx, ϕ1.(xx), legend=false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a convex function\n",
    "with a unique global minimum $\\phi(0) = 0$. To find this minimum, we\n",
    "might first consider Newton’s iteration:\n",
    "$$\n",
    "  x_{k+1} = x_k - \\frac{\\phi'(x)}{\\phi''(x)} = x_k - (1+x_k^2) \\tan^{-1}(x_k).\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 1.0\n",
    "xhist = [x]\n",
    "for k = 1:10\n",
    "    x -= (1+x^2) * atan(x)\n",
    "    push!(xhist, x)\n",
    "end\n",
    "plot(abs.(xhist[xhist .!= 0]), yscale=:log10, legend=false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Newton step is always in a descent direction, and the iteration\n",
    "converges for $|x_0| \\leq \\xi \\approx 1.3917$; here $\\xi$ is the\n",
    "solution to the “anti-fixed-point” equation\n",
    "$$\n",
    "  -\\xi = \\xi - (1+\\xi^2) \\tan^{-1}(\\xi).\n",
    "$$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g(ξ) = 2*ξ-(1+ξ^2)*atan(ξ)\n",
    "dg(ξ) = 1-2*ξ*atan(ξ)\n",
    "ξ = 1.4\n",
    "for k = 1:5\n",
    "    ξ -= g(ξ)/dg(ξ)\n",
    "end\n",
    "println(\"ξ is $ξ; g(ξ)=$(g(ξ))\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For any $|x_0| < \\xi$, the iterates monotonically decrease in magnitude,\n",
    "For any $|x_0| > \\xi$, the iterates blow up, alternating between \n",
    "positive and negative numbers of increasingly wild magnitudes.\n",
    "The Newton step always goes in the right direction, but it goes too far."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = ξ-1e-3\n",
    "xhist = [x]\n",
    "for k = 1:12\n",
    "    x -= (1+x^2) * atan(x)\n",
    "    push!(xhist, x)\n",
    "end\n",
    "plot(abs.(xhist[xhist .!= 0]), yscale=:log10, legend=false)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = ξ+1e-3\n",
    "xhist = [x]\n",
    "for k = 1:12\n",
    "    x -= (1+x^2) * atan(x)\n",
    "    push!(xhist, x)\n",
    "end\n",
    "plot(abs.(xhist).-ξ, yscale=:log10, legend=false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A simple fix, which works in this case, is to check for progress and cut\n",
    "the step in half if it is not obtained; that is, we take\n",
    "$$\n",
    "x_{k+1} = x_k - \\alpha_k \\frac{\\phi'(x_k)}{\\phi''(x_k)}\n",
    "$$\n",
    "where $\\alpha_k$ is the first value $2^{-j}$ for $j = 0, 1, \\ldots$ that\n",
    "guarantees $\\phi(x_{k+1}) < \\phi(x_k)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function backtracking_newton1(x, ϕ, dϕ, Hϕ; nsteps=100, atol=1e-8, monitor=(x, α)->nothing)\n",
    "\n",
    "    α = 1.\n",
    "    p = -dϕ(x)/Hϕ(x)\n",
    "    \n",
    "    for k = 1:nsteps\n",
    "        xnew = x+α*p\n",
    "        if ϕ(xnew) < ϕ(x)  # Progress!\n",
    "\n",
    "            # Accept the step\n",
    "            monitor(x, α)\n",
    "            x = xnew\n",
    "\n",
    "            # Check for convergence\n",
    "            if norm(p) < atol\n",
    "                return x\n",
    "            end\n",
    "            \n",
    "            # Reset step length and recompute Newton step\n",
    "            α = 1.\n",
    "            p = -dϕ(x)/Hϕ(x)\n",
    "\n",
    "        else  # Step did not decrease ϕ\n",
    "\n",
    "            # Try with half a step\n",
    "            α /= 2\n",
    "\n",
    "        end\n",
    "    end\n",
    "    error(\"Did not converge in $nsteps steps\")\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x0 = 10.0\n",
    "xhist = Array{Float64,1}([])\n",
    "αhist = Array{Float64,1}([])\n",
    "function monitor_xα!(x, α)\n",
    "    push!(xhist, x)\n",
    "    push!(αhist, α)\n",
    "end\n",
    "x = backtracking_newton1(x0, ϕ1, dϕ1, Hϕ1, monitor=monitor_xα!)\n",
    "p1 = plot(abs.(xhist[xhist .!= 0.]), yscale=:log10, label=\"err\")\n",
    "p2 = plot(αhist[xhist .!= 0.], label=\"alpha\")\n",
    "plot(p1, p2, layout=@layout [a; b])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1.  Where did the equation for $\\xi$ come from?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Answer*:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Write a monitor function to verify that $\\alpha = 1$ in the call to backtracking Newton on this\n",
    "   problem iff $|x| < \\xi$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Obscure oscillation\n",
    "\n",
    "As a second example, consider minimizing the polynomial\n",
    "$$\n",
    "  \\phi(x) = 19x^2 - 4x^4 + \\frac{7}{9} x^6.\n",
    "$$\n",
    "The relevant derivatives are\n",
    "$$\\begin{aligned}\n",
    "  \\phi'(x) &= 38x - 16x^3 + \\frac{14}{3} x^5 \\\\\n",
    "  \\phi''(x) &= 38 - 48x^2 + \\frac{70}{3} x^4.\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ϕ2(x) = 19*x^2 - 4*x^4 + 7/9*x^6\n",
    "dϕ2(x) = 38*x - 16*x^3 + 14/3*x^5\n",
    "Hϕ2(x) = 38 - 48*x^2 + 70/3*x^4\n",
    "\n",
    "xx = range(-2, 2, length=100)\n",
    "plot(xx, ϕ2.(xx), legend=false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function is convex — the minimum value of $\\phi''(x)$ is about $13.3$ —\n",
    "and there is a unique global minimum at zero. So what happens if we\n",
    "start Newton’s iteration at $x_0 = 1.01$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 1.01\n",
    "xhist = [x]\n",
    "for k = 1:50\n",
    "    x -= dϕ2(x)/Hϕ2(x)\n",
    "    push!(xhist, x)\n",
    "end\n",
    "p1 = plot(ϕ2.(xhist), label=\"Objective\")\n",
    "p2 = plot(xhist, label=\"xk\")\n",
    "plot(p1, p2, layout=@layout [a; b])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we look only at the objective values, we seem to be making progress;\n",
    "each successive iterates is smaller than the preceding one. But the\n",
    "values of $\\phi$ are not converging toward zero, but toward\n",
    "$\\phi(\\pm 1) = 142/9 \\approx 15.778$! The iterates themselves slosh back\n",
    "and forth, converging to a limit cycle where the iteration cycles\n",
    "between $1$ and $-1$.\n",
    "\n",
    "Furthermore, while this polynomial was carefully\n",
    "chosen, the qualitative cycling behavior is robust to small\n",
    "perturbations to the starting guess and to the polynomial coefficients.\n",
    "Though it appears to be making progress, the iteration is well and truly\n",
    "stuck.\n",
    "\n",
    "The moral is that decreasing the function value from step to step is not\n",
    "sufficient. Though just insisting on a decrease in the objective\n",
    "function from step to step will give convergence for many problems, we\n",
    "need a stronger condition to give any sort of guarantee. But this, too,\n",
    "can be fixed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1.  Plot $|\\phi(x)-\\phi(1)|$ and $|x|-1$ on a semilog scale for the above example.  What can you say about the convergence?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Answer*:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. For a general $\\phi$, give a system of two equations in two unknowns that characterizes this type of period-2 cycling in Newton iteration.  For the polynomial in this section, illustrate quadratic convergence of a Newton iteration on the equation for the cycle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Answer*: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The planes of despair\n",
    "\n",
    "As a final example, consider the function\n",
    "$$\\phi(x) = \\exp(-x^2/2)-\\exp(-x^4/4).$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ϕ3(x) = exp(-x^2/2)-exp(-x^4/4)\n",
    "dϕ3(x) = -x*exp(-x^2/2) + x^3*exp(-x^4/4)\n",
    "Hϕ3(x) = (x^2 - 1)*exp(-x^2/2) - (x^6 - 3*x^2)*exp(-x^4/4)\n",
    "\n",
    "xx = range(-3, 3, length=100)\n",
    "p1 = plot(xx, ϕ3.(xx), label=\"phi\")\n",
    "p2 = plot(xx, dϕ3.(xx), label=\"phi'\")\n",
    "plot(p1, p2, layout=@layout [a; b])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function has two global minima close at\n",
    "around $\\pm 0.88749$ separated by a local maximum at zero, and two\n",
    "global maximum around $\\pm 1.8539$. But if we always move in a descent\n",
    "direction, then any iterate that lands outside the interval\n",
    "$[-1.8539, 1.8539]$ dooms the iteration to never enter that interval,\n",
    "and hence never find either of the minima. Instead, most solvers are\n",
    "likely to march off toward infinity until the function is flat enough\n",
    "that the solver decides it has converged and terminates. This is the\n",
    "type of problem that we do *not* solve with globalization, and\n",
    "illustrates why good initial guesses remain important even with\n",
    "globalization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1.  What does a Newton solver with simple backtracking (as above) do if started at $x = 0$ for this function?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Answer*: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking search and the Armijo rule\n",
    "\n",
    "The idea of a backtracking search is to try successively shorter steps\n",
    "until reaching one that makes “good enough” progress. The step sizes\n",
    "have the form $\\alpha \\rho^j$ for $j = 0, 1, 2, \\ldots$ where $\\alpha$\n",
    "is the default step size and $\\rho < 1$ is a backtracking factor (often\n",
    "chosen to be $0.5$). As we saw in our examples, we need a more stringent\n",
    "acceptance condition than just a decrease in the function value —\n",
    "otherwise, we might get unlucky and end up converging to a limit cycle.\n",
    "That stronger condition is known as the *sufficient decrease* or the\n",
    "*Armijo rule*. For optimization, this condition takes the form\n",
    "$$\n",
    "  \\phi(x_k + \\alpha p_k) \\leq \\phi(x_k) + c_1 \\alpha \\phi'(x_k) p_k\n",
    "$$\n",
    "for some $c_1 \\in (0,1)$. Assuming that $p_k$ is a descent direction,\n",
    "this condition can always be satisfied for small enough $\\alpha$, as\n",
    "Taylor expansion gives\n",
    "$$\\\n",
    "  \\phi(x_k + \\alpha p_k) = \\phi(x_k) + \\alpha \\phi'(x_k) p_k + o(\\alpha).\n",
    "$$\n",
    "\n",
    "In practice, it is fine to choose $c_1$ to be quite small; the value of\n",
    "$10^{-4}$ is suggested by several authors. This condition can always be\n",
    "satisfied for small enough choices of $\\alpha$. Such a line search\n",
    "algorithm looks much the same as the naive line search that we described\n",
    "earlier, but with a more complicated termination condition on the line\n",
    "search loop.  The contraction factor $\\rho$ may be chosen a priori\n",
    "(e.g. $\\rho = 0.5$), or it may be chosen dynamically from some range\n",
    "$[\\rho_{\\min}, \\rho_{\\max}]$ where $0 < \\rho_{\\min} < \\rho_{\\max} < 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function backtracking_newton2(x, ϕ, dϕ, Hϕ; nsteps=100, atol=1e-8, monitor=(x, α)->nothing)\n",
    "\n",
    "    α = 1.\n",
    "    p = -dϕ(x)/Hϕ(x)\n",
    "    c1 = 1e-4\n",
    "    \n",
    "    for k = 1:nsteps\n",
    "        xnew = x+α*p\n",
    "        if ϕ(xnew) <= ϕ(x) + c1*α*dot(dϕ(x), p)  # Sufficient progress (per Armijo)!\n",
    "\n",
    "            # Accept the step\n",
    "            monitor(x, α)\n",
    "            x = xnew\n",
    "\n",
    "            # Check for convergence\n",
    "            if norm(p) < atol\n",
    "                return x\n",
    "            end\n",
    "            \n",
    "            # Reset step length and recompute Newton step\n",
    "            α = 1.\n",
    "            p = -dϕ(x)/Hϕ(x)\n",
    "\n",
    "        else  # Step did not decrease ϕ\n",
    "\n",
    "            # Try with half a step\n",
    "            α /= 2\n",
    "\n",
    "        end\n",
    "    end\n",
    "    error(\"Did not converge in $nsteps steps\")\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x0 = 1.01\n",
    "xhist = Array{Float64,1}([])\n",
    "αhist = Array{Float64,1}([])\n",
    "function monitor_xα!(x, α)\n",
    "    push!(xhist, x)\n",
    "    push!(αhist, α)\n",
    "end\n",
    "x = backtracking_newton2(x0, ϕ2, dϕ2, Hϕ2, monitor=monitor_xα!)\n",
    "p1 = plot(abs.(xhist[xhist .!= 0.]), yscale=:log10, label=\"err\")\n",
    "p2 = plot(αhist[xhist .!= 0.], label=\"alpha\")\n",
    "plot(p1, p2, layout=@layout [a; b])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The curvature condition\n",
    "\n",
    "Backtracking line search is not the only way to choose the step length.\n",
    "For example, one can also use methods based on a polynomial\n",
    "approximation to the objective function along the ray defined by the\n",
    "search direction, and this may be a better choice for non-Newton. In\n",
    "this case, we need to guard not only against steps that are too long,\n",
    "but also steps that are too short. To do this, it is helpful to enforce\n",
    "the *curvature condition*\n",
    "$$\n",
    "  \\frac{\\partial \\phi}{\\partial p_k}(x_k+\\alpha p_k) \\geq c_2\n",
    "  \\frac{\\partial \\phi}{\\partial p_k}(x_k)\n",
    "$$\n",
    "for some $0 < c_1 < c_2 < 1$. The curvature condition simply says that if the\n",
    "slope in the $p_k$ direction at a proposed new point is almost the same\n",
    "as the slope at the starting point, then we should keep going downhill!\n",
    "Together, the sufficient descent condition and the curvature conditions\n",
    "are known as the *Wolfe conditions*. Assuming $\\phi$ is at least\n",
    "continuously differentiable and that it is bounded from below along the\n",
    "ray $x_k+\\alpha p_k$, it is always possible to choose a step size\n",
    "$\\alpha$ that satisfies the Wolfe conditions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Armijo and nonlinear equations\n",
    "\n",
    "While the Armijo rule evolved in optimization theory, the same concept\n",
    "of sufficient decrease of the function applies in nonlinear equation\n",
    "solving. To measure progress, we typically monitor the residual norm\n",
    "$\\|f(x)\\|$. If $p_k = -f'(x_k)^{-1} f(x_k)$ is the Newton direction from\n",
    "a point $x_k$, a linear model of $f$ predicts that\n",
    "$$\n",
    "  \\|f(x_k + \\alpha p_k)\\| \\approx\n",
    "  \\|f(x_k) + \\alpha f'(x_k) p_k\\| =\n",
    "  (1-\\alpha) \\|f(x_k)\\|;\n",
    "$$ \n",
    "that is, the predicted decrease is by\n",
    "$\\alpha \\|f(x_k)\\|$. We insist on some fraction of the predicted\n",
    "decrease as a sufficient decrease to accept a step, yielding the\n",
    "condition\n",
    "$$\n",
    "  \\|f(x_k + \\alpha p_k)\\| \\leq (1-c_1 \\alpha) \\|f(x_k)\\|.\n",
    "$$\n",
    "We don’t have to take a Newton step to use this criteria; it is sufficient\n",
    "that the step satisfy an inexact Newton criterion such as\n",
    "$$\n",
    "  \\|f(x_k) + f'(x_k) p_k\\| \\leq \\eta \\|f(x_k)\\|\n",
    "$$\n",
    "for some $\\eta < 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Global convergence\n",
    "\n",
    "In general, if we seek to minimize an objective $\\phi$ that is $C^1$\n",
    "with a Lipschitz first derivative and\n",
    "\n",
    "-   We use one of the line search algorithms sketched above\n",
    "    (backtracking line search or line search satisfying the Wolfe\n",
    "    conditions),\n",
    "\n",
    "-   The steps $p_k$ are *gradient related* ($\\|p_k\\| \\geq m\n",
    "      \\|\\nabla \\phi(x_k)\\|$ for all $k$ – they don’t shrink too fast),\n",
    "\n",
    "-   The angles between $p_k$ and $-\\nabla \\phi(x_k)$ are acute and\n",
    "    uniformly bounded away from away from ninety degrees.\n",
    "\n",
    "-   The iterates are bounded (it is sufficient that the set of points\n",
    "    less than $\\phi(x_0)$ is bounded),\n",
    "\n",
    "then we are guaranteed global convergence to a stationary point. Of\n",
    "course, even with all these conditions, we might converge to a saddle or\n",
    "a local minimizer that is different from the solution we hoped to find;\n",
    "and we are not guaranteed *fast* convergence. So the choice of\n",
    "initial guess, and the choice of iterative methods, still matters a\n",
    "great deal. Nonetheless, the point remains that an appropriately chosen\n",
    "line search can help improve the convergence behavior of the methods we\n",
    "have described so far by quite a bit.\n",
    "\n",
    "We have not described the full range of possible line searches. In\n",
    "addition to algorithms that inexactly minimize the objective with espect\n",
    "to the line search parameter, there has also been some work on\n",
    "*non-monotone* line search algorithms that allow increases in the\n",
    "function values, as long as progress is made in some more averaged sense\n",
    "(e.g. the new point has a objective function value smaller than the\n",
    "maximum objective function for the past few points). This is useful for\n",
    "improving convergence speed on some hard problems, and is useful in the\n",
    "context of particular classes of methods such as spectral projected\n",
    "gradient (about which we will say nothing in this class other than the\n",
    "name).\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.3.1",
   "language": "julia",
   "name": "julia-1.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}