Frontmatter

If you are publishing this notebook on the web, you can set the parameters below to provide HTML metadata. This is useful for search engines and social media.

Notebook for 2023-03-24

The topic for this lecture is optimization in 1D. We concretely consider minimizing $-\sin(x)$ on the interval $[0, 2]$. Of course, we know in advance that the solution to this problem is at $\pi/2$, but it is fun to see what different algorithms do.
md"""
# Notebook for 2023-03-24

The topic for this lecture is optimization in 1D. We concretely consider minimizing $-\sin(x)$ on the interval $[0, 2]$. Of course, we know in advance that the solution to this problem is at $\pi/2$, but it is fun to see what different algorithms do.
"""
141 ms
using Plots
2.6 s
using LinearAlgebra
244 μs
begin
xx = range(0.0, 2.0, length=100)
ϕ(x) = -sin(x)
g(x) = -cos(x)
dg(x) = sin(x)
plot(xx, ϕ.(xx))
end
3.6 s

Newton's iteration

To minimize a differentiable function $\phi(x)$, we want to solve the stationary equation $\phi'(x) = 0$. We know how to do this by Newton's method for nonlinear equations. Of course, we also know Newton's method can fail to converge without safeguarding! But in this case, it might also converge just fine, but not to a minimizer.

I suggest you add a monitor function and plot the convergence!
md"""
## Newton's iteration

To minimize a differentiable function $\phi(x)$, we want to solve the stationary equation $\phi'(x) = 0$. We know how to do this by Newton's method for nonlinear equations. Of course, we also know Newton's method can fail to converge without safeguarding! But in this case, it might also converge just fine, but not to a minimizer.

I suggest you add a monitor function and plot the convergence!
"""
183 μs
newton_opt1d (generic function with 1 method)
function newton_opt1d(g, dg, x; gtol=1e-8, maxiter=100)
for iter=1:maxiter
gx = g(x)
if abs(gx) < gtol
return x
end
dx = gx/dg(x)
x -= dx
end
x
end
1.3 ms
1.5707963267954879
newton_opt1d(g, dg, 1.0)
15.6 ms
-1.5707963267954879
newton_opt1d(g, dg, -1.0)
28.1 μs

Golden section

As described in the notes, golden section search is a bisection-like solver for finding a minimum of a unimodal function (so one local minimum) in 1D.
md"""
## Golden section

As described in the notes, golden section search is a bisection-like solver for finding a minimum of a unimodal function (so one local minimum) in 1D.
"""
142 μs
golden_section (generic function with 1 method)
function golden_section(ϕ, a, b; xtol=1e-6, maxiter=100, monitor=(a,b)->nothing)

# Compute intermediate points of new interval
golden = (1.0+sqrt(5.0))/2.0
get_x1(a,b) = b + (a-b)/golden
get_x2(a,b) = a + (b-a)/golden

# Set up initial intermediate points
x1 = get_x1(a,b)
x2 = get_x2(a,b)

# Get evaluations at end points and intermediate points
ϕa = ϕ(a)
ϕb = ϕ(b)
ϕ1 = ϕ(x1)
ϕ2 = ϕ(x2)

for k = 1:maxiter

# Call the monitor function if present, check for convergence
monitor(a, b)
if b-a < 2*xtol
return a,b
end
if ϕ1 < ϕ2 # Minimum is in [a,x2], shrink interval

# Note: x1 = get_x2(a,x2)
a, x1, x2, b = a, get_x1(a,x2), x1, x2
3.3 ms
begin
errs = []
lost_bracket = false
function gsmon(a,b)
push!(errs, (b-a)/2)
if a > π/2 || b < π/2
lost_bracket = true
end
end
xlo, xhi = golden_section(ϕ, 0.0, 2.0, monitor=gsmon)
π/2-xlo, xhi-π/2
end
16.2 ms
plot(errs, yscale=:log10)
257 ms