Applied problems which consist of finding the maximum or minimum of a function of a single variable are a special case of optimization problems which can be written asunconstrained: find x in a suitable (admissible) set S
such that it satisfies:
max x in S F(x)
constrained: find x in a suitable (admissible) set S
such that it satisfies:
max x in S F(x)
along with equality constraints
G(x) = 0, and inequality constraints
H(x) < = 0Such problems can occur in engineering, science, mathematics, economics. Some examples are:
These problems are very ill-defined (usually) and can be extremely difficult to solve (e.g. the scheduling or "traveling salesman" problems).
- Economics: Find a set of mutual funds and growth stocks which will optimize revenue over a 6 month period.
- Engineering: Find a set of flow rates and other parameters which will maximize the production of gasoline and plastics from a refinery.
- Mathematics: Find the minimum of function of four variables (x,y,z,t), subject to the linear constraints x-y+z > 0 and t>0, and the nonlinear constraint exp(x+y+z) > sin(x-y).
- Scheduling: Find the routes and departure times which minimize delays in U.S. airspace over a 12 hour period.
As a simple model we consider the one-dimensional problemmax x in S f(x) where S is a set of real numbers.Question 1 (Existence) When does a solution exist to the prceding problem?
Answer [Extreme Value Theorem] If f(x) is continuous, and S is a closed interval [a,b], then f(x) has a maximum, x=c, and a minimum, x=d, in the interval [a,b].
Note: If f(x) fails to be continous, or if S is not closed, then a max and min can fail to exist.
Types of maxima and minima. A point x=c is an absolute maximum for f(x) if f(c) >= f(x) for all x in domain(f). Similarly, a point x=c is an absolute minimum for f(x) if f(c) <= f(x) for all x in domain(f). A point x=c is a local maximum for f if f(c) >= f(x) for x on some interval containing x=c. A point x=c is a local minimum for f if f(c) <= f(x) for x on some interval containing x=c.Such points may be difficult to find, but in the case of a smooth function f (that is f'(x) exists everywhere), local maxima and local minima can only occur at point where f'(x)=0! Physically, local maxima and minima must be at the tops of hills and bottoms of valleys respectively.
Question 2 (Characterization) What property characterizes local max/mins?
Answer [Fermat's Theorem] If f has a local extremum (either max or min) at x=c, and if f'(c) exists, then f'(c)=0.
Can a max or min occur anywhere else? Answer - In one dimensional problems, the only places a max or min may occur are at the following places:The latter two types of points are called critical points .
- Endpoints of the interval, x=a or x=b.
- Places where f'(x) = 0.
- Places where f' fails to exist.
Question 3 (Uniqueness) are local or absolute maxima/minima unique?Answer No, not in general. Consider the function f(x)=sin(1/x). This has an infinite number of absolute maxima and absolute minima on any interval containing x=0!
A partial answer is the following
If f is continuous on [a,b] and f''(x) > 0 on (a,b), then f has a unique absolute minima. Similary for maxima in the case f''(x)<0. Such functions are convex. (Note: Some type of local convexity is necessary for uniqueness of local maxima/minima, in general.)
Question 4 (Construction) How does one actually compute maxima/minima.Answer For functions of a single variable, look at the critical points (where f'=0 or fails to exist) and the endpoints. The abslute max and min are among these points (which usually give a small number of points to consider).
In the general case (such as the airplane scheduling problem) one uses very sophisticated mathematical algorithms, which are very time consuming to implement numerically, even on the largest computers available.
Question If f'(c)=0 for some c in (a,b), is c a local max or min?Answer Not necessarily. Consider f(x)= x3 on [-1,1]. f'(0)=0, but is not a local min or max! (It is an inflection point, actually).