12 - Optimization

Optimization in One Dimension

• The problem: Given $f : \mathbb{R} \to \mathbb{R}$, find $x$ that minimizes $f(x)$
• Such $x$ is called a minimizer and often denoted $x^*$

อย่างใน Airline scheduling, they can model how they assign their crew, which pilot take which flight, ต่าง ๆ สุดท้ายก็คือ Minimize cost → Maximize the profit

Local vs Global Optimization

Visual Representation

• Will cover only local optimization as global optimization is much more difficult to obtain
• (Informal) Definition: $x^*$ is a local minimizer of $f$ when $f(x^*)$ is smaller than or equal to the function values of all points near $x^*$

Analogy: Think of a local minimum like being in a valley in the mountains. You're at the lowest point in your immediate area (local), but there might be a deeper valley somewhere else on the mountain range (global). Global optimization is like finding the absolute lowest point across all valleys, which is much harder!

เหมือนว่าในบทนี้จะหาแค่ Local minimizer

คำถาม: ถ้าอยากหา Maximum บ้างล่ะ ซึ่งจริง ๆ แล้วมันคือสิ่งเดียวกัน แค่เปลี่ยนเครื่องหมายแล้วหา Minimum ซะ55555

Successive Parabolic Interpolation

Algorithm Steps

• Initially, evaluate $f$ at three points
• Find the quadratic interpolant that fits the three points
• The minimum of the parabola interpolant (assuming it has one) is taken as a new approximate minimum of the function

Iteration Process

• At a given iteration, we have three points, say $u$, $v$, and $w$, with corresponding function values $f_u$, $f_v$, and $f_w$, where $v$ is the best approximate minimum of the function so far
• The minimum of the parabola interpolating the three points is given by:
  $\boxed{v - \frac{1}{2} \frac{(v-u)^2(f_v - f_w) - (v-w)^2(f_v - f_u)}{(v-u)(f_v - f_w) - (v-w)(f_v - f_u)}}$
• Replace $u$ by $w$, $w$ by $v$, and $v$ by the new approximate minimum above (replace the oldest point, which is always $u$)
• Repeat until convergence

Visual Representation

Convergence Properties

• Successive parabolic interpolation is not guaranteed to converge
• But if started close enough to a minimum and the function is well-behaved, it converges superlinearly with convergence rate $r \approx 1.324$

Analogy: Imagine you're trying to find the bottom of a bowl by fitting curved slides (parabolas) through three points you've measured. Each time, you slide down to where your curved slide predicts the bottom is, then measure new points around there. If you start reasonably close to the actual bottom, you'll quickly zoom in on it!

Example 1: Successive Parabolic Interpolation

Problem: Minimize $f(x) = 0.5 - xe^{-x^2}$

Initial Setup

• Choose three initial points: $x_0 = 0$, $x_1 = 1.2$, and $x_2 = 0.6$
• Evaluate:
  • $f(x_0) = 0.5 - 0e^{-0^2} = 0.5$
  • $f(x_1) = 0.5 - (1.2)e^{-(1.2)^2} = 0.216$
  • $f(x_2) = 0.5 - (0.6)e^{-(0.6)^2} = 0.081$

Iteration Results

• The minimizer of the parabola fitting these three points by the formula is: $x_3 = 0.754$
  • แทนเข้าสูตรยาว ๆ เมื่อกี้ ได้ $x_3$ ออกมา
• Discard $x_0$ and repeat the process with the three remaining points $x_1$, $x_2$, and $x_3$

Iteration Table

Newton's Method for One-Dimensional Optimization

Derivation

• The first three terms of Taylor series give:
  $f(x+h) \approx f(x) + f'(x)h + \frac{1}{2}f''(x)h^2 \quad (1)$

• Suppose we know a point $x^{(k)}$ that is close to a minimizer of $f$

• We want to find $h$ such that $f(x^{(k)} + h)$ is minimized

• Using the approximation in (1), let us instead find $h$ such that
  $f(x^{(k)}) + f'(x^{(k)})h + \frac{1}{2}f''(x^{(k)})h^2 = g(h)$

  is minimized

Finding the Minimum

• The minimum of $g(h)$ (if exists) is the point where:
  $g'(h) = f'(x^{(k)}) + f''(x^{(k)})h = 0$
• Solve for $h$: