Line 33: | Line 33: | ||
The '''KKT condition (FONC) '''for local minimizer <span class="texhtml">''x''<sup> * </sup></span> of <span class="texhtml">''f''</span> is: | The '''KKT condition (FONC) '''for local minimizer <span class="texhtml">''x''<sup> * </sup></span> of <span class="texhtml">''f''</span> is: | ||
− | <font color="#ff0000"><span style="font-size: 17px;">'''<math>\text{1. } \mu^{*}\geq0</math>'''</span></font> | + | <font color="#ff0000"><span style="font-size: 17px;">''' <math>\text{1. } \mu^{*}\geq0</math>'''</span></font> |
− | <font color="#ff0000"><span style="font-size: 20px;">'''<math>\text{2. } Df\left ( x^{*} \right )+\lambda ^{*T}Dh\left ( x^{*} \right )+\mu ^{*T}Dg\left ( x^{*} \right )=0^{T}</math>'''</span></font> | + | <font color="#ff0000"><span style="font-size: 20px;">''' <math>\text{2. } Df\left ( x^{*} \right )+\lambda ^{*T}Dh\left ( x^{*} \right )+\mu ^{*T}Dg\left ( x^{*} \right )=0^{T}</math>'''</span></font> |
− | <font color="#ff0000"><math>\text{3. } \mu ^{*T}g\left ( x^{*} \right )=0</math><br></font> | + | <font color="#ff0000"> <math>\text{3. } \mu ^{*T}g\left ( x^{*} \right )=0</math><br></font> |
− | <font color="#ff0000"></font><math>\text{4. } h\left ( x^{*} \right )=0</math> | + | <font color="#ff0000"></font> <math>\text{4. } h\left ( x^{*} \right )=0</math> |
− | <math>\text{5. } g \left( x^{*} \right) \leq0</math><br> | + | <math>\text{5. } g \left( x^{*} \right) \leq0</math><br> |
− | '''Definision: Regular point''' | + | '''Definision: Regular point''' |
− | | + | |
− | + | <math>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 \}</math> | |
− | ''' | + | ''' <math>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)</math> ''' |
− | <math>\text{ | + | '''SONC: '''Suppose that <span class="texhtml">''x''<sup> * </sup></span> is regular<br> <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>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 \}</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 \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 | '''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> |
− | <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: Dh\left( x^{*} \right)y=0, 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\left( x^{*} \right)y=0, Dg_{i}\left( x^{*} \right)y=0, i\in \tilde{J}\left( x^{*},\mu^{*} \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> | + | <math>\tilde{J}\left ( x^{\ast },\mu ^{\ast } \right )= \left \{ i:g_{i}\left ( x^{\ast } \right ) = 0,\mu_{i}^{\ast }> 0\right \}</math> |
'''Process:''' | '''Process:''' | ||
− | a. Write down the KKT condition for this probelm | + | 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. | + | 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. | + | c. Find all points in part b that also satisfy the SONC. |
− | d. Find all points in part c that also satisfy the SOSC. | + | d. Find all points in part c that also satisfy the SOSC. |
− | e. Find all points in part c that are local minimizers. | + | e. Find all points in part c that are local minimizers. |
---- | ---- | ||
Line 194: | Line 195: | ||
\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. |
Revision as of 12:26, 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 \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\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{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\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 $
From 3, x1 + x2 = 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