I am currently trying to tell wheter or not those two problems are equivalent :

$$\min_x \|x\|_1 \text { s.t. } \|Ax-y\|^2_2 \le \varepsilon.$$


$$\min_x \|Ax-y\|^2_2 \text { s.t. } \|x\|_1\le t.$$

With $x$ and $y$ vectors and $A$ a compatible matrix.

I know that the second problem is equivalent to :

$$\min_x \|Ax-y\|^2_2 + \lambda \|x\|_1.$$

(Lagrangian form)

The same process for the first problem would give :

$$\min_x \|x\|_1 + \mu \|Ax-y\|^2_2$$

Does this lead somewhere ?

Thank for your help.


The first problem $$\min_x \|x\|_1 \text { subject to } \|Ax-y\|^2_2 \le \epsilon$$ can be described by the equivalent saddle point problem: $$ \min_x\max_{\lambda\ge 0}\left[ \|x\|_1 +\lambda(\|Ax-y\|_2^2-\epsilon)\right]=\max_{\lambda\ge 0}\min_x\left[ \|x\|_1 +\lambda(\|Ax-y\|_2^2-\epsilon)\right], $$ by Lagrange's multiplier theorem. Let $\lambda_0\ge 0$ be the solution of the above problem such that $$ \max_{\lambda\ge 0}\min_x\left[ \|x\|_1 +\lambda(\|Ax-y\|_2^2-\epsilon)\right]=\min_x\left[ \|x\|_1 +\lambda_0(\|Ax-y\|_2^2-\epsilon)\right]. $$If we have $\lambda_0 = 0$, then the minimizer should be $x=0$ and $\|y\|^2_2\leq\epsilon.$ Let us exclude this trivial case and assume that $\lambda_0>0$. By complementary slackness, we should have $\|Ax_0-y\|_2^2 =\epsilon$ where $x_0$ is the solution of the first problem.

In the same manner, the second problem can be equivalently described as $$ \min_{x'}\max_{\mu\ge 0}\left[ \|Ax'-y\|_2^2 +\mu (\|x'\|_1-t)\right]=\max_{\mu\ge 0}\min_{x'}\left[ \|Ax'-y\|_2^2 +\mu (\|x'\|_1-t)\right]\quad\cdots(*), $$ where $t = \|x_0\|_1$. If we look at the formulation of the second problem carefully, we can see that the solution $(\mu_0, x_0')$ should be $(\frac{1}{\lambda_0},x_0)$. To see this, one can plug $\mu=\lambda_0^{-1}$ and $x_0'=x_0$ into the $(*)$ to check if equality holds. In fact, equality holds since given $\mu=\lambda_0^{-1}$, $x=x_0$ is the minimizer and conversely, given $x=x_0$, $\mu =\lambda_0^{-1}$ is the maximizer. This establishes that Lagrangian dual problems in this case (in fact, generally) are equivalent.

  • $\begingroup$ Thanks a lot. Not sure I fully understand your answer for now but all that I get seems very logical and meaningfull. I will look further into it. $\endgroup$ – nicomezi Dec 20 '18 at 10:50

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.