(7 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
[[Category:ECE]]
 +
[[Category:QE]]
 +
[[Category:CNSIP]]
 +
[[Category:problem solving]]
 +
[[Category:automatic control]]
 +
[[Category:optimization]]
  
 
=QE2012_AC-3_ECE580-2=
 
=QE2012_AC-3_ECE580-2=
  
−
 
+
:[[QE2012_AC-3_ECE580-1|Part 1]],[[QE2012_AC-3_ECE580-2|2]],[[QE2012_AC-3_ECE580-3|3]],[[QE2012_AC-3_ECE580-4|4]],[[QE2012_AC-3_ECE580-5|5]]
−
 
+
−
'''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:  
 
Solution:  
  
 
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 
       <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>
+
    Use initial point x<sup>(0)</sup> = [0,0]<sup>T</sub> and H<sub>0</sub> = I<sub>2</sub>
−
      <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}
+
In this case
 +
    <math>g^{(k)} = \begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
 
   1 & 2
 
   1 & 2
Line 33: Line 24:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
−
       <span class="texhtml">''H''''e''''n''''c''''e'',</span>
+
       Hence
−
      <math>g^{(0)} = \begin{bmatrix}
+
    <math>g^{(0)} = \begin{bmatrix}
 
   -2  \\
 
   -2  \\
 
   -1
 
   -1
Line 50: Line 41:
 
<br>  
 
<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>
+
       Because f is a quadratic function
  
 
       <math>\alpha_0 = argminf(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}
 
       <math>\alpha_0 = argminf(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}
Line 78: Line 69:
 
   \frac{1}{2}
 
   \frac{1}{2}
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
−
      <math>g^{(1)} =\begin{bmatrix}
+
    <math>g^{(1)} =\begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
 
   1 & 2
 
   1 & 2
Line 96: Line 87:
 
<br>  
 
<br>  
  
−
       <span class="texhtml">''O''''b''''s''''e''''r''''v''''e''</span> <span class="texhtml">''t''''h''''a''''t'':</span>
+
       Observe that
−
      <math>\Delta x^{(0)} \Delta x^{(0)^T} = \begin{bmatrix}
+
    <math>\Delta x^{(0)} \Delta x^{(0)^T} = \begin{bmatrix}
 
   1  \\
 
   1  \\
 
   \frac{1}{2}  
 
   \frac{1}{2}  
Line 106: Line 97:
 
   \frac{1}{2}  & \frac{1}{4}  
 
   \frac{1}{2}  & \frac{1}{4}  
 
  \end{bmatrix} </math>
 
  \end{bmatrix} </math>
−
      <math> \Delta x^{(0)^T} \Delta g^{(0)} = \begin{bmatrix}
+
    <math> \Delta x^{(0)^T} \Delta g^{(0)} = \begin{bmatrix}
 
   1  & \frac{1}{2}  
 
   1  & \frac{1}{2}  
 
  \end{bmatrix}\begin{bmatrix}
 
  \end{bmatrix}\begin{bmatrix}
Line 112: Line 103:
 
   2  
 
   2  
 
  \end{bmatrix}  = \frac{5}{2}</math>
 
  \end{bmatrix}  = \frac{5}{2}</math>
−
      <math>H_0 \Delta g^{(0)} = \begin{bmatrix}
+
    <math>H_0 \Delta g^{(0)} = \begin{bmatrix}
 
   1 & 0 \\
 
   1 & 0 \\
 
   0 & 1
 
   0 & 1
Line 125: Line 116:
 
   3 & 4
 
   3 & 4
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
−
      <math>\Delta g^{(0)^T}H_0 \Delta g^{(0)} = \begin{bmatrix}
+
    <math>\Delta g^{(0)^T}H_0 \Delta g^{(0)} = \begin{bmatrix}
 
   \frac{3}{2}  & 2  
 
   \frac{3}{2}  & 2  
 
  \end{bmatrix} \begin{bmatrix}
 
  \end{bmatrix} \begin{bmatrix}
Line 133: Line 124:
 
   \frac{3}{2}  \\ 2  
 
   \frac{3}{2}  \\ 2  
 
  \end{bmatrix} = \frac{25}{4}</math>
 
  \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>
+
    <font face="serif" size="3">''Using the above, now we have''</font>
−
      <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}
+
    <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 \\
 
   1 & 0 \\
 
   0 & 1
 
   0 & 1
Line 148: Line 139:
 
  \end{bmatrix}</math>
 
  \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>
+
       <span class="texhtml">''T'hen we have''</span><span class="texhtml">''','''</span>
−
      <math>d^{(1)} = -H_1 g^{(0)} = - \begin{bmatrix}
+
    <math>d^{(1)} = -H_1 g^{(0)} = - \begin{bmatrix}
 
   \frac{26}{25} & -\frac{7}{25} \\
 
   \frac{26}{25} & -\frac{7}{25} \\
 
   -\frac{7}{25} & \frac{23}{50}
 
   -\frac{7}{25} & \frac{23}{50}
Line 189: Line 180:
 
   -\frac{3}{2}
 
   -\frac{3}{2}
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
−
      <math>g^{(2)} = \begin{bmatrix}
+
    <math>g^{(2)} = \begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
 
   1 & 2
 
   1 & 2
Line 200: Line 191:
 
  \end{bmatrix}</math>
 
  \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">''Note that we have''</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}
+
    <span class="texhtml">''that is''</span>, <math>d^{(0)} = \begin{bmatrix}
 
   2  \\
 
   2  \\
 
   1
 
   1
−
  \end{bmatrix}</math> <span class="texhtml">''a''''n''''d''</span> <math>d^{(1)}  = \begin{bmatrix}
+
  \end{bmatrix}</math> and  <math>d^{(1)}  = \begin{bmatrix}
 
   \frac{4}{5}  \\
 
   \frac{4}{5}  \\
 
   -\frac{3}{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>
+
  \end{bmatrix}</math> <span class="texhtml">''are Q-conjugate directions''</span><span class="texhtml">'''.'''</span>
 +
 
 +
 
 +
Solution 2:
 +
 
 +
<math>
 +
\text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix}
 +
\text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}
 +
 
 +
</math>
 +
 
 +
<math>g^{(k)} = \begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix} x^{(k)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} , \text{so}</math>
 +
 
 +
<math>g^{(0)} = \begin{bmatrix}
 +
  -2  \\
 +
  -1
 +
\end{bmatrix},</math>  <math>d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix}
 +
  1 & 0 \\
 +
  0 & 1
 +
\end{bmatrix}\begin{bmatrix}
 +
  -2  \\
 +
  -1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 
 +
<math>\alpha_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>
 +
 
 +
<math>
 +
\text{If we plug in the above numbers in the formula, we can get}
 +
</math>
 +
 
 +
<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>
 +
 
 +
<math>d^{(1)} = -H_1 g^{(1)} = - \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 = - \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^{(2)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  0  \\
 +
  0
 +
\end{bmatrix}</math>
 +
 
 +
<math>
 +
\text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix}
 +
  3 \\
 +
  -1
 +
\end{bmatrix}
 +
</math>
  
 
<br>  
 
<br>  
  
 +
----
 +
----
 +
<font face="serif"></font><math>\color{blue}\text{Related Problem: }</math>
 +
Employ the DFP method to find the minimizer of the following function
  
 +
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 +
      <math>  =\frac{1}{2}x^T
 +
\begin{bmatrix}
 +
  4 & 2 \\
 +
  2 & 2
 +
\end{bmatrix}x-x^T\begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}</math>
  
 +
Solution: This problem is essentially the same with the previous one except that the numbers are different.
 +
 +
<math>
 +
\text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix}
 +
\text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}
 +
 +
</math>
 +
 +
<math>g^{(k)} = \begin{bmatrix}
 +
  4 & 4 \\
 +
  4 & 2
 +
\end{bmatrix} x^{(k)} - \begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix} , \text{so}</math>
 +
 +
<math>g^{(0)} = \begin{bmatrix}
 +
  1  \\
 +
  -1
 +
\end{bmatrix},</math>  <math>d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix}
 +
  1 & 0 \\
 +
  0 & 1
 +
\end{bmatrix}\begin{bmatrix}
 +
  1  \\
 +
  -1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
<math>\alpha_0 = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}
 +
  1 & -1
 +
\end{bmatrix}\begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}}{\begin{bmatrix}
 +
  -1 & 1\end{bmatrix}\begin{bmatrix}
 +
  4 & 2 \\
 +
  2 & 2
 +
\end{bmatrix}\begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}} = \frac{1}{2}</math>
 +
 +
<math>x^{(1)} = x^{(0)} + \alpha d^{(0)} = \begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix} </math>
 +
 +
<math>\Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
<math>g^{(1)} =\begin{bmatrix}
 +
  4 & 2 \\
 +
  2 & 2
 +
\end{bmatrix} x^{(1)} - \begin{bmatrix}
 +
  -1  \\
 +
  1
 +
\end{bmatrix}= \begin{bmatrix}
 +
  -1  \\
 +
  -1
 +
\end{bmatrix}</math>
 +
 +
<math>\Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix}
 +
  -2  \\
 +
  0
 +
\end{bmatrix} </math>
 +
 +
<math>
 +
\text{If we plug in the above numbers in the formula, we can get}
 +
</math>
 +
 +
<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{1}{2} & -\frac{1}{2} \\
 +
  -\frac{1}{2} & \frac{1}{2}
 +
\end{bmatrix} - \begin{bmatrix}
 +
  1 & 0 \\
 +
  0 & 0
 +
\end{bmatrix} = \begin{bmatrix}
 +
  \frac{1}{2} & -\frac{1}{2} \\
 +
  -\frac{1}{2} & \frac{3}{2}
 +
\end{bmatrix}</math>
 +
 +
<math>d^{(1)} = -H_1 g^{(1)} = \begin{bmatrix}
 +
  0  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
<math>\alpha_1 = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = \frac{1}{2}</math>
 +
 +
<math>x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix}
 +
  -1  \\
 +
  3/2
 +
\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}
 +
  4 & 4 \\
 +
  4& 2
 +
\end{bmatrix} x^{(2)} - \begin{bmatrix}
 +
  -1 \\
 +
  1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  0  \\
 +
  0
 +
\end{bmatrix}</math>
  
 +
<math>
 +
\text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix}
 +
  -1 \\
 +
  3/2
 +
\end{bmatrix}
 +
</math>
  
 
[[ QE2012 AC-3 ECE580-1|Back to QE2012 AC-3 ECE580-1]]
 
[[ QE2012 AC-3 ECE580-1|Back to QE2012 AC-3 ECE580-1]]

Latest revision as of 09:12, 13 September 2013


QE2012_AC-3_ECE580-2

Part 1,2,3,4,5

Solution: 

      $ f = \frac{1}{2}x^TQx - x^Tb+c  $
   Use initial point x(0) = [0,0]T</sub> and H0 = I2

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 have
   $ 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'hen 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.


Solution 2:

$ \text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix} \text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} $

$ g^{(k)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} , \text{so} $

$ g^{(0)} = \begin{bmatrix} -2 \\ -1 \end{bmatrix}, $ $ d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -2 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $

$ \alpha_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} $

$ \text{If we plug in the above numbers in the formula, we can get} $

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

$ d^{(1)} = -H_1 g^{(1)} = - \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 = - \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^{(2)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $

$ \text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix} 3 \\ -1 \end{bmatrix} $


$ \color{blue}\text{Related Problem: } $ Employ the DFP method to find the minimizer of the following function 

      $ f = \frac{1}{2}x^TQx - x^Tb+c  $
     $   =\frac{1}{2}x^T  \begin{bmatrix}   4 & 2 \\   2 & 2  \end{bmatrix}x-x^T\begin{bmatrix}   -1  \\   1  \end{bmatrix} $

Solution: This problem is essentially the same with the previous one except that the numbers are different.

$ \text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix} \text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} $

$ g^{(k)} = \begin{bmatrix} 4 & 4 \\ 4 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} -1 \\ 1 \end{bmatrix} , \text{so} $

$ g^{(0)} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}, $ $ d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} -1 \\ 1 \end{bmatrix} $

$ \alpha_0 = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix} 1 & -1 \end{bmatrix}\begin{bmatrix} -1 \\ 1 \end{bmatrix}}{\begin{bmatrix} -1 & 1\end{bmatrix}\begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix}\begin{bmatrix} -1 \\ 1 \end{bmatrix}} = \frac{1}{2} $

$ x^{(1)} = x^{(0)} + \alpha d^{(0)} = \begin{bmatrix} -1 \\ 1 \end{bmatrix} $

$ \Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix} -1 \\ 1 \end{bmatrix} $

$ g^{(1)} =\begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix} x^{(1)} - \begin{bmatrix} -1 \\ 1 \end{bmatrix}= \begin{bmatrix} -1 \\ -1 \end{bmatrix} $

$ \Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix} -2 \\ 0 \end{bmatrix} $

$ \text{If we plug in the above numbers in the formula, we can get} $

$ 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{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} \end{bmatrix} - \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & \frac{3}{2} \end{bmatrix} $

$ d^{(1)} = -H_1 g^{(1)} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} $

$ \alpha_1 = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = \frac{1}{2} $

$ x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix} -1 \\ 3/2 \end{bmatrix} $

$ \Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix} 2 \\ -\frac{3}{2} \end{bmatrix} $

$ g^{(2)} = \begin{bmatrix} 4 & 4 \\ 4& 2 \end{bmatrix} x^{(2)} - \begin{bmatrix} -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $

$ \text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix} -1 \\ 3/2 \end{bmatrix} $

Back to QE2012 AC-3 ECE580-1

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE2012_AC-3_ECE580-2&oldid=58211"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

BSEE 2004, current Ph.D. student researching signal and image processing.

Landis Huffman