Line 17: Line 17:
 
<math>\color{blue}\left( \text{i} \right) \text{Does } x^{*} \text{ satisfy the FONC for minimum or maximum? Where are the KKT multipliers?}</math>  
 
<math>\color{blue}\left( \text{i} \right) \text{Does } x^{*} \text{ satisfy the FONC for minimum or maximum? Where are the KKT multipliers?}</math>  
  
−
<math>\color{blue}\text{Solution 1:}</math>
+
<math>\color{blue}\text{Solution 1:}</math>  
  
−
<math>f\left( x \right) = \left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2}</math>
+
<math>f\left( x \right) = \left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2}</math>  
  
−
<math>g_{1}\left( x \right) x_{1}^{2}-x_{2}\leq0</math>
+
<math>g_{1}\left( x \right) x_{1}^{2}-x_{2}\leq0</math>  
  
−
<math>g_{2}\left( x \right) x_{1}+x_{2}-2\leq0</math>
+
<math>g_{2}\left( x \right) x_{1}+x_{2}-2\leq0</math>  
  
−
<math>g_{3}\left( x \right) -x_{1}\leq0</math>
+
<math>g_{3}\left( x \right) -x_{1}\leq0</math>  
  
−
The problem is to optimize f(x)
+
The problem is to optimize f(x), &nbsp;<math>\text{subject to } g_{1}\leq 0, g_{2}\leq 0, g_{3}\leq 0</math>
  
−
<math>\text{subject to } g_{1}\leq 0, g_{2}\leq 0, g_{3}\leq 0</math>
+
<math>l\left( \mu ,\lambda \right)=\nabla f\left(x  \right)+\mu_{1} \nabla g_{1}\left( x \right)+\mu_{2} \nabla g_{2}\left( x \right)+\mu_{3} \nabla g_{3}\left( x \right)</math>  
  
−
<math>l\left( \mu ,\lambda \right)=\nabla f\left(x  \right)+\mu_{1} \nabla g_{1}\left( x \right)+\mu_{2} \nabla g_{2}\left( x \right)+\mu_{3} \nabla g_{3}\left( x \right)</math>
+
<font color="#ff0000"><span style="font-size: 17px;">'''<math>=\begin{pmatrix}
−
 
+
2x_{1}-4\\  
−
<math>\end{pmatrix} +\mu_{1} \begin{pmatrix}
+
2x_{2}-2
 +
\end{pmatrix} +\mu_{1} \begin{pmatrix}
 
2x_{1}\\  
 
2x_{1}\\  
 
-1
 
-1
Line 43: Line 44:
 
0
 
0
 
\end{pmatrix} =0</math>
 
\end{pmatrix} =0</math>
 +
'''</span></font>
  
 +
<font color="#ff0000"><span style="font-size: 17px;"</span></font><math>\mu_{1} g_{1}\left( x \right)+\mu_{2} g_{2}\left( x \right)+\mu_{3} g_{3}\left( x \right)</math>
  
 +
<math>= \mu_{1} \left( x_{1}^2-x_{2} \right)+\mu_{2} \left( x_{1}+x_{2}-2 \right)+\mu_{3} \left( -x_{1} \right) =0</math><br>
 +
 +
<math>\text{Let } x^{*}=\begin{bmatrix}
 +
0\\
 +
0
 +
\end{bmatrix} \text{, }</math><br>
 +
 +
<math>\left\{\begin{matrix}
 +
\nabla l\left( x,\mu \right)=\begin{pmatrix}
 +
-4+\mu_{2}-\mu_{3}\\
 +
-2-\mu_{1}-\mu_{2}
 +
\end{pmatrix}= \begin{pmatrix} 0 \\ 0\end{pmatrix} \\
 +
-2\mu_{2}=0
 +
\end{matrix}\right. \Rightarrow \left\{\begin{matrix}
 +
\mu_{1}=-2\\
 +
\mu_{2}=0\\
 +
\mu_{3}=-4
 +
\end{matrix}\right.</math>
 +
 +
<math>\text{As } \mu^{*}\leq 0, x^{*}\begin{bmatrix}
 +
0\\0
 +
\end{bmatrix} \text{satisfies the FONC for maximum.}</math>
  
 
----
 
----
Line 81: Line 106:
 
-4+\mu_{2}-\mu_{3}\\  
 
-4+\mu_{2}-\mu_{3}\\  
 
-2-\mu_{1}-\mu_{2}
 
-2-\mu_{1}-\mu_{2}
−
\end{pmatrix}=\binom{0}{0} \\  
+
\end{pmatrix}=\begin{pmatrix} 0\\0 \end{pmatrix}\\  
 
-2\mu_{2}=0
 
-2\mu_{2}=0
 
\end{matrix}\right.  \Rightarrow \left\{\begin{matrix}
 
\end{matrix}\right.  \Rightarrow \left\{\begin{matrix}
Line 90: Line 115:
  
 
<math>\therefore x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{ satisfy FONC for maximum}</math><font color="#aaaaaa"><br></font>  
 
<math>\therefore x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{ satisfy FONC for maximum}</math><font color="#aaaaaa"><br></font>  
 +
 +
----
 +
 +
<math>\color{blue}\left( \text{ii} \right) \text{Does } x^{*} \text{ satisfy SOSC? Carefully justify your answer.}</math><br>
 +
 +
<math>\color{blue}\text{Solution 1:}</math>
 +
 +
 +
 +
----
 +
 +
<math>\color{blue}\text{Solution 2:}</math>
 +
 +
<math>L\left ( x_{1}\mu  \right )= D^{2}\l \left ( x _{1}\mu  \right )= \begin{bmatrix}
 +
2+2\mu_{1} & 0 \\
 +
0 & 2
 +
\end{bmatrix}</math>
 +
 +
<math>\text{for point } x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{, we get } \mu_{1}=-2  \text{ from KKT condition.}</math>
 +
 +
<math>\therefore \L \left ( x^{\ast } \mu ^{\ast }\right )=\begin{bmatrix}
 +
-2 & 0 \\
 +
0 & 2
 +
\end{bmatrix}</math>
 +
 +
<math>\tilde{T}\left( x^{\ast }\mu^{\ast } \right)= \left{ y:Dg_{i}\left( x^{\ast } \right)y=0, i\epsilon \tilde{J}\left( x^{\ast },\mu^{\ast } \right) \right}</math>
 +
 +
<math>\tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i^{\ast }}> 0\right \}</math>&nbsp; &nbsp; &nbsp;<math>\therefore i= 2</math>
 +
 +
<math>\therefore \tilde{T}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ y:\left [ 1,1 \right ]y= 0 \right \}= \left \{ y:y_{1}= -y_{2} \right \}</math>
 +
 +
<math>\left [ y_{1},y_{2} \right ]\begin{bmatrix}
 +
-2 & 0\\
 +
0 & 2
 +
\end{bmatrix} \begin{bmatrix}
 +
y_{1}\\
 +
y_{2}
 +
\end{bmatrix} \geqslant 0</math>
 +
 +
<math>-2y_{1}^{2}+2y_{2}^{2}\geqslant 0\cdots \left ( 1 \right )</math>
 +
 +
<math>\text{for } y_{1}= y_{2} \text{, is always satisfied.}</math>
 +
 +
<math>\therefore \text{For all } y\in T\left( x^{*} \right ) \text{, we have } y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y\geq 0</math>
 +
 +
<math>\therefore \text{point } x^{*} \text{satisfy the SOSC}</math>
  
  

Revision as of 20:54, 27 June 2012


ECE Ph.D. Qualifying Exam: Automatic Control (AC)- Question 3, August 2011

 $ \color{blue}\text{5. } \left( \text{20 pts} \right) \text{ Consider the optimization problem, } $

                            $ \text{optimize} \left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2} $

                        $ \text{subject to } x_{2}- x_{1}^{2}\geq0 $

                                                 $ 2-x_{1}-x_{2}\geq0, x_{1}\geq0. $

$ \color{blue} \text{The point } x^{*}=\begin{bmatrix} 0 & 0 \end{bmatrix}^{T} \text{ satisfies the KKT conditions.} $

$ \color{blue}\left( \text{i} \right) \text{Does } x^{*} \text{ satisfy the FONC for minimum or maximum? Where are the KKT multipliers?} $

$ \color{blue}\text{Solution 1:} $

$ f\left( x \right) = \left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2} $

$ g_{1}\left( x \right) x_{1}^{2}-x_{2}\leq0 $

$ g_{2}\left( x \right) x_{1}+x_{2}-2\leq0 $

$ g_{3}\left( x \right) -x_{1}\leq0 $

The problem is to optimize f(x),  $ \text{subject to } g_{1}\leq 0, g_{2}\leq 0, g_{3}\leq 0 $

$ l\left( \mu ,\lambda \right)=\nabla f\left(x \right)+\mu_{1} \nabla g_{1}\left( x \right)+\mu_{2} \nabla g_{2}\left( x \right)+\mu_{3} \nabla g_{3}\left( x \right) $

$ =\begin{pmatrix} 2x_{1}-4\\ 2x_{2}-2 \end{pmatrix} +\mu_{1} \begin{pmatrix} 2x_{1}\\ -1 \end{pmatrix}+\mu_{2}+\begin{pmatrix} 1\\ 1 \end{pmatrix}+\mu_{3}+\begin{pmatrix} -1\\ 0 \end{pmatrix} =0 $

<span style="font-size: 17px;"</span>$ \mu_{1} g_{1}\left( x \right)+\mu_{2} g_{2}\left( x \right)+\mu_{3} g_{3}\left( x \right) $

$ = \mu_{1} \left( x_{1}^2-x_{2} \right)+\mu_{2} \left( x_{1}+x_{2}-2 \right)+\mu_{3} \left( -x_{1} \right) =0 $

$ \text{Let } x^{*}=\begin{bmatrix} 0\\ 0 \end{bmatrix} \text{, } $

$ \left\{\begin{matrix} \nabla l\left( x,\mu \right)=\begin{pmatrix} -4+\mu_{2}-\mu_{3}\\ -2-\mu_{1}-\mu_{2} \end{pmatrix}= \begin{pmatrix} 0 \\ 0\end{pmatrix} \\ -2\mu_{2}=0 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} \mu_{1}=-2\\ \mu_{2}=0\\ \mu_{3}=-4 \end{matrix}\right. $

$ \text{As } \mu^{*}\leq 0, x^{*}\begin{bmatrix} 0\\0 \end{bmatrix} \text{satisfies the FONC for maximum.} $

$ \color{blue}\text{Solution 2:} $

$ \text{ Standard form: optimize} \left(x_{1}-2\right)^{2}+\left(x_{2}-1\right)^{2} $

                                  $ \text{subject to } g_{1}\left( x \right) x_{1}^{2}-x_{2}\leq0 $

                                                           $ g_{2}\left( x \right) x_{1}+x_{2}-2\leq0 $

                                                           $ g_{3}\left( x \right) -x_{1}\leq0 $

$ \text{KKT condition: (1) } Dl\left( \mu ,\lambda \right)=Df\left(x \right)+\mu_{1}Dg_{1}\left( x \right)+\mu_{2}Dg_{2}\left( x \right)+\mu_{3}Dg_{3}\left( x \right) $

                                                                      $ =\left [ 2x_{1}-4+2\mu_{1}x_{1}+\mu_{2}-\mu_{3}, 2x_{2}-2-\mu_{1}+\mu_{2} \right ] $

                                        $ \left ( 2 \right ) \mu^{T}g\left ( x \right )=0 \Rightarrow \mu_{1}\left ( x_{2}^2-x_{2} \right )+\mu_{2}\left ( x_{1}+x_{2}-2 \right ) - \mu_{3}x_{1}=0 $

                                        $ \left ( 3 \right ) \mu_{1},\mu_{2},\mu_{3}\geq 0 \text{ for minimizer} $

                                               $ \mu_{1},\mu_{2},\mu_{3}\leq 0 \text{ for maximizer} $

                                        $ \text{where } \mu^{*}=\begin{bmatrix} \mu_{1}\\ \mu_{2}\\ \mu_{3} \end{bmatrix} \text{ are the KKT multiplier.} $

$ \text{For } x^{*}=\begin{bmatrix} 0\\ 0 \end{bmatrix} \text{, } $       $ \left\{\begin{matrix} \nabla l\left( x,\mu \right)=\begin{pmatrix} -4+\mu_{2}-\mu_{3}\\ -2-\mu_{1}-\mu_{2} \end{pmatrix}=\begin{pmatrix} 0\\0 \end{pmatrix}\\ -2\mu_{2}=0 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} \mu_{1}=-2\\ \mu_{2}=0\\ \mu_{3}=-4 \end{matrix}\right. $

$ \therefore x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{ satisfy FONC for maximum} $

$ \color{blue}\left( \text{ii} \right) \text{Does } x^{*} \text{ satisfy SOSC? Carefully justify your answer.} $

$ \color{blue}\text{Solution 1:} $


$ \color{blue}\text{Solution 2:} $

$ L\left ( x_{1}\mu \right )= D^{2}\l \left ( x _{1}\mu \right )= \begin{bmatrix} 2+2\mu_{1} & 0 \\ 0 & 2 \end{bmatrix} $

$ \text{for point } x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{, we get } \mu_{1}=-2 \text{ from KKT condition.} $

$ \therefore \L \left ( x^{\ast } \mu ^{\ast }\right )=\begin{bmatrix} -2 & 0 \\ 0 & 2 \end{bmatrix} $

$ \tilde{T}\left( x^{\ast }\mu^{\ast } \right)= \left{ y:Dg_{i}\left( x^{\ast } \right)y=0, i\epsilon \tilde{J}\left( x^{\ast },\mu^{\ast } \right) \right} $

$ \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i^{\ast }}> 0\right \} $     $ \therefore i= 2 $

$ \therefore \tilde{T}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ y:\left [ 1,1 \right ]y= 0 \right \}= \left \{ y:y_{1}= -y_{2} \right \} $

$ \left [ y_{1},y_{2} \right ]\begin{bmatrix} -2 & 0\\ 0 & 2 \end{bmatrix} \begin{bmatrix} y_{1}\\ y_{2} \end{bmatrix} \geqslant 0 $

$ -2y_{1}^{2}+2y_{2}^{2}\geqslant 0\cdots \left ( 1 \right ) $

$ \text{for } y_{1}= y_{2} \text{, is always satisfied.} $

$ \therefore \text{For all } y\in T\left( x^{*} \right ) \text{, we have } y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y\geq 0 $

$ \therefore \text{point } x^{*} \text{satisfy the SOSC} $


Automatic Control (AC)- Question 3, August 2011
Problem 1:  https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion
Problem 2:  https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-2
Problem 3:  https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-3
Problem 4:  https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-4

Back to ECE Qualifying Exams (QE) page

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=ECE-QE_AC3-2011_solusion-5&oldid=51716"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

ECE462 Survivor

Seraj Dosenbach