Local and global optimality

Earlier we plotted the polynomial function

whose graph is reported again for convenience in Fig. 2.23. The stationarity points can be found by setting its derivative to zero:

Using numerical methods, we find the following roots of f′(x):

which are indeed the points at which f is stationary. Observing the graph, we see that x₁ is the global minimum, x₂ is a local maximum, and x₃ is a local minimum. In order to formalize these intuitive concepts, we need to define the neighborhood of a point on the real line.

Fig. 2.23 Graph of f(x) = x⁴ + x³ − 29x² − 9x + 180.

DEFINITION 2.13 (Neighborhood of a point) Given point , we define its (open) neighborhood of radius  as the interval , which is also denoted by .

In practice, for a small radius  the neighborhood  consists of the points close to x₀, i.e., points within a distance from x₀ bounded by . The concept can be generalized to multiple dimensions easily.

DEFINITION 2.14 (Global optimality) Given a function f defined over a domain D, we say that  is a global minimizer of function f if , for any other x ∈ D. We speak of a strict global minimizer if  for . By the very same token we define a global maximizer  by requiring , for any other x ∈ D. The definition of strict global maximizer is obvious.

In this definition we should not confuse, e.g., the minimizer  with the minimum . In a minimum-cost problem, the minimizer is a decision, whereas the minimum is the cost of that decision. The domain D could be restricted by the conditions under which the function is defined or by constraints on the decisions. Finally, a global minimizer need not be unique, as the minimum value f* could be attained by more than one point, unless it is a strict minimum.

DEFINITION 2.15 (Local optimality) Given a function f defined over a domain D, we say that  is a local minimizer of function f if there exists a neighborhood  such that f , for any other . The definition for a local maximizer is obtained similarly.

In local optimality we consider the intersection of the domain D and the neighborhood . In plain words, a local minimum is a point such that we cannot find anything better in its neighborhood, even though there might be a better solution if we look far enough. When dealing with a function of a single variable, a local minimizer is a point such that if we look both to the left and to the right, we see an increase in the function. Clearly, this local view does not imply that, outside this neighborhood, there is no point associated with a smaller function value. It is rather intuitive to generalize the concept to a function of two variables (we move on a plane), or a function of three variables (we move within a three-dimensional space).