ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)
Question 3, Part 2, August 2011
$ \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) 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 $
$ \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{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 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
Go to
- Problem 1: solutions and discussions
- Problem 2: solutions and discussions
- Problem 3: solutions and discussions
- Problem 4: solutions and discussions
- Problem 5: solutions and discussions
