AC - 3 August 2012 QE
1. (20 pts)
(i) (10 pts) Find the factor by which the uncertainty range is reduced when using the Fibonacci method. Assume that the last step has the form
$ \begin{align} 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, \end{align} $
where $ N - 1 $ is the number of steps performed in the uncertainty range reduction process.
Solution:
The reduction factor is $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) $ Since $ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $ we have $ 1- \rho_{N-2} = \frac{F_{3}}{F_{4}} $ and so on.
Then, we have $ (1- \rho_{1})(1- \rho_{2})(1- \rho_{3})...(1- \rho_{N-1}) = \frac{F_{N}}{F_{N+1}} \frac{F_{N-1}}{F_{N}} ... \frac{F_{2}}{F_{3}} = \frac{F_{2}}{F_{N+1}} $ Therefore, the reduction factor is $ \frac{2}{F_{N+1}} $
(ii)(10 pts) It is known that the minimizer of a certain function f(x) is located in the interval[-5, 15]. What is the minimal number of iterations of the Fibonacci method required to box in the minimizer within the range 1.0? Assume that the last useful value of the factor reducing the uncertainty range is 2/3, that is
$ 1- \rho_{N-1} = \frac{F_{2}}{F_{3}} = \frac{2}{3}, $
Solution:
Final Range: 1.0; Initial Range: 20.
$ \frac{2}{F_{N+1}} \le \frac{1.0}{20} $, or $ F_{N+1} \ge 40 $
So, $ N+1 = 9 $
Therefore, the minimal iterations is N-1 or 7.
2. (20pts) Employ the DFP method to construct a set of Q-conjugate directions using the function
$ f = \frac{1}{2}x^TQx - x^Tb+c $ $ =\frac{1}{2}x^T \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}x-x^T\begin{bmatrix} 2 \\ 1 \end{bmatrix} + 3. $
Where $ x^{(0)} $ is arbitrary.
Solution:
$ f = \frac{1}{2}x^TQx - x^Tb+c $ $ Use $ $ initial $ $ point $ $ x^{(0)} = [0, 0]^T and $ $ H_0 = I_2 $ $ In $ $ this $ $ case, $ $ g^{(k)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(k)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} $
$ Hence, $ $ g^{(0)} = \begin{bmatrix} -2 \\ -1 \end{bmatrix}, $ $ d^{(0)} = -H_0g^{(0)} =- \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -2 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $
$ Because $ $ f $ $ is $ $ a $ $ quadratic $ $ function, $
$ \alpha_0 = argminf(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)^T}d^{(0)}}{d^{(0)^T}Qd^{(0)}} = - \frac{\begin{bmatrix} -2 & -1 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}}{\begin{bmatrix} 2 & 1\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 2 \\ 1 \end{bmatrix}} = \frac{1}{2} $
$ x^{(1)} = x^{(0)} + \alpha d^{(0)} = \frac{1}{2} \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $
$ \Delta x^{(0)} = x^{(1)}- x^{(0)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} $ $ g^{(1)} =\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(1)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix}= \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} $
$ \Delta g^{(0)} = g^{(1)} - g^{(0)} = \begin{bmatrix} -\frac{3}{2} \\ 2 \end{bmatrix} $
$ Observe $ $ that: $ $ \Delta x^{(0)} \Delta x^{(0)^T} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} \begin{bmatrix} 1 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 1 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{4} \end{bmatrix} $ $ \Delta x^{(0)^T} \Delta g^{(0)} = \begin{bmatrix} 1 & \frac{1}{2} \end{bmatrix}\begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \frac{5}{2} $ $ H_0 \Delta g^{(0)} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix}, $ $ (H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T = \begin{bmatrix} \frac{9}{4} & 3 \\ 3 & 4 \end{bmatrix} $ $ \Delta g^{(0)^T}H_0 \Delta g^{(0)} = \begin{bmatrix} \frac{3}{2} & 2 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{3}{2} \\ 2 \end{bmatrix} = \frac{25}{4} $ $ Using $ $ the $ $ above, $ $ now $ $ we $ $ compute $ $ H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)^T}}{\Delta x^{(0)^T} \Delta g^{(0)}} - \frac{(H_0 \Delta g^{(0)})(H_0 \Delta g^{(0)})^T}{\Delta g^{(0)^T}H_0 \Delta g^{(0)} } = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} \frac{2}{5} & \frac{1}{5} \\ \frac{1}{5} & \frac{1}{10} \end{bmatrix} - \frac{25}{4}\begin{bmatrix} \frac{9}{4} & 3 \\ 3 & 4 \end{bmatrix} = \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} $
$ Then $ $ we $ $ have, $ $ d^{(1)} = -H_1 g^{(0)} = - \begin{bmatrix} \frac{26}{25} & -\frac{7}{25} \\ -\frac{7}{25} & \frac{23}{50} \end{bmatrix} \begin{bmatrix} -\frac{1}{2} \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $
$ \alpha_1 = argminf(x^{(1)} + \alpha d^{(1)}) = - \frac{g^{(1)^T}d^{(1)}}{d^{(1)^T}Qd^{(1)}} = - \frac{\begin{bmatrix} -2 & 1 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}}{\begin{bmatrix} \frac{4}{5} & -\frac{3}{5}\end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix}} = \frac{5}{2} $
$ x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix} 1 \\ \frac{1}{2} \end{bmatrix} + \frac{5}{2}\begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} = \begin{bmatrix} 3 \\ -1 \end{bmatrix} $
$ \Delta x^{(1)} = x^{(2)} - x^{(1)} = \begin{bmatrix} 2 \\ -\frac{3}{2} \end{bmatrix} $ $ g^{(2)} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} x^{(0)} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $
$ Note $ $ that $ $ we $ $ have $ $ d^{(0)^T}Qd^{(0)} = 0; $ $ that $ $ is, $ $ d^{(0)} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $ $ and $ $ d^{(1)} = \begin{bmatrix} \frac{4}{5} \\ -\frac{3}{5} \end{bmatrix} $ $ are $ $ Q-conjugate $ $ directions. $
3. (20pts) For the system of linear equations,$ Ax = b $, where
$ A = \begin{bmatrix} 1 & 0 &-1 \\ 0 & 1 & 0 \\ 0 & -1& 0 \end{bmatrix}, b = \begin{bmatrix} 0 \\ 2 \\ 1 \end{bmatrix} $
Find the minimum length vector $ x^{(\ast)} $ that minimizes $ \| Ax -b\|^{2}_2 $
Solutions:
$ A = BC = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 &-1 \\ 0 & 1 & 0 \end{bmatrix} $
$ B^{\dagger} = (B^T B)^{-1}B^T = \begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} \end{bmatrix} $
$ C^{\dagger} = C^T(CC^T)^{-1} =\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ -1 & 0 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} \frac{1}{2} & 0 \\ 0 & 1 \\ -\frac{1}{2} & 0 \end{bmatrix} $
$ A^{\dagger} = C^{\dagger}B^{\dagger} =\begin{bmatrix} \frac{1}{2} & 0 \\ 0 & 1 \\ -\frac{1}{2} & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & 0 & 0 \end{bmatrix} $
$ x^{\ast} = A^{\dagger} b = \begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & 0 & 0 \end{bmatrix}\begin{bmatrix} 0 \\ \frac{1}{2} \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ \frac{1}{2} \\ 0 \end{bmatrix} $
4. (20pts) Use any simplex method to solve the following linear program.
$ Maximize $ $ x_1 + 2x_2 $ $ Subject $ $ to $ $ -2x_1+x_2 \le 2 $ $ x_1-x_2 \ge -3 $ $ x_1 \le -3 $ $ x_1 \ge 0, x_2 \ge 0. $
Solution:
We can transfer the problem to the following standard form:
$ Minimize $ $ -x_1 - 2x_2 $
$ Subject $ $ to $ $ -2x_1+x_2 + x_3 = 2 $
$ - x_1+x_2 + x_4 = 3 $
$ x_1 + x_5 = 3 $
$ x_1, x_2, x_3, x_4, x_5 \ge 0. $
We form the corresponding tableau for the problem
$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ -2 & 1& 1 &0& 0& 2 \\ -1& 1& 0 &1 &0 &3\\ 1 &0& 0& 0& 1& 3\\ -1& -2 &0& 0& 0& 0 \end{matrix} $
Since it is already in canonical form. Because $ r_2 = -7 $, we bring $ a_2 $ into the basis.
After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ -2 & 1& 1 &0& 0& 2 \\ 1& 0& -1 &1 &0 &1\\ 1 &0& 0& 0& 1& 3\\ -5& 0 &2& 0& 0& 4 \end{matrix} $
Similarly, we pivot about the (2,1) element to obtain
$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ 0 & 1& -1 &2& 0& 4 \\ 1& 0& -1 &1 &0 &1\\ 0 &0& 1& -1& 1& 2\\ 0& 0 &-3& 5& 0& 9 \end{matrix} $
Similarly, we pivot about the (3,3) element to obtain
$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ 0 & 1& 0 &1& 1& 6 \\ 1& 0& 0 &0 &1 &3\\ 0 &0& 1& -1& 1& 2\\ 0& 0 &0& 2& 3& 15 \end{matrix} $
Therefore, $ x_1 = 3, $ $ x_2 = 6, $ maximize the function.
5.(20pts) Solve the following problem:
$ Minimize $ $ -x_1^2 + 2x_2 $ $ Subject $ $ to $ $ x_1^2+x_2^2 \le 1 $ $ x_1 \ge 0 $ $ x_2 \ge 0 $
(i)(10pts) Find the points that satisfy the KKT condition.
Solution:
Standard Form:
$ Minimize $ $ -x_1^2 + 2x_2 $
$ Subject $ $ to $ $ g_1(x) = x_1^2+x_2^2 - 1 \le 0 $
$ g_2(x) = -x_2 \le 0 $
The KKT Condition.
$ 1. \mu _1, \mu _2 \ge 0 $
$ 2. -2x_1 + 2x_1 \mu _1 = 0 $
$ 2. 2 + 2x_2 \mu _1 -\mu _2 = 0 $
$ 3. (x_1^2+x_2^2-1)\mu_1 - x_2\mu _2 = 0 $
$ 4. g_1(x),g_2(x) \le 0 $
Case 1:
$ If $ $ \mu_1 = 0 $ and $ \mu_2 = 0, $
$ then, 2 = 0 $which is impossible.
Case 2:
$ If $ $ \mu_1 = 0 $ and $ \mu_2 \not= 0, $
$ then, \mu_2 = 2, x_1 = 0, x_2 = 0. $.
Case 3:
$ If $ $ \mu_1 \not= 0 $ and $ \mu_2 = 0, $
$ then, x_1^2 + x_2^2 = 1 $
$ if x1 \not= 0, then \mu_1 = 1, x_2 = -1 $which is impossible.
$ if x1 = 0, then x_2 = 1, \mu_1 = -1 $which is impossible.
Case 4:
$ If $ $ \mu_1 \not= 0 $ and $ \mu_2 \not= 0, $
$ then, x_2 = 0, x_1^2 + x_2^2 = 1. So, x_1 = 1, \mu_1 = 1, \mu_2 = 2. $.
Therefore, there are two points that satisfy KKT condition.
$ \begin{bmatrix} \mu_1 ^{\ast}= 0 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 0 \\x_2^{\ast}= 0 \end{bmatrix}and \begin{bmatrix} \mu_1 ^{\ast}= 1 \\ \mu_2 ^{\ast}= 2 \\ x_1^{\ast}= 1 \\x_2^{\ast}= 0 \end{bmatrix} $
(ii)(10pts)Apply the SONC and SOSC to determine the nature of the critical points from the previous part.
Solution:
Apply SOSC to the first point.
$ \nabla g_2(x)^t y = 0 $
$ \begin{bmatrix} 0 & -1 \end{bmatrix} y = 0 $
$ y = \begin{bmatrix} a \\ 0 \end{bmatrix}, a\not= 0 $
$ L(x,\mu) = F(x) + \mu_2 G_2(x) =\begin{bmatrix} -2 & 0 \\ 0 & 0 \end{bmatrix} $ $ Check $$ y^tL(x,\mu)y $ $ \begin{bmatrix} a & 0 \end{bmatrix}\begin{bmatrix} -2 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} a \\ 0 \end{bmatrix} = -2a^2 \lneq 0 $ which means SOSC fails.
Apply SOSC to the second point.
$ \nabla g_1(x)^t y = 0, $
$ \begin{bmatrix} 2x_1 & 2x_2 \end{bmatrix} y = 0 $ $ y = \begin{bmatrix} 0 \\ a \end{bmatrix} where a\not= 0 $
$ L(x,\mu) = F(x) + \mu_1 G_1(x) + \mu_2 G_2(x) =\begin{bmatrix} -2 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} $ $ Check $$ y^tL(x,\mu)y $ $ \begin{bmatrix} 0 & a \end{bmatrix}\begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} 0 \\ a \end{bmatrix} = 2a^2 \gneq 0 $ that implies $ \begin{bmatrix} x^{\ast} = 1\\ x^{\ast} = 0 \end{bmatrix} $ is the minimized point.
