| Line 206: | Line 206: | ||
\end{bmatrix}</math> | \end{bmatrix}</math> | ||
| − | <math>\ | + | <math>\alpha_1 = argminf(x^{(1)} + \alpha d^{(1)}) = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix} |
| − | -2 & | + | -2 & 1 |
\end{bmatrix}\begin{bmatrix} | \end{bmatrix}\begin{bmatrix} | ||
| − | + | \frac{4}{5} \\ | |
| − | + | -\frac{3}{5} | |
\end{bmatrix}}{\begin{bmatrix} | \end{bmatrix}}{\begin{bmatrix} | ||
| − | + | \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix} | |
1 & 1 \\ | 1 & 1 \\ | ||
1 & 2 | 1 & 2 | ||
\end{bmatrix}\begin{bmatrix} | \end{bmatrix}\begin{bmatrix} | ||
| + | \frac{4}{5} \\ | ||
| + | -\frac{3}{5} | ||
| + | \end{bmatrix}} = \frac{5}{2}</math> | ||
| + | |||
| + | <math>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} </math> | ||
| + | |||
| + | <math>\Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix} | ||
| + | 2 \\ | ||
| + | -\frac{3}{2} | ||
| + | \end{bmatrix}</math> | ||
| + | <math>g^{(2)} = \begin{bmatrix} | ||
| + | 1 & 1 \\ | ||
| + | 1 & 2 | ||
| + | \end{bmatrix} x^{(0)} - \begin{bmatrix} | ||
| + | 2 \\ | ||
| + | 1 | ||
| + | \end{bmatrix} = \begin{bmatrix} | ||
| + | 0 \\ | ||
| + | 0 | ||
| + | \end{bmatrix}</math> | ||
| + | |||
| + | <math>Note</math> <math>that</math> <math>we</math> <math>have</math> <math>d^{(0)^T}Qd^{(0)} = 0;</math> | ||
| + | <math>that</math> <math>is,</math> <math>d^{(0)} = \begin{bmatrix} | ||
2 \\ | 2 \\ | ||
1 | 1 | ||
| − | \end{bmatrix}} = \frac{ | + | \end{bmatrix}</math> <math>and</math> <math>d^{(1)} = \begin{bmatrix} |
| + | \frac{4}{5} \\ | ||
| + | -\frac{3}{5} | ||
| + | \end{bmatrix}</math> <math>are</math> <math>Q-conjugate</math> <math>directions.</math> | ||
Revision as of 10:39, 10 January 2013
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. $
