Rewrite constrained optimization objective 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!
 A: 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.
