first-order.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# First Order\n",
    "\n",
    "This notebook was automatically generated from the Algorithms for Optimization source code. Each cell generates a figure from the original text. While this code is not optimized for use in lectures, we provide it here to be adapted for such projects. We hope you find it useful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "include(\"support_code.jl\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "\n",
    "p = let\n",
    "\tfunction secant_method(df, x1, x2, ϵ)\n",
    "\t    df1 = df(x1)\n",
    "\n",
    "\t    delta = Inf\n",
    "\t    while abs(delta) > ϵ\n",
    "\t    \tdf2 = df(x2)\n",
    "\t        delta = (x2 - x1)/(df2 - df1)*df2\n",
    "\t        x1, x2, df1 = x2, x2 - delta, df2\n",
    "\t    end\n",
    "\t    x2\n",
    "\tend\n",
    "\n",
    "\tf = (x,y) -> x^2 + y^2 + y*sin(x)\n",
    "\tdf = (x,y) -> [2x + y*cos(x), 2y + sin(x)]\n",
    "\n",
    "\txdomain = (-2, 4)\n",
    "\tydomain = (-2, 4)\n",
    "\n",
    "\tp0 = (-0.5, 3.5)\n",
    "\tpts = Tuple{Float64,Float64}[p0]\n",
    "\tfor i in 1 : 3\n",
    "\t\tx,y = pts[end]\n",
    "\t\tdp = df(x, y)\n",
    "\t\tvdp = VecE2{Float64}(-dp[1], -dp[2])\n",
    "\n",
    "\t\tf1d = a -> begin\n",
    "\t\t\tx2 = x + a*dp[1]\n",
    "\t\t\ty2 = y + a*dp[2]\n",
    "\n",
    "\t\t\tda = df(x2, y2)\n",
    "\t\t\tpa = VecE2{Float64}(da[1], da[2])\n",
    "\t\t\tproj(pa, vdp, Float64)\n",
    "\t\tend\n",
    "\t\talpha = secant_method(f1d, 0.0, 1.0, 0.001)\n",
    "\n",
    "\t\tpush!(pts, (x + alpha*dp[1], y + alpha*dp[2]))\n",
    "\tend\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=0:2:10, style=\"width=\\\\columnwidth\"))\n",
    "\tpush!(plots, Plots.Linear3([p[1] for p in pts], [p[2] for p in pts], [f(p[1], p[2]) for p in pts], style=\"black, solid, mark=*, mark size = 1, mark options={draw=black}\"))\n",
    "\n",
    "\tg = GroupPlot(2, 1)\n",
    "\tpush!(g, Axis(plots, height=\"5cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", zlabel=L\"y\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false\"))\n",
    "\tpush!(g, Axis(plots, width=\"5cm\", height=\"5cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, axis equal, view={0}{90}\"))\n",
    "\tg\n",
    "end\n",
    "\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "using LinearAlgebra\n",
    "\n",
    "pts_gradient_banana = Tuple{Float64,Float64}[]\n",
    "\n",
    "p = let\n",
    "\tfunction secant_method(df, x1, x2, ϵ)\n",
    "\t    df1 = df(x1)\n",
    "\n",
    "\t    delta = Inf\n",
    "\t    while abs(delta) > ϵ\n",
    "\t    \tdf2 = df(x2)\n",
    "\t        delta = (x2 - x1)/(df2 - df1)*df2\n",
    "\t        x1, x2, df1 = x2, x2 - delta, df2\n",
    "\t    end\n",
    "\t    x2\n",
    "\tend\n",
    "\n",
    "\n",
    "\tf = (x,y) -> (1-x)^2 + 5*(y - x^2)^2\n",
    "\tdf = (x,y) -> [2*(10*x^3-10*x*y+x-1), 10*(y-x^2)]\n",
    "\n",
    "\txdomain = (-2, 2)\n",
    "\tydomain = (-2, 2)\n",
    "\n",
    "\tp0 = (-1, -1)\n",
    "\tpts = Tuple{Float64,Float64}[p0]\n",
    "\tfor i in 1 : 10\n",
    "\t\tx,y = pts[end]\n",
    "\t\tdp = normalize(-VecE2{Float64}(df(x, y)...))\n",
    "\n",
    "\t\tf1d = a -> begin\n",
    "\t\t\tx2 = x + a*dp.x\n",
    "\t\t\ty2 = y + a*dp.y\n",
    "\n",
    "\t\t\tda = df(x2, y2)\n",
    "\t\t\tpa = VecE2{Float64}(da[1], da[2])\n",
    "\t\t\tproj(pa, dp, Float64)\n",
    "\t\tend\n",
    "\t\talpha = secant_method(f1d, 0.0, 1.0, 0.0001)\n",
    "\t\tpush!(pts, (x + alpha*dp.x, y + alpha*dp.y))\n",
    "\tend\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=[1,2,3,5,10,20,50,100], style=\"width=\\\\columnwidth\"))\n",
    "\tpush!(plots, Plots.Linear3([p[1] for p in pts], [p[2] for p in pts], [f(p[1], p[2]) for p in pts], style=\"black, solid, mark=none\"))\n",
    "\n",
    "\tappend!(pts_gradient_banana, pts)\n",
    "\n",
    "\tAxis(plots, width=\"8cm\", height=\"8cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, axis equal, view={0}{90}\")\n",
    "end\n",
    "\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "abstract type DescentMethod end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "p = let\n",
    "\n",
    "\tA = Float64[1 -0.9; -0.9 1]\n",
    "\tb = Float64[0, 0]\n",
    "\tf = x -> (x'*A*x)[1]\n",
    "\t∇f = x -> 2*A'*x\n",
    "\n",
    "\tx = Float64[-1.1, -1.8]\n",
    "\tpts = Vector{Float64}[x]\n",
    "\n",
    "\tfunction get_optimal_step_size(d, A, b)\n",
    "\t\treturn -(d'*(A*x+b))[1]/(d'*A*d)[1]\n",
    "\tend\n",
    "\n",
    "\t# FIRST ITERATION\n",
    "\td = -∇f(x)\n",
    "\tα = get_optimal_step_size(d, A, b)\n",
    "\tx += α*d\n",
    "\tpush!(pts, x)\n",
    "\n",
    "\t# SECOND ITERATION\n",
    "\tg = ∇f(x)\n",
    "\tβ = (g'*A*d)[1] / (d'*A*d)[1]\n",
    "\td = -g + β*d\n",
    "\tα = get_optimal_step_size(d, A, b)\n",
    "\tx += α*d\n",
    "\tpush!(pts, x)\n",
    "\n",
    "\txdomain = (-2, 2)\n",
    "\tydomain = (-2, 2)\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain))\n",
    "\tpush!(plots, Plots.Linear3([x[1] for x in pts],\n",
    "\t                           [x[2] for x in pts],\n",
    "\t                           [f(x) for x in pts], style=\"black, solid, mark=*, mark size = 1, mark options={draw=black}\"))\n",
    "\tpush!(plots, Plots.Node(L\"1\", pts[1][1], pts[1][2], style=\"right\"))\n",
    "\tpush!(plots, Plots.Node(L\"2\", pts[2][1], pts[2][2], style=\"left\"))\n",
    "\tpush!(plots, Plots.Node(L\"3\", pts[3][1], pts[3][2], style=\"right\"))\n",
    "\n",
    "\n",
    "\tAxis(plots, width=\"\\\\columnwidth\", height=\"\\\\columnwidth\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, axis equal, view={0}{90}\")\n",
    "end\n",
    "\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "\n",
    "p = let\n",
    "\tfunction secant_method(df, x1, x2, ϵ)\n",
    "\t    df1 = df(x1)\n",
    "\n",
    "\t    delta = Inf\n",
    "\t    while abs(delta) > ϵ\n",
    "\t    \tdf2 = df(x2)\n",
    "\t        delta = (x2 - x1)/(df2 - df1)*df2\n",
    "\t        x1, x2, df1 = x2, x2 - delta, df2\n",
    "\t    end\n",
    "\t    x2\n",
    "\tend\n",
    "\n",
    "\tf = x -> (1-x[1])^2 + 5*(x[2] - x[1]^2)^2\n",
    "\tdf = x -> [2*(10*x[1]^3-10*x[1]*x[2]+x[1]-1), 10*(x[2]-x[1]^2)]\n",
    "\n",
    "\tx0 = Float64[-1, -1]\n",
    "\tpts = Vector{Float64}[x0]\n",
    "\tg0 = df(x0)\n",
    "\td0 = -g0\n",
    "\tf1d = a -> begin\n",
    "\t\tda = df(x0 + a*d0)\n",
    "\t\tproj(VecE2{Float64}(da[1], da[2]), VecE2{Float64}(d0[1], d0[2]), Float64)\n",
    "\tend\n",
    "\talpha = secant_method(f1d, 0.0, 0.1, 0.0001) # NOTE: is sensitive to the value of 0.1, does not work with 1.0!\n",
    "\tpush!(pts, x0 + alpha*d0)\n",
    "\n",
    "\tfor i in 1 : 5\n",
    "\t\tx = pts[end]\n",
    "\t\tg1 = df(x)\n",
    "\t\tβ = max(0.0, dot(g1, g1-g0)/dot(g0,g0))\n",
    "\t\td1 = -g1 + β*d0\n",
    "\n",
    "\t\tf1d = a -> begin\n",
    "\t\t\tda = df(x + a*d1)\n",
    "\t\t\tproj(VecE2{Float64}(da[1], da[2]), VecE2{Float64}(d1[1], d1[2]), Float64)\n",
    "\t\tend\n",
    "\t\talpha = secant_method(f1d, 0.0, 0.1, 0.0001)\n",
    "\t\tpush!(pts, x + alpha*d1)\n",
    "\n",
    "\t\td0 = d1\n",
    "\t\tg0 = g1\n",
    "\tend\n",
    "\n",
    "\txdomain = (-2, 2)\n",
    "\tydomain = (-2, 2)\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=[1,2,3,5,10,20,50,100], style=\"width=\\\\columnwidth\"))\n",
    "\tpush!(plots, Plots.Linear3([p[1] for p in pts_gradient_banana],\n",
    "\t                           [p[2] for p in pts_gradient_banana],\n",
    "\t                           [f([p[1], p[2]]) for p in pts_gradient_banana], style=\"gray, solid, mark=none\"))\n",
    "\tpush!(plots, Plots.Linear3([p[1] for p in pts], [p[2] for p in pts], [f(p) for p in pts], style=\"black, solid, mark=none\"))\n",
    "\n",
    "\n",
    "\tAxis(plots, width=\"8cm\", height=\"8cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, axis equal, view={0}{90}\")\n",
    "end\n",
    "\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "p = let\n",
    "\tAxis([\n",
    "\t\tPlots.Linear(x->-exp(-x^2), (-4,4), style=\"solid, black, mark=none\"),\n",
    "\t\tPlots.Linear(x->-exp(-x^2), (-4,-2.5), style=\"solid, thick, pastelBlue, mark=none\"),\n",
    "\t\tPlots.Linear(x->-exp(-x^2), (2.5,4), style=\"solid, thick, pastelBlue, mark=none\"),\n",
    "\t\t], xlabel=L\"x\", ylabel=L\"-\\exp(-x^2)\", width=\"9cm\", style=\"enlarge x limits=0\"\n",
    "\t)\n",
    "end\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "\n",
    "struct GradientDescent <: DescentMethod\n",
    "\tα\n",
    "end\n",
    "init!(M::GradientDescent, f, ∇f, x) = M\n",
    "function step!(M::GradientDescent, f, ∇f, x)\n",
    "\tα, g = M.α, ∇f(x)\n",
    "\treturn x - α*g\n",
    "end\n",
    "mutable struct Momentum <: DescentMethod\n",
    "\tα # learning rate\n",
    "\tβ # momentum decay\n",
    "\tv # momentum\n",
    "end\n",
    "function init!(M::Momentum, f, ∇f, x)\n",
    "\tM.v = zeros(length(x))\n",
    "\treturn M\n",
    "end\n",
    "function step!(M::Momentum, f, ∇f, x)\n",
    "\tα, β, v, g = M.α, M.β, M.v, ∇f(x)\n",
    "\tv[:] = β*v - α*g\n",
    "\treturn x + v\n",
    "end\n",
    "\n",
    "p = let\n",
    "\tf = x -> (1-x[1])^2 + 100*(4x[2] - x[1]^2)^2\n",
    "\t∇f = x -> [2*(200x[1]^3 - 800x[1]*x[2] + x[1] - 1), -800*(x[1]^2 - 4x[2])]\n",
    "\n",
    "\txdomain = (-3, 2)\n",
    "\tydomain = (-0.5, 2)\n",
    "\n",
    "\tfunction this_step!(M::DescentMethod, v::VecE2{Float64})\n",
    "\t    x = Float64[v.x, v.y]\n",
    "\t    return VecE2{Float64}(step!(M, f, ∇f, x)...)\n",
    "\tend\n",
    "\tfunction run_descent_method(M::DescentMethod, x₀::VecE2{Float64}, N::Int)\n",
    "\t    pts = [x₀]\n",
    "\t    init!(M, f, ∇f, Float64[x₀.x, x₀.y])\n",
    "\t    for i in 1 : N\n",
    "\t        push!(pts, this_step!(M, pts[end]))\n",
    "\t    end\n",
    "\t    return pts\n",
    "\tend\n",
    "\tfunction get_descent_plot(pts::Vector{VecE2{Float64}}, name, color::String=\"black\")\n",
    "\t    Plots.Linear([P.x for P in pts], [P.y for P in pts], style=\"thick, $color, solid, mark=none, line join=round\", legendentry=name) #$\n",
    "\tend\n",
    "\n",
    "\tx₀ = VecE2{Float64}(-2,1.5)\n",
    "\tN = 40\n",
    "\n",
    "\tstuff = Tuple{DescentMethod, String, String}[]\n",
    "\tpush!(stuff, (GradientDescent(0.0003), \"gradient descent\", \"pastelRed\"))\n",
    "\tpush!(stuff, (Momentum(0.0003, 0.9, zeros(2)), \"momentum\", \"black\"))\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=[2,10,50,200,500], style=\"forget plot, width=\\\\columnwidth\", xbins=150, ybins=150))\n",
    "\tfor (M, name, color) in stuff\n",
    "\t    pts = run_descent_method(M, x₀, N)\n",
    "\t    push!(plots, get_descent_plot(pts, name, color))\n",
    "\tend\n",
    "\tAxis(plots, width=\"12cm\", height=\"6cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, view={0}{90}, legend pos=outer north east\")\n",
    "end\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "\n",
    "mutable struct NesterovMomentum <: DescentMethod\n",
    "\tα # learning rate\n",
    "\tβ # momentum decay\n",
    "\tv # momentum\n",
    "end\n",
    "function init!(M::NesterovMomentum, f, ∇f, x)\n",
    "\tM.v = zeros(length(x))\n",
    "\treturn M\n",
    "end\n",
    "function step!(M::NesterovMomentum, f, ∇f, x)\n",
    "\tα, β, v = M.α, M.β, M.v\n",
    "\tv[:] = β*v - α*∇f(x + β*v)\n",
    "\treturn x + v\n",
    "end\n",
    "\n",
    "p = let\n",
    "\tf = x -> (1-x[1])^2 + 100*(4x[2] - x[1]^2)^2\n",
    "\t∇f = x -> [2*(200x[1]^3 - 800x[1]*x[2] + x[1] - 1), -800*(x[1]^2 - 4x[2])]\n",
    "\n",
    "\txdomain = (-3, 2)\n",
    "\tydomain = (-0.5, 2)\n",
    "\n",
    "\tfunction this_step!(M::DescentMethod, v::VecE2{Float64})\n",
    "\t    x = convert(Vector{Float64}, v)\n",
    "\t    return VecE2{Float64}(step!(M, f, ∇f, x))\n",
    "\tend\n",
    "\tfunction run_descent_method(M::DescentMethod, x₀::VecE2{Float64}, N::Int)\n",
    "\t    pts = [x₀]\n",
    "\t    init!(M, f, ∇f, convert(Vector{Float64}, x₀))\n",
    "\t    for i in 1 : N\n",
    "\t        push!(pts, this_step!(M, pts[end]))\n",
    "\t    end\n",
    "\t    return pts\n",
    "\tend\n",
    "\tfunction get_descent_plot(pts::Vector{VecE2{Float64}}, name, color::String=\"black\")\n",
    "\t    Plots.Linear([P.x for P in pts], [P.y for P in pts], style=\"thick, $color, solid, mark=none, line join=round\", legendentry=name) #$\n",
    "\tend\n",
    "\n",
    "\tx₀ = VecE2{Float64}(-2,1.5)\n",
    "\tdm = GradientDescent(0.0003)\n",
    "\tN = 40\n",
    "\n",
    "\tstuff = Tuple{DescentMethod, String, String}[]\n",
    "\t# push!(stuff, (GradientDescent(0.0003), \"gradient descent\", \"black\"))\n",
    "\tpush!(stuff, (Momentum(0.0003, 0.9, zeros(2)), \"momentum\", \"black\"))\n",
    "\tpush!(stuff, (NesterovMomentum(0.0002, 0.92, zeros(2)), \"Nesterov momentum\", \"pastelRed\"))\n",
    "\t# push!(stuff, (Adagrad(0.1, 1e-8, zeros(2)), \"Adagrad\", \"green\"))\n",
    "\t# push!(stuff, (RMSProp(0.65, 0.45, 1e-8, zeros(2)), \"RMSProp\", \"green\"))\n",
    "\t# push!(stuff, (Adadelta(0.8, 0.8, 1e-3, zeros(2), zeros(2)), \"Adadelta\", \"orange\"))\n",
    "\t# push!(stuff, (Adam(0.8, 0.9, 0.9, 1e-8, 0, zeros(2), zeros(2)), \"Adam\", \"purple\"))\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=[2,10,50,200,500], style=\"forget plot, width=\\\\columnwidth\", xbins=150, ybins=150))\n",
    "\tfor (M, name, color) in stuff\n",
    "\t    pts = run_descent_method(M, x₀, N)\n",
    "\t    push!(plots, get_descent_plot(pts, name, color))\n",
    "\tend\n",
    "\tAxis(plots, width=\"12cm\", height=\"6cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, view={0}{90}, legend pos=outer north east\")\n",
    "end\n",
    "plot(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Vec\n",
    "\n",
    "mutable struct HyperGradientDescent <: DescentMethod\n",
    "\tα0 # initial learning rate\n",
    "\tμ # learning rate of the learning rate\n",
    "\tα # current learning rate\n",
    "\tg_prev # previous gradient\n",
    "end\n",
    "function init!(M::HyperGradientDescent, f, ∇f, x)\n",
    "\tM.α = M.α0\n",
    "\tM.g_prev = zeros(length(x))\n",
    "\treturn M\n",
    "end\n",
    "function step!(M::HyperGradientDescent, f, ∇f, x)\n",
    "\tα, μ, g, g_prev = M.α, M.μ, ∇f(x), M.g_prev\n",
    "\tα = α + μ*(g⋅g_prev)\n",
    "\tM.g_prev, M.α = g, α\n",
    "\treturn x - α*g\n",
    "end\n",
    "\n",
    "mutable struct HyperNesterovMomentum <: DescentMethod\n",
    "\tα0 # initial learning rate\n",
    "\tμ # learning rate of the learning rate\n",
    "\tβ # momentum decay\n",
    "\tv # momentum\n",
    "\tα # current learning rate\n",
    "\tg_prev # previous gradient\n",
    "end\n",
    "function init!(M::HyperNesterovMomentum, f, ∇f, x)\n",
    "\tM.α = M.α0\n",
    "\tM.v = zeros(length(x))\n",
    "\tM.g_prev = zeros(length(x))\n",
    "\treturn M\n",
    "end\n",
    "function step!(M::HyperNesterovMomentum, f, ∇f, x)\n",
    "\tα, β, μ = M.α, M.β, M.μ\n",
    "\tv, g, g_prev = M.v, ∇f(x), M.g_prev\n",
    "\tα = α - μ*(g⋅(-g_prev - β*v))\n",
    "\tv[:] = β*v + g\n",
    "\tM.g_prev, M.α = g, α\n",
    "\treturn x - α*(g + β*v)\n",
    "end\n",
    "\n",
    "p = let\n",
    "\tf = x -> (1-x[1])^2 + 100*(4x[2] - x[1]^2)^2\n",
    "\t∇f = x -> [2*(200x[1]^3 - 800x[1]*x[2] + x[1] - 1), -800*(x[1]^2 - 4x[2])]\n",
    "\n",
    "\txdomain = (-3, 2)\n",
    "\tydomain = (-0.5, 2)\n",
    "\n",
    "\tfunction this_step!(M::DescentMethod, v::VecE2{Float64})\n",
    "\t    x = convert(Vector{Float64}, v)\n",
    "\t    return VecE2{Float64}(step!(M, f, ∇f, x))\n",
    "\tend\n",
    "\tfunction run_descent_method(M::DescentMethod, x₀::VecE2{Float64}, N::Int)\n",
    "\t    pts = [x₀]\n",
    "\t    init!(M, f, ∇f, convert(Vector{Float64}, x₀))\n",
    "\t    for i in 1 : N\n",
    "\t        push!(pts, this_step!(M, pts[end]))\n",
    "\t    end\n",
    "\t    return pts\n",
    "\tend\n",
    "\tfunction get_descent_plot(pts::Vector{VecE2{Float64}}, name, color::String=\"black\")\n",
    "\t    Plots.Linear([P.x for P in pts], [P.y for P in pts], style=\"thick, $color, solid, mark=none, line join=round\", legendentry=name) #$\n",
    "\tend\n",
    "\n",
    "\tx₀ = VecE2{Float64}(-2,1.5)\n",
    "\tdm = GradientDescent(0.0003)\n",
    "\tN = 40\n",
    "\n",
    "\tstuff = Tuple{DescentMethod, String, String}[]\n",
    "\tpush!(stuff, (HyperGradientDescent(0.0004, 8e-13, NaN, zeros(2)), \"hypergradient\", \"black\"))\n",
    "\tpush!(stuff, (HyperNesterovMomentum(0.00023, 1e-12, 0.93, zeros(2), NaN, zeros(2)), \"hyper-Nesterov\", \"pastelRed\"))\n",
    "\n",
    "\tplots = Plots.Plot[]\n",
    "\tpush!(plots, Plots.Contour(f, xdomain, ydomain, levels=[2,10,50,200,500], style=\"forget plot, width=\\\\columnwidth\", xbins=150, ybins=150))\n",
    "\tfor (M, name, color) in stuff\n",
    "\t    pts = run_descent_method(M, x₀, N)\n",
    "\t    push!(plots, get_descent_plot(pts, name, color))\n",
    "\tend\n",
    "\tAxis(plots, width=\"12cm\", height=\"6cm\", xlabel=L\"x_1\", ylabel=L\"x_2\", style=\"xtick=\\\\empty, ytick=\\\\empty, contour/labels=false, view={0}{90}, legend pos=outer north east\")\n",
    "end\n",
    "plot(p)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.1",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}