1
$\begingroup$

The procedure for doing this usually goes as follows:

  1. Find the critical points of the function,
  2. Check which ones are in the region,
  3. Find critical points of the function on thr boundary,
  4. Compare the value of the function at each one of these points and choose the largest to be the maximum and smallest to be the minimum.

My question is: why do we claim this method works? It could very well be that the function restricted to the boundary has a minimum, but this point is neither a local minimum nor maximum on the region. Take for example $f(x,y)=y^2+1−\frac{1}{1+x}$on the right half plane. It is obvious that this function will have a minimum on the y-axis, but this point will not be a minimum on the region. 

My question arose from reviewing some multivariable calculus. The problem in question was to find the maxima and minima of $f(x,y)=x^2+y^2+2x+4y-1$ on the closed region above the diagonal $y=-x$. It is easy to find that $\nabla f =0$ at $(-1,-2)$. Since this point is not within the region, we restrict $f$ to the diagonal and find that its minimum over this boundary occurs at $(1/2,-1/2)$. In the answer sheets, the instructor claims this is a minimum for the function over the whole region, however I find this claim rigorously unjustified. How do we know whether or not there is some other point on which $f$ is smaller?

I tried to prove this formally by assuming that such a point, say $\vec x$ exists, then defining a "gradient descent" sequence $S=\{\vec x_n\}$ as follows:

$$ \vec x_0=\vec x$$ $$ \vec x_{n+1}= \vec x_n-\nabla f(x_n)$$ Since $f$ grows to infinity in all directions, it seems intuitive that $S$ should be bounded, at which point the result is proven.

It is also very possible I am missing something obvious. Any help is appreciated.

$\endgroup$
  • $\begingroup$ I'm not sure what you're driving at with your gradient descent argument. How exactly do you argue it puts the method in question on rigorous theoretical footing? $\endgroup$ – eepperly16 Nov 25 '17 at 8:00
  • $\begingroup$ @eepperly16 the instructor claims that the point on the boundary is a minimum, but how do we know for sure that there is no other point on the region at which the function is smaller? With the gradient descent idea I wanted to show that if this were the case, then the function would either have a local minimum somewhere in the region, or it would take smaller values on the boundary (i.e. wherever the sequence crossed over the diagonal), both of which are false. $\endgroup$ – Guacho Perez Nov 25 '17 at 8:11
1
$\begingroup$

If a function $f : D \to \Bbb R$ from a closed and bounded domain $D$ and is everywhere differentiable, then a maxima or minima must occur at a point where $\nabla f = 0$, for if not then for $x$ with $\nabla f(x) \ne 0$ we would have $f(x + \epsilon \nabla f) = f(x) + \epsilon \nabla f \cdot \nabla f + O(\epsilon^2)$, which is $\ge f(x)$ for sufficiently small $\epsilon$. Thus any minimizer $x$ of $f$ must either satisfy $\nabla f(x) = 0$ or $x$ must be on the boundary. We may thus enumerate the critical points in the region and on the boundary, and since the absolute maxima and minima must be a local maxima or minima, among them is our absolute maximum and minimum.

The problem with rigor comes when the function is defined on a region which is unbounded. In this case, the function is not guaranteed to have an absolute minimum. If it does have an absolute minimum, then the minimizer $x$ must satisfy $\nabla f(x) = 0$ or be on the boundary, as is argued above. If there is no absolute minimum, then this method tells you nothing.

$\endgroup$
  • $\begingroup$ And how do we know in general if a point on the boundary is a minimum for the function over the whole region? $\endgroup$ – Guacho Perez Nov 25 '17 at 8:07
  • $\begingroup$ @Guacho Perez Suppose I have a magic black box that tells me the absolute minimum on the boundary. As argued above, provided the objective function is everywhere differentiable, every local minima in the interior of $D$ must satisfy $\nabla f(x) = 0$. Thus, we may enumerate a list of potential candidates, one candidate from our black box for the boundary and a list of critical points satisfying $\nabla f(x) = 0$ from the interior. Any absolute minimum is guarenteed to be one of our candidates $\endgroup$ – eepperly16 Nov 25 '17 at 8:10
  • $\begingroup$ It is not the case that if a function has a minimum on the boundary it is a minimum for the function: this is not in general the case. Rather, the candidate will always be on the list and the list will always a point from the boundary (provided the boundary has a global minimum, which must be true if the original region is bounded) $\endgroup$ – eepperly16 Nov 25 '17 at 8:12
  • $\begingroup$ I understand that if a point is a local minimum, then the gradient is zero at that point. However, what if this point is not a local minimum? What if it is only smaller than than the minimum of the function on the boundary? For example, if the function is $y^2+1-\frac {1}{x+1}$ on the right half plane, then the function has no critical points, but on the y axis it is smallest at the origin. Its value at the origin is not a minimum over the whole region, since at $(1,0)$ we obtain a smaller value for the function. $\endgroup$ – Guacho Perez Nov 25 '17 at 8:15
  • $\begingroup$ Sorry, it took me too long to write my comment. What I am trying to get at is how do we know if a minimum for the function restricted to the boundary is a minimum for the function on the region or if there are smaller values for the function which might go undetected by setting the gradient equal to 0? $\endgroup$ – Guacho Perez Nov 25 '17 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.