Difference between revisions of "QE2012 AC-3 ECE580" - Rhea

      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⁽⁰⁾ 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 Q − c'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'n,μ2 = 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 $