Line 1: Line 1:
== '''AC - 3 August 2012 QE''' ==
+
== '''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  
 
+
'''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
+
  
 
<math>  
 
<math>  
Line 14: Line 11:
 
</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> 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>
Solution: 
+
  Since  
 
+
  <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>
+
  we have  
    Since  
+
  <math> 1- \rho_{N-2} = \frac{F_{3}}{F_{4}}</math>    and so on.
    <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
 
     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>
+
  <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
+
  Therefore, the reduction factor is
    <math>\frac{2}{F_{N+1}}</math>
+
  <math>\frac{2}{F_{N+1}}</math>
  
 +
<br>
  
 +
<font color="#ff0000">
 +
Solution :2
  
'''(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>'''
+
'''(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:  
+
<br> Solution:  
  
 
       Final Range: 1.0; Initial Range: 20.
 
       Final Range: 1.0; Initial Range: 20.
Line 46: Line 44:
 
       <math> \frac{2}{F_{N+1}} \le \frac{1.0}{20}</math>, or <math> F_{N+1} \ge 40</math>  
 
       <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>
+
       So, <span class="texhtml">''N'' + 1 = 9</span>
  
 
       Therefore, the minimal iterations is N-1 or 7.
 
       Therefore, the minimal iterations is N-1 or 7.
  
 +
<br>
  
 
+
'''2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function'''
'''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 62:
 
  \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.  
 
+
  
 +
<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>
      <math>Use</math> <math>initial</math>  <math> point</math> <math>x^{(0)} = [0, 0]^T and</math> <math> H_0 = I_2</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>
      <math>In</math> <math>this</math> <math>case,</math>
+
      <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}
+
      <math>g^{(k)} = \begin{bmatrix}
 
   1 & 1 \\
 
   1 & 1 \\
 
   1 & 2
 
   1 & 2
Line 81: Line 79:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
       <math> Hence,</math>  
+
       <span class="texhtml">''H''''e''''n''''c''''e'',</span>  
      <math>g^{(0)} = \begin{bmatrix}
+
      <math>g^{(0)} = \begin{bmatrix}
 
   -2  \\
 
   -2  \\
 
   -1
 
   -1
Line 96: Line 94:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
   
+
<br>
       <math>Because</math> <math>f</math> <math>is</math> <math>a</math> <math>quadratic</math> <math>function,</math>
+
 
 +
       <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>
  
 
       <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 125: Line 124:
 
   \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 141: Line 140:
 
  \end{bmatrix} </math>
 
  \end{bmatrix} </math>
  
 +
<br>
  
       <math>Observe</math> <math>that:</math>
+
       <span class="texhtml">''O''''b''''s''''e''''r''''v''''e''</span> <span class="texhtml">''t''''h''''a''''t'':</span>
      <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 152: Line 152:
 
   \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 158: Line 158:
 
   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 171: Line 171:
 
   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 179: Line 179:
 
   \frac{3}{2}  \\ 2  
 
   \frac{3}{2}  \\ 2  
 
  \end{bmatrix} = \frac{25}{4}</math>
 
  \end{bmatrix} = \frac{25}{4}</math>
      <math>Using</math> <math>the</math> <math>above, </math> <math>now</math> <math>we</math> <math>compute</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>
      <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 194: Line 194:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
       <math>Then</math> <math>we</math> <math>have,</math>
+
       <span class="texhtml">''T''''h''''e''''n''</span> <span class="texhtml">''w''''e''</span> <span class="texhtml">''h''''a''''v''''e'',</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 235: Line 235:
 
   -\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 246: Line 246:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
       <math>Note</math> <math>that</math> <math>we</math> <math>have</math> <math>d^{(0)^T}Qd^{(0)} = 0;</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>
      <math>that</math> <math>is,</math> <math>d^{(0)} = \begin{bmatrix}
+
      <span class="texhtml">''t''''h''''a''''t''</span> <span class="texhtml">''i''''s'',</span> <math>d^{(0)} = \begin{bmatrix}
 
   2  \\
 
   2  \\
 
   1
 
   1
  \end{bmatrix}</math> <math>and</math> <math>d^{(1)}  = \begin{bmatrix}
+
  \end{bmatrix}</math> <span class="texhtml">''a''''n''''d''</span> <math>d^{(1)}  = \begin{bmatrix}
 
   \frac{4}{5}  \\
 
   \frac{4}{5}  \\
 
   -\frac{3}{5}
 
   -\frac{3}{5}
  \end{bmatrix}</math> <math>are</math> <math>Q-conjugate</math> <math>directions.</math>
+
  \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>
  
 +
<br>
  
 
+
'''3. (20pts) For the system of linear equations,<span class="texhtml">''A''''x'' = ''b''</span>, where'''
'''3. (20pts) For the system of linear equations,<math> Ax = b</math>, where
+
  
 
<math>A = \begin{bmatrix}
 
<math>A = \begin{bmatrix}
Line 267: Line 267:
 
   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>'''
+
 
+
  
 +
Find the minimum length vector <math>x^{(\ast)}</math> that minimizes <math>\| Ax -b\|^{2}_2</math>
  
 +
<br>
  
Solutions:
+
<br> Solutions:  
  
 
       <math>A = BC = \begin{bmatrix}
 
       <math>A = BC = \begin{bmatrix}
Line 336: Line 335:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
  
 +
<br>
  
 +
<br> '''4. (20pts) Use any simplex method to solve the following linear program. '''
  
 +
            <span class="texhtml">''M''''a''''x''''i''''m''''i''''z''''e''</span>    <span class="texhtml">''x''<sub>1</sub> + 2''x''<sub>2</sub></span>
 +
          <span class="texhtml">''S''''u''''b''''j''''e''''c''''t''</span> <span class="texhtml">''t''''o''</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>
  
'''4. (20pts) Use any simplex method to solve the following linear program.
+
<br>  
            <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>'''
+
  
 +
<br> Solution:
  
 
 
Solution:
 
 
         We can transfer the problem to the following standard form:
 
         We can transfer the problem to the following standard form:
            <math>Minimize</math>    <math>-x_1 - 2x_2</math>
+
          <span class="texhtml">''M''''i''''n''''i''''m''''i''''z''''e''</span>    <span class="texhtml"> − ''x''<sub>1</sub> − 2''x''<sub>2</sub></span>
            <math>Subject</math> <math>to</math>    <math>-2x_1+x_2 + x_3  = 2</math>
+
          <span class="texhtml">''S''''u''''b''''j''''e''''c''''t''</span> <span class="texhtml">''t''''o''</span>    <span class="texhtml"> − 2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>
                          <math> - x_1+x_2 + x_4  = 3</math>
+
                          <span class="texhtml"> − ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span>
                          <math>x_1 + x_5  = 3</math>
+
                          <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>x_1, x_2, x_3, x_4, x_5 \ge 0.</math>
  
 
         We form the corresponding tableau for the problem
 
         We form the corresponding tableau for the problem
        <math>\begin{matrix}
+
        <math>\begin{matrix}
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   -2 & 1& 1 &0& 0& 2 \\
 
   -2 & 1& 1 &0& 0& 2 \\
Line 365: Line 364:
 
   -1& -2 &0& 0& 0& 0
 
   -1& -2 &0& 0& 0& 0
 
  \end{matrix}</math>
 
  \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.
+
      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
 
       After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
        <math>\begin{matrix}
+
        <math>\begin{matrix}
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   -2 & 1& 1 &0& 0& 2 \\
 
   -2 & 1& 1 &0& 0& 2 \\
Line 378: Line 377:
  
 
       Similarly, we pivot about the (2,1) element to obtain  
 
       Similarly, we pivot about the (2,1) element to obtain  
        <math>\begin{matrix}
+
        <math>\begin{matrix}
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   0 & 1& -1 &2& 0& 4 \\
 
   0 & 1& -1 &2& 0& 4 \\
Line 387: Line 386:
  
 
       Similarly, we pivot about the (3,3) element to obtain  
 
       Similarly, we pivot about the (3,3) element to obtain  
        <math>\begin{matrix}
+
        <math>\begin{matrix}
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 
   0 & 1& 0 &1& 1& 6 \\
 
   0 & 1& 0 &1& 1& 6 \\
Line 395: Line 394:
 
  \end{matrix}</math>
 
  \end{matrix}</math>
  
       Therefore, <math>x_1 = 3,</math> <math>x_2 = 6,</math> maximize the function.
+
       Therefore, <span class="texhtml">''x''<sub>1</sub> = 3,</span> <span class="texhtml">''x''<sub>2</sub> = 6,</span> maximize the function.
  
 +
<br> '''5.(20pts) Solve the following problem:'''
  
'''5.(20pts) Solve the following problem:
+
            <span class="texhtml">''M''''i''''n''''i''''m''''i''''z''''e''</span>    <math>-x_1^2 + 2x_2</math>
            <math>Minimize</math>    <math>-x_1^2 + 2x_2</math>
+
          <span class="texhtml">''S''''u''''b''''j''''e''''c''''t''</span> <span class="texhtml">''t''''o''</span>    <math>x_1^2+x_2^2 \le 1</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_1 \ge 0</math>
+
                          <math>x_2 \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.'''  
'''
+
 
 +
Solution:
  
Solution:
 
 
         Standard Form:
 
         Standard Form:
            <math>Minimize</math>    <math>-x_1^2 + 2x_2</math>
+
          <span class="texhtml">''M''''i''''n''''i''''m''''i''''z''''e''</span>    <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>
+
          <span class="texhtml">''S''''u''''b''''j''''e''''c''''t''</span> <span class="texhtml">''t''''o''</span>    <math>g_1(x) = x_1^2+x_2^2 - 1 \le 0</math>
                          <math>g_2(x) = -x_2 \le 0</math>
+
                          <math>g_2(x) = -x_2 \le 0</math>
  
 
         The KKT Condition.
 
         The KKT Condition.
        <math>1. \mu _1, \mu _2 \ge 0</math>  
+
        <math>1. \mu _1, \mu _2 \ge 0</math>  
        <math>2. -2x_1 + 2x_1 \mu _1 = 0</math>  
+
        <span class="texhtml">2. − 2''x''<sub>1</sub> + 2''x''<sub>1</sub>μ<sub>1</sub> = 0</span>  
          <math>2. 2 + 2x_2 \mu _1 -\mu _2 = 0</math>  
+
          <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>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>4. g_1(x),g_2(x) \le 0</math>  
  
 +
<br>
  
 
         Case 1:
 
         Case 1:
        <math>If</math> <math>\mu_1 = 0</math> and <math>\mu_2 = 0,</math>
+
        <span class="texhtml">''I''''f''</span> <span class="texhtml">μ<sub>1</sub> = 0</span> and <span class="texhtml">μ<sub>2</sub> = 0,</span>
              <math>then, 2 = 0 </math>which is impossible.
+
              <span class="texhtml">''t''''h''''e''''n'',2 = 0</span>which is impossible.
       
+
       
        Case 2:
+
        Case 2:
        <math>If</math> <math>\mu_1 = 0</math> and <math>\mu_2 \not= 0,</math>
+
        <span class="texhtml">''I''''f''</span> <span class="texhtml">μ<sub>1</sub> = 0</span> and <math>\mu_2 \not= 0,</math>
              <math>then, \mu_2 = 2, x_1 = 0, x_2 = 0. </math>.
+
              <span class="texhtml">''t''''h''''e''''n'',μ<sub>2</sub> = 2,''x''<sub>1</sub> = 0,''x''<sub>2</sub> = 0.</span>.
  
 
         Case 3:
 
         Case 3:
        <math>If</math> <math>\mu_1 \not= 0</math> and <math>\mu_2 = 0,</math>
+
        <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>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 \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.
+
                        <span class="texhtml">''i''''f''''x''1 = 0,''t''''h''''e''''n''''x''<sub>2</sub> = 1,μ<sub>1</sub> = 1</span>which is impossible.
  
 
         Case 4:
 
         Case 4:
        <math>If</math> <math>\mu_1 \not= 0</math> and <math>\mu_2 \not= 0,</math>
+
        <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>.
+
              <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.
 
         Therefore, there are two points that satisfy KKT condition.
 
   
 
   
        <math>\begin{bmatrix}
+
        <math>\begin{bmatrix}
 
   \mu_1 ^{\ast}= 0 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 0 \\x_2^{\ast}= 0  
 
   \mu_1 ^{\ast}= 0 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 0 \\x_2^{\ast}= 0  
 
  \end{bmatrix}and \begin{bmatrix}
 
  \end{bmatrix}and \begin{bmatrix}
Line 447: Line 447:
 
  \end{bmatrix} </math>  
 
  \end{bmatrix} </math>  
  
 
+
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''  
'''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''
+
  
 
Solution:  
 
Solution:  
  
 
         Apply SOSC to the first point.
 
         Apply SOSC to the first point.
        <math>\nabla g_2(x)^t y = 0</math>
+
        <math>\nabla g_2(x)^t y = 0</math>
        <math>\begin{bmatrix}
+
        <math>\begin{bmatrix}
 
   0 & -1
 
   0 & -1
 
  \end{bmatrix} y = 0</math>
 
  \end{bmatrix} y = 0</math>
        <math>y = \begin{bmatrix}
+
        <math>y = \begin{bmatrix}
 
   a \\ 0
 
   a \\ 0
 
  \end{bmatrix},  a\not= 0</math>
 
  \end{bmatrix},  a\not= 0</math>
Line 464: Line 463:
 
   -2 & 0 \\ 0 & 0  
 
   -2 & 0 \\ 0 & 0  
 
  \end{bmatrix} </math>
 
  \end{bmatrix} </math>
        <math>Check</math><math> y^tL(x,\mu)y</math>
+
        <span class="texhtml">''C''''h''''e''''c''''k''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
        <math>\begin{bmatrix}
+
        <math>\begin{bmatrix}
 
   a & 0
 
   a & 0
 
  \end{bmatrix}\begin{bmatrix}
 
  \end{bmatrix}\begin{bmatrix}
Line 473: Line 472:
 
  \end{bmatrix} = -2a^2 \lneq 0</math> which means SOSC fails.
 
  \end{bmatrix} = -2a^2 \lneq 0</math> which means SOSC fails.
  
 +
<br>
  
 
         Apply SOSC to the second point.
 
         Apply SOSC to the second point.
        <math>\nabla g_1(x)^t y = 0, </math>
+
        <math>\nabla g_1(x)^t y = 0, </math>
  
 
         <math>\begin{bmatrix}
 
         <math>\begin{bmatrix}
 
   2x_1 & 2x_2
 
   2x_1 & 2x_2
 
  \end{bmatrix} y = 0</math>
 
  \end{bmatrix} y = 0</math>
        <math>y = \begin{bmatrix}
+
        <math>y = \begin{bmatrix}
 
   0 \\ a
 
   0 \\ a
 
  \end{bmatrix} where a\not= 0</math>
 
  \end{bmatrix} where a\not= 0</math>
Line 491: Line 491:
 
   0 & 0 \\ 0 & 2  
 
   0 & 0 \\ 0 & 2  
 
  \end{bmatrix} </math>
 
  \end{bmatrix} </math>
        <math>Check</math><math> y^tL(x,\mu)y</math>
+
        <span class="texhtml">''C''''h''''e''''c''''k''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
        <math>\begin{bmatrix}
+
        <math>\begin{bmatrix}
 
   0 & a
 
   0 & a
 
  \end{bmatrix}\begin{bmatrix}
 
  \end{bmatrix}\begin{bmatrix}
Line 499: Line 499:
 
   0 \\ a
 
   0 \\ a
 
  \end{bmatrix} = 2a^2 \gneq 0</math> that implies
 
  \end{bmatrix} = 2a^2 \gneq 0</math> that implies
        <math>\begin{bmatrix}
+
        <math>\begin{bmatrix}
 
   x^{\ast} = 1\\ x^{\ast} = 0  
 
   x^{\ast} = 1\\ x^{\ast} = 0  
 
  \end{bmatrix}</math> is the minimized point.
 
  \end{bmatrix}</math> is the minimized point.

Revision as of 17:12, 25 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 − ρ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


(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  $
     U's'e i'n'i't'i'a'l  p'o'i'n't x(0) = [0,0]Ta'n'd H0 = I2
     I'n t'h'i's c'a's'e,
     $ g^{(k)} = \begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix} x^{(k)} - \begin{bmatrix}   2  \\   1  \end{bmatrix} $
      H'e'n'c'e, 
     $ 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} $


      B'e'c'a'u's'e f i's a q'u'a'd'r'a't'i'c f'u'n'c't'i'o'n,
      $ \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}  $


      O'b's'e'r'v'e t'h'a't:
     $ \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} $
     U's'i'n'g t'h'e a'b'o'v'e, n'o'w w'e c'o'm'p'u't'e
     $ 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'h'e'n w'e h'a'v'e,
     $ 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} $
      N'o't'e t'h'a't w'e h'a'v'e $ d^{(0)^T}Qd^{(0)} = 0; $
     t'h'a't i's, $ d^{(0)} = \begin{bmatrix}   2  \\   1  \end{bmatrix} $ a'n'd $ d^{(1)}  = \begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix} $ a'r'e Qc'o'n'j'u'g'a't'e d'i'r'e'c't'i'o'n's.


3. (20pts) For the system of linear equations,A'x = 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 $



Solutions:

      $ A = BC = \begin{bmatrix}   1 & 0  \\   0 & 1   \\   0 & -1  \end{bmatrix} \begin{bmatrix}   1 & 0 &-1  \\   0 & 1 & 0    \end{bmatrix} $
      $ 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} $
      $ 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}  $
      $ 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} $
      $  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} $



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

           M'a'x'i'm'i'z'e    x1 + 2x2
          S'u'b'j'e'c't t'o    $ -2x_1+x_2 \le 2 $
                         $ x_1-x_2 \ge -3 $
                         $ x_1 \le -3 $
                         $ x_1 \ge 0, x_2 \ge 0. $



Solution:

        We can transfer the problem to the following standard form:
          M'i'n'i'm'i'z'e    x1 − 2x2
          S'u'b'j'e'c't t'o     − 2x1 + x2 + x3 = 2
                         x1 + x2 + x4 = 3
                         x1 + x5 = 3
                         $ x_1, x_2, x_3, x_4, x_5 \ge 0. $
       We form the corresponding tableau for the problem
       $ \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} $
        
     Since it is already in canonical form. Because r2 =  − 7, we bring a2 into the basis.
      After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
       $ \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} $
      Similarly, we pivot about the (2,1) element to obtain 
       $ \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} $
      Similarly, we pivot about the (3,3) element to obtain 
       $ \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} $
      Therefore, x1 = 3, x2 = 6, maximize the function.


5.(20pts) Solve the following problem:

           M'i'n'i'm'i'z'e    $ -x_1^2 + 2x_2 $
          S'u'b'j'e'c't t'o    $ 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.

Solution:

        Standard Form:
          M'i'n'i'm'i'z'e    $ -x_1^2 + 2x_2 $
          S'u'b'j'e'c't t'o    $ g_1(x) = x_1^2+x_2^2 - 1 \le 0 $
                         $ g_2(x) = -x_2 \le 0 $
        The KKT Condition.
       $ 1. \mu _1, \mu _2 \ge 0 $  
       2. − 2x1 + 2x1μ1 = 0  
         2.2 + 2x2μ1 − μ2 = 0  
       $ 3. (x_1^2+x_2^2-1)\mu_1 - x_2\mu _2 = 0 $  
       $ 4. g_1(x),g_2(x) \le 0 $  


        Case 1:
       I'f μ1 = 0 and μ2 = 0,
             t'h'e'n,2 = 0which is impossible.
       
       Case 2:
       I'f μ1 = 0 and $ \mu_2 \not= 0, $
             t'h'e'n2 = 2,x1 = 0,x2 = 0..
        Case 3:
       I'f $ \mu_1 \not= 0 $ and μ2 = 0,
             $ then, x_1^2 + x_2^2 = 1  $
                       $ if x1 \not= 0, then \mu_1 = 1, x_2 = -1  $which is impossible.
                       i'f'x1 = 0,t'h'e'n'x2 = 1,μ1 =  − 1which is impossible.
        Case 4:
       I'f $ \mu_1 \not= 0 $ and $ \mu_2 \not= 0, $
             $ then, x_2 = 0, x_1^2 + x_2^2 = 1. So,  x_1 = 1, \mu_1 = 1, \mu_2 = 2.  $.
        Therefore, there are two points that satisfy KKT condition.

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


(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.
       $ \nabla g_2(x)^t y = 0 $
       $ \begin{bmatrix}   0 & -1  \end{bmatrix} y = 0 $
       $ y = \begin{bmatrix}   a \\ 0  \end{bmatrix},  a\not= 0 $
        $ L(x,\mu) = F(x) + \mu_2 G_2(x) =\begin{bmatrix}   -2 & 0 \\ 0 & 0   \end{bmatrix}  $
       C'h'e'c'kytL(x,μ)y
       $ \begin{bmatrix}   a & 0  \end{bmatrix}\begin{bmatrix}   -2 & 0 \\ 0 & 0   \end{bmatrix} \begin{bmatrix}   a \\ 0  \end{bmatrix} = -2a^2 \lneq 0 $ which means SOSC fails.


        Apply SOSC to the second point.
       $ \nabla g_1(x)^t y = 0,  $
        $ \begin{bmatrix}   2x_1 & 2x_2  \end{bmatrix} y = 0 $
       $ y = \begin{bmatrix}   0 \\ a  \end{bmatrix} where a\not= 0 $
        $ 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}  $
       C'h'e'c'kytL(x,μ)y
       $ \begin{bmatrix}   0 & a  \end{bmatrix}\begin{bmatrix}   0 & 0 \\ 0 & 2   \end{bmatrix} \begin{bmatrix}   0 \\ a  \end{bmatrix} = 2a^2 \gneq 0 $ that implies
       $ \begin{bmatrix}   x^{\ast} = 1\\ x^{\ast} = 0   \end{bmatrix} $ is the minimized point.

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett