Line 70: Line 70:
 
Solution:  
 
Solution:  
 
        
 
        
−
       Quadratic Form: <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
+
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
−
       Use initial point <math>x^{(0)} = [0, 0]^T and H_0 = I_2</math>
+
       <math>Use</math> <math>initial</math>  <math> point</math> <math>x^{(0)} = [0, 0]^T and</math> <math> H_0 = I_2</math>
−
       In this case,
+
       <math>In</math> <math>this</math> <math>case,</math>
 
       <math>g^{(k)} = \begin{bmatrix}
 
       <math>g^{(k)} = \begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
Line 81: Line 81:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
−
       Hence,  
+
       <math> Hence,</math>
 
       <math>g^{(0)} = \begin{bmatrix}
 
       <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  \\
 
   2  \\
 
   1
 
   1
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
 +
 +
   
 +
      <math>Because</math> <math>f</math> <math>is</math> <math>a</math> <math>quadratic</math> <math>function,</math>
 +
 +
      <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>
 +
 +
 +
      <math>Observe</math> <math>that:</math>
 +
      <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>
 +
      <math>Using</math> <math>the</math> <math>above, </math> <math>now</math> <math>we</math> <math>compute</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>Then</math> <math>we</math> <math>have,</math>
 +
      <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_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>

Revision as of 10:28, 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_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} $
Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE2012_AC-3_ECE580&oldid=52978"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang