The key fact that we used in the previous developments
was that for every
,
points of the form
for
sufficiently
close to 0 belong to
. This is no longer the case if
has
a boundary
(e.g.,
is a closed ball in
) and
is a point on this boundary.
Such situations do not fit into the unconstrained optimization scenario as we defined it at the beginning of Section 1.2.1; however, for simple enough sets
and with some extra care, a similar analysis is possible. Let us call a vector
a *feasible direction* (at
) if
for small enough
(see Figure 1.1).
If not all directions
are feasible, then the condition
is no longer necessary for optimality. We can still define the
function (1.4) for every feasible direction
, but the proof
of (1.7) is no longer valid
because
is now nonnegative. We leave it to the reader
to modify that argument and
show that if
is a local
minimum, then
for
every feasible direction
.
As for the second-order necessary condition, the
inequality (1.14) is still
true if
,
which together with (1.10) and (1.15)
implies that we must have
for all feasible directions
satisfying
.

If the set
is *convex*, then the line segment connecting
to an
arbitrary
other point
lies entirely in
. All points on this line segment
take the form
,
for
some
and
.
This means that
the feasible direction approach is particularly
suitable for the case of a convex
. But if
is not convex,
then the first-order and second-order necessary
conditions in terms of feasible directions are conservative. The next
exercise touches on the issue of sufficiency.

When we are not dealing with the completely unconstrained case in which is the entire , we think of as the constraint set over which is being minimized. Particularly important in optimization theory is the case when equality constraints are present, so that is a lower-dimensional surface in (see Figure 1.2). In such situations, the above method which utilizes feasible directions represented by straight lines is no longer suitable: there might not be any feasible directions, and then the corresponding necessary conditions are vacuous. We will describe a refined approach to constrained optimization in Section 1.2.2; it essentially replaces straight lines by arbitrary curves.

So far we have only discussed local minima. In practice, however, one is typically interested in finding a global minimum over a given domain (or constraint set) , if such a global minimum exists. We now briefly discuss how conditions for local optimality can be useful for solving global optimization problems as well, provided that these global problems have certain nice features.

The following basic existence result is known as the **Weierstrass Theorem**: *If
is a continuous
function and
is a compact set, then there exists a global
minimum of
over
.* The reader will recall that for subsets
of
, compactness can be defined in three equivalent ways:

- is compact if it is closed and bounded.
- is compact if every open cover of has a finite subcover.
- is compact if every sequence in has a subsequence converging to some point in (sequential compactness).

We will revisit compactness and the Weierstrass Theorem in the infinite-dimensional optimization setting.

The necessary conditions for local optimality that we discussed earlier
suggest the following procedure for finding a global minimum.
First, find all interior points of
satisfying
(the stationary points).
If
is not differentiable everywhere, include also points
where
does not exist (these points
together with the stationary points comprise the
*critical points*).
Next, find all boundary points satisfying
for all feasible
.
Finally, compare values at all these candidate points and choose the smallest
one.
If one can afford the computation of second derivatives, then
the second-order conditions can be used
in combination with the first-order ones.

If is a convex set and is a convex function, then the minimization problem is particularly tractable. First, a local minimum is automatically a global one. Second, the first-order necessary condition (for ) is also a sufficient condition. Thus if for all feasible directions , or in particular if is an interior point of and , then is a global minimum. These properties are consequences of the fact (illustrated in Figure 1.3) that the graph of a convex function lies above that of the linear approximation .

Efficient numerical algorithms--such as the well-known steepest descent (or gradient) method--exist for converging to points satisfying (stationary points). For convex problems, these algorithms yield convergence to global minima.