AC - 3 August 2012 QE
1. (20 pts)
(i) (10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form
$ \begin{align} 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, \end{align} $
where $ N - 1 $ is the number of steps performed in the uncertainty range reduction process.
Solution:
The reduction factor is $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) $ Since $ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $ we have $ 1- \rho_{N-2} = \frac{F_{3}}{F_{4}} $ and so on.
Then, we have $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $ Therefore, the reduction factor is $ \frac{2}{F_{N+1}} $
(ii)(10 pts) It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is
$ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $
Solution:
Final Range: 1.0; Initial Range: 20.
$ \frac{2}{F_{N+1}} \le \frac{1.0}{20} $, or $ F_{N+1} \ge 40 $
So, $ N+1 = 9 $
Therefore, the minimal iterations is N-1 or 7.
2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function
$ f = \frac{1}{2}x^TQx - x^Tb+c $ $ =\frac{1}{2}x^T \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}x-x^T\begin{bmatrix} 2 \\ 1 \end{bmatrix} + 3. $
Where $ x^{(0)} $ is arbitrary.
Solution:
$ f = \frac{1}{2}x^TQx - x^Tb+c $ $ Use $ $ initial $ $ point $ $ x^{(0)} = [0, 0]^T and $ $ H_0 = I_2 $ $ In $ $ this $ $ case, $ $ g^{(k)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} $
$ Hence, $ $ g^{(0)} = \begin{bmatrix} -2 \\ -1 \end{bmatrix}, $ $ d^{(0)} = -H_0g^{(0)} =- \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -2 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $
$ Because $ $ f $ $ is $ $ a $ $ quadratic $ $ function, $
$ \alpha_0 = argminf(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix} -2 & -1 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}}{\begin{bmatrix} 2 & 1\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}} = \frac{1}{2} $
$ x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $
$ \Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $ $ g^{(1)} =\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(1)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix}= \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} $
$ \Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix} -\frac{3}{2} \\ 2 \end{bmatrix} $
$ Observe $ $ that: $ $ \Delta x^{(0)} \Delta x^{(0)^T} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} \begin{bmatrix} 1 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 1 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{4} \end{bmatrix} $ $ \Delta x^{(0)^T} \Delta g^{(0)} = \begin{bmatrix} 1 & \frac{1}{2} \end{bmatrix}\begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \frac{5}{2} $ $ H_0 \Delta g^{(0)} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix}, $ $ (H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T = \begin{bmatrix} \frac{9}{4} & 3 \\ 3 & 4 \end{bmatrix} $ $ \Delta g^{(0)^T}H_0 \Delta g^{(0)} = \begin{bmatrix} \frac{3}{2} & 2 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \frac{25}{4} $ $ Using $ $ the $ $ above, $ $ now $ $ we $ $ compute $ $ H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} } = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} \frac{2}{5} & \frac{1}{5} \\ \frac{1}{5} & \frac{1}{10} \end{bmatrix} - \frac{25}{4}\begin{bmatrix} \frac{9}{4} & 3 \\ 3 & 4 \end{bmatrix} = \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} $
$ Then $ $ we $ $ have, $ $ d^{(1)} = -H_1 g^{(0)} = - \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $
$ \alpha_1 = argminf(x^{(1)} + \alpha d^{(1)}) = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix} -2 & 1 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}}{\begin{bmatrix} \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}} = \frac{5}{2} $
$ x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} + \frac{5}{2}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} = \begin{bmatrix} 3 \\ -1 \end{bmatrix} $
$ \Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix} 2 \\ -\frac{3}{2} \end{bmatrix} $ $ g^{(2)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(0)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $
$ Note $ $ that $ $ we $ $ have $ $ d^{(0)^T}Qd^{(0)} = 0; $ $ that $ $ is, $ $ d^{(0)} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $ $ and $ $ d^{(1)} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $ $ are $ $ Q-conjugate $ $ directions. $
