Homework 9

Due: Jan. 04, 22:00:00

Strong duality, Slater's condition

1. Consider the following optimization problem:

   $min{x}_1^2+x_2^2$$\min \quad x_1^2+x_2^2$

   $\text{subject to}(x_1-1{)}^2+(x_2-1{)}^2\le 1,(x_1-1{)}^2+(x_2+1{)}^2\le 1.$$\text{subject to} \quad (x_1-1)^2+(x_2-1)^2\leq 1, \, (x_1-1)^2+(x_2+1)^2\leq 1.$

   • Sketch the feasible set and the level sets of the objective function. Find the optimal point $x^{\ast }$$x^*$ and the optimal value $f^{\ast }$$f^*$.
   • Give the KKT conditions. Do there exist Lagrange multipliers ${\mu }_1^{\ast }$$\mu_1^*$ and ${\mu }_2^{\ast }$$\mu_2^*$ that satisfy KKT conditions?
   • Write down the Lagrange dual function and the dual problem.
   • Solve the dual problem. Does strong duality hold? Does Slater's condition hold?

Projected gradient descent

2. Consider the following optimization problem:

   $minf(x)=x^{T}Qx$$\min \quad f(x)=x^T Q x$

   $\text{subject to}\Vert x{\Vert }_2=2.$$\text{subject to} \quad \lVert x\rVert_2=2.$

   We would like to solve it by the projected gradient descent method: $x_{k+1}=\mathcal{P}(x_k-t\cdot \mathrm{\nabla }f(x_k))$$x_{k+1} = \mathcal{P}(x_k-t\cdot \nabla f(x_k))$.

   • Suppose that $x_k\ne \mathbf{0}$$x_k \neq \mathbf{0}$. Find the closed form of $x_{k+1}$$x_{k+1}$.
   • Let $\begin{array}{c}Q=\left(\begin{array}{cc}1& 0\\ 0& 2\end{array}\right)\end{array}$$Q = \begin{pmatrix}1 & 0 \\ 0 & 2 \end{pmatrix}$ from now on. Solve the optimization problem by finding Lagrange multipliers.
   • Assume that $\{x_k\}$$\{x_k\}$ is the sequence produced by the projected gradient descent method. Let $x_k=(x_{k,1},x_{k,2})$$x_k = (x_{k,1}, x_{k,2})$ and $y_k=x_{k,2}/x_{k,1}$$y_k = x_{k,2}/x_{k,1}$. Find the connection between $y_{k+1}$$y_{k+1}$ and $y_k$$y_k$ (assume $x_{k,1}\ne 0$$x_{k,1}\neq 0$).
   • Find a possible value of $t$$t$ so that $\{x_k\}$$\{x_k\}$ will converge.

Questionnaire

• How long does it take you to do this homework?
• If $1$$1$ represents "very easy" and $10$$10$ represents "too hard", how difficult do you feel this homework is? (You can give different points for different problems.)