| Line 47: | Line 47: | ||
<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> | ||
| − | '''SOSC:''' There exist a feasible point <span class="texhtml">''x''<sup> * <sub></sub><sub></sub></sup></span>that | + | <math>T\left( x^{* } \right)= \left \{ y\in\Re^{n}: Dh_{i}\left( x^{*} \right)y=0, Dg_{j}\left( x^{*} \right)y=0, j\in \tilde{J}\left( x^{*} \right) \right \}</math> |
| + | |||
| + | '''SOSC:''' There exist a feasible point <span class="texhtml">''x''<sup> * <sub></sub><sub></sub></sup></span>that | ||
<math>\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</math> | <math>\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</math> | ||
| Line 53: | Line 55: | ||
<math>\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</math> | <math>\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</math> | ||
| − | <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> | + | <math>\tilde{T}\left( x^{* },\mu^{*} \right)= \left \{ y: Dh_{i}\left( x^{*} \right)y=0, Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \right) \right \}</math> |
'''Process:''' | '''Process:''' | ||
| Line 187: | Line 189: | ||
\end{pmatrix}</math><br> | \end{pmatrix}</math><br> | ||
| − | <font color="#ff0000">''' | + | <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 203: | Line 205: | ||
<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> | ||
| Line 224: | Line 226: | ||
<span class="texhtml"> for ''y''<sub>1</sub> = ''y''<sub>2</sub>, (1) is always satisfied.</span> | <span class="texhtml"> for ''y''<sub>1</sub> = ''y''<sub>2</sub>, (1) is always satisfied.</span> | ||
| − | <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{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</math> |
<math>\therefore \text{point } x^{*} \text{satisfy the SOSC}</math><br> | <math>\therefore \text{point } x^{*} \text{satisfy the SOSC}</math><br> | ||
Revision as of 22:36, 28 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 $
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_{i}\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 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_{i}\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} $
$ \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{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} $
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
