| Line 53: | Line 53: | ||
<math>\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</math> | <math>\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</math> | ||
| − | <math>T\left( x^{* } \right)= \left \{ y\in\Re^{n}: Dh\left( x^{*} \right)y=0, Dg_{j}\left( x^{*} \right)y=0, j\in | + | <math>T\left( x^{* } \right)= \left \{ y\in\Re^{n}: Dh\left( x^{*} \right)y=0, Dg_{j}\left( x^{*} \right)y=0, j\in J\left( x^{*} \right) \right \}</math> |
<math>J\left(x^{*}\right)= \left \{ j:g_{j}\left(x^{*}\right)=0 \right \}</math> | <math>J\left(x^{*}\right)= \left \{ j:g_{j}\left(x^{*}\right)=0 \right \}</math> | ||
| Line 121: | Line 121: | ||
\end{bmatrix} \text{, }</math><br> | \end{bmatrix} \text{, }</math><br> | ||
| − | <math>\left\{\begin{matrix} | + | <math>\left\{\begin{matrix} |
\nabla l\left( x,\mu \right)=\begin{pmatrix} | \nabla l\left( x,\mu \right)=\begin{pmatrix} | ||
-4+\mu_{2}-\mu_{3}\\ | -4+\mu_{2}-\mu_{3}\\ | ||
| Line 197: | Line 197: | ||
\end{pmatrix}</math><br> | \end{pmatrix}</math><br> | ||
| − | <font color="#ff0000">'''<math>\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 \}</math><br>'''</font> | + | <font color="#ff0000">'''<math>\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 \}</math><br>'''</font> |
SOSC is trivially satisfied. | SOSC is trivially satisfied. | ||
| Line 205: | Line 205: | ||
<math>\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 \}</math> | <math>\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 \}</math> | ||
| − | <math>\color{red} \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right ) \text{ has constrain for } \mu ^{\ast } \text{, } \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\right \}</math> | + | <math>\color{red} \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right ) \text{ has constrain for } \mu ^{\ast } \text{, } \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\right \}</math> |
---- | ---- | ||
| Line 211: | Line 211: | ||
<math>\color{blue}\text{Solution 2:}</math> | <math>\color{blue}\text{Solution 2:}</math> | ||
| − | <font color="#ff0000"><span style="font-size: 17px;">'''<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>'''</span></font> | + | <font color="#ff0000"><span style="font-size: 17px;">'''<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>'''</span></font> |
<math>\text{for point } x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{, we get } \mu_{1}=-2 \text{ from KKT condition.}</math> | <math>\text{for point } x^{*}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \text{, we get } \mu_{1}=-2 \text{ from KKT condition.}</math> | ||
| − | <font color="#ff0000" size="5">'''<math>\therefore L \left ( x^{*}, \mu ^{*}\right )=\begin{bmatrix} -2 & 0 \\ 0 & 2 \end{bmatrix}</math><br>'''</font> | + | <font color="#ff0000" size="5">''' <math>\therefore L \left ( x^{*}, \mu ^{*}\right )=\begin{bmatrix} -2 & 0 \\ 0 & 2 \end{bmatrix}</math><br>'''</font> |
<font color="#ff0000"><span style="font-size: 20px;">'''<math>\tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y:Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \right) \right \}</math>'''</span></font> | <font color="#ff0000"><span style="font-size: 20px;">'''<math>\tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y:Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \right) \right \}</math>'''</span></font> | ||
| − | <math>\tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\right \}</math> <math>\therefore i= 2</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> <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>\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>\begin{bmatrix} | + | <math>y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y=\begin{bmatrix} |
y_{1}& | y_{1}& | ||
y_{2} | y_{2} | ||
Revision as of 20:01, 29 June 2012
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) 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 $
Definision: Regular point
$ x^{*} \text{ satisfy } h\left( x^{*} \right)=0, g\left( x^{*} \right)\leq0 \text{ and let } J\left(x^{*}\right)= \left \{ j:g_{j}\left(x^{*}\right)=0 \right \} $
$ x^{*}\text{ is regular point if } \nabla h_{i} \left( x^{*} \right), \nabla g_{j} \left( x^{*} \right), 1\leq i\leq m, j\in J \left( x^{*} \right) $
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 J\left( x^{*} \right) \right \} $
$ J\left(x^{*}\right)= \left \{ j:g_{j}\left(x^{*}\right)=0 \right \} $
SOSC: There exist a feasible point x * that
$ \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 \} $
$ \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\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} $
$ \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{red} \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right ) \text{ has constrain for } \mu ^{\ast } \text{, } \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\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 \} $
$ y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y=\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\geq0 $
$ \text{2. } \begin{bmatrix} 2 \left(x_{1}-1 \right) & -1 \end{bmatrix} +\mu \begin{bmatrix} 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix} $
$ \text{3. } \mu \left( x_{1}+x_{2}-2 \right)=0 $
$ \text{From 2, } \mu=1 \text{, and } 2\left ( x_{1}-1 \right )=-1 $
$ \text{From 3, } \left( x_{1}+x_{2} \right) =2 $
$ \text{From above two equations, we obtain a candidate point for the minimizer } x^{*}=\begin{bmatrix} 1/2\\ 3/2 \end{bmatrix} $
Check for SOSC:
$ L \left ( x^{*}, \mu ^{*}\right )= F\left ( x^{*}\right )+ \mu ^{*} G\left ( x^{*}\right )=\begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} $
Because μ * > 0 ,we have
$ \tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y: \begin{bmatrix} 1 & 1 \end{bmatrix}y=0 \right \} = \left \{ y: =\begin{bmatrix} a & -a \end{bmatrix}:a\in\Re \right \} $
$ \text{Hence } y^{T}L\left ( x^{\ast },\mu ^{\ast } \right )y=\begin{bmatrix} a & -a \end{bmatrix}\begin{bmatrix} 2 & 0\\ 0 & 0 \end{bmatrix}\begin{bmatrix} a \\ -a \end{bmatrix}=2a^{2}>0 $
$ \therefore x^{*} \text{ satisfies the SOSC for strict local minimizer. } $
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
