I am trying to find the solution for the following optimization problem:
$\max_{w} {z^Tw - \lambda ||w - w_0||_1}$
where $z, w, w_0 \in R^{Nx1}$ and $z, w_0$ are known.
We let $s$ be the subgradient of $\lambda ||w - w_0||_1, \hspace{2mm} s \in \{ {u | u^T(w - w_0) = \lambda ||w - w_0||_1, ||u||_{\infty} \leq \lambda \} }$.
If we write $\lambda ||w - w_0||_1 = \max_{||s||_{\infty} \leq \lambda} s^T(w - w_0)$, the objective function can now be written as:
$\max_{w} \min_{||s||_{\infty} \leq \lambda} {z^Tw - s^T(w - w_0)}$
$\min_{||s||_{\infty} \leq \lambda} \max_{w} {z^Tw - s^T(w - w_0)}$.
The first order condition for the inner objective function is:
$0 = z - s \hspace{1cm} [1]$
Substituting [1] into the objective function,
$\min_{||s||_{\infty} \leq \lambda} s^Tw_0$.
Hence, this objective function can be simplified as,
$\min_s s^Tw_0 \text{ s.t } -\lambda \leq s \leq \lambda$.
However, if all the steps above are correct (which I am not very certain about), I am not sure how the solution of s from the "simplified" optimization above will help me solve for w.
The sequence of steps taken to solve the initial optimization problem was inspired by the following paper.
Any help on this is very much appreciated. Thank you.
There is a slight error in your derivation: you cannot set $s=z$ if $||z||_\infty > \infty$. Otherwise, the solution to $$\min_s \left\{ s^Tw_0 : -\lambda \leq s \leq \lambda \right\}$$ is trivial: you set $s_i = \lambda$ if $w_0\leq 0$, and $s_i = -\lambda$ otherwise, resulting in the objective value $-\lambda||w_0||_\infty$ (but again, this is wrong because you cannot always have $s=z$).
I would solve the optimization problem like this: \begin{align} \max_{w} {z^Tw - \lambda ||w - w_0||_1} &= \max_{w} {z^T(w+w_0) - \lambda ||w||_1} \\ &= z^T w_0 + \max_{w} {z^Tw - \lambda ||w||_1} \\ &= \begin{cases} z^T w_0 & \text{if } ||z||_\infty \leq \lambda \\ \infty & \text{otherwise.}\end{cases} \end{align} The last step is like computing the dual of the 1-norm.