I have been reading about constrained optimization and understood when there are just equality constraints but am having trouble understanding when there are inequality constraints. I was initially following KhanAcademy's multivariable calculus course but wanted to expand from the simple Lagrange Multipliers treatment so I began looking at pdfs online from different college courses.
I am thinking of things in 2 variables for now and let's just assume one inequality constraint for simplicity.
I understand that during an optimization of the form: $$ \begin{gathered} \max _{x, y} f\left(x, y\right) \text { subject to : } \\ g\left(x, y\right) \leq b . \end{gathered} $$
that there are two possible cases.
One is where the candidate point is in the interior of the boundary (i.e. $g(x, y) \lt b$) and that case makes sense to me that we are basically looking for unconstrainted local extrema (maxima here) by checking where $\nabla f(x, y)=\mathbf{0}$.
For the other case, the candidate points are on the boundary. I understand that for candidate point $(x^*, y^*)$, $\nabla g(x^*, y^*)$ will point outwards from the boundary and that $\nabla f(x^*, y^*)$ will be parallel to it. All the resources I am looking at say that when looking for maxima that you only consider the point if the gradient $\nabla f(x^*, y^*)$ points outward/in the same direction as $\nabla g(x^*, y^*)$. The explanation is that if $\nabla f(x^*, y^*)$ pointed inward then we know that there are some feasible points such that when $f$ is evaluated there that it will be greater than $f(x^*, y^*)$. Let's say we find such a point $(x^*, y^*)$ where the $\nabla f(x^*, y^*)$ is pointed inward.
I agree with the above reasoning that there will be some feasible points in the interior that will have higher values of $f$. Let's say one of these feasible points in the interior with a higher value of $f$ is $(x^1, y^1)$. What I don't follow is how we can safely ignore the point $(x^*, y^*)$ without being 100% sure that the local unconstrained maximum case above (so setting $\nabla f(x, y)=\mathbf{0}$) will find the point $(x^1, y^1)$. Couldn't it be the case that although $f$ 'dips' down on the interior of the boundary near $(x^*, y^*)$ that it will rise back up in some way that it won't be a local maximum and therefore the KKT conditions won't find it? In that case wouldn't we want to consider $(x^*, y^*)$ since at the very least we know it is an extrema of the boundary?
Apologies in advance if any of the math above feels hand wavey. I am trying to get an intuitive sense of things rather than something super rigorous. My basic question is that if we know there is some point in the interior ($g(x, y) \lt b$) such that $f$ will be greater than $f(x^*, y^*)$ are we guaranteed (or guaranteed under some conditions) to find it by just looking for unconstrained maxima? There might be some theorem I am missing here that'd help.
In one dimension I can picture that if $f$ decreases/stays equal within the feasible region (after initially increasing right at the boundary near $(x^*, y^*)$) that we immediately have a critical point by Rolle's theorem. And that if $f$ only increases then the other end of the boundary will have the max point. But I can't seem to make that same leap for 2+ dimensions.
If it helps I am thinking of a set up like the one in the picture below where the red region is the set of feasible points.
Thanks in advance for the help!
From your discussion I guess you assume that $f$ is smooth (at least differentiable). Inside the feasible set (boundary excluded), the constraint is said to be "inactive". There the KKT conditions are simply $\nabla f(x,y)=0$. If there exists such a point (a critical point of $f$) inside the set, then some algorithms (e.g., gradient ascent) might converge to it.
Now, if we assume that $f$ has no critical point inside the feasibility region, then since $\nabla f(x^\ast,y^\ast)$ points inward the set, there exists another point $(x,y)$ on the boundary where $f(x,y)\geq f(x^\ast,y^\ast)$. Indeed, $f$ must be non-decreasing, otherwise we would have a critical point of $f$ inside the set, by Roll's theorem.