Equivalence of two optimization problems

1.7k Views Asked by At

Consider the optimization problem A defined as $$ \max_{x,y} f(x,y)\text{ subject to } x+y\leq 0. $$ and the optimization problem $B$ defined as $$ \max_{x,y} f(x,y) - \lambda (x+y) $$ where $\lambda$ is set, outside of the optimization problem, so that after optimization $x+y = 0$.

The function $f$ is strictly increasing. Other than that I would like to remain as general as possible on the function $f$ and the sets in which $x$ and $y$ live but feel free to make assumptions if needed.

Are these problems equivalent? I believe that the answer is yes under fairly general conditions. It seems that this is just a way of reformulating the Lagrangian approach but I am unable to write a formal proof.

1

There are 1 best solutions below

2
On BEST ANSWER

Tentative answer.

Take a point $(x^B,y^B)$ that solves problem B. Then, by the definition of $\lambda$ it must be that $x^B+y^B=0$. Now this point must also solve problem A. To see this, notice that any solution to $A$ must be such that $x+y=0$. Now suppose that $(x^B,y^B)$ is not a solution to $A$. Then there is another point $(\tilde{x},\tilde{y})\neq (x^B,y^B)$ with $\tilde{x}+\tilde{y}=0$ such that $f(\tilde{x},\tilde{y})>f(x^B,y^B)$ but this point would have solved problem B, so we have a contradiction.

Conversely, take a point $(x^A,y^A)$ that solves problem A. Then it must be that $x^A+y^A=0$ since the constraint binds. Now this point must also solve problem B. Suppose not. Then there is another point $(\tilde{x},\tilde{y})\neq (x^A,y^A)$ with $\tilde{x}+\tilde{y}=0$ (by the definition of $\lambda$) such that $f(\tilde{x},\tilde{y})+\lambda*0>f(x^A,y^A)+\lambda*0$. But then this point would have solved problem A, so we have a contradiction.

Anything wrong with this answer?