Lagrange method does not work

Question

$f : \mathbb{R} \to \mathbb{R}$ is given by $f(x,y) = -x^2 - y^2$. Calculate $\max[f]$ subject to $x + y \leq 1$.

Define $\mathcal{L}(x,y,\lambda) = -x^2 - y^2 - \lambda (x + y - 1)$. We need to calculate $\nabla (x,y,\lambda) = 0 \implies (x,y,\lambda) = \left(\frac{1}{2}, \frac{1}{2}, 1\right)$.

This neither solves for $\max[f] \text{ subject to } x + y \leq 1$ nor for $\min[f] \text{ subject to } x + y \leq 1$. Why is that the case and how to calculate the two (specifically) using Lagrange multipliers?

Answer 1

The Lagrange method requires that the involved manifolds be continuously derivable. As the restriction $x+1\le 1$ does not fulfill this requirement, we can apply the method after transforming the inequality into an equivalent equation. So we consider instead $x+y-1+s^2=0$, with $s$ a so called slack variable. The Lagrangian now is

$$ L(x,y,\lambda,s) = -x^2-y^2+\lambda(x+y-1+s^2) $$

now the stationary points are the solutions for

$$ \nabla L = 0 = \left\{ \begin{array}{l} \lambda -2 x \\ \lambda -2 y \\ s^2+x+y-1 \\ 2 \lambda s \\ \end{array} \right. $$

etc.

Answer 2

The original problem cannot be solved with the Lagrange method. The constraint needs to be an equality, not an inequality.

You've actually solved a different problem, where the constraint is

$$x+y=1$$

You've obtained the maximum of the original function, constrained to the set $\{x,y\in\mathbb{R}|x+y=1\}$, which is

$$f\left(\frac{1}{2},\frac{1}{2}\right) = -\frac{1}{4}-\frac{1}{4}=-\frac{1}{2}$$

---

Generally you'll need stronger methods to solve problems like your original one. Problems that include $\le$ and $\ge$ conditions are usually solved by the Simplex Method or other Linear Programming Techniques (Interior Point Algorithms, Active Set Methods, etc.). See more on the Linear Programming Wikipedia page.

---

Of course, this is just a toy example, and with the $x+y \le 1$ condition, the solution is clearly $f(0,0)=0$; so you don't need to apply the Simplex Method or anything complicated here.

Answer 3

A more basic approach to solve a problem like this is to check for local maxima for our function in three general areas:

1. Interior to the domain.
2. Along the smooth boundary.
3. At the corners of the boundary.

We then compare values of $f$ at corners and at critical points on boundary/interior. The largest of these will be global maximum.

A numerical approach like simplex method might be applicable to larger variety of problems, but for your example, because your function is differentiable and the boundary of the domain is smooth and easy to parameterize, we can solve it completely by basic calculus techniques.

Along boundary: $y = 1-x$. Substituting, $$f(x,1-x) = -x^2-(1-x)^2 = -2x^2+2x-1.$$ This function has critical point at $x = 1/2$. Now, $$f(1/2,1-1/2) = f(1/2,1/2) = -1/2.$$ There is no other boundary to the domain, so now we look at interior of the domain, asking when gradient of $f$ is zero. $$f_x = -2x = 0,\quad f_y = -2y = 0,$$ which gives us a critical point of $(0,0)$ (you should verify that (0,0) is in the interior of the domain) and $f(0,0) = 0 > -1/2.$ So, the solution is $\max[f] = f(0,0) = 0.$