Extrema subject to constraints

Question

I had general questions about finding extrema subject to constraints. If I have a function, let's say:

$f(x,y) = x^2+y^2-xy-x-y$

and I want to find its max/min in the domain $D = \{ (x,y)| x+y \leq 3, x \geq 0 , y \geq 0 \}$ (it looks like a triangle)

So, I looked for the the critical points inside D(inside the triangle) and then in the 3 outer lines of the triangle.

However,I saw, that I also needed to take into account the points (0,0) (0,3) and (3,0). This is my first question. Why do I need to take into account these points? Why aren't they included already in the three line segments?

And my second question is that when I find the max/min in D by equating the gradient of f to the 0 vector, I get the point (1,1). Do I need to make sure that this point is NOT a saddle point by using for example the Hessian criteria? Or can I, at the end, just evaluate f at (1,1) and compare it to the value of f given by the rest of critical points and then decide wether it is a max or min value?

Answer 1

Here's your function over $D$:

Setting the derivative of $f$ to zero will find a local extremum (or inflection point) within a region, but if an extremum is on the boundary, in general it will not.

Take the simple one-dimensional case $f(x) = x$ over $0 \leq x \leq 1$. Your derivative is never zero, but the maximum lies on the boundary $(x = 1)$. So you have to check those.

Using this fact you'll find the extrema at the corners of your $D$ by finding the values at the ends of each line segment, and hence will not need to also check the corner points individually.

Answer 2

Calling $f(x,y) = x^2+y^2-xy-x-y$ and with the help of some slack variables $s_k$ to transform the inequalities into equations we have the lagrangian

$$ L(x,y,\lambda,s) = f(x,y) + \lambda_1(x+y-3+s_1^2)+\lambda_2(x-s_2^2)+\lambda_3(y-s_3^2) $$

The stationary points are the solutions for

$$ \nabla L = 0 = \cases{\lambda_1+\lambda_2+2x-y-1\\ \lambda_1+\lambda_3-x+2y-1\\ x+y-3+s_1^2\\ x-s_2^2\\ y-s_3^2\\ \lambda_1s_1\\ \lambda_2s_2\\ \lambda_3 s_3 } $$

This solution gives

$$ \left[ \begin{array}{ccccccccc} f & x & y & \lambda_1 & \lambda_2 & \lambda_3 & s_1^2 & s_2^2&s_3^2\\ -1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ -\frac{3}{4} & \frac{3}{2} & \frac{3}{2} & -\frac{1}{2} & 0 & 0 & 0 & \frac{3}{2} & \frac{3}{2} \\ -\frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{3}{2} & 0 & \frac{5}{2} & 0 & \frac{1}{2} \\ -\frac{1}{4} & \frac{1}{2} & 0 & 0 & 0 & \frac{3}{2} & \frac{5}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 3 & 0 & 0 \\ 6 & 0 & 3 & -5 & 9 & 0 & 0 & 0 & 3 \\ 6 & 3 & 0 & -5 & 0 & 9 & 0 & 3 & 0 \\ \end{array} \right] $$

Here $s_k = 0$ indicates that the corresponding restriction is active and $\lambda_k =0$ indicates that the stationary point is interior to the restriction. Attached a plo showing the stationary points location (red) as well as the feasible region (light blue). In black the level curves to the objective function.