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$.

\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.

  • $\begingroup$ Will it suffice to provide a numerical method for this solution which is guaranteed to converge? $\endgroup$
    – Zim
    May 18, 2021 at 15:32
  • $\begingroup$ @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^*$. $\endgroup$
    – vpy
    May 18, 2021 at 20:09
  • $\begingroup$ 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 $\endgroup$
    – Zim
    May 18, 2021 at 23:41
  • $\begingroup$ Ah darn, I was mistaken. Interesting question! $\endgroup$
    – Zim
    May 19, 2021 at 13:45


You must log in to answer this question.