Homework 8

Due: Dec. 30, 22:00:00

KKT matrix and KKT system

1. Consider the following optimization problem:

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

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

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

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

Newton's method

2. Consider the following optimization problem:

   $\min \quad e^{x_1}+e^{2x_2}$

   $\text{subject to} \quad x_1+x_2=1.$

   • Write down the Lagrangian function and the Lagrange multiplier condition.
   • Solve the problem by the Lagrange multiplier method.
   • Apply Newton's method to solve it from the the initial point $\mathbf{x} = (1,0)^\mathsf{T}$: write down the KKT system; find the closed form expression for the Newton direction; and then run an iteration.

KKT condition

3. Consider the following optimization problem:

   $\min\quad f(x_1,x_2) = e^{x_1+x_2} + e^{x_1-x_2}$

   $\text{subject to} \quad x_1+x_2 \geq 1, x_1\geq 0$.

   • Sketch the feasible set and label it properly.
   • Write down the KKT conditions.
   • Find the optimal solution and corresponding multipliers.

4. Consider the following optimization problem:

   $\min \quad \frac{1}{2} \lVert x-x_0 \rVert^2$

   $\text{subject to} \quad g(x) \leq 0$.

   Suppose that $g(x):\mathbb{R}^n\to \mathbb{R}$ is a continuously differentiable function, $x_0 \in \mathbb{R}^n$ and $g(x_0) >0$.

   Let $x^*$ be the optimal solution and we further assume that $x^*$ is a regular point. Apply KKT condition to determine:

   • Whether $g(x^*) = 0$ or $g(x^*) < 0$ ?
   • Whether $(x^*-x_0)^\mathsf{T}\nabla g(x^*) < 0$, $=0$, or $>0$ ?