Revision as of 18:54, 29 June 2012

ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)

Question 3, Part 1, August 2011

Part 1,2,3,4,5

 $ \color{blue}\text{1. } \left( \text{20 pts} \right) \text{ Consider the optimization problem, } $

               $ \text{maximize} -x_{1}^{2}+x_{1}-x_{2}-x_{1}x_{2} $

               $ \text{subject to } x_{1}\geq0, x_{2}\geq0 $

Definition: Feasible Direction

        $ \text{A vector } d\in\Re^{n}, d\neq0, \text{ is a feasible direction at } x\in\Omega $

        $ \text{if there exists } \alpha_{0}>0 \text{ such that } x+\alpha d\in\Omega \text{ for all } \alpha\in\left[ 0,\alpha_{0}\right] $

FONC:

        If x* is a local minimizer of f over Ω, then for any feasible direction d at x*, we have 

        $ d^{T} \nabla f\left ( x^{*} \right )\geq0 $

FONC Interior Case:

         $ \nabla f\left ( x^{*} \right )=0 $

SONC: 

        Let x* a local minimizer of f and d a feasible direction at x*,

        If $ d^{T} \nabla f\left ( x^{*} \right )=0 $ , then  $ d^{T} F\left ( x^{*} \right )d\geq 0 $

SONC Interior Case: 

        If $ \nabla f\left ( x^{*} \right )=0 $  , then $ d^{T} F\left ( x^{*} \right )d\geq 0 $

$ \color{blue}\left( \text{i} \right) \text{ Characterize feasible directions at the point } x^{*}=\left[ \begin{array}{c} \frac{1}{2} \\ 0 \end{array} \right] $

$ \color{blue}\text{Solution 1:} $

$ \text{We need to find a direction }d\text{, such that } \exists\alpha_{0}>0, $ 

         $ \left( \begin{array}{c} \frac{1}{2} \\ 0 \end{array} \right) + \alpha d \text{ for all } \alpha\in \left[0,\alpha_{0}\right] $

$ \text{As } x_{1}\geq0, x_{2}\geq0, d= \left( \begin{array}{c} x \\ y \end{array} \right)\text{where } x\in\Re, \text{ and } y\geq0. $

$ \color{blue}\text{Solution 2:} $

$ d\in\Re^{2}, d\neq0 \text{ is a feasible direction at } x^{*} $ 

         $ \text{ if } \exists \alpha_{0} \text{ that } \left[ \begin{array}{c} \frac{1}{2} \\ 0 \end{array} \right] + \alpha\left[ \begin{array}{c} d_{1} \\ d_{2} \end{array} \right] \in\Omega \text{ for all } 0\leq\alpha\leq\alpha_{0} $

$ \because \begin{Bmatrix}x\in\Omega: x_{1}\geq0, x_{2}\geq0\end{Bmatrix} $

$ \therefore d= \left[ \begin{array}{c} d_{1} \\ d_{2} \end{array} \right], d_{1}\in\Re, d_{2}\geq0 $

$ \color{blue}\left( \text{ii} \right) \text{Write down the second-order necessary condition for } x^{*} \text{. Does the point } x^{*} \text{ satisfy this condition?} $

$ \color{blue}\text{Solution 1:} $

$ \text{Let } f\left(x\right)=x_{1}^{2}-x_{1}+x_{2}+x_{1}x_{2} \text{ , } g_{1}\left(x\right)=-x_{1} \text{ , } g_{2}\left(x\right)=-x_{2} $

$ \text{It is equivalent to minimize } f\left(x\right) \text{, } $  

                                           $ \text{ subject to } g_{1}(x)\leq0, g_{2}(x)\leq0 $

$ \left\{\begin{matrix} l\left(x,\mu \right) = \nabla f(x)+\mu_{1}\nabla g_{1}(x)+ \mu_{2}\nabla g_{2}(x) \\ =\left( \begin{array}{c} 2x_{1}-1+x_{2} \\ 1+x_{1} \end{array} \right) + \left( \begin{array}{c} -\mu_{1} \\ 0 \end{array} \right) +\left( \begin{array}{c} 0 \\ -\mu_{2} \end{array} \right) =0\\ -\mu_{1}x_{1}-\mu_{2}x_{2} = 0 \\ x_{1} = \frac{1}{2},x_{2} = 0 \end{matrix}\right. $
$ \Rightarrow \mu_{1}=0 , \mu_{2}=3/2 $   

$ \therefore x^{*} \text{ satisfies FONC} $              

$ \color{green} \text{There exist } \mu \text{ which make point } x^{*} \text{ satisfies FONC.} $

$ \text{SONC: } L(x^{*},\mu^{*}) = \nabla l(x^{*},\mu^{*})=\left( \begin{array}{cc} 2 & 1 \\ 1 & 0 \end{array} \right) $

$ T(x^{*},\mu^{*}): \begin{cases} y^{T}\nabla g_{1}(x)=0 \\ y^{T}\nabla g_{2}(x)=0 \end{cases} : \begin{cases} y^{T}\left( \begin{array}{c} -1 \\ 0 \end{array} \right)=0 \\ y^{T}\left( \begin{array}{c} 0 \\-1 \end{array} \right)=0 \end{cases} \Rightarrow y=\left( \begin{array}{c} 0 \\0 \end{array} \right) $

$ \color{green} \text {Here not using formal set expression. } $  $ \color{red} T\left( x^{* },\mu^{* } \right) \text{ should be } T\left( x^{* } \right) $

$ \text{The SONC condition is for all } y\in T \left(x^{*},\mu^{*} \right) , y^{T}L\left(x^{*},\mu^{*} \right)y \geq 0 $

$ y^{T}L\left(x^{*},\mu^{*} \right)y =0 \geq 0 \text{. So } x^{*} \text{satisfies SONC.} $

$ \color{red} \text{For SONC, } 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 \} $

                           $ \color{red} J\left(x^{*}\right)= \left \{ j:g_{j}\left(x^{*}\right)=0 \right \} $

$ \color{red} \text{For SOSC, } \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 \} $

                          $ \color{red} \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:} $

$ \text{The problem is equivalent to min} f\left(x_{1},x_{2}\right) = x_{1}^{2}-x_{1}+x_{2}+x_{1}x_{2} $  

                                                                      $ \text{subject to } x_{1}\leq0, x_{2}\leq0 $

$ Df\left ( x \right )=\left ( \nabla f\left ( x \right ) \right )^{T} = \left [ \frac{\partial f}{\partial x_{1}}\left ( x \right ),\frac{\partial f}{\partial x_{2}}\left ( x \right ) \right ]=\left [ 2x_{1}-1+x_{2},1+x_{1} \right ] $

$ F\left ( x \right ) =D^{2}f\left ( x \right )=\begin{bmatrix} \frac{\partial^{2} f}{\partial x_{1}^{2}}\left ( x \right ) & \frac{\partial^{2} f}{\partial x_{2}\partial x_{1}}\left ( x \right )\\ \frac{\partial^{2} f}{\partial x_{1}\partial x_{2}}\left ( x \right ) & \frac{\partial^{2} f}{\partial x_{2}^{2}}\left ( x \right ) \end{bmatrix}=\left [ \begin{array}{cc} 2 & 1 \\ 1 & 0 \end{array} \right ] $

$ \text{SONC for local minimizer } x^{*}=\begin{bmatrix} \frac{1}{2}\\0 \end{bmatrix} $

                  $ d^{T} \nabla f\left ( x^{*} \right )=0 \cdots \left ( 1 \right ) $     

                  $ d^{T} F\left ( x^{*} \right )d\geq 0 \cdots \left ( 2\right ) $

$ \text{For (1), } \begin{bmatrix} d_{1} & d_{2} \end{bmatrix}\begin{bmatrix} 0\\ \frac{3}{2}\end{bmatrix} =0 \Rightarrow d_{1}\in\Re, d_{2}=0 $

$ \text{For (2), } F\left ( x \right ) = \begin{bmatrix} 2 &1 \\ 1 &0\end{bmatrix}>0 $       $ \color{green} A=\begin{bmatrix} a &b \\ c &d\end{bmatrix} \text{ is positive definite when } a>0 \text{ and } ac-b^{2}>0 $

$ \therefore \text{ for all } d\in\Re^{n}, d^{T}F\left ( x^{*} \right )d\geq 0 $

$ \text{The point } x^{*}=\begin{bmatrix} \frac{1}{2}\\0 \end{bmatrix} \text{ satisfies SONC for local minimizer.} $

$ \color{blue}\text{Related Problem: For function } $

        $ f\left( x_{1},x_{2} \right) =\frac{1}{3} x_{1}^{3} + \frac{1}{3} x_{2}^{3} -x_{1}x_{2} $

$ \color{blue} \text{Find point(s) that satisfy FONC and check if they are strict local minimizers.} $

$ \color{blue}\text{Solution:} $

$ \text{Applying FONC gives } \nabla f\left ( x \right )=\begin{bmatrix} x_{1}^{2}-x_{2}\\ x_{2}^{2}-x_{1} \end{bmatrix}=0 $

        $ \Rightarrow x^{\left ( 1 \right )}=\begin{bmatrix} 0\\ 0 \end{bmatrix} \text{ and }x^{\left ( 2 \right )}=\begin{bmatrix} 1\\ 1 \end{bmatrix} $

$ \text{The Hessian matrix: } F\left ( x \right )=\begin{bmatrix} 2x_{1} & -1\\ -1 & 2x_{2} \end{bmatrix} $

        $ \text{The matrix } F\left ( x^{\left ( 1 \right )} \right )=\begin{bmatrix} 0 & -1\\ -1 & 0 \end{bmatrix} \text{ is indefinite. The point is not a minimizer.} $

        $ \text{The matrix } F\left ( x^{\left ( 2\right )} \right )=\begin{bmatrix} 0 & -1\\ -1 & 0 \end{bmatrix} \text{ is positive definite. } $

$ \therefore x^{\left ( 2 \right )}=\begin{bmatrix} 1\\ 1 \end{bmatrix} \text{ satisfies SOSC to be a strict local minimizer.} $

Automatic Control (AC)- Question 3, August 2011

Go to

• Part 1: solutions and discussions
• Part 2: solutions and discussions
• Part 3: solutions and discussions
• Part 4: solutions and discussions
• Part 5: solutions and discussions

Back to ECE Qualifying Exams (QE) page