(18 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
== '''AC - 3 August 2012 QE'''  ==
+
[[Category:ECE]]
 +
[[Category:QE]]
 +
[[Category:CNSIP]]
 +
[[Category:problem solving]]
 +
[[Category:automatic control]]
 +
[[Category:optimization]]
  
−
'''Problem 1. (20 pts)'''
+
<center>
 +
<font size= 4>
 +
[[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]]
 +
</font size>
  
−
(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
+
<font size= 4>
 +
Automatic Control (AC)
  
 +
Question 3: Optimization
 +
</font size>
 +
 +
August 2012
 +
</center>
 +
----
 +
----
 +
:Student answers and discussions for [[QE2012_AC-3_ECE580-1|Part 1]],[[QE2012_AC-3_ECE580-2|2]],[[QE2012_AC-3_ECE580-2|3]],[[QE2012_AC-3_ECE580-4|4]],[[QE2012_AC-3_ECE580-5|5]]
 +
----
 +
'''1.(20 pts)'''
 +
<br>
 +
'''(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>  
 
<math>  
 
\begin{align}
 
\begin{align}
Line 11: Line 32:
 
</math>  
 
</math>  
  
−
where <span class="texhtml">''N'' − 1</span> is the number of steps performed in the uncertainty range reduction process.  
+
'''where <span class="texhtml">''N'' − 1</span> is the number of steps performed in the uncertainty range reduction process. '''
  
 
<br>  
 
<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 44: Line 41:
 
<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:  
+
:'''Click [[QE2012_AC-3_ECE580-1|here]] to view [[QE2012_AC-3_ECE580-1|student answers and discussions]]'''
−
 
+
----
−
      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 <span class="texhtml">1.0</span> and the initial range is <span class="texhtml">20</span>, we can say '''Failed to parse (syntax error): \frac{2}{F_{N+1}} \le \frac{1.0}{20} or equivalently F_{N+1}} \ge 40 '''  
+
−
 
+
−
From the inequality, we get <math> F_{N+1} \ge 40 , so N+1=9 </math>. Therefore the minimum number of iteration is N-1=7
+
−
 
+
−
<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 78: Line 58:
 
Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary.  
 
Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary.  
  
−
<br>
+
:'''Click [[QE2012_AC-3_ECE580-2|here]] to view [[QE2012_AC-3_ECE580-2|student answers and discussions]]'''
  
−
Solution:
+
----
  
−
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
+
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where '''
−
    <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" />'''h'''i'''s'' <span class="texhtml" />''c'''a'''s'''e'''''<b>,</b>''
+
−
    <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''</span>'''''u'''a'''d'''r'''a'''t'''i'''c'''''<b><span class="texhtml">''f''</span></b>''u'''n'''c'''t'''i'''o'''n'',
+
−
 
+
−
      <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'''''<b>:</b></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>
+
−
    <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> <span class="texhtml">''a''''n''''d''</span> <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>
+
−
 
+
−
<br>
+
−
 
+
−
'''Problem 3. (20pts) For the system of linear equations,<span class="texhtml" />''''x'' = ''b'', where
+
  
 
<math>A = \begin{bmatrix}
 
<math>A = \begin{bmatrix}
Line 285: Line 76:
  
  
−
Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math>  
+
'''Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math> '''
  
−
<br>
+
:'''Click [[QE2012_AC-3_ECE580-3|here]] to view [[QE2012_AC-3_ECE580-3|student answers and discussions]]'''
−
 
+
----
−
<br> Solutions:  
+
−
 
+
−
      <math>A = BC = \begin{bmatrix}
+
−
  1 & 0  \\
+
−
  0 & 1  \\
+
−
  0 & -1
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  1 & 0 &-1  \\
+
−
  0 & 1 & 0 
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math>B^{\dagger} = (B^T B)^{-1}B^T = \begin{bmatrix}
+
−
  1 & 0 \\
+
−
  0 & 2 
+
−
\end{bmatrix}^{-1} \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & 1 & -1 
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2} 
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math>C^{\dagger} = C^T(CC^T)^{-1} =\begin{bmatrix}
+
−
  1 & 0  \\
+
−
  0 & 1  \\
+
−
  -1 & 0
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  2 & 0 \\
+
−
  0 & 1 
+
−
\end{bmatrix}^{-1} = \begin{bmatrix}
+
−
  \frac{1}{2} & 0  \\
+
−
  0 & 1  \\
+
−
  -\frac{1}{2} & 0
+
−
\end{bmatrix} </math>
+
−
 
+
−
      <math>A^{\dagger} = C^{\dagger}B^{\dagger} =\begin{bmatrix}
+
−
  \frac{1}{2} & 0  \\
+
−
  0 & 1  \\
+
−
  -\frac{1}{2} & 0
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2} 
+
−
\end{bmatrix} =  \begin{bmatrix}
+
−
  \frac{1}{2} & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2}  \\
+
−
  -\frac{1}{2} & 0 & 0
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math> x^{\ast} = A^{\dagger} b = \begin{bmatrix}
+
−
  \frac{1}{2} & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2}  \\
+
−
  -\frac{1}{2} & 0 & 0
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  0 \\
+
−
  \frac{1}{2} \\
+
−
  1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  0 \\
+
−
  \frac{1}{2} \\
+
−
  0
+
−
\end{bmatrix}</math>
+
−
 
+
−
<br>
+
−
 
+
−
Solution 2:
+
−
 
+
−
<math>x^{(\ast)}=A^{\dagger}b</math>
+
−
 
+
−
Since <math>A = BC = \begin{bmatrix}
+
−
  1 & 0  \\
+
−
  0 & 1  \\
+
−
  0 & -1
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  1 & 0 &-1  \\
+
−
  0 & 1 & 0 
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>B^{\dagger} = (B^T B)^{-1}B^T = \begin{bmatrix}
+
−
  1 & 0 \\
+
−
  0 & 2 
+
−
\end{bmatrix}^{-1} \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & 1 & -1 
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2} 
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math>C^{\dagger} = C^T(CC^T)^{-1} =\begin{bmatrix}
+
−
  1 & 0  \\
+
−
  0 & 1  \\
+
−
  -1 & 0
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  2 & 0 \\
+
−
  0 & 1 
+
−
\end{bmatrix}^{-1} = \begin{bmatrix}
+
−
  \frac{1}{2} & 0  \\
+
−
  0 & 1  \\
+
−
  -\frac{1}{2} & 0
+
−
\end{bmatrix} </math>
+
−
 
+
−
      <math>A^{\dagger} = C^{\dagger}B^{\dagger} =\begin{bmatrix}
+
−
  \frac{1}{2} & 0  \\
+
−
  0 & 1  \\
+
−
  -\frac{1}{2} & 0
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  1 & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2} 
+
−
\end{bmatrix} =  \begin{bmatrix}
+
−
  \frac{1}{2} & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2}  \\
+
−
  -\frac{1}{2} & 0 & 0
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math> x^{\ast} = A^{\dagger} b = \begin{bmatrix}
+
−
  \frac{1}{2} & 0 & 0  \\
+
−
  0 & \frac{1}{2} & -\frac{1}{2}  \\
+
−
  -\frac{1}{2} & 0 & 0
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  0 \\
+
−
  \frac{1}{2} \\
+
−
  1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  0 \\
+
−
  \frac{1}{2} \\
+
−
  0
+
−
\end{bmatrix}</math>
+
−
 
+
−
<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 426: Line 88:
 
                         <math>x_1 \ge 0, x_2 \ge 0.</math>
 
                         <math>x_1 \ge 0, x_2 \ge 0.</math>
  
−
<br>
+
:'''Click [[QE2012_AC-3_ECE580-4|here]] to view [[QE2012_AC-3_ECE580-4|student answers and discussions]]'''
−
 
+
----
−
<br> Solution:  
+
−
 
+
−
        We can transfer the problem to the following standard form:
+
−
        <span class="texhtml">''Mnimize''</span>'''    <span class="texhtml"> − ''x''<sub>1</sub> − 2''x''<sub>2</sub></span>'''
+
−
        <span class="texhtml">''Sbject to''</span>'''    <span class="texhtml"> − 2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>'''
+
−
                        <span class="texhtml"> − ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span>
+
−
                        <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>5</sub> = 3</span>
+
−
                        <math>x_1, x_2, x_3, x_4, x_5 \ge 0.</math>
+
−
 
+
−
        We form the corresponding tableau for the problem
+
−
      <math>\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  -2 & 1& 1 &0& 0& 2 \\
+
−
  -1& 1& 0 &1 &0 &3\\
+
−
  1 &0& 0& 0& 1& 3\\
+
−
  -1& -2 &0& 0& 0& 0
+
−
\end{matrix}</math>
+
−
     
+
−
Since it is already in canonical form. Because <span class="texhtml">''r''<sub>2</sub> =  − 7</span>, we bring <span class="texhtml">''a''<sub>2</sub></span> into the basis.
+
−
 
+
−
      After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
+
−
      <math>\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  -2 & 1& 1 &0& 0& 2 \\
+
−
  1& 0& -1 &1 &0 &1\\
+
−
  1 &0& 0& 0& 1& 3\\
+
−
  -5& 0 &2& 0& 0& 4
+
−
\end{matrix}</math>
+
−
 
+
−
      Similarly, we pivot about the (2,1) element to obtain
+
−
      <math>\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  0 & 1& -1 &2& 0& 4 \\
+
−
  1& 0& -1 &1 &0 &1\\
+
−
  0 &0& 1& -1& 1& 2\\
+
−
  0& 0 &-3& 5& 0& 9
+
−
\end{matrix}</math>
+
−
 
+
−
      Similarly, we pivot about the (3,3) element to obtain
+
−
      <math>\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  0 & 1& 0 &1& 1& 6 \\
+
−
  1& 0& 0 &0 &1 &3\\
+
−
  0 &0& 1& -1& 1& 2\\
+
−
  0& 0 &0& 2& 3& 15
+
−
\end{matrix}</math>
+
−
 
+
−
      Therefore, <span class="texhtml">''x''<sub>1</sub> = 3,</span> <span class="texhtml">''x''<sub>2</sub> = 6,</span> maximize the function.
+
−
 
+
−
Solution 2:
+
−
 
+
−
The standard form for this problem is
+
−
        <span class="texhtml">''Mnimize''</span>'''    <span class="texhtml"> − ''x''<sub>1</sub> − 2''x''<sub>2</sub></span>'''
+
−
        <span class="texhtml">''Sbject to''</span>'''    <span class="texhtml"> − 2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>'''
+
−
                        <span class="texhtml"> − ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span>
+
−
                        <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>5</sub> = 3</span>
+
−
                        <math>x_1, x_2, x_3, x_4, x_5 \ge 0.</math>
+
−
 
+
−
<math>\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  -2 & 1& 1 &0& 0& 2 \\
+
−
  -1& 1& 0 &1 &0 &3\\
+
−
  1 &0& 0& 0& 1& 3\\
+
−
  -1& -2 &0& 0& 0& 0
+
−
\end{matrix}\Rightarrow
+
−
 
+
−
\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  -2 & 1& 1 &0& 0& 2 \\
+
−
  1& 0& -1 &1 &0 &1\\
+
−
  1 &0& 0& 0& 1& 3\\
+
−
  -5& 0 &2& 0& 0& 4
+
−
\end{matrix}
+
−
\Rightarrow
+
−
\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  0 & 1& -1 &2& 0& 4 \\
+
−
  1& 0& -1 &1 &0 &1\\
+
−
  0 &0& 1& -1& 1& 2\\
+
−
  0& 0 &-3& 5& 0& 9
+
−
\end{matrix}
+
−
\Rightarrow
+
−
\begin{matrix}
+
−
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
+
−
  0 & 1& 0 &1& 1& 6 \\
+
−
  1& 0& 0 &0 &1 &3\\
+
−
  0 &0& 1& -1& 1& 2\\
+
−
  0& 0 &0& 2& 3& 15
+
−
\end{matrix}</math>
+
−
 
+
−
From the last tableau, we can see that <math>\begin{bmatrix}
+
−
  x^{1} = 3\\ x^{2} = 6 
+
−
\end{bmatrix}</math>
+
−
maximizes the object function. The maximum value is 15
+
  
 
<br> '''Problem 5.(20pts) Solve the following problem:'''  
 
<br> '''Problem 5.(20pts) Solve the following problem:'''  
Line 532: Line 100:
 
'''(i)(10pts) Find the points that satisfy the KKT condition.'''  
 
'''(i)(10pts) Find the points that satisfy the KKT condition.'''  
  
−
Solution:
 
  
−
        Standard Form:
 
−
        <span class="texhtml">''Minimize''</span>'''    <math>-x_1^2 + 2x_2</math>'''
 
−
        <span class="texhtml">''Su''</span>'''  <math>g_1(x) = x_1^2+x_2^2 - 1 \le 0</math>'''
 
−
                        <math>g_2(x) = -x_2 \le 0</math>
 
  
−
        The KKT Condition.
+
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''
−
      <math>1. \mu _1, \mu _2 \ge 0</math> 　
+
−
      <span class="texhtml">2. − 2''x''<sub>1</sub> + 2''x''<sub>1</sub>μ<sub>1</sub> = 0</span> 　
+
−
        <span class="texhtml">2.2 + 2''x''<sub>2</sub>μ<sub>1</sub> − μ<sub>2</sub> = 0</span> 　
+
−
      <math>3. (x_1^2+x_2^2-1)\mu_1 - x_2\mu _2 = 0</math> 　
+
−
      <math>4. g_1(x),g_2(x) \le 0</math> 　
+
−
 
+
−
<br>
+
−
 
+
−
        Case 1:
+
−
      <span class="texhtml">''I''''f'''''</span>''''' <span class="texhtml">μ<sub>1</sub> = 0</span> and <span class="texhtml">μ<sub>2</sub> = 0,</span>'''''
+
−
            <span class="texhtml">''t''''h''''e''''n'''''<b>,2 = 0</b></span>'''which is impossible.'''
+
−
     
+
−
      Case 2:
+
−
      <span class="texhtml">''I''''f'''''</span>''''' <span class="texhtml">μ<sub>1</sub> = 0</span> and <math>\mu_2 \not= 0,</math>'''''
+
−
            <span class="texhtml">''t''''h''''e''''n'''''<b>,μ<sub>2</sub> = 2,''x''<sub>1</sub> = 0,''x''<sub>2</sub> = 0.</b></span>'''.'''
+
−
 
+
−
        Case 3:
+
−
      <span class="texhtml">''I''''f'''''</span>''''' <math>\mu_1 \not= 0</math> and <span class="texhtml">μ<sub>2</sub> = 0,</span>'''''
+
−
            <math>then, x_1^2 + x_2^2 = 1 </math>
+
−
                      <math>if x1 \not= 0, then \mu_1 = 1, x_2 = -1 </math>which is impossible.
+
−
                      <span class="texhtml">''i'''f '''x''1 = 0,''then x''<sub>2</sub> = 1,μ<sub>1</sub> =  − 1</span>which is impossible.
+
−
 
+
−
        Case 4:
+
−
      <span class="texhtml">''I''''f'''''</span>''''' <math>\mu_1 \not= 0</math> and <math>\mu_2 \not= 0,</math>'''''
+
−
            <math>then, x_2 = 0, x_1^2 + x_2^2 = 1. So,  x_1 = 1, \mu_1 = 1, \mu_2 = 2. </math>.
+
−
 
+
−
        Therefore, there are two points that satisfy KKT condition.
+
−
+
−
      <math>\begin{bmatrix}
+
−
  \mu_1 ^{\ast}= 0 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 0 \\x_2^{\ast}= 0
+
−
\end{bmatrix}and \begin{bmatrix}
+
−
  \mu_1 ^{\ast}= 1 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 1 \\x_2^{\ast}= 0
+
−
\end{bmatrix} </math>
+
−
 
+
−
Solution 2:
+
−
 
+
−
Because in both the object and subject function, the term related to <math>x_1</math> is <math>x_1^{2}</math>, which doesn't depend on the sign of <math>x_1</math>, we can ignore the constraint function <math> x_1 >0 </math> for now.
+
−
 
+
−
The standard form of the optimizing problem is
+
−
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;
+
−
<math>\text{minimize } -x_1^2 + 2x_2</math>
+
−
 
+
−
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\text{subject to  }  g_1(x)=x_1^2+x_2^2-1 \le 0  \text { and }  g_2(x)=-x_2 \le 0</math>
+
−
 
+
−
The KKT Condition.
+
−
      <math>1. \mu _1, \mu _2 \ge 0</math> 　
+
−
      <math>2.\begin{bmatrix}
+
−
  -2x_1+2\mu_1 x_1 \\ 2+2\mu_1 x_2-\mu_2
+
−
\end{bmatrix}=0</math>
+
−
      <math>3. (x_1^2+x_2^2-1)\mu_1 - x_2\mu _2 = 0</math> 　
+
−
      <math>4. g_1(x),g_2(x) \le 0</math> 　
+
−
 
+
−
<math>\text {Case 1: } \mu_1=\mu_2=0 \text{, which implies } 2=0 \Rightarrow \text{Impossible} </math>
+
−
 
+
−
<math>\text {Case 2: } \mu_1 \neq 0,  \mu_2=0 \Rightarrow
+
−
\left\{\begin{matrix}
+
−
 
+
−
x_1^2+x_2^2-1=0\\
+
−
-2x_1+2\mu_1x_1=0\\
+
−
2+2\mu_1 x_1=0
+
−
\end{matrix}\right. \Rightarrow
+
−
 
+
−
\left\{\begin{matrix}
+
−
 
+
−
\mu_1=1\\
+
−
\mu_2=0\\
+
−
x_1=0\\
+
−
x_2=-1
+
−
\end{matrix}\right.
+
−
 
+
−
\Rightarrow
+
−
 
+
−
x_2<0,
+
−
\text{ Impossible }
+
−
 
+
−
</math>
+
−
 
+
−
 
+
−
 
+
−
<math>\text {Case 3: } \mu_1 = 0,  \mu_2 \neq 0 \Rightarrow
+
−
\left\{\begin{matrix}
+
−
 
+
−
-x_2\mu_2=0\\
+
−
-2x_1=0\\
+
−
2-\mu_2=0
+
−
\end{matrix}\right. \Rightarrow
+
−
 
+
−
\left\{\begin{matrix}
+
−
 
+
−
\mu_1=0\\
+
−
\mu_2=2\\
+
−
x_1=0\\
+
−
x_2=0
+
−
\end{matrix}\right.
+
−
 
+
−
</math>
+
−
 
+
−
<math>\text {Case 4: } \mu_1 \neq 0,  \mu_2 \neq 0 \Rightarrow
+
−
\left\{\begin{matrix}
+
−
 
+
−
x_1^2+x_2^2-1=0\\
+
−
x_2=0\\
+
−
\end{matrix}\right. \Rightarrow
+
−
 
+
−
\left\{\begin{matrix}
+
−
 
+
−
\mu_1=1\\
+
−
\mu_2=2\\
+
−
x_1=1\\
+
−
x_2=0
+
−
\end{matrix}\right.
+
−
 
+
−
</math>
+
−
 
+
−
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''  
+
−
 
+
−
Solution:
+
−
 
+
−
        Apply SOSC to the first point.
+
−
      <math>\nabla g_2(x)^t y = 0</math>
+
−
      <math>\begin{bmatrix}
+
−
  0 & -1
+
−
\end{bmatrix} y = 0</math>
+
−
      <math>y = \begin{bmatrix}
+
−
  a \\ 0
+
−
\end{bmatrix},  a\not= 0</math>
+
−
 
+
−
        <math>L(x,\mu) = F(x) + \mu_2 G_2(x) =\begin{bmatrix}
+
−
  -2 & 0 \\ 0 & 0
+
−
\end{bmatrix} </math>
+
−
      <span class="texhtml">''Check ''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
+
−
      <math>\begin{bmatrix}
+
−
  a & 0
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  -2 & 0 \\ 0 & 0
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  a \\ 0
+
−
\end{bmatrix} = -2a^2 \lneq 0</math> which means SOSC fails.
+
−
 
+
−
<br>
+
−
 
+
−
        Apply SOSC to the second point.
+
−
      <math>\nabla g_1(x)^t y = 0, </math>
+
−
 
+
−
        <math>\begin{bmatrix}
+
−
  2x_1 & 2x_2
+
−
\end{bmatrix} y = 0</math>
+
−
      <math>y = \begin{bmatrix}
+
−
  0 \\ a
+
−
\end{bmatrix} where a\not= 0</math>
+
−
 
+
−
        <math>L(x,\mu) = F(x) + \mu_1 G_1(x) + \mu_2 G_2(x) =\begin{bmatrix}
+
−
  -2 & 0 \\ 0 & 0
+
−
\end{bmatrix}  + \begin{bmatrix}
+
−
  2 & 0 \\ 0 & 2 
+
−
\end{bmatrix}  = \begin{bmatrix}
+
−
  0 & 0 \\ 0 & 2
+
−
\end{bmatrix} </math>
+
−
      <span class="texhtml">''Check ''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
+
−
      <math>\begin{bmatrix}
+
−
  0 & a
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  0 & 0 \\ 0 & 2
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  0 \\ a
+
−
\end{bmatrix} = 2a^2 \gneq 0</math> that implies
+
−
      <math>\begin{bmatrix}
+
−
  x^{\ast} = 1\\ x^{\ast} = 0
+
−
\end{bmatrix}</math> is the minimized point.
+
−
 
+
−
Solution 2:
+
−
 
+
−
<math>\text{For } \left\{\begin{matrix}
+
−
 
+
−
\mu_1=0\\
+
−
\mu_2=2\\
+
−
x_1=0\\
+
−
x_2=0
+
−
\end{matrix}\right. \text{, let } \nabla g_2(x)^T y=0, \text{We get } y=\begin{bmatrix}
+
−
  a\\  0
+
−
\end{bmatrix} \text{, where } y \text { are all the points on the tangent plane}</math>
+
−
 
+
−
<math>
+
−
L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix}
+
−
  -2 & 0\\ 0 & 0
+
−
\end{bmatrix}
+
−
</math>
+
−
 
+
−
<math>
+
−
y^T L(x,\mu)y=-2a^2 \le 0 \Rightarrow \text{It doesn;t satisfy SOSC}
+
−
</math>
+
−
 
+
−
 
+
−
<math>\text{For } \left\{\begin{matrix}
+
−
 
+
−
\mu_1=1\\
+
−
\mu_2=2\\
+
−
x_1=1\\
+
−
x_2=0
+
−
\end{matrix}\right. \text{, let } \nabla g_2(x)^T y=0, \text{We get } y=\begin{bmatrix}
+
−
  0\\ a
+
−
\end{bmatrix} \text{, where } y \text { are all the points on the tangent plane}</math>
+
−
 
+
−
<math>
+
−
L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix}
+
−
  0 & 0\\ 0 & 2
+
−
\end{bmatrix}
+
−
</math>
+
−
 
+
−
<math>
+
−
y^T L(x,\mu)y=2a^2 \geq 0 \Rightarrow \text{It doesn;t satisfy SOSC}
+
−
</math>
+
−
 
+
−
<math>
+
−
\text{So, }
+
−
\begin{bmatrix}
+
−
x^{\ast} = 1\\ x^{\ast} = 0
+
−
\end{bmatrix}
+
−
\text{is the minimum point.}
+
−
</math>
+
−
 
+
−
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>
+
:'''Click [[QE2012_AC-3_ECE580-5|here]] to view [[QE2012_AC-3_ECE580-5|student answers and discussions]]'''
−
\text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix}
+
----
−
  3 \\
+
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]
−
  -1
+
−
\end{bmatrix}
+
−
</math>
+

Latest revision as of 10:17, 13 September 2013


ECE Ph.D. Qualifying Exam

Automatic Control (AC)

Question 3: Optimization

August 2012

Student answers and discussions for Part 1,2,3,4,5

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.




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

Click here to view student answers and discussions

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.

Click here to view student answers and discussions

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 $

Click here to view student answers and discussions

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. $
Click here to view student answers and discussions


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.

Click here to view student answers and discussions

Back to ECE QE page

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

Alumni Liaison

Recent Math PhD now doing a post-doctorate at UC Riverside.

Kuei-Nuan Lin