(45 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]]
  
 +
<center>
 +
<font size= 4>
 +
[[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]]
 +
</font size>
  
 +
<font size= 4>
 +
Automatic Control (AC)
  
 +
Question 3: Optimization
 +
</font size>
  
−
'''1. (20 pts)
+
August 2012
−
 
+
</center>
−
(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
+
----
−
 
+
----
 +
: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 14: Line 32:
 
</math>  
 
</math>  
  
−
where <math>N - 1 </math> 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> '''(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
  
−
Solution: 
+
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>
  
−
    The reduction factor is <math> (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) </math>
+
:'''Click [[QE2012_AC-3_ECE580-1|here]] to view [[QE2012_AC-3_ECE580-1|student answers and discussions]]'''
−
    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
+
'''Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function'''
−
    <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>
+
−
 
+
−
 
+
−
 
+
−
'''(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
+
−
 
+
−
<math> 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, </math>'''
+
−
 
+
−
 
+
−
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, <math> N+1 = 9</math>
+
−
 
+
−
      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
+
  
 
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
−
        <math>  =\frac{1}{2}x^T  
+
      <math>  =\frac{1}{2}x^T  
 
\begin{bmatrix}
 
\begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
Line 64: Line 56:
 
  \end{bmatrix} + 3.</math>
 
  \end{bmatrix} + 3.</math>
  
−
Where <math>x^{(0)} </math> is arbitrary.'''
+
Where <span class="texhtml">''x''<sup>(0)</sup></span> is arbitrary.  
  
 +
:'''Click [[QE2012_AC-3_ECE580-2|here]] to view [[QE2012_AC-3_ECE580-2|student answers and discussions]]'''
  
 +
----
  
−
Solution:
+
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where '''
−
     
+
−
      <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
+
−
      <math>Use</math> <math>initial</math>  <math> point</math> <math>x^{(0)} = [0, 0]^T and</math> <math> H_0 = I_2</math>
+
−
      <math>In</math> <math>this</math> <math>case,</math>
+
−
      <math>g^{(k)} = \begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix} x^{(k)} - \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}</math>
+
−
 
+
−
      <math> Hence,</math>
+
−
      <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>
+
−
 
+
−
   
+
−
      <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_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>
+
−
 
+
−
      <math>Note</math> <math>that</math> <math>we</math> <math>have</math> <math>d^{(0)^T}Qd^{(0)} = 0;</math>
+
−
      <math>that</math> <math>is,</math> <math>d^{(0)} = \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}</math> <math>and</math> <math>d^{(1)}  = \begin{bmatrix}
+
−
  \frac{4}{5}  \\
+
−
  -\frac{3}{5}
+
−
\end{bmatrix}</math> <math>are</math> <math>Q-conjugate</math> <math>directions.</math>
+
−
 
+
−
 
+
−
 
+
−
'''3. (20pts) For the system of linear equations,<math> Ax = b</math>, where
+
  
 
<math>A = \begin{bmatrix}
 
<math>A = \begin{bmatrix}
Line 267: Line 72:
 
   2 \\
 
   2 \\
 
   1
 
   1
−
  \end{bmatrix}</math>
+
  \end{bmatrix}</math>  
−
 
+
−
Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math>'''
+
−
 
+
−
 
+
−
 
+
−
 
+
−
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>
+
−
 
+
−
 
+
−
 
+
−
 
+
−
'''4. (20pts) Use any simplex method to solve the following linear program.
+
−
            <math>Maximize</math>    <math>x_1 + 2x_2</math>
+
−
            <math>Subject</math> <math>to</math>    <math>-2x_1+x_2 \le 2</math>
+
−
                          <math>x_1-x_2 \ge -3</math>
+
−
                          <math>x_1 \le -3</math>
+
−
                          <math>x_1 \ge 0, x_2 \ge 0.</math>'''
+
−
 
+
−
 
+
−
 
+
−
 
+
−
Solution:
+
−
        We can transfer the problem to the following standard form:
+
−
            <math>Minimize</math>    <math>-x_1 - 2x_2</math>
+
−
            <math>Subject</math> <math>to</math>    <math>-2x_1+x_2 + x_3  = 2</math>
+
−
                          <math> - x_1+x_2 + x_4  = 3</math>
+
−
                          <math>x_1 + x_5  = 3</math>
+
−
                          <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 <math>r_2 = -7 </math>, we bring <math>a_2</math> 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, <math>x_1 = 3,</math> <math>x_2 = 6,</math> maximize the function.
+
−
 
+
−
 
+
−
'''5.(20pts) Solve the following problem:
+
−
            <math>Minimize</math>    <math>-x_1^2 + 2x_2</math>
+
−
            <math>Subject</math> <math>to</math>    <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.'''
+
−
'''
+
−
 
+
−
Solution:
+
−
        Standard Form:
+
−
            <math>Minimize</math>    <math>-x_1^2 + 2x_2</math>
+
−
            <math>Subject</math> <math>to</math>    <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.
+
−
        <math>1. \mu _1, \mu _2 \ge 0</math> 　
+
−
        <math>2. -2x_1 + 2x_1 \mu _1 = 0</math> 　
+
−
          <math>2. 2 + 2x_2 \mu _1 -\mu _2 = 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> 　
+
−
 
+
  
−
        Case 1:
 
−
        <math>If</math> <math>\mu_1 = 0</math> and <math>\mu_2 = 0,</math>
 
−
              <math>then, 2 = 0 </math>which is impossible.
 
−
       
 
−
        Case 2:
 
−
        <math>If</math> <math>\mu_1 = 0</math> and <math>\mu_2 \not= 0,</math>
 
−
              <math>then, \mu_2 = 2, x_1 = 0, x_2 = 0. </math>.
 
  
−
        Case 3:
 
−
        <math>If</math> <math>\mu_1 \not= 0</math> and <math>\mu_2 = 0,</math>
 
−
              <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.
 
−
                        <math>if x1 = 0, then  x_2 = 1, \mu_1 = -1</math>which is impossible.
 
  
−
        Case 4:
+
'''Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math> '''
−
        <math>If</math> <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.
+
:'''Click [[QE2012_AC-3_ECE580-3|here]] to view [[QE2012_AC-3_ECE580-3|student answers and discussions]]'''
−
+
----
−
        <math>\begin{bmatrix}
+
'''Problem 4. (20pts) Use any simplex method to solve the following linear program. '''
−
  \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>
+
  
 +
            <span class="texhtml">''Maximize''</span>'''    <span class="texhtml">''x''<sub>1</sub> + 2''x''<sub>2</sub></span>'''
 +
        <span class="texhtml">''S'ubject to''</span>'''    <math>-2x_1+x_2 \le 2</math>'''
 +
                        <math>x_1-x_2 \ge -3</math>
 +
                        <math>x_1 \le -3</math>
 +
                        <math>x_1 \ge 0, x_2 \ge 0.</math>
  
−
'''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''
+
:'''Click [[QE2012_AC-3_ECE580-4|here]] to view [[QE2012_AC-3_ECE580-4|student answers and discussions]]'''
 +
----
  
−
Solution:  
+
<br> '''Problem 5.(20pts) Solve the following problem:'''
  
−
        Apply SOSC to the first point.
+
            <span class="texhtml">''Minimize''</span>'''    <math>-x_1^2 + 2x_2</math>'''
−
        <math>\nabla g_2(x)^t y = 0</math>
+
         <span class="texhtml">''Subject to''</span>'''    <math>x_1^2+x_2^2 \le 1</math>'''
−
         <math>\begin{bmatrix}
+
                        <math> x_1 \ge 0</math>
−
  0 & -1
+
                        <math>x_2 \ge 0</math>
−
\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}
+
'''(i)(10pts) Find the points that satisfy the KKT condition.'''
−
  -2 & 0 \\ 0 & 0
+
−
\end{bmatrix} </math>
+
−
        <math>Check</math><math> y^tL(x,\mu)y</math>
+
−
        <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.
+
  
  
−
        Apply SOSC to the second point.
 
−
        <math>\nabla g_1(x)^t y = 0, </math>
 
  
−
        <math>\begin{bmatrix}
+
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''
−
  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}
+
:'''Click [[QE2012_AC-3_ECE580-5|here]] to view [[QE2012_AC-3_ECE580-5|student answers and discussions]]'''
−
  -2 & 0 \\ 0 & 0
+
----
−
\end{bmatrix}  + \begin{bmatrix}
+
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]
−
  2 & 0 \\ 0 & 2 
+
−
\end{bmatrix}  = \begin{bmatrix}
+
−
  0 & 0 \\ 0 & 2
+
−
\end{bmatrix} </math>
+
−
        <math>Check</math><math> y^tL(x,\mu)y</math>
+
−
        <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.
+

Latest revision as of 09: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

Prof. Math. Ohio State and Associate Dean
Outstanding Alumnus Purdue Math 2008

Jeff McNeal