Line 234: Line 234:
 
<math>\color{blue}\text{Relative Problem: }</math>  
 
<math>\color{blue}\text{Relative Problem: }</math>  
  
<span class="texhtml">''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m''''i''''n''''i''''m''''i''''z''''e &nbsp; '''''<b>&nbsp;− ''x''<sub>2</sub> + (''x''<sub>1</sub> − 1)<sup>2</sup> − 2</b></span>  
+
<span class="texhtml">''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minimize'''&nbsp; &nbsp;'''''<b>&nbsp;− ''x''<sub>2</sub> + (''x''<sub>1</sub> − 1)<sup>2</sup> − 2</b></span>  
  
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\text{subject to } x_{1}+x_{2}\leq2</math>  
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\text{subject to } x_{1}+x_{2}\leq2</math>  
Line 240: Line 240:
 
<math>\text{KKT condition: 1. } \mu\leq0 \Rightarrow</math>  
 
<math>\text{KKT condition: 1. } \mu\leq0 \Rightarrow</math>  
  
<math>\text{2. } \left[ 2 \left(x_{1}-1 \right)-1 \left] +\mu \left[ 1 1 \right] = \left[0 0 \right]</math><br>
+
<font color="#ff0000"><span style="font-size: 17px;">'''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\begin{bmatrix}
 +
2 \left(x_{1}-1 \right) & -1  
 +
\end{bmatrix} +\mu \begin{bmatrix}
 +
1 & 1  
 +
\end{bmatrix} = \begin{bmatrix}
 +
0 & 0  
 +
\end{bmatrix} \Rightarrow \mu=1</math>
 +
'''</span></font>  
  
<font color="#ff0000">'''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<math>\text{3. } \mu \left( x_{1}+x_{2}-2 \right)=0</math><br>'''</font>  
+
<font color="#ff0000">'''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>\text{3. } \mu \left( x_{1}+x_{2}-2 \right)=0 \Rightarrow x_{1}+x_{2}=2</math><br>'''</font>  
  
 
<br>  
 
<br>  

Revision as of 00:54, 29 June 2012

ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)

Question 3, Part 2, August 2011

Part 1,2,3,4,5

 $ \color{blue}\text{5. } \left( \text{20 pts} \right) \text{ Consider the following 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.} $


Theorem:

For the problem:    minimize  $ f \left( x \right) $

                             subject to   $ h \left( x \right) =0 $

                                                $ g \left( x \right) \leq 0 $

The KKT condition (FONC) for local minimizer x *  of f is:

$ \text{1. } \mu^{*}\geq0 $

$ \text{2. } Df\left ( x^{*} \right )+\lambda ^{*T}Dh\left ( x^{*} \right )+\mu ^{*T}Dg\left ( x^{*} \right )=0^{T} $

$ \text{3. } \mu ^{*T}g\left ( x^{*} \right )=0 $

$ \text{4. } h\left ( x^{*} \right )=0 $

$ \text{5. } g \left( x^{*} \right) \leq0 $

SONC: Suppose that x *  is regular
$ \text{1. } \mu ^{*}\geq0 \text{, } Df\left ( x^{*} \right )+\lambda ^{*T}Dh\left ( x^{*} \right )+\mu ^{*T}Dg\left ( x^{*} \right )=0^{T} \text{, } \mu ^{*T}g\left ( x^{*} \right )=0 $

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

$ T\left( x^{* } \right)= \left \{ y\in\Re^{n}: Dh\left( x^{*} \right)y=0, Dg_{j}\left( x^{*} \right)y=0, j\in \tilde{J}\left( x^{*} \right) \right \} $

SOSC: There exist a feasible point xthat 

$ \text{1. } \mu ^{*}\geq0 \text{, } Df\left ( x^{*} \right )+\lambda ^{*T}Dh\left ( x^{*} \right )+\mu ^{*T}Dg\left ( x^{*} \right )=0^{T} \text{, } \mu ^{*T}g\left ( x^{*} \right )=0 $

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

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

Process:

a. Write down the KKT condition for this probelm

b. Find all points (and KKT multipliers) satisfying the KKT condition. In each case, determine if the point is regular.

c. Find all points in part b that also satisfy the SONC.

d. Find all points in part c that also satisfy the SOSC.

e. Find all points in part c that are local minimizers.


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

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

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

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

$ \text{Let } 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 $

$ \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 ]=0 $                                            $ \left ( 2 \right ) \mu^{T}g\left ( x \right )=0 \Rightarrow \mu_{1}\left ( x_{1}^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:} $

$ L\left ( x^{*},\mu^{*} \right )= \nabla l \left( x^{*},\mu^{*} \right)= \begin{pmatrix} 2&0 \\ 0&2 \end{pmatrix}-2\begin{pmatrix} 2&0 \\ 0&0 \end{pmatrix} = \begin{pmatrix} -2&0 \\ 0&2 \end{pmatrix} $

'Failed to parse (lexing error): \tilde{T}\left( x^{* }\mu^{*} \right) : \left\{ \begin{matrix} y^{T}\binom{0}{-1} =0 \\ y^{T}\binom{-1}{0} =0 \end{matrix} \right. \Rightarrow \tilde{T}\left( x^{* }\mu^{*} \right)= \left \{ \binom{0}{0} \right \}'

SOSC is trivially satisfied.

$ \color{red} \text{This solution misunderstood the range of } y \text{ for SOSC condition } y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y\geq 0 $

$ \color{red} y\in \tilde{T}\left( x^{* }\mu^{*} \right) \text{, where } \tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y:Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \right) \right \} $


$ \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^{*}, \mu ^{*}\right )=\begin{bmatrix} -2 & 0 \\ 0 & 2 \end{bmatrix} $

$ \tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y:Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \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 \} $

$ \begin{bmatrix} y_{1}& y_{2} \end{bmatrix}\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 ) $

                    for y1 = y2,  (1) is always satisfied.

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

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


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

                  minimize    − x2 + (x1 − 1)2 − 2

                  $ \text{subject to } x_{1}+x_{2}\leq2 $

$ \text{KKT condition: 1. } \mu\leq0 \Rightarrow $

                                $ \begin{bmatrix} 2 \left(x_{1}-1 \right) & -1 \end{bmatrix} +\mu \begin{bmatrix} 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix} \Rightarrow \mu=1 $

                                        $ \text{3. } \mu \left( x_{1}+x_{2}-2 \right)=0 \Rightarrow x_{1}+x_{2}=2 $




Automatic Control (AC)- Question 3, August 2011

Go to


Back to ECE Qualifying Exams (QE) page

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood