Line 1: Line 1:
 
  
 
=QE2012_AC-3_ECE580-5=
 
=QE2012_AC-3_ECE580-5=
Line 5: Line 4:
  
  
Put your content here . . .
+
Solution:
 +
 
 +
        Standard Form:
 +
        <span class="texhtml">''Minimize''</span>'''    <math>-x_1^2 + 2x_2</math>'''
 +
        <span class="texhtml">''Su''</span>'''  <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>  
 +
      <span class="texhtml">2. − 2''x''<sub>1</sub> + 2''x''<sub>1</sub>μ<sub>1</sub> = 0</span>  
 +
        <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>4. g_1(x),g_2(x) \le 0</math>  
 +
 
 +
<br>
 +
 
 +
        Case 1:
 +
      <span class="texhtml">''I''''f'''''</span>''''' <span class="texhtml">μ<sub>1</sub> = 0</span> and <span class="texhtml">μ<sub>2</sub> = 0,</span>'''''
 +
            <span class="texhtml">''t''''h''''e''''n'''''<b>,2 = 0</b></span>'''which is impossible.'''
 +
     
 +
      Case 2:
 +
      <span class="texhtml">''I''''f'''''</span>''''' <span class="texhtml">μ<sub>1</sub> = 0</span> and <math>\mu_2 \not= 0,</math>'''''
 +
            <span class="texhtml">''t''''h''''e''''n'''''<b>,μ<sub>2</sub> = 2,''x''<sub>1</sub> = 0,''x''<sub>2</sub> = 0.</b></span>'''.'''
 +
 
 +
        Case 3:
 +
      <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>if x1 \not= 0, then \mu_1 = 1, x_2 = -1 </math>which is impossible.
 +
                      <span class="texhtml">''i'''f '''x''1 = 0,''then x''<sub>2</sub> = 1,μ<sub>1</sub> =  − 1</span>which is impossible.
 +
 
 +
        Case 4:
 +
      <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>.
 +
 
 +
        Therefore, there are two points that satisfy KKT condition.
 +
 +
      <math>\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} </math>
 +
 
 +
Solution 2:
 +
 
 +
The standard form of the optimizing problem is
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;
 +
<math>\text{minimize } -x_1^2 + 2x_2</math>
 +
 
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\text{subject to  }  g_1(x)=x_1^2+x_2^2-1 \le 0  \text { and }  g_2(x)=-x_2 \le 0</math>
 +
 
 +
The KKT Condition.
 +
      <math>1. \mu _1, \mu _2 \ge 0</math>  
 +
      <math>2.\begin{bmatrix}
 +
  -2x_1+2\mu_1 x_1 \\ 2+2\mu_1 x_2-\mu_2
 +
\end{bmatrix}=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>\text {Case 1: } \mu_1=\mu_2=0 \text{, which implies } 2=0 \Rightarrow \text{Impossible} </math>
 +
 
 +
<math>\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 }
 +
 
 +
</math>
 +
 
 +
 
 +
 
 +
<math>\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.
 +
 
 +
</math>
 +
 
 +
<math>\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.
 +
 
 +
</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>
 +
 
 +
 
 +
Solution:
 +
 
 +
        Apply SOSC to the first point.
 +
      <math>\nabla g_2(x)^t y = 0</math>
 +
      <math>\begin{bmatrix}
 +
  0 & -1
 +
\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}
 +
  -2 & 0 \\ 0 & 0
 +
\end{bmatrix} </math>
 +
      <span class="texhtml">''Check ''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
 +
      <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.
 +
 
 +
<br>
 +
 
 +
        Apply SOSC to the second point.
 +
      <math>\nabla g_1(x)^t y = 0, </math>
 +
 
 +
        <math>\begin{bmatrix}
 +
  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}
 +
  -2 & 0 \\ 0 & 0
 +
\end{bmatrix}  + \begin{bmatrix}
 +
  2 & 0 \\ 0 & 2 
 +
\end{bmatrix}  = \begin{bmatrix}
 +
  0 & 0 \\ 0 & 2
 +
\end{bmatrix} </math>
 +
      <span class="texhtml">''Check ''</span><span class="texhtml">''y''<sup>''t''</sup>''L''(''x'',μ)''y''</span>
 +
      <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.
 +
 
 +
Solution 2:
 +
 
 +
<math>\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}</math>
 +
 
 +
<math>
 +
L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix}
 +
  -2 & 0\\ 0 & 0
 +
\end{bmatrix}
 +
</math>
 +
 
 +
<math>
 +
y^T L(x,\mu)y=-2a^2 \le 0 \Rightarrow \text{It doesn;t satisfy SOSC}
 +
</math>
 +
 
 +
 
 +
<math>\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}</math>
 +
 
 +
<math>
 +
L(x,\mu)=F(x,\mu)+\mu_2 G_2 (x)=\begin{bmatrix}
 +
  0 & 0\\ 0 & 2
 +
\end{bmatrix}
 +
</math>
 +
 
 +
<math>
 +
y^T L(x,\mu)y=2a^2 \geq 0 \Rightarrow \text{It doesn;t satisfy SOSC}
 +
</math>
  
 +
<math>
 +
\text{So, }
 +
\begin{bmatrix}
 +
x^{\ast} = 1\\ x^{\ast} = 0
 +
\end{bmatrix}
 +
\text{is the minimum point.}
 +
</math>
  
 +
<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>\color{blue}
 +
\mu
 +
</math>
 +
is used to find out the tangent plane.
 +
</span></font>
  
  
 
[[ QE2012 AC-3 ECE580|Back to QE2012 AC-3 ECE580]]
 
[[ QE2012 AC-3 ECE580|Back to QE2012 AC-3 ECE580]]

Revision as of 06:19, 26 January 2013

QE2012_AC-3_ECE580-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:
     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.
                     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} $


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.


Back to QE2012 AC-3 ECE580

Alumni Liaison

ECE462 Survivor

Seraj Dosenbach