# Dual Problem of Projection onto the ${L}_{1}$ Ball

This is a very famous problem and there are many articles discussing it. For example: https://stanford.edu/~jduchi/projects/DuchiShSiCh08.pdf .

$$\min_{\|x\|_1 \leq \tau} \frac{1}{2}\|x-z\|^2$$

My question is how to derive its dual problem.

The following is my effort:

he Lagrangian dual is the following:
\begin{align*} L(x,u) = \frac{1}{2}\|x-z\|^2 + u(\|x\|_1 -\tau) \end{align*}So \begin{align*} \nabla_x L = (x - z) + \bar{u} \end{align*} where the $i$-th entry of $\bar{u}$ is
\begin{align*} \bar{u}_i=\begin{cases} u_i, &x_i > 0\\ [-u_i,u_i], &x_i=0 \\ -u_i, &x_i< 0 \end{cases} \end{align*} So let $\nabla_x L = 0$, we have $x^* = z-\bar{u}$. So \begin{align*} L(u) = \frac{1}{2}\|\bar{u}\|^2 + u(\|z-\bar{u}\|_1 - \tau) \end{align*}

I am confused that there are three cases for $\bar{u}$, and they are imbedded in the norm functions. I have no idea how to write down a neat and clear dual problem.

• Could you explain what is $\bar{u}$? – Royi Jun 19 '17 at 6:18
• @Royi $\bar{u}$ is a vector with elements $\bar{u}_i$. $\bar{u}_i$ is defined in my problem – sleeve chen Jun 19 '17 at 6:20
• Silly me. I thought it should be the the result of the Lagrangian Multiplier and the sign of $x$ yet overlooked and missed you defined it just like that. – Royi Jun 19 '17 at 6:25

Since the above it the Orthogonal Projection onto the Unit Simplex here is the solution using the Dual Function.

The Lagrangian in that case is given by:

\begin{align} L \left( x, \mu \right) & = \frac{1}{2} {\left\| x - y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x - 1 \right) && \text{} \\ \end{align}

The trick is to leave non negativity constrain implicit.
Hence the Dual Function is given by:

\begin{align} g \left( \mu \right) & = \inf_{x \succeq 0} L \left( x, \mu \right) && \text{} \\ & = \inf_{x \succeq 0} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \mu {x}_{i} \right) - \mu && \text{Component wise form} \end{align}

Again, taking advantage of the Component Wise form the solution is given:

\begin{align} {x}_{i}^{\ast} = { \left( {y}_{i} - \mu \right) }_{+} \end{align}

Where the solution includes the non negativity constrain by Projecting onto ${\mathbb{R}}_{+}$

Again, the solution is given by finding the $\mu$ which holds the constrain (Pay attention, since the above was equality constrain, $\mu$ can have any value and it is not limited to non negativity as $\lambda$ above).

The objective function (From the KKT) is given by:

\begin{align} h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} - 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{+} - 1 \end{align}

The above is a Piece Wise linear function of $\mu$ and its Derivative given by:

\begin{align} \frac{\mathrm{d} }{\mathrm{d} \mu} h \left( \mu \right) & = \frac{\mathrm{d} }{\mathrm{d} \mu} \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{+} \\ & = \sum_{i = 1}^{n} -{ \mathbf{1} }_{\left\{ {y}_{i} - \mu > 0 \right\}} \end{align}

Hence it can be solved using Newton Iteration.

I wrote MATLAB code which implements them both at Mathematics StackExchange Question 2338491 - GitHub.
There is a test which compares the result to a reference calculated by CVX.