Consider the ellipse $x_1^2/2^2 + x_2^2/2^2=1$ and the following inequality $x_2 \geq x_1-4$ . Algebraically it's not hard to check, but I need a solution on computer that checks every point of the ellipse. Since it has infinite number of points, it's not possible to check all, but I can check for a lot of points, this is the brute force method(which I want to avoid).
I've heard that you only need to check a few(or 1) special point that fulfils the KKT condition(s). Since I've never used those conditions and reading about them didn't really help, I'm asking if anyone knows how to use them in this task.
The method of Lagrange multipliers will usually give you only a handful of points to check. First a small rewrite. Define the functions $$ f(x) = x_2-x_1+4\\ g(x) = \frac{x^2_1}{2^2} + \frac{x_2^2}{2^2} - 1 $$ (Hopefully you can see where I got these functions from.) Now, what you want to know is, is $f$ ever negative on the points where $g$ is equal to $0$ (i.e. the ellipse)? If you only want to check a handful of points rather than all the points on the ellipse, we can first figure out where on the ellipse $f$ has a minimum. Well, minima are hard to find directly, but we can find extrema. That's almost as good.
When you want to find extrema of a function, you differentiate and find where the derivative is $0$. So that's what we set out to do: Differentiate $f$ along the ellipse, and figure out where it is $0$. Since $f$ is continuous and differentiable, and the ellipse is smooth, these are the only places extrema can be.
This can of course be done by, for instance, parametrising the ellipse and differentiating the value of $f$ applied to that parametrisation. In this case that might work well. In general, one standard tool for solving this problem is the method of Lagrange multipliers.
The genius of the method of Lagrange multipliers is this observation: If the derivative of $f$ along the ellipse is $0$ at a point, then the gradient of $f$ must be orthogonal to the ellipse. And the gradient of $g$ is always orthogonal to the ellipse.
So we look for points (on the ellipse) where the gradient of the two functions are parallel, i.e. one is a multiple of the other: $$ \cases{\nabla f(x_1, x_2) = \lambda\nabla g(x_1, x_2)\\g(x_1, x_2) = 0}\\ \cases{\displaystyle-1 = \lambda \frac{x_1}2\\\displaystyle 1 = \lambda \frac{x_2}2\\g(x_1, x_2) = 0} $$ The first two equations tell us that $x_1 = -x_2$ ($\lambda$ itself is not relevant to solve for; it's not really interesting how large the gradients are in relation to one another, only that they are parallel). Inserting this into the final equation, we get $$ g(x_1, -x_1) = 0\\ \frac{x_1^2}{2^2} + \frac{(-x_1)^2}{2^2} - 1 = 0\\ \frac{x_1^2}2 = 1\\ x_1 = \pm \sqrt2 $$ So that's it. The two points you need to check are $(\sqrt2, -\sqrt2)$ and $(-\sqrt2, \sqrt2)$.