ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)
Question 3, August 2011, Part 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 $
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{red} \tilde{J}\left ( x^{\ast },\mu ^{\ast } \right ) \subset J\left(x^{*}\right) $, $ \color{red} T\left( x^{* } \right) \subset \tilde{T}\left( x^{* },\mu^{*} \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{Related 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
