how to find global minimum and max over set s

Question

I need to find the global minimum and maximum points of the linear function $f (x, y) = 5x − 8y$ over the set $S =\{(x, y) \in \mathbb R^2: 5x^2 − 8xy + 4y^2 + 8x − 8y ≤ 5\}$

Answer 1

first of all, your problem is convex:

$$\text{min./max. }f(x,y) = 5x - 8y$$

$$\text{s.t. } 5x^2 - 8xy + 4y^2 + 8x-8y \leq 5$$

You can see that the inequality constraint could be written as $(x~y)^T = z$ and $z^T A z + c^T z \leq 5$, which might be the more intuitive equation to see it's an ellipse (see the plot).

Affine functions (as your objective) are convex, any set $S$ bound by an ellipse is a convex set

$$S = \{x\in\mathbb{R}^n| x^T A x + c^T x \leq b\}$$

For convex problems Karush-Kuhn-Tucker holds, there exists one unique solution (the global maximum/minimum), hence you are searching for each one minimum and maximum. As @Matti P. has already mentioned, it will be on the edge of the ellipse, which means

$$5x^2 - 8xy + 4y^2 + 8x-8y = 5$$

Solving this equation and plugging it into the now un-constrained problem, I come up with:

$$(x, y)_{min} = \left(\frac{9}{5}, 4 \right)$$

$$(x, y)_{max} = \left(-\frac{9}{5}, -2 \right)$$

with $f((x, y)_{min}) = -23$ and $f((x, y)_{max}) = 7$, which looks rougly looks like this solution plot. I hope this helps.