Revision as of 19:30, 26 January 2013

QE2012_AC-3_ECE580-5

Part 1,2,3,4,5

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:
     If μ1 = 0 and μ2 = 0,
           then,2 = 0which is impossible.
     
     Case 2:
     If μ1 = 0 and $ \mu_2 \not= 0, $
           then,μ2 = 2,x1 = 0,x2 = 0..

        Case 3:
     If $ \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:
     If $ \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} $

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{SOSC is not satisfied.} $

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

$ \color{blue}\text{Related Problem: } $

Solve the following problem:

           Minimize    $ x_1 x_2 $
        Subject to    $ x_1+x_2 \ge 2 $
                       $  x_2 \ge x_1  $
        

Find the points that satisfy the KKT condition and check whether it satisfies SOSC .

Solution The standard form of the optimizing problem is

Minimize $  x_1 x_2 $ 

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

The KKT Condition.

     $ 1. \mu _1, \mu _2 \ge 0 $ 　
     $ 2.\begin{bmatrix}   x_2-\mu_1+\mu_2 \\ x_1-\mu_1-\mu_2  \end{bmatrix}=0 $
     $ 3. (-x_1-x_2+2)\mu_1 +(x_1-x_2)\mu _2 = 0 $ 　
     $ 4. g_1(x),g_2(x) \le 0 $ 

Similar to the previous problem, we need to discuss the four possible cases of $ \mu_1 , \mu_2 $

It turns out that there is only one point that satisfy all conditions.

$ \left\{\begin{matrix} \mu_1=1\\ \mu_2=0\\ x_1=1\\ x_2=1 \end{matrix}\right. $

Now, we need to check whether SOSC is satisfied.

$ L(x,\mu)=F(x,\mu)+\mu_1 G_1 (x)=\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} $

$ y=\begin{bmatrix} -a\\ a \end{bmatrix} \text{, where } y \text { are all the points on the tangent plane} $

$ y^T L(x,\mu)y=-2a^2 \geq 0 \Rightarrow $

$ \text{SOSC is not satisfied.} $

$ \text{So, } \begin{bmatrix} x_{1} = 1\\ x_{2} = 1 \end{bmatrix} \text{is not the minimum point.} $

Back to QE2012 AC-3 ECE580