     Next: 1.2.2 Constrained optimization Up: 1.2.1 Unconstrained optimization Previous: 1.2.1.2 Second-order conditions for   Contents   Index

### 1.2.1.3 Feasible directions, global minima, and convex problems

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:

1. is compact if it is closed and bounded.
2. is compact if every open cover of has a finite subcover.
3. 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.     Next: 1.2.2 Constrained optimization Up: 1.2.1 Unconstrained optimization Previous: 1.2.1.2 Second-order conditions for   Contents   Index
Daniel 2010-12-20