Homework 9

Due: Jan. 04, 22:00:00

Lagrange dual

1. Consider the following optimization problem:

   $\min \quad f(x) = \log(1+e^x)$

   $\text{subject to} \quad x \geq 0$.

   • Find the optimal solution and the optimal value of $f$.
   • Write down the dual function and find the closed form.
   • Write down the dual problem.
   • Find the optimal solution to the dual problem.

Strong duality, Slater's condition

2. Consider the following optimization problem:

   $\min \quad x_1^2+x_2^2$

   $\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 of the problem, and the level sets of the objective function.
   • Find the optimal solution $x^*$ and the optimal value $f^*$.
   • Give the KKT conditions. Do there exist Lagrange multipliers $\mu_1^*$ and $\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?