1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Could you explain what is $ \bar{u} $? $\endgroup$ – Royi Jun 19 '17 at 6:18
  • $\begingroup$ @Royi $\bar{u}$ is a vector with elements $\bar{u}_i$. $\bar{u}_i$ is defined in my problem $\endgroup$ – sleeve chen Jun 19 '17 at 6:20
  • $\begingroup$ 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. $\endgroup$ – Royi Jun 19 '17 at 6:25
1
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.