Convex Optimization Closed Form Solution I'm currently studying for my exame in convex optimization. It covers problem formulation, first and second order conditions of optimality, unconstrained optimization, constrained optimization with KKT, epigraph techniques and LP duality. I have the following problem from last year's exame
I am at a complete loss on how to solve this, can anyone help me? Even a hint would be helpfull
 A: Hint: Use Lagrange multipliers.
In both problems, the case $r \ge 0$ is trivially solved by the zero
vector. So in what follows, we assume $r < 0$. Also, to ensure
feasibility we'll be assuming $s \ne 0$.
(a) You can replace $\|x\|$ with $\frac{1}{2}\|x\|^2$ and this
won't change the solution (why ?). Now, consider the Lagrangian
\begin{eqnarray}
L(x, \lambda) := \frac{1}{2}\|x\|^2 + \lambda (s^Tx - r).
\end{eqnarray}
Differentiating w.r.t $x$ and setting to $0$ yields: $x + \lambda x =
0$, i.e $x = -\lambda s$.
Differentiating w.r.t $\lambda$ and setting to $0$ yields: $s^Tx - r =
0$, from which $s^T(-\lambda s) = r$, i.e $\lambda =
-\frac{r}{\|s\|^2}$.
Thus putting everything together, the (unique) solution is
$x = -\lambda s = \frac{r}{\|s\|^2}s$.
(b) Sorry I can't see some symbols in the question clearly. To
keep the ball rolling, I'll assume the blurred stuff is
$\mathbb{R}^n$. OK, Lagrange multipliers won't help here. Let's try
something even funkier. 
Your problem can be conveniently rewritten in the form
\begin{eqnarray}
\text{Find }\hat{x} \in \underset{x \in \mathbb{R}^n}{\text{argmin }}g(x) + f(s^Tx),
\end{eqnarray}
where we've introduced the proper convex l.s.c. functions
$g: \mathbb{R}^n \rightarrow ]-\infty, +\infty[$, $x \mapsto \|x\|_1$
    and $f : \mathbb{R} \in ]-\infty, +\infty]$, $u \mapsto i_{u \le
      r} = \begin{cases}0, &\mbox{if }u \le r,\\+\infty, &\mbox{
        otherwise.}\end{cases}$
Now, the Fenchel-Rockerfellar dual of the above problem is
\begin{eqnarray}
\text{Find }\hat{u} \in \underset{u \in \mathbb{R}}{\text{argmax }}-g^*(-us) - f^*(u), 
\end{eqnarray}
i.e,
\begin{eqnarray}
\text{Find }\hat{u} \in \underset{u \in \mathbb{R}}{\text{argmin }}g^*(-us) + f^*(u), 
\end{eqnarray}
where $g^*$ is the convex conjugate (aka Fenchel-Legendre transform) of $g$ defined by
\begin{eqnarray}
g^*(x) := \underset{z}{\text{max }}z^Tx - g(z).
\end{eqnarray}
It's easy to see that $g^*(y) = i_{\|y\|_\infty \le 1}
= \begin{cases}0, &\mbox{ if }\|y\|_\infty \le 1,\\+\infty, &\mbox{
    otherwise}\end{cases}$
and $f^*(u)
= \begin{cases} ru, &\mbox{ if } u \ge 0,\\+\infty, &\mbox{
    otherwise.}\end{cases}$
Thus the aforementioned dual problem can be rewritten as
\begin{eqnarray}
\hat{u} \in \underset{u \ge 0}{\text{argmin }}i_{\|us\|_\infty \le 1} + ru =
\underset{0 \le u \le 1/\|s\|_\infty}{\text{argmin }}ru
\end{eqnarray}
Thus since $r < 0$, the dual solution is $\hat{u}
= 1/\|s\|_\infty$.
Now the primal and dual solutions are linked by the optimality
condtions
\begin{eqnarray}
\hat{x}^Ts \in \partial f^*(\hat{u})\text{ and } -\hat{u}s \in \partial
g(\hat{x}) = \{\theta \in \mathbb{R}^n | \|\theta\|_\infty \le 1,
\theta^T\hat{x} = \|\hat{x}\|_1\} = sign(\hat{x}),
\end{eqnarray}
where the $sign(x)$ function is to be understood pointwise and
$sign(0) := 0$. Using the second optimality condition, we see that if
$j$ is an index such that $|s|_j < \|s\|_\infty$, then $\hat{x}_j =
0$. Thus $supp(\hat{x}) := \{1 \le j \le n| \hat{x}_j \ne 0\} \subseteq \Gamma := \{1 \le j \le n| \|s\|_\infty = |s|_j\}$.
Now, by Holder's inequality, $|\hat{x}^Ts| \le \|\hat{x}\|_1\|s\|_\infty$ and so $\|\hat{x}\|_1 \ge \frac{|\hat{x}^Ts|}{\|s\|_\infty} \ge \frac{-r}{\|s\|_\infty} > 0$.
Excercise:
Letting $\gamma := \#\Gamma$ and using the last inequality, show that the choice
$\hat{x}_j = \begin{cases}\frac{r}{\gamma s_j}, &\mbox{ if }j \in \Gamma,\\0, &\mbox{otherwise}\end{cases}$
solves the original / primal problem.
Hint:
It suffices to show that with this choice, we have $s^T\hat{x} \le r$ and $\|\hat{x}\|_1 = -r/\|s\|_\infty$.
A: I'll assume $s \neq 0$, otherwise the problems might be infeasible.
For part a), we want to know which point in the halfspace $s^T x \leq r$ is closest to the origin.  If $r \geq 0$, then the origin already belongs to this halfspace, so the best choice of $x$ is simply $x = 0$.  If $r < 0$, then visually we can see that the shortest way to get from the origin to the halfspace is to move in the direction $s$ (which is the direction normal to the hyperplane $s^T x = r$).  And how far should we move in that direction?  We should move until the equation of the halfspace is satisfied.  In other words, we should take $x = c s$, where $c$ is a scalar chosen so that $s^T x = c s^T s = r$.  So, $c = r/\|s\|^2$, and $x = r s/\|s\|^2$.
For part $b$, if $r > 0$ then again the best choice of $x$ is simply $x = 0$.  If $r < 0$, then how can we satisfy the equation $s^T x = r$ in such a way that the $1$-norm of $x$ is as small as possible?  Upon reflection, there is a simple strategy for choosing $x$.  Pick $i$ so that $|s_i| \geq |s_j|$ for all $j$.  (Here $s_j$ is the $j$th component of $s$.)  When we pick $x$, we should "put all our resources" into the $i$th component of $x$, and choose the other components of $x$ to be $0$.  So, we should choose $x$ so that 
\begin{equation}
x_j =
\begin{cases}
\frac{r}{s_i} & \qquad \text{if } j = i, \\
0 & \qquad \text{otherwise}.
\end{cases}
\end{equation} 
(This is an example of how penalizing the $1$-norm promotes sparsity.)
By putting our resources into the $i$th component of $x$, we get the most bang for our buck.
