Homework 8

Due: Dec. 28, 22:00:00

Newton's method

1. Consider the following optimization problem:

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

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

   • Write down the Lagrangian function and the (first-order) optimality condition.
   • Solve the problem by the Lagrange multiplier method.
   • Find the closed form expression for the Newton direction, and run an iteration starting from the initial point $\mathbf{x}=(1,0{)}^{\mathsf{T}}$$\mathbf{x} = (1,0)^\mathsf{T}$.

KKT condition

2. Consider the following optimization problem:

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

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

   • Write down the Lagrangian function and the KKT conditions.
   • Find the optimal point and corresponding multipliers.

3. Consider the following optimization problem:

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

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

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

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

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

Lagrange dual

4. Consider the following optimization problem:

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

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

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

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