Friday 9 October 2015

Lecture 1 homework

1. Consider $P_b$: minimize $f(x)=-x$, in two cases:

(a) $h(x)=\sqrt{x}$, $b=2$;

(b) $h(x)=x^2$, $b=16$.

What happens when you try to solve these problems using Lagrangian methods? In each case, find $\phi(b)$ and explain whether strong duality holds.

 2. Given $a_1,\dotsc,a_n>0$,
 \[
 \begin{align*}
\text{minimize}\ &- \sum_{i=1}^n \log(a_i+x_i)\\[4pt]
 \text{subject to } & x_1,\dotsc,x_n\geq 0\text{ and } \sum_{i=1}^nx_i =b.
 \end{align*}
 \]
The optimal $x$ corresponds to one that can be found by a so-called `water filling algorithm'. Imagine placing bars of heights $a_i$ side by side in the fashion of a histogram and then flooding above these bars so as to cover area of $b$. Draw a picture to illustrate this idea.