# 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!

• These problems cannot be equivalent unless you mean $\arg\min$ instead of $\min$. – Did Aug 1 '13 at 9:20

## 1 Answer

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 $$

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 $$

For the problems to be equivalent you obviously must have (equating  and) $$\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.