[Numerical Analysis] 12. Optimization
Optimization
- Golden Ratio Search
- Fibonacci Search
- Methods for locating extrema (maxima or minima) of functions
Functions of One Variable
- The function $f$ has a local minimum value at $x=p$, if there exist an open interval $I$ containing $p$ s.t. $f(p) \leq f(x) $ for all $x \in I$
- $f$ has a local maximun value at $x=p$, if there exists an open interval $I$ containing $p$ s.t. $f(x) \leq f(p)$ for all $x \in I$
- $f$ has a local extremum value at $x=p$, if it has local minimum or maximun value at $x=p$
Definition ) Assume that $f(x)$ is defined on the interval $I$
- if $x_1 < x_2$ implies that $f(x_1) < f(x_2)$ for all $x_1, x_2 \in I$, then $f$ is said to be increasing on $I$.
- if $x_1 < x_2$ implies that $f(x_1) > f(x_2)$ for all $x_1, x_2 \in I$, then $f$ is said to be decreasing on $I$.
Theorem 1 ) Suppose that $f(x)$ is continuous on $I = [a,b]$ and is differentialbe on $(a,b)$
- if $f'(x) > 0 $ for all $x \in (a,b)$, then $f(x)$ is increasing on $I$.
- if $f'(x) < 0 $ for all $x \in (a,b)$, then $f(x)$ is decreasing on $I$.
Theorem 2 ) First Derivative Test : Suppose that $f(x)$ is continuous on $I=[a,b]$ and $f'(x)$ is defined for all $x \in (a,b)$, except possibly at $x=p$
- if $f'(x) < 0 $ on $(a,p)$ and $f'(x) > 0 $ on $(p, b$, then $f(p)$ is a local minimun.
- if $f'(x) > 0 $ on $(a, p)$ and $f'(x) < 0 $ on $(p,b)$, then $f(p)$ is a local maximun.
Theorem 3 ) Second Derivative Test : Suppose that $f(x)$ is continuous on $I = [a,b]$ and $f'$ and $f''$ are defined on $(a,b)$. Also, $p \in (a,b)$ is a critical point where $f'(p) = 0$.
- if $f''(p) > 0$, then $f(p)$ is a local minimun of $f$.
- if $f''(p) < 0$, then $f(p)$ is a local maxinum of $f$.
- if $f''(p) = 0$, then this test is inconclusive. -> min, max, 변곡점 결정 못함
Bracketing Search Methods
- Evaluate the function many times and search for a local minimum / maximun
- To reduce the number of function evaluations, a good strategy is needed for determining where the function is to bee evaluated
Definition ) The function $f(x)$ is unimodal on $I = [a,b]$, if there exists a unique number $p \in I$ such that
- $f(x)$ is decreasing on $[a, p]$
- $f(x)$ is increasing on $[a, p]$
Golden Ratio Search
- if $f(x)$ is unimodal on $[a,b]$, then it is possible to replace the interval with a subinterval on which $f(x)$ takes on its minimun value
- Select two interior points $c < d \to a < c < d < b $
- When $f(c) \leq f(d) $ : The minimum must occur in $[a,d]$ -> New subinterval $[a, d]$
- Selection of $c$ and $d$. are selected so that $[a,c]$ and $[d, b]$ are symmetrical $ ( b -d = c - a) $.
: $ c = a + (1-r)(b-a) = ra + (1-r)b$, $d = b - (1-r)(b-a) = (1-r)a + rb$ , $\frac{1}{2} < r < 1$
: $ r = \frac{c - a}{b - a} = \frac{b - d}{b - a}$
- We want $r$ to remain constant on each subinterval
- One of old interior points will be used as a new interior points and a new endpoint
: $a_ 0 \to a_1$, $d_0 \to b_1$ or $c_0 \to a_1$ , $b_0 \to b_1$
- $0(a_0)$ , $1-r(c_0)$ , $r(d_0)$, $1(b_0)$ -> $0(a_0)$, $r(1-r)(c_1)$ ,$r^2=1-r(c_0=d_1)$, $r(b_0)$ ->> $r^2 = 1 - r$ , $\frac{1}{2} < r < 1 $
- $r = \frac{-1 - \sqrt{5}}{2}$
- Example : $f(x) = x^2 - \sin (x) $
> $c_0 = 0 + (1 - r)(1-0)$
> $d_0 = 1 - (1-r)(1-0)$
> $a_1 = a_0$, $b_1 = d_0$, $d_1 = c_0$
> $c_1 = a_1 + (1-r)(b_1 - a_1)$
> ...
- When $(fc) \leq f(d)$ -> The minimun must occur in [a, d]
- New subinterval [a, d]
Fibonacci Search
- The value $r$ is not constant on each subinterval
- Number of subintervals (iterations) is predetermined and based on the specified tolerance
- Fibonacci number : ${F_k}^{\infty}_{k=0}$
- Assume $f(x)$ that is unimodal on the interval [$a_0$, $b_0$]
- $r_0$ ( 1/2 < $r_0$ < 1 ) is selected so that both interior points $c_0$ and $d_0$ will be used in the next subinterval => only one evaluation
- Assume $f(c_0) \leq f(d_0)$ -> $a_1 = a_0$, $b_1 = d_0$, and $d_1 = c_0$
- Select $r_1$ for [$a_1$, $b_1$] such that $d_0 - c_0 = b_1 - d_1$ => $ $r_1 = \frac{1-r_0}{r_0}$
- Substituting $r_0 = \frac{F_{n-1}}{F_n}$, $n \geq 4$
> $r_1 = \frac{F_{n-2}}{F_{n-1}}$
- Reasoning inductively, $r_0 = \frac{F_{n-1}}{F_n}$ and continued $r_k = \frac{F_{n-1-k}}{F_{n-k}}$, for $k = 1,2,\cdots , n-3$
- $r-3 = \frac{F_2}{F_3} = \frac{1}{2}$, thus no new points can be added
- Total $(n-3) +1 = n-2$ steps
- Length of $(k+1)$st subinterval is obtained by reducing the length of k-th subinterval by a factor $r_k = \frac{F_{n-1-k}}{F_{n-k}}$
- Length of the last subinterval is $\frac{F_{n-1}\cdots F_2}{F_n \cdots F_3}(b_0 - a_0) = \frac{1}{F_n}(b_0 - a_0)$
> $\frac{b_0- a_0}{F_n} < \epsilon$
- $r_{n-3}$ => two interior points are same => use a small distinguishability constane, $e$
> To distinguish the two interior points, introduce the coefficient of $(b_k - a_k)$ are $\frac{1}{2} - e$ or $\frac{1}{2} + e$
- Example $f(x) = x^2 - \sin (x)$ [0, 1]
> Use a tolerance of $\epsilon = 10^{-4}$
> distinguishability constant $e = 0.01$
- Find the smallest Fibonacci number $n$
> $F_n > \frac{b_0- a_0}{\epsilon} = \frac{1-0}{10^{-4}} = 10000$
> $F_{21} = 10946$ -> $n = 21$, $r_0 = \frac{F_{20}}{F_{21}}$
- $c_{18} = a_{18} + (0.5 - 0.01)(b_{18} - a_{18}$
Multidimensional Optimization
- Find the extremum of a function of serveral variables
> Direct method (No derivatives)
> Gradient method ( Use derivatives)
Direct Methods - Random Search
- Based on evaluation of the function randomly at selected values of the independent variables.
- If a sufficient number of samples are conducted, the optimum will be eventually located.
- Advantages
> Works even for discontinuous and nondifferentiable functions.
- Disadvantages
> As the number of independent variables grows, the task can become onerous.
> Not efficient, it does not account for the behavior of underlying function.
Univariate and Pattern searches
- More efficient than random search and still doesn't require derivative evaluation.
- The basic strategy
> Change one variable at a time while the other variables are held constant.
> Problem is reduced to a sequence of one-dimensional searches that can be solved by variety of methods ( bracketing search)
> The search becomes less efficient as you approach the maximum.
Gradient
Gradient of a function $f$, $\triangledown f$
- What is the steepest ascent?
> Direction that will yield the greatest change in $f$
- How much we will gain by taking that step?
> Indicate by the magnitude of $ \triangledown f$
Testing Optimum Point - 2D
> If a point is an optimum point, then $ \frac{\partial f}{\partial x} =0$ and $\frac{\partial f}{\partial y} = 0$
> In addition, if the point is a maximum point, then $ \frac{\partial^2 f}{\partial x^2} < 0$ and $ \frac{\partial^2 f}{\partial y^2} < 0 $
> Question : If both of these conditions are satisfied for a point, can we conclude that the point is a maximum point?
- No!
> When viewed along the $x$ and $y$ directions. second derivative is 0
> When viewed along the $y=x$ direction.
> $(a,b)$ is saddle point
- For 2D functions, we also have to take into consideration of $\frac{\partial^2 f}{\partial x \partial y}$
- That is, whether a maximum or a minimum occurs involves both partial derivatives $x$ and $y$ and the second partials $x$ and $y$.
Hessian Matrix ( or Hessian of $f$ )
- Also known as the matrix of second partial derivatives.
- It provides a way to discern if an function has reched an optimum or not.
- The quantity $|H|$ is equal to the determinant of the Hessian matrix of $f$.
- Finite Difference Approximation using Centered-difference approach
Gradient Method - Steepest Ascend
- start at an initial point $(x_0, y_0)$, determine the direction of steepest ascend, that is, the gradient. Then search along the direction of the gradient, $h_0$, until we find maximum. Process is then repeated.
