[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$

example : $f(x,y) = xy^2$

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.