Line 5: Line 5:
 
(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  
 
(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  
  
 +
<math>
 +
\begin{align}
 +
1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3},
 +
\end{align}
 +
</math>
  
 +
where <span class="texhtml">''N'' − 1</span> is the number of steps performed in the uncertainty range reduction process.
 +
 +
<br>
 +
 +
<br> Solution:
 +
 +
    The reduction factor is <span class="texhtml">(1 − ρ<sub>1</sub>)(1 − ρ<sub>2</sub>)(1 − ρ<sub>3</sub>)...(1 − ρ<sub>''N'' − 1</sub>)</span>
 +
Since
 +
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>
 +
we have
 +
<math> 1- \rho_{N-2} = \frac{F_{3}}{F_{4}}</math>    and so on.
 +
 +
    Then, we have
 +
<math> (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}}</math>
 +
Therefore, the reduction factor is
 +
<math>\frac{2}{F_{N+1}}</math>
 +
 +
<br>
 +
 +
Solution 2:
 +
 +
The uncertainty interval is reduced by <math> (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}}</math>
 +
 +
<font color="#ff0000"><span style="font-size: 19px;"><math>\color{blue}
 +
\text{In this specific case, we use only N-1 iterations. }
 +
</math></span></font>
 +
 +
<br>
  
 
<br> '''(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  
 
<br> '''(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  
Line 11: Line 44:
 
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>  
 
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>  
  
 +
<br> Solution:
  
 +
      Final Range: 1.0; Initial Range: 20.
 +
 +
      <math> \frac{2}{F_{N+1}} \le \frac{1.0}{20}</math>, or <math> F_{N+1} \ge 40</math>
 +
 +
      So, <span class="texhtml">''N'' + 1 = 9</span>
 +
 +
      Therefore, the minimal iterations is N-1 or 7.
 +
 +
<br>
 +
 +
Solution 2:
 +
Since the final range is 1 and the initial range is 20, we can say
 +
<math>
 +
\frac{2}{F_{N+1}} \le \frac{1.0}{20} \text{or equivalently } F_{N+1} \ge 40
 +
</math>
 +
 +
From the inequality, we get <math> F_{N+1} \ge 40 , \text{ so } N+1=9 </math>. Therefore the minimum number of iteration is N-1=7
 +
 +
<font color="#0000FF "><span style="font-size: 19px;"><math>\color{blue}
 +
F_9=55 \text{ and } F_8=34
 +
</math></span></font>
 +
 +
<br>
  
 
Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function'''  
 
Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function'''  
Line 29: Line 86:
 
<br>  
 
<br>  
  
 +
Solution:
  
 +
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 +
    Use initial point x<sup>(0)</sup> = [0,0]<sup>T</sub> and H<sub>0</sub> = I<sub>2</sub>
 +
   
 +
In this case
 +
    <math>g^{(k)} = \begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix} x^{(k)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
      Hence
 +
    <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>
 +
 +
      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}
 +
  -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>
 +
 +
      Observe that
 +
    <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>
 +
    <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}
 +
  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'hen we have''</span><span class="texhtml">''','''</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">''Note that we have''</span> <math>d^{(0)^T}Qd^{(0)} = 0;</math>
 +
    <span class="texhtml">''that is''</span>, <math>d^{(0)} = \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}</math> and  <math>d^{(1)}  = \begin{bmatrix}
 +
  \frac{4}{5}  \\
 +
  -\frac{3}{5}
 +
\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>
  
 
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where  
 
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where  
Line 48: Line 448:
  
 
<br>  
 
<br>  
−
 
  
 
'''Problem 4. (20pts) Use any simplex method to solve the following linear program. '''  
 
'''Problem 4. (20pts) Use any simplex method to solve the following linear program. '''  
Line 60: Line 459:
 
<br>  
 
<br>  
  
 +
 +
 +
<br> '''Problem 5.(20pts) Solve the following problem:'''
 +
 +
            <span class="texhtml">''Minimize''</span>'''    <math>-x_1^2 + 2x_2</math>'''
 +
        <span class="texhtml">''Subject to''</span>'''    <math>x_1^2+x_2^2 \le 1</math>'''
 +
                        <math> x_1 \ge 0</math>
 +
                        <math>x_2 \ge 0</math>
  
 
'''(i)(10pts) Find the points that satisfy the KKT condition.'''  
 
'''(i)(10pts) Find the points that satisfy the KKT condition.'''  

Revision as of 05:22, 26 January 2013

AC - 3 August 2012 QE

Problem 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 − ρ1)(1 − ρ2)(1 − ρ3)...(1 − ρ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}} $


Solution 2:

The uncertainty interval is reduced by $ (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}} $

$ \color{blue} \text{In this specific case, we use only N-1 iterations. } $



(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.


Solution 2: Since the final range is 1 and the initial range is 20, we can say $ \frac{2}{F_{N+1}} \le \frac{1.0}{20} \text{or equivalently } F_{N+1} \ge 40 $

From the inequality, we get $ F_{N+1} \ge 40 , \text{ so } N+1=9 $. Therefore the minimum number of iteration is N-1=7

$ \color{blue} F_9=55 \text{ and } F_8=34 $


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


Problem 3. (20pts) For the system of linear equations,$ Ax=b $ where

$ A = \begin{bmatrix} 1 & 0 &-1 \\ 0 & 1 & 0 \\ 0 & -1& 0 \end{bmatrix}, b = \begin{bmatrix} 0 \\ 2 \\ 1 \end{bmatrix} $


Find the minimum length vector $ x^{(\ast)} $ that minimizes $ \| Ax -b\|^{2}_2 $


Problem 4. (20pts) Use any simplex method to solve the following linear program. 

           Maximize    x1 + 2x2
        S'ubject to    $ -2x_1+x_2 \le 2 $
                       $ x_1-x_2 \ge -3 $
                       $ x_1 \le -3 $
                       $ x_1 \ge 0, x_2 \ge 0. $




Problem 5.(20pts) Solve the following problem: 

           Minimize    $ -x_1^2 + 2x_2 $
        Subject to    $ x_1^2+x_2^2 \le 1 $
                       $  x_1 \ge 0 $
                       $ x_2 \ge 0 $

(i)(10pts) Find the points that satisfy the KKT condition.



(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.

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

Alumni Liaison

Sees the importance of signal filtering in medical imaging

Dhruv Lamba, BSEE2010