Homework 7

Due: Dec. 17, 22:00:00

Lagrange multiplier

1. Consider the following optimization problem:

   $min{x}_1^2+2x_1{x}_2+3x_2^2+4x_1+5x_2+6x_3$$\min \quad x_1^2+2x_1x_2+3x_2^2+4x_1+5x_2+6x_3$

   $\text{subject to}{x}_1+2x_2=3,4x_3+5x_1=6.$$\text{subject to} \quad x_1+2x_2=3, \, 4x_3+5x_1=6.$

   • Write down the Lagrangian function and the (first-order) optimality condition.
   • Find the point satisfying the condition and find the corresponding Lagrange multiplier.
   • For each point satisfying the condition, determine whether it is the optimal solution.

2. Consider the following optimization problem:

   $min{x}_1^2+(x_2+1{)}^2+(x_3+1{)}^2$$\min \quad x_1^2+(x_2+1)^2+(x_3+1)^2$

   $\text{subject to}{x}_1^2+(x_2-2{)}^2+(x_3+2{)}^2=4,x_1^2+x_2^2+x_3^2=4.$$\text{subject to} \quad x_1^2+(x_2-2)^2+(x_3+2)^2=4, x_1^2+x_2^2+x_3^2=4.$

   • Write down the Lagrangian function and the (first-order) optimality condition.
   • Show that if a point $(x_1,x_2,x_3)$$(x_1,x_2,x_3)$ satisfies the condition, then $x_2-x_3=2$$x_2-x_3=2$.

3. Consider the following optimization problem:

   $min{x}_1^2+(x_2+1{)}^2+(x_2-1{)}^2$$\min \quad x_1^2+(x_2+1)^2+(x_2-1)^2$

   $\text{subject to}{x}_1^2+(x_2-2{)}^2+x_2^2=4.$$\text{subject to} \quad x_1^2+(x_2-2)^2+x_2^2=4.$

   • Write down the Lagrangian function and the (first-order) optimality condition.
   • Find the point satisfying the condition and find the corresponding Lagrange multiplier.
   • For each point satisfying the condition, determine whether it is the optimal solution.

   (In fact, it is exactly the optimization problem in Problem $2$$2$ by substituting $x_3=x_2-2$$x_3 = x_2 - 2$.)

KKT matrix and KKT system

4. Consider the following optimization problem:

   $min\frac{1}{2}\Vert Qx-w{\Vert }^2$$\min \quad \frac{1}{2}\lVert Qx-w\rVert^2$

   $\text{subject to}Ax=b$$\text{subject to} \quad Ax = b$,

   where $x\in {\mathbb{R}}^n$$x\in \mathbb{R}^n$, $Q\in {\mathbb{R}}^{m\times n}$$Q \in \mathbb{R}^{m\times n}$ with $\mathrm{rank}(Q)=n$$\mathrm{rank}(Q) = n$, $w\in {\mathbb{R}}^m$$w \in \mathbb{R}^m$, $A\in {\mathbb{R}}^{\ell \times n}$$A \in \mathbb{R}^{\ell \times n}$ with $\mathrm{rank}(A)=\ell$$\mathrm{rank}(A) = \ell$ and $b\in {\mathbb{R}}^{\ell }$$b\in \mathbb{R}^\ell$.

   • Write down the KKT system.
   • Find the closed form solution for the optimal solution $x^{\ast }$$x^*$ and the corresponding Lagrange multiplier ${\lambda }^{\ast }$$\lambda^*$.

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.)