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:
If μ1 = 0 and μ2 = 0,
then, 2 = 0 which 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 $
$ \text{if } x_1 \not= 0, \text{then } \mu_1 = 1, x_2 = -1 $which is impossible.
if x1 = 0, then x2 = 1,μ1 = − 1 which 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 $
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 x1x2 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 x1x2
$ \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.( − x1 − x2 + 2)μ1 + (x1 − x2)μ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 μ1,μ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 $
SOSC is not satisfied.
$ \text{So, } \begin{bmatrix} x_{1} = 1\\ x_{2} = 1 \end{bmatrix} \text{is not the minimum point.} $
