Hi,


I wanted to ask, under which conditions can one rewrite the optimization objective


$\min\_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$


as


$\min\_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$


I have particular interest in the case where $f(x) = \|x\|\_1$ and $g(x) = \|y - Ax\|\_2$ (i.e. for the Lasso!), but would like to know the details for the general case.


References to appropriate books would be equally useful.


Thank you!



Rewrite optimization objective
Here's a solution for the specific case where $f(x)=\| x \|\_{1}$ and $g(x)=\| y-Ax \|\_{2}$. The same appraoch applies to $g(x)=\| A^{T}(y-Ax) \|\_{\infty}$.


There are two cases. 


1. If $g(0) \leq s$, then $x^{\*}=0$ is feasible for the first problem and because $f(x) > 0$ for all $x \neq 0$, $x^{\*}=0$ is the unique optimal solution to the first problem. In that case, let $t=0$. Then $x^{\*}=0$ is the only feasible solution to the second problem and thus the unique optimal solution to the second problem.
2. If $g(0) > s$, then $x=0$ is infeasible for the first problem. Since $x=0$ is the only unconstrained minimum of $f(x)$, any optimal solution to the first problem must have $g(x)=s$. Let $x^{\*}$ be an optimal solution to the first problem. Let $t=f(x^{\*})$. Clearly, $x^{\*}$ is feasible for the second problem. We will show that $x^{\*}$ is also optimal for the second problem.


suppose that there is some better solution to the second problem, $\hat{x}$. That is, 


$f(\hat{x}) \leq t=f(x^{\*})$


and


$g(\hat{x}) < g(x^{\*}) = s $


Since $\hat{x}$ is interior to the feasible set for problem one (or simply because $g$ is continuous), we can find an $\epsilon$ with $0 < \epsilon < 1$ and such that 


$\tilde{x}=(1-\epsilon)\hat{x}$


has $g(\tilde{x}) \leq s$. 


Note that 


$f(\tilde{x})=(1-\epsilon)f(\hat{x}) < f(x^{\*})$.


This contradicts the assumption that $x^{\*}$ was optimal for problem one. 


This proof generalizes to any case where $f(x)$ is a vector norm and $g(x)$ is a continuous function. 


