Inequality constrained norm minimization

I am trying to understand the solution for the following optimization problem:
$$\max_w \mu^Tw - \gamma||w-w_0||_1 \text{ s.t. } \phi^Tw = 0.2$$
where $$\mu, w, w_0, \phi \in R^{N x1}$$ and $$\mu, w_0, \phi$$ are constants and only $$w$$ is the variable to be optimized over.

The Lagrangian for the above problem is:
$$L(\lambda, w) = \mu^Tw - \gamma||w-w_0||_1 - \lambda(0.2 - \phi^Tw)$$

Given that is not clear how I can proceed from the Lagrangian to find $$w^*$$ as it would require taking derivative of the absolute function, I try another route, by looking at the dual.

Form the Lagrangian, the dual function is defined as:
$$g(\lambda) = \inf_w (\mu^Tw - \gamma||w-w_0||_1 - \lambda(0.2 - \phi^Tw))$$

We can proceed to find the optimal value of $$g(\lambda)$$. Since $$w_0$$ is a constant, we can define $$z = w-w_0$$. \begin{align} g(\lambda) &= \inf_z (\mu^T(z+w_0) - \gamma||z||_1 - \lambda(0.2 - \phi^T(z+w_0))) \\ g(\lambda) &= \inf_z (-0.2\lambda + \mu^Tw_0 + \lambda\phi^Tw_0 + \mu^Tz+ \lambda\phi^Tz- \gamma||z||_1) \\ &\text{Let } s = \mu + \lambda \phi \\ g(\lambda) &= \inf_z (-0.2\lambda + s^Tw_0 + s^Tz - \gamma||z||_1) \\ g(\lambda) &= \inf_z (-0.2\lambda + s^Tw_0 -(\gamma||z||_1 - s^Tz)) \\ g(\lambda) &= -0.2\lambda + s^Tw_0 - \inf_z(\gamma||z||_1 - s^Tz) \end{align}

From slide 6 of Boyd's notes, we know that $$\inf_x(||x|| - y^Tx) = 0 \text{ if } ||y||_* \leq 1 \text{ else } -\infty$$.

Hence,
\begin{align} g(\lambda) &= \begin{cases} -0.2\lambda + s^Tw_0 & \text{if } ||s||_\infty \leq \gamma \\ \infty & \text{otherwise.}\end{cases} \end{align}

From the lower bound property of the dual problem, I learn that the lower bound of the original optimization is $$-0.2\lambda + s^Tw_0$$ if $$||s||_\infty \leq \gamma$$. Since, $$s = \mu + \lambda \phi$$ we also learn something about the dual variable.

However, I am still not able to make any headway towards understanding (or even approximating) the analytical form of $$w^*$$ (the primal). It is not clear to me how the primal-dual variable complementary slackness relationship could be used to infer $$w^*$$ from $$\lambda$$.

Any help and suggestions are very welcomed and deeply appreciated. Thanks in advance.

• Will it suffice to provide a numerical method for this solution which is guaranteed to converge?
– Zim
May 18, 2021 at 15:32
• @Zim I am familiar with the convex numerical method for this solution. However, I am trying to understand he behavior of the optimal primal variable and hence, I am looking for at least a close analytical proxy for the optimal variable, $w^*$.
– vpy
May 18, 2021 at 20:09
• I think you'll end up getting the infimal convolution of the Legendre conjugate of those two functions; time permitting I'll round back on this
– Zim
May 18, 2021 at 23:41
• Ah darn, I was mistaken. Interesting question!
– Zim
May 19, 2021 at 13:45