# Is this “theorem” true in Optimization Theory?

If I have a function $f(x,y)$ subjected to a region $D$ on the xy-plane, then the extreme values of $f(x,y)$ occurs at the extreme "corners" points of $D$?

I remember waaaaaaay back in calculus, if the region is something even simple or "complicated" like a rectangle we had to do traces of $f(x,y)$ along planes and see where the maximum or min value of the single variable function is.

Is there a point in doing that? I could've sworn there's a theorem in Optimization that says "don't waste your time testing/finding extreme values on a region formed by a line because the optimal value occurs only at extreme points and the lines formed by the extreme points will never be a min or max"

I went back and pick up an old calculus textbook and I see authors doing the 'traces'. For instance, on a simple square [0,1] x [0,1], authors would make traces like

$f(x,0)$ = blah blah blah

-
For linear functions, this can, with the right conditions on $D$, be true. For non-linear, it need not be true. – André Nicolas Jun 2 '12 at 3:05
Could you remind me why it is only true for linear functions? Because i just remembered I remembered this from linear optimization, but I don't remember why this is true. – Hawk Jun 2 '12 at 3:06
Meanwhile, a harmonic function does take extreme values on the boundary of a nice region, but consider $x^2 - y^2$ on the square $-1 \leq x \leq 1, \; \; -1 \leq y \leq 1,$ where the extreme points $(1,0),(-1,0), (0,1),(0,-1)$ are not located at the corners. – Will Jagy Jun 2 '12 at 3:10
Draw a reasonable region $D$, like an ellipse. Pick a linear function, like $2x+3y$. Draw the lines $2x+3y=1$, $2x+3y=4.5$, $2x+3y=6.1$, and so on. The line goes further and further "out." So max value of $x+3y$ on $D$ occurs when we are just leaving $D$, when we get tangency. If the region $D$ is bounded by lines (is polygon), it happens at a corner (and maybe along a whole line). Didn't say it was only true for linear. – André Nicolas Jun 2 '12 at 3:11
Are you thinking of the Maximum Modulus Principe in Complex Analysis? – Gamma Function Jul 15 '13 at 0:31

Let the region $D$ be the region you picked, all points in the plane which are on or inside the square with corners $(0,0)$, $(1,0)$, $(1,1)$, and $(0,1)$. Let $f(x,y)=x^2+y^2-x$.

If a max or min occurs in the interior of the square, the partial derivatives there will be $0$. We have $\frac{\partial f}{\partial x}=2x-1$ and $\frac{\partial f}{\partial y}=2y$. Set these both equal to $0$ and solve. The only solution is $x=1/2$, $y=0$. There, our function value is $-1/4$. So the maximum certainly does not occur in the interior of the square.

Thus the maximum occurs somewhere on the boundary of $D$. It is clear that to maximize $x^2+y^2-x$ in our region, we should take $y$ as large as possible, namely $1$. So our maximum will occur on the upper edge of the square.

Where on the upper edge? We need to maximize $x^2-x+1$. By standard $1$-variable calculus, or by completing the square, we can see that the maximum of $x^2-x+1$ (if $0 \le x\le 1$) is reached at $x=1/2$. So our function $f$ is maximized in the region $D$ at the point $(1/2,1)$. This is not a corner point.

If we take a linear function $f(x,y)=ax+by+c$, and neither $a$ nor $b$ is $0$, then the maximum of $ax+by+c$ is reached at a corner, and nowhere else. If one of $a$ or $b$ is $0$, and the other is not, the maximum will be reached along an entire edge of the square, so at a couple of corner points, plus other points.

-

Sometimes one picture is better than a thousand words

-
But that's three pictures. – Will Jagy Jun 2 '12 at 3:45
I guess that's 3,000 words then? – copper.hat Jun 2 '12 at 4:15
I'm not sure the relationship between pictures and words is linear. – Will Jagy Jun 2 '12 at 5:49