2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't think $(1/2,1/2,1)$ makes gradient zero. Check it yourself. $\endgroup$
    – Doug
    Jun 14, 2022 at 13:45
  • $\begingroup$ One need just to use Lagrange method correctly. Correct usage when constraint is inequality suggests consideration of two cases: maximum is obtained on boundary or maximum is obtained not on boundary. For first case one should use $L=f(x,y)+\lambda R(x,y)$. For second case one should use $L=f(x,y)$ and check for $R(x,y) > 0$. $\endgroup$
    – Ivan Kaznacheyeu
    Jun 14, 2022 at 14:33

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I accepted this earlier but I have a doubt now. There are two cases that arise: $(x,y,\lambda) \in \{(1,1,2), (0,0,0)\}$. The latter case would mean $s = \sqrt{-1}$. $\endgroup$
    – sigmafunction
    Jun 23, 2022 at 7:17
  • $\begingroup$ I think it'll be $\frac{\partial L}{\partial \lambda} = s^2 + x+xy -1$ and $\frac{\partial L}{\partial s} = 2 \lambda s$. $\endgroup$
    – sigmafunction
    Jun 23, 2022 at 7:24
  • $\begingroup$ Thanks. Now it is fixed. $\endgroup$
    – Cesareo
    Jun 23, 2022 at 8:37
  • $\begingroup$ When the maxima occurs at a satiation point which does not lie on the constraint, we can always add a slack variable and find that, right? Or will there be cases when this won't be true? Thank you! $\endgroup$
    – sigmafunction
    Jun 23, 2022 at 8:54
  • $\begingroup$ The value of $s$ gives us the answer. It $s=0$ then the constraint is actuating and when $s^2>0$ the stationary point is interior to the restriction domain. $\endgroup$
    – Cesareo
    Jun 23, 2022 at 11:08
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .