Lasso - constraint form equivalent to penalty form We know that there are two definitions to describe lasso.
Regression with constraint definition:
$$\min\limits_{\beta} \|y-X\beta\|^2, \sum\limits_{p}|\beta_p|\leq t, \exists t
$$
Regression with penalty definition:
$$\min\limits_{\beta} \|y-X\beta\|^2+\lambda\sum\limits_{p}|\beta_p|, \exists\lambda$$
But how to convince these two definition are equivalent for some $t$ and $\lambda$? I think Lagrange multipliers is the key to show the relationship between two definitions. However, I failed to work out it rigorously because I assume the properties of lasso ($\sum\limits_{p}|\beta_p|=t$) in regression with constraint definition.
Does anyone can show me the complete and rigorous proof of these two definitions are equivalent for some $t$ and $\lambda$?
Thank you very much if you can help.
EDIT: According to the the comments below, I edited my question.
 A: Here is one direction.
(1) The constrained problem is of the form
\begin{array}{ll}
  \text{Find} & x \\
  \text{To minimize} & f(x) \\
  \text{such that} & g(x) \leqslant t \\
                 & \llap{-} g(x) \leqslant t.
\end{array}
Its Lagrangian is 
$$ L(x, \mu_1, \mu_2) = f(x) + \mu_1' ( g(x) - t ) + \mu_2' ( - g(x) - t ) $$
and the KKT conditions are
\begin{align*}
  \nabla f + \mu_1' \nabla g - \mu_2' \nabla g &= 0 \\
  \mu_1, \mu_2 &\geqslant 0 \\
  \mu_1' ( g(x) - t ) &= 0 \\
  \mu_2' ( - g(x) - t ) &= 0 .
\end{align*}
(2) The penalized problem is just the minimization of 
$f(x) + \lambda' g(x)$. It is unconstrained, and the first order condition 
is 
$$ \nabla f + \lambda ' \nabla g = 0. $$
Given a solution of the constrained problem,
the penalized problem with $\lambda = \mu_1 - \mu_2$ has the same solution.
(For a complete proof, you also need to check that, in your situation, the KKT conditions and the first order condition are necessary and sufficient conditions.)
A: It's not really intuitive to see, but here is one way to look at it using only basic inference.
Suppose $\beta^{*}$ is a solution to the regression with penalty problem (with some $\lambda$) and $\beta^{**}$ is a solution to the regression with constraint problem with $t = |\beta^{*}|$ (where $|\bullet|$ denotes the $\ell_1$ norm : $|\beta| = \sum\limits_{p}|\beta_p|$).
We show that the two problems are equivalent in the sense that $\beta^{*}$ is also a solution to the constraint problem and that $\beta^{**}$ is also a solution to the penalty problem.


*

*Because $\beta^{*}$ is a solution of the penalty problem, for all $\beta$ we have $\|y-X\beta\|^2+\lambda|\beta| \ge \|y-X\beta^{*}\|^2+\lambda|\beta^{*}|$ 
which implies that $\|y-X\beta\|^2 \ge \|y-X\beta^{*}\|^2$ for all $\beta$ such that $|\beta| \le t = \beta^{*} $ from which we conlude that $\beta^{*}$ is a solution to the constraint problem.

*Because $\beta^{**}$ is a solution of the constraint problem we have $|\beta^{**}| \le t=|\beta^{*}|$ and  $\|y-X\beta^{*}\|^2 \ge \|y-X\beta^{**}\|^2$ and because $\beta^{*}$ is a solution of the penalty problem we have 
$\forall \beta, \space \|y-X\beta\|^2+\lambda|\beta| \ge \|y-X\beta^{*}\|^2+\lambda|\beta^{*}|$.
Those imply $\forall \beta, \space \|y-X\beta\|^2+\lambda|\beta| \ge \|y-X\beta^{**}\|^2+\lambda|\beta^{**}|$ which allows us to say that $\beta^{**}$ is a solution to the penalty problem.


We can easily see that $|\beta^{*}| = |\beta^{**}|$ and $\|y-X\beta^{*}\|^2 = \|y-X\beta^{**}\|^2$ but we don't really need this in the proof.
