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!
look up duality. In the meantime, you may think along these lines: Form the Lagrangean for the first problem (Karush-Kuhn-Tucker conditions): $$L_1= f(x)+\lambda_1 (g(x)-s) $$ and obtain your first order-condition: $$\frac{\partial L_1}{\partial x} = f'(x)+\lambda_1 g'(x)=0\;\Rightarrow\;f'(x)=-\lambda_1 g'(x)\qquad [1]$$
Now do the same for the second formulation: $$L_2= g(x)+\lambda_2 (f(x)-t) $$ and again obtain your first order-condition: $$\frac{\partial L_2}{\partial x} = g'(x)+\lambda_2 f'(x)=0\;\Rightarrow\;f'(x)=-\frac{1}{\lambda_2} g'(x)\qquad [2]$$
For the problems to be equivalent you obviously must have (equating [1] and[2]) $$\lambda_1=\frac{1}{\lambda_2}$$
Already this means that $\lambda_1\neq0\;,\;\lambda_2\neq0$ i.e. that in both formulations the constraint must be binding.
An alternative would be that both constraints are non-binding, in which case the problems will be equivalent if there exist $x^\star$ such that $f'(x^\star)=g'(x^\star)=0$. Another case would obtain, if the solution could be at the boundary of the feasible set. Here both $f'(x)$ and $g'(x)$ should not become zero in the feasible set, and the feasible set should be the same in both formulations. This is just food for thought - not the whole picture.