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 $d\in\mathbb{R}^n$ , points of the form $x^*+\alpha d$ for $\alpha$ sufficiently close to 0 belong to $D$ . This is no longer the case if $D$ has a boundary (e.g., $D$ is a closed ball in $\mathbb{R}^n$ ) and $x^*$ 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 $D$ and with some extra care, a similar analysis is possible. Let us call a vector $d\in\mathbb{R}^n$ a feasible direction (at $x^*$ ) if $x^*+\alpha d\in D$ for small enough $\alpha> 0$ (see Figure 1.1). If not all directions $d$ are feasible, then the condition $\nabla f(x^*)=0$ is no longer necessary for optimality. We can still define the function (1.4) for every feasible direction $d$ , but the proof of (1.7) is no longer valid because $\alpha$ is now nonnegative. We leave it to the reader to modify that argument and show that if $x^*$ is a local minimum, then $\nabla f(x^*)\cdot d\ge 0$ for every feasible direction $d$ . As for the second-order necessary condition, the inequality (1.14) is still true if $g'(0)=0$ , which together with (1.10) and (1.15) implies that we must have $d^T\nabla^2 f(x^*)d\ge 0$ for all feasible directions satisfying $\nabla f(x^*)\cdot d=0$ .

Figure: Feasible directions

If the set $D$ is convex, then the line segment connecting $x^*$ to an arbitrary other point $x\in D$ lies entirely in $D$ . All points on this line segment take the form $x^*+\alpha d$ , $\alpha\in[0,\bar\alpha]$ for some $d\in\mathbb{R}^n$ and $\bar\alpha>0$ . This means that the feasible direction approach is particularly suitable for the case of a convex $D$ . But if $D$ 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 $D$ is the entire $\mathbb{R}^n$ , we think of $D$ as the constraint set over which $f$ is being minimized. Particularly important in optimization theory is the case when equality constraints are present, so that $D$ is a lower-dimensional surface in $\mathbb{R}^n$ (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.

Figure: A surface

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) $D$ , 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 $f$ is a continuous function and $D$ is a compact set, then there exists a global minimum of $f$ over $D$ . The reader will recall that for subsets of $\mathbb{R}^n$ , compactness can be defined in three equivalent ways:

1. $D$ is compact if it is closed and bounded.
2. $D$ is compact if every open cover of $D$ has a finite subcover.
3. $D$ is compact if every sequence in $D$ has a subsequence converging to some point in $D$ (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 $D$ satisfying $\nabla f(x^*)=0$ (the stationary points). If $f$ is not differentiable everywhere, include also points where $\nabla f$ does not exist (these points together with the stationary points comprise the critical points). Next, find all boundary points satisfying $\nabla f(x^*)\cdot d\ge 0$ for all feasible $d$ . 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 $D$ is a convex set and $f$ 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 $f\in\mathcal C^1$ ) is also a sufficient condition. Thus if $\nabla f(x^*)\cdot d\ge 0$ for all feasible directions $d$ , or in particular if $x^*$ is an interior point of $D$ and $\nabla f(x^*)=0$ , then $x^*$ is a global minimum. These properties are consequences of the fact (illustrated in Figure 1.3) that the graph of a convex function $f$ lies above that of the linear approximation $x\mapsto f(x^*)+\nabla f(x^*)\cdot (x-x^*)$ .

Figure: A convex function

Efficient numerical algorithms--such as the well-known steepest descent (or gradient) method--exist for converging to points satisfying $\nabla f(x^*)=0$ (stationary points). For convex problems, these algorithms yield convergence to global minima.