| Line 1: | Line 1: | ||
| − | |||
=QE2012_AC-3_ECE580-2= | =QE2012_AC-3_ECE580-2= | ||
| Line 5: | Line 4: | ||
| − | + | '''2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function''' | |
| + | |||
| + | <math>f = \frac{1}{2}x^TQx - x^Tb+c </math> | ||
| + | <math> =\frac{1}{2}x^T | ||
| + | \begin{bmatrix} | ||
| + | 1 & 1 \\ | ||
| + | 1 & 2 | ||
| + | \end{bmatrix}x-x^T\begin{bmatrix} | ||
| + | 2 \\ | ||
| + | 1 | ||
| + | \end{bmatrix} + 3.</math> | ||
| + | |||
| + | Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary. | ||
| + | |||
| + | <br> | ||
| + | |||
| + | Solution: | ||
| + | |||
| + | <math>f = \frac{1}{2}x^TQx - x^Tb+c </math> | ||
| + | <span class="texhtml">''U''''s''''e''</span> <span class="texhtml">''i''''n''''i''''t''''i''''a''''l''</span> <span class="texhtml">''p''''o''''i''''n''''t''</span> <span class="texhtml">''x''<sup>(0)</sup> = [0,0]<sup>''T''</sup>''a''''n''''d''</span> <span class="texhtml">''H''<sub>0</sub> = ''I''<sub>2</sub></span> | ||
| + | <span class="texhtml">''I''''n''</span> <span class="texhtml">''t''''h''''i''''s''</span> <span class="texhtml">''c''''a''''s''''e'',</span> | ||
| + | <math>g^{(k)} = \begin{bmatrix} | ||
| + | 1 & 1 \\ | ||
| + | 1 & 2 | ||
| + | \end{bmatrix} x^{(k)} - \begin{bmatrix} | ||
| + | 2 \\ | ||
| + | 1 | ||
| + | \end{bmatrix}</math> | ||
| + | |||
| + | <span class="texhtml">''H''''e''''n''''c''''e'',</span> | ||
| + | <math>g^{(0)} = \begin{bmatrix} | ||
| + | -2 \\ | ||
| + | -1 | ||
| + | \end{bmatrix},</math> <math>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}</math> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | <span class="texhtml">''B''''e''''c''''a''''u''''s''''e''</span> <span class="texhtml">''f''</span> <span class="texhtml">''i''''s''</span> <span class="texhtml">''a''</span> <span class="texhtml">''q''''u''''a''''d''''r''''a''''t''''i''''c''</span> <span class="texhtml">''f''''u''''n''''c''''t''''i''''o''''n'',</span> | ||
| + | |||
| + | <math>\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}</math> | ||
| + | |||
| + | <math>x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix} | ||
| + | 2 \\ | ||
| + | 1 | ||
| + | \end{bmatrix} = \begin{bmatrix} | ||
| + | 1 \\ | ||
| + | \frac{1}{2} | ||
| + | \end{bmatrix}</math> | ||
| + | |||
| + | <math>\Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix} | ||
| + | 1 \\ | ||
| + | \frac{1}{2} | ||
| + | \end{bmatrix}</math> | ||
| + | <math>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}</math> | ||
| + | |||
| + | <math>\Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix} | ||
| + | -\frac{3}{2} \\ | ||
| + | 2 | ||
| + | \end{bmatrix} </math> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | <span class="texhtml">''O''''b''''s''''e''''r''''v''''e''</span> <span class="texhtml">''t''''h''''a''''t'':</span> | ||
| + | <math>\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} </math> | ||
| + | <math> \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}</math> | ||
| + | <math>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},</math> <math>(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T = \begin{bmatrix} | ||
| + | \frac{9}{4} & 3 \\ | ||
| + | 3 & 4 | ||
| + | \end{bmatrix}</math> | ||
| + | <math>\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}</math> | ||
| + | <span class="texhtml">''U''''s''''i''''n''''g''</span> <span class="texhtml">''t''''h''''e''</span> <span class="texhtml">''a''''b''''o''''v''''e'',</span> <span class="texhtml">''n''''o''''w''</span> <span class="texhtml">''w''''e''</span> <span class="texhtml">''c''''o''''m''''p''''u''''t''''e''</span> | ||
| + | <math>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}</math> | ||
| + | |||
| + | <span class="texhtml">''T''''h''''e''''n''</span> <span class="texhtml">''w''''e''</span> <span class="texhtml">''h''''a''''v''''e'',</span> | ||
| + | <math>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}</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 & 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}</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> | ||
| + | |||
| + | <span class="texhtml">''N''''o''''t''''e''</span> <span class="texhtml">''t''''h''''a''''t''</span> <span class="texhtml">''w''''e''</span> <span class="texhtml">''h''''a''''v''''e''</span> <math>d^{(0)^T}Qd^{(0)} = 0;</math> | ||
| + | <span class="texhtml">''t''''h''''a''''t''</span> <span class="texhtml">''i''''s'',</span> <math>d^{(0)} = \begin{bmatrix} | ||
| + | 2 \\ | ||
| + | 1 | ||
| + | \end{bmatrix}</math> <span class="texhtml">''a''''n''''d''</span> <math>d^{(1)} = \begin{bmatrix} | ||
| + | \frac{4}{5} \\ | ||
| + | -\frac{3}{5} | ||
| + | \end{bmatrix}</math> <span class="texhtml">''a''''r''''e''</span> <span class="texhtml">''Q'' − ''c''''o''''n''''j''''u''''g''''a''''t''''e''</span> <span class="texhtml">''d''''i''''r''''e''''c''''t''''i''''o''''n''''s''.</span> | ||
| + | |||
| + | <br> | ||
| + | |||
Revision as of 20:01, 25 January 2013
QE2012_AC-3_ECE580-2
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 $ U's'e i'n'i't'i'a'l p'o'i'n't x(0) = [0,0]Ta'n'd H0 = I2 I'n t'h'i's c'a's'e, $ g^{(k)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} $
H'e'n'c'e, $ 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} $
B'e'c'a'u's'e f i's a q'u'a'd'r'a't'i'c f'u'n'c't'i'o'n,
$ \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} $
O'b's'e'r'v'e t'h'a't: $ \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} $ U's'i'n'g t'h'e a'b'o'v'e, n'o'w w'e c'o'm'p'u't'e $ 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} $
T'h'e'n w'e h'a'v'e, $ 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} $
N'o't'e t'h'a't w'e h'a'v'e $ d^{(0)^T}Qd^{(0)} = 0; $ t'h'a't i's, $ d^{(0)} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $ a'n'd $ d^{(1)} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $ a'r'e Q − c'o'n'j'u'g'a't'e d'i'r'e'c't'i'o'n's.
