Line 64: Line 64:
 
From the inequality, we get <math> F_{N+1} \ge 40 , \text{ so } N+1=9 </math>. Therefore the minimum number of iteration is N-1=7  
 
From the inequality, we get <math> F_{N+1} \ge 40 , \text{ so } N+1=9 </math>. Therefore the minimum number of iteration is N-1=7  
  
−
<font color="#ff0000"><span style="font-size: 19px;"><math>\color{blue}
+
<font color="#0000FF "><span style="font-size: 19px;"><math>\color{blue}
 
F_9=55 \text{ and } F_8=34
 
F_9=55 \text{ and } F_8=34
 
</math></span></font>
 
</math></span></font>
Line 89: Line 89:
  
 
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
 
       <math>f = \frac{1}{2}x^TQx - x^Tb+c </math>
−
     Use initial point x<sup>(0)</sup> = [0,0]<sup>T and H<sub>0</sub> = I<sub>2</sub>
+
     Use initial point x<sup>(0)</sup> = [0,0]<sup>T</sub> and H<sub>0</sub> = I<sub>2</sub>
 
      
 
      
 
In this case  
 
In this case  
Line 271: Line 271:
 
   2  \\
 
   2  \\
 
   1
 
   1
−
  \end{bmatrix}</math> <span class="texhtml">''a''''n''''d''</span> <math>d^{(1)}  = \begin{bmatrix}
+
  \end{bmatrix}</math> and  <math>d^{(1)}  = \begin{bmatrix}
 
   \frac{4}{5}  \\
 
   \frac{4}{5}  \\
 
   -\frac{3}{5}
 
   -\frac{3}{5}
 
  \end{bmatrix}</math> <span class="texhtml">''are Q-conjugate directions''</span><span class="texhtml">'''.'''</span>
 
  \end{bmatrix}</math> <span class="texhtml">''are Q-conjugate directions''</span><span class="texhtml">'''.'''</span>
 +
 +
 +
Solution 2:
 +
 +
<math>
 +
\text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix}
 +
\text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}
 +
 +
</math>
 +
 +
<math>g^{(k)} = \begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix} x^{(k)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} , \text{so}</math>
 +
 +
<math>g^{(0)} = \begin{bmatrix}
 +
  -2  \\
 +
  -1
 +
\end{bmatrix},</math>  <math>d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix}
 +
  1 & 0 \\
 +
  0 & 1
 +
\end{bmatrix}\begin{bmatrix}
 +
  -2  \\
 +
  -1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
<math>\alpha_0 = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}
 +
  -2 & -1
 +
\end{bmatrix}\begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}}{\begin{bmatrix}
 +
  2 & 1\end{bmatrix}\begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix}\begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}} = \frac{1}{2}</math>
 +
 +
<math>x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  1  \\
 +
  \frac{1}{2}
 +
\end{bmatrix}</math>
 +
 +
<math>\Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix}
 +
  1  \\
 +
  \frac{1}{2}
 +
\end{bmatrix}</math>
 +
 +
<math>g^{(1)} =\begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix} x^{(1)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix}= \begin{bmatrix}
 +
  -\frac{1}{2}  \\
 +
  1
 +
\end{bmatrix}</math>
 +
 +
<math>\Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix}
 +
  -\frac{3}{2}  \\
 +
  2
 +
\end{bmatrix} </math>
 +
 +
<math>
 +
\text{If we plug in the above numbers in the formula, we can get}
 +
</math>
 +
 +
<math>H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} }  = \begin{bmatrix}
 +
  1 & 0 \\
 +
  0 & 1
 +
\end{bmatrix} + \begin{bmatrix}
 +
  \frac{2}{5} & \frac{1}{5} \\
 +
  \frac{1}{5} & \frac{1}{10}
 +
\end{bmatrix} - \frac{25}{4}\begin{bmatrix}
 +
  \frac{9}{4} & 3 \\
 +
  3 & 4
 +
\end{bmatrix} = \begin{bmatrix}
 +
  \frac{26}{25} & -\frac{7}{25} \\
 +
  -\frac{7}{25} & \frac{23}{50}
 +
\end{bmatrix}</math>
 +
 +
<math>d^{(1)} = -H_1 g^{(1)} = - \begin{bmatrix}
 +
  \frac{26}{25} & -\frac{7}{25} \\
 +
  -\frac{7}{25} & \frac{23}{50}
 +
\end{bmatrix} \begin{bmatrix}
 +
  -\frac{1}{2}  \\
 +
  1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  \frac{4}{5}  \\
 +
  -\frac{3}{5}
 +
\end{bmatrix}</math>
 +
 +
<math>\alpha_1 = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix}
 +
  -2 & 1
 +
\end{bmatrix}\begin{bmatrix}
 +
  \frac{4}{5}  \\
 +
  -\frac{3}{5}
 +
\end{bmatrix}}{\begin{bmatrix}
 +
  \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix}\begin{bmatrix}
 +
  \frac{4}{5}  \\
 +
  -\frac{3}{5}
 +
\end{bmatrix}} = \frac{5}{2}</math>
 +
 +
<math>x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix}
 +
  1  \\
 +
  \frac{1}{2}
 +
\end{bmatrix} + \frac{5}{2}\begin{bmatrix}
 +
  \frac{4}{5}  \\
 +
  -\frac{3}{5}
 +
\end{bmatrix} = \begin{bmatrix}
 +
  3  \\
 +
  -1
 +
\end{bmatrix} </math>
 +
 +
<math>\Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix}
 +
  2  \\
 +
  -\frac{3}{2}
 +
\end{bmatrix}
 +
</math>
 +
 +
<math>
 +
g^{(2)} = \begin{bmatrix}
 +
  1 & 1 \\
 +
  1 & 2
 +
\end{bmatrix} x^{(2)} - \begin{bmatrix}
 +
  2  \\
 +
  1
 +
\end{bmatrix} = \begin{bmatrix}
 +
  0  \\
 +
  0
 +
\end{bmatrix}</math>
 +
 +
<math>
 +
\text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix}
 +
  3 \\
 +
  -1
 +
\end{bmatrix}
 +
</math>
  
 
<br>  
 
<br>  
  
−
'''Problem 3. (20pts) For the system of linear equations,<span class="texhtml" />''''x'' = ''b'', where  
+
'''Problem 3. (20pts) For the system of linear equations,<math> Ax=b </math> where  
  
 
<math>A = \begin{bmatrix}
 
<math>A = \begin{bmatrix}
Line 423: Line 576:
 
   0
 
   0
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
 +
 +
<font color="#ff0000"><span style="font-size: 19px;"><math>\color{blue}
 +
\text{ The pseudo inverse of a matrix has the property }
 +
(BC)^{\dagger}=C^{\dagger}B^{\dagger}
 +
</math></span></font>
  
 
<br>  
 
<br>  
Line 529: Line 687:
 
  \end{bmatrix}</math>
 
  \end{bmatrix}</math>
 
maximizes the object function. The maximum value is 15
 
maximizes the object function. The maximum value is 15
 +
 +
<font color="#0000FF "><span style="font-size: 19px;">
 +
<math>\color{blue}
 +
\text{ It should be noted that, }
 +
\begin{bmatrix}
 +
  x^{1} = 3\\ x^{2} = 6 
 +
\end{bmatrix} \text{actually minimizes the standard form,}
 +
</math>
 +
<math>\color{blue}
 +
\text{which equivalently maximizes the original problem}
 +
</math>
 +
</span></font>
  
 
<br> '''Problem 5.(20pts) Solve the following problem:'''  
 
<br> '''Problem 5.(20pts) Solve the following problem:'''  
Line 582: Line 752:
  
 
Solution 2:
 
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
 
The standard form of the optimizing problem is
Line 660: Line 828:
  
 
</math>
 
</math>
 +
 +
<font color="#0000FF "><span style="font-size: 19px;">
 +
It's a lot more easier as the student notice that ignoring the constraint 
 +
<math>\color{blue}
 +
x_1>0
 +
</math>
 +
doesn't have any effect on the optimizing problem.This will save the time of discussing 4 more cases. But the student should have explain why this is true. </span></font>
 +
 +
<font color="#0000FF "><span style="font-size: 19px;">
 +
Each coefficient <math>\color{blue}\mu </math> can be either 0 or not. When solving the equations, a systematic way would be to discuss all cases.
 +
<math>\color{blue}
 +
 +
</math>
 +
</span></font>
  
 
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''  
 
<br> '''(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.'''  
Line 768: Line 950:
 
</math>
 
</math>
  
−
Solution 2:
+
<font color="#0000FF "><span style="font-size: 19px;">
−
 
+
When checking the SOSC condition, we need to find out the tangent plane. Only the subject function with a non-zero  
−
<math>
+
<math>\color{blue}
−
\text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix}
+
\mu
−
\text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix}
+
−
 
+
−
</math>
+
−
 
+
−
<math>g^{(k)} = \begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix} x^{(k)} - \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix} , \text{so}</math>
+
−
 
+
−
<math>g^{(0)} = \begin{bmatrix}
+
−
  -2  \\
+
−
  -1
+
−
\end{bmatrix},</math>  <math>d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix}
+
−
  1 & 0 \\
+
−
  0 & 1
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  -2  \\
+
−
  -1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>\alpha_0 = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}
+
−
  -2 & -1
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}}{\begin{bmatrix}
+
−
  2 & 1\end{bmatrix}\begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}} = \frac{1}{2}</math>
+
−
 
+
−
<math>x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  1  \\
+
−
  \frac{1}{2}
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>\Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix}
+
−
  1  \\
+
−
  \frac{1}{2}
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>g^{(1)} =\begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix} x^{(1)} - \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix}= \begin{bmatrix}
+
−
  -\frac{1}{2}  \\
+
−
  1
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>\Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix}
+
−
  -\frac{3}{2}  \\
+
−
  2
+
−
\end{bmatrix} </math>
+
−
 
+
−
<math>
+
−
\text{If we plug in the above numbers in the formula, we can get}
+
−
</math>
+
−
 
+
−
<math>H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} } = \begin{bmatrix}
+
−
  1 & 0 \\
+
−
  0 & 1
+
−
\end{bmatrix} + \begin{bmatrix}
+
−
  \frac{2}{5} & \frac{1}{5} \\
+
−
  \frac{1}{5} & \frac{1}{10}
+
−
\end{bmatrix} - \frac{25}{4}\begin{bmatrix}
+
−
  \frac{9}{4} & 3 \\
+
−
  3 & 4
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  \frac{26}{25} & -\frac{7}{25} \\
+
−
  -\frac{7}{25} & \frac{23}{50}
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>d^{(1)} = -H_1 g^{(1)} = - \begin{bmatrix}
+
−
  \frac{26}{25} & -\frac{7}{25} \\
+
−
  -\frac{7}{25} & \frac{23}{50}
+
−
\end{bmatrix} \begin{bmatrix}
+
−
  -\frac{1}{2}  \\
+
−
  1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  \frac{4}{5}  \\
+
−
  -\frac{3}{5}
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>\alpha_1 = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix}
+
−
  -2 & 1
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  \frac{4}{5}  \\
+
−
  -\frac{3}{5}
+
−
\end{bmatrix}}{\begin{bmatrix}
+
−
  \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix}\begin{bmatrix}
+
−
  \frac{4}{5}  \\
+
−
  -\frac{3}{5}
+
−
\end{bmatrix}} = \frac{5}{2}</math>
+
−
 
+
−
<math>x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix}
+
−
  1  \\
+
−
  \frac{1}{2}
+
−
\end{bmatrix} + \frac{5}{2}\begin{bmatrix}
+
−
  \frac{4}{5}  \\
+
−
  -\frac{3}{5}
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  3  \\
+
−
  -1
+
−
\end{bmatrix} </math>
+
−
 
+
−
<math>\Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix}
+
−
  2  \\
+
−
  -\frac{3}{2}
+
−
\end{bmatrix}
+
−
</math>
+
−
 
+
−
<math>
+
−
g^{(2)} = \begin{bmatrix}
+
−
  1 & 1 \\
+
−
  1 & 2
+
−
\end{bmatrix} x^{(2)} - \begin{bmatrix}
+
−
  2  \\
+
−
  1
+
−
\end{bmatrix} = \begin{bmatrix}
+
−
  0  \\
+
−
  0
+
−
\end{bmatrix}</math>
+
−
 
+
−
<math>
+
−
\text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix}
+
−
  3 \\
+
−
  -1
+
−
\end{bmatrix}
+
 
</math>
 
</math>
 +
is used to find out the tangent plane.
 +
</span></font>

Revision as of 04:54, 26 January 2013

AC - 3 August 2012 QE

Problem 1. (20 pts)

(i) (10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form

$ \begin{align} 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, \end{align} $

where N − 1 is the number of steps performed in the uncertainty range reduction process.



Solution: 

   The reduction factor is (1 − ρ1)(1 − ρ2)(1 − ρ3)...(1 − ρN − 1)
Since 
$  1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3},  $
we have 
$  1- \rho_{N-2} = \frac{F_{3}}{F_{4}} $     and so on.

   Then, we have
$  (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}}   \frac{F_{N-1}}{F_{N}}   ...   \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $
Therefore, the reduction factor is
$ \frac{2}{F_{N+1}} $


Solution 2:

The uncertainty interval is reduced by $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $

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



(ii)(10 pts) It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is

$ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $


Solution: 

      Final Range: 1.0; Initial Range: 20.

      $  \frac{2}{F_{N+1}} \le \frac{1.0}{20} $, or $  F_{N+1} \ge 40 $ 

      So, N + 1 = 9

      Therefore, the minimal iterations is N-1 or 7.


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

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

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


Problem 2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function 

      $ f = \frac{1}{2}x^TQx - x^Tb+c  $
     $   =\frac{1}{2}x^T  \begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix}x-x^T\begin{bmatrix}   2  \\   1  \end{bmatrix} + 3. $

Where x(0) is arbitrary.


Solution: 

      $ f = \frac{1}{2}x^TQx - x^Tb+c  $
   Use initial point x(0) = [0,0]T</sub> and H0 = I2

In this case 

   $ g^{(k)} = \begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix} x^{(k)} - \begin{bmatrix}   2  \\   1  \end{bmatrix} $

      Hence
   $ g^{(0)} = \begin{bmatrix}   -2  \\   -1  \end{bmatrix}, $  $ d^{(0)} = -H_0g^{(0)} =- \begin{bmatrix}   1 & 0 \\   0 & 1  \end{bmatrix}\begin{bmatrix}   -2  \\   -1  \end{bmatrix} = \begin{bmatrix}   2  \\   1  \end{bmatrix} $



      Because f is a quadratic function

      $ \alpha_0 = argminf(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix}   -2 & -1   \end{bmatrix}\begin{bmatrix}   2  \\   1  \end{bmatrix}}{\begin{bmatrix}   2 & 1\end{bmatrix}\begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix}\begin{bmatrix}   2  \\   1  \end{bmatrix}} = \frac{1}{2} $

      $ x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix}   2  \\   1  \end{bmatrix} = \begin{bmatrix}   1  \\   \frac{1}{2}  \end{bmatrix} $

      $ \Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix}   1  \\   \frac{1}{2}  \end{bmatrix} $
   $ g^{(1)} =\begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix} x^{(1)} - \begin{bmatrix}   2  \\   1  \end{bmatrix}= \begin{bmatrix}   -\frac{1}{2}  \\   1  \end{bmatrix} $

      $ \Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix}   -\frac{3}{2}  \\   2  \end{bmatrix}  $



      Observe that
   $ \Delta x^{(0)} \Delta x^{(0)^T} = \begin{bmatrix}   1  \\   \frac{1}{2}   \end{bmatrix} \begin{bmatrix}   1  & \frac{1}{2}   \end{bmatrix} = \begin{bmatrix}   1 & \frac{1}{2}  \\   \frac{1}{2}  & \frac{1}{4}   \end{bmatrix}  $
   $  \Delta x^{(0)^T} \Delta g^{(0)} = \begin{bmatrix}   1  & \frac{1}{2}   \end{bmatrix}\begin{bmatrix}   \frac{3}{2}   \\   2   \end{bmatrix}  = \frac{5}{2} $
   $ H_0 \Delta g^{(0)} = \begin{bmatrix}   1 & 0 \\   0 & 1  \end{bmatrix} \begin{bmatrix}   \frac{3}{2}   \\   2   \end{bmatrix} = \begin{bmatrix}   \frac{3}{2}   \\   2   \end{bmatrix}, $ $ (H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T = \begin{bmatrix}   \frac{9}{4}  & 3 \\   3 & 4  \end{bmatrix} $
   $ \Delta g^{(0)^T}H_0 \Delta g^{(0)} = \begin{bmatrix}   \frac{3}{2}  & 2   \end{bmatrix} \begin{bmatrix}   1 & 0 \\   0 & 1  \end{bmatrix} \begin{bmatrix}   \frac{3}{2}  \\ 2   \end{bmatrix} = \frac{25}{4} $
   Using the above, now we have
   $ H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} }  = \begin{bmatrix}   1 & 0 \\   0 & 1  \end{bmatrix} + \begin{bmatrix}   \frac{2}{5} & \frac{1}{5} \\   \frac{1}{5} & \frac{1}{10}  \end{bmatrix} - \frac{25}{4}\begin{bmatrix}   \frac{9}{4} & 3 \\   3 & 4  \end{bmatrix} = \begin{bmatrix}   \frac{26}{25} & -\frac{7}{25} \\   -\frac{7}{25} & \frac{23}{50}  \end{bmatrix} $

      T'hen we have,
   $ d^{(1)} = -H_1 g^{(0)} = - \begin{bmatrix}   \frac{26}{25} & -\frac{7}{25} \\   -\frac{7}{25} & \frac{23}{50}  \end{bmatrix} \begin{bmatrix}   -\frac{1}{2}  \\   1  \end{bmatrix} = \begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix} $

      $ \alpha_1 = argminf(x^{(1)} + \alpha d^{(1)}) = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix}   -2 & 1   \end{bmatrix}\begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix}}{\begin{bmatrix}   \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix}\begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix}} = \frac{5}{2} $

      $ x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix}   1  \\   \frac{1}{2}  \end{bmatrix} + \frac{5}{2}\begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix} = \begin{bmatrix}   3  \\   -1  \end{bmatrix}  $

      $ \Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix}   2  \\   -\frac{3}{2}  \end{bmatrix} $
   $ g^{(2)} = \begin{bmatrix}   1 & 1 \\   1 & 2  \end{bmatrix} x^{(0)} - \begin{bmatrix}   2  \\   1  \end{bmatrix} = \begin{bmatrix}   0  \\   0  \end{bmatrix} $

      Note that we have $ d^{(0)^T}Qd^{(0)} = 0; $
   that is, $ d^{(0)} = \begin{bmatrix}   2  \\   1  \end{bmatrix} $ and  $ d^{(1)}  = \begin{bmatrix}   \frac{4}{5}  \\   -\frac{3}{5}  \end{bmatrix} $ are Q-conjugate directions.


Solution 2:

$ \text{Let the initial point be } x^{(0)}= \begin{bmatrix} 0\\ 0 \end{bmatrix} \text{and initial Hessian be } H_0=\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} $

$ g^{(k)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} , \text{so} $

$ g^{(0)} = \begin{bmatrix} -2 \\ -1 \end{bmatrix}, $ $ d^{(0)} = -H_0 g^{(0)} =- \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -2 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $

$ \alpha_0 = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix} -2 & -1 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}}{\begin{bmatrix} 2 & 1\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}} = \frac{1}{2} $

$ x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $

$ \Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $

$ g^{(1)} =\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(1)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix}= \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} $

$ \Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix} -\frac{3}{2} \\ 2 \end{bmatrix} $

$ \text{If we plug in the above numbers in the formula, we can get} $

$ H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} } = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} \frac{2}{5} & \frac{1}{5} \\ \frac{1}{5} & \frac{1}{10} \end{bmatrix} - \frac{25}{4}\begin{bmatrix} \frac{9}{4} & 3 \\ 3 & 4 \end{bmatrix} = \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} $

$ d^{(1)} = -H_1 g^{(1)} = - \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $

$ \alpha_1 = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix} -2 & 1 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}}{\begin{bmatrix} \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}} = \frac{5}{2} $

$ x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} + \frac{5}{2}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} = \begin{bmatrix} 3 \\ -1 \end{bmatrix} $

$ \Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix} 2 \\ -\frac{3}{2} \end{bmatrix} $

$ g^{(2)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(2)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $

$ \text{When the gradient is 0, we reach the minimum point, which is } x^{(2)}=\begin{bmatrix} 3 \\ -1 \end{bmatrix} $


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

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


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



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


Solution 2:

$ x^{(\ast)}=A^{\dagger}b $

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

$ \color{blue} \text{ The pseudo inverse of a matrix has the property } (BC)^{\dagger}=C^{\dagger}B^{\dagger} $


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



Solution: 

        We can transfer the problem to the following standard form:
        Mnimize     − x1 − 2x2
        Sbject to     − 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.

Solution 2:

The standard form for this problem is 

        Mnimize     − x1 − 2x2
        Sbject to     − 2x1 + x2 + x3 = 2
                        − x1 + x2 + x4 = 3
                       x1 + x5 = 3
                       $ x_1, x_2, x_3, x_4, x_5 \ge 0. $

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

From the last tableau, we can see that $ \begin{bmatrix} x^{1} = 3\\ x^{2} = 6 \end{bmatrix} $ maximizes the object function. The maximum value is 15

$ \color{blue} \text{ It should be noted that, } \begin{bmatrix} x^{1} = 3\\ x^{2} = 6 \end{bmatrix} \text{actually minimizes the standard form,} $ $ \color{blue} \text{which equivalently maximizes the original problem} $


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.

Solution: 

        Standard Form:
        Minimize    $ -x_1^2 + 2x_2 $
        Su   $ 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.
                     if x1 = 0,then 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}  $

Solution 2:

The standard form of the optimizing problem is                                                                                                                                                                                          $ \text{minimize } -x_1^2 + 2x_2 $

                        $ \text{subject to } g_1(x)=x_1^2+x_2^2-1 \le 0 \text { and } g_2(x)=-x_2 \le 0 $

The KKT Condition. 

     $ 1. \mu _1, \mu _2 \ge 0 $ 　
     $ 2.\begin{bmatrix}   -2x_1+2\mu_1 x_1 \\ 2+2\mu_1 x_2-\mu_2   \end{bmatrix}=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 $ 　

$ \text {Case 1: } \mu_1=\mu_2=0 \text{, which implies } 2=0 \Rightarrow \text{Impossible} $

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


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

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

It's a lot more easier as the student notice that ignoring the constraint $ \color{blue} x_1>0 $ doesn't have any effect on the optimizing problem.This will save the time of discussing 4 more cases. But the student should have explain why this is true.

Each coefficient $ \color{blue}\mu $ can be either 0 or not. When solving the equations, a systematic way would be to discuss all cases. $ \color{blue} $


(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}  $
     Check ytL(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}  $
     Check ytL(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.

Solution 2:

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

$ L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix} -2 & 0\\ 0 & 0 \end{bmatrix} $

$ y^T L(x,\mu)y=-2a^2 \le 0 \Rightarrow \text{It doesn;t satisfy SOSC} $


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

$ L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix} 0 & 0\\ 0 & 2 \end{bmatrix} $

$ y^T L(x,\mu)y=2a^2 \geq 0 \Rightarrow \text{It doesn;t satisfy SOSC} $

$ \text{So, } \begin{bmatrix} x^{\ast} = 1\\ x^{\ast} = 0 \end{bmatrix} \text{is the minimum point.} $

When checking the SOSC condition, we need to find out the tangent plane. Only the subject function with a non-zero $ \color{blue} \mu $ is used to find out the tangent plane.

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

Alumni Liaison

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

Dr. Paul Garrett