Next: 4.6 Notes and references Up: 4. The Maximum Principle Previous: 4.4.4 Fuller's problem   Contents   Index

4.5 Existence of optimal controls

To motivate the subject of this section, let us consider the following (obviously absurd) claim: The largest positive integer is 1. To prove" this statement, let be the largest positive integer and suppose that . Then we have , which contradicts the property of being the largest positive integer. Therefore, .

This argument is known as Perron's paradox. Although clearly farcical, it highlights a serious issue which we have been dodging up until now: it warns us about the danger of assuming the existence of an optimal solution. Indeed, finding the largest positive integer is an optimization problem. Of course, a solution to this problem does not exist. In the language of this book, the above reasoning correctly shows that is a necessary condition for optimality. Thus a necessary condition can be useless--even misleading--unless we know that a solution exists.

We know very well that the maximum principle only provides necessary conditions for optimality. The same is true for the Euler-Lagrange equation and several other results that we have derived along the way. We have said repeatedly that fulfillment of necessary conditions alone does not guarantee optimality. However, the basic question of whether an optimal solution even exists has not been systematically addressed yet, and it is time to do it now.

Suppose that we are given an optimal control problem which falls into the general class of problems formulated in Section 3.3. How can we ensure the existence of an optimal control? For a start, we must assume that there exists at least one control that drives the state of the system from the initial condition to the target set (more precisely, the pair should evolve from to ). Otherwise, the problem is ill posed (has infinite cost). We can view this as a type of controllability assumption. It may be nontrivial to check, especially for general control sets . Still, it would be nice if this controllability assumption were enough to guarantee the existence of an optimal control. Simple examples show that unfortunately this is not the case.

Observe that in the above example, arbitrarily fast transfer is possible because the control set is unbounded. Let us see if the problem becomes well posed when is taken to be bounded.

This time, the difficulty is caused by the fact that the control set is not closed. The reader is probably beginning to guess that we want to have both boundedness and closedness, i.e., compactness. To make this statement precise, however, we should be working not with the control set itself but with the set of all points reachable from using controls that take values in . For , let us denote by the set of points reachable from at time (for a given control set ). We already worked with reachable sets on page , in the context of linear systems. We saw there that if is the fastest transfer time from to , then must be a boundary point of ; this situation is illustrated in Figure 4.18.

In the two scalar examples considered earlier, the reachable set computation is straightforward and the negative conclusions are readily explained by the above property being impossible to satisfy. In Example 4.3, for all , which is unbounded and cannot contain on its boundary. In Example 4.4, which is not closed and does not include the boundary point , while for each the set already contains in its interior. We can now formulate a refined guess saying that for optimal controls to exist, we want to have compact reachable sets. We could generalize this discussion to target sets instead of fixed terminal points; we will also see that compactness of reachable sets is relevant not only for time-optimal control problems.

For nonlinear systems, explicit computation of reachable sets is usually not feasible. Instead, we can rely on the following general result known as Filippov's theorem: Given a control system in the standard form (3.18) with , assume that its solutions exist on a time interval for all controls and that for every pair the set is compact and convex. Then the reachable set is compact for each .

We do not prove this theorem but make some comments on it. For the result to be valid, controls must a priori be understood as measurable functions from to ; see the discussion on page . (We can hope to show afterwards that optimal controls belong to a nicer class of functions, e.g., that they enjoy the bang-bang property.) It is important to note that the first hypothesis in the theorem (existence of solutions on a given interval) is not implied by the second hypothesis (compactness and convexity of the right-hand side); for example, solutions of blow up in finite time even for . Filippov's theorem actually has a stronger statement, from which compactness of follows: it says that the set of all trajectories of the system, as a subset of , is compact with respect to the topology induced by the 0-norm , i.e., the topology of uniform convergence. Boundedness of the reachable sets can be shown without the convexity assumption, but convexity is crucial for establishing closedness (the argument relies on the separating hyperplane theorem). The next exercise should help clarify the role of the convexity assumption.

Filippov's theorem applies to useful classes of systems, most notably, to systems affine in controls given by (4.59) with compact and convex control sets . For such systems, the set is compact and convex for each as the image of under an affine map. As we already warned the reader, existence of solutions on a time interval of interest needs to be assumed separately. In the special case of linear systems (4.51), though, global existence of solutions is automatic. The right-hand side of the system is allowed to depend on time as well. For linear systems the reachable set is also convex, as can be easily seen from convexity of and the variation-of-constants formula for solutions.

Filippov's theorem provides sufficient conditions for compactness of reachable sets. Earlier, we argued that compactness of reachable sets should be useful for proving existence of optimal controls. Let us now confirm that this is indeed true, at least for certain classes of problems. The connection between compactness of reachable sets and existence of optimal controls is especially easy to see for problems in the Mayer form (terminal cost only). Suppose that the control system satisfies the hypotheses of Filippov's theorem, that the cost is with a continuous function, and--in order to arrive at the simplest case--that the target set is (a fixed-time, free-endpoint problem). Since is a continuous function and is a compact set, the Weierstrass Theorem (see page ) guarantees that has a global minimum over . By the definition of , there exists at least one control that steers the state to this minimum at time , and every such control is optimal.

For certain fixed-time problems in the Bolza form, it is possible to establish existence of optimal controls by combining compactness of the set of system trajectories (provided by the stronger form of Filippov's theorem) with continuity of the cost functional on this set and invoking the infinite-dimensional version of the Weierstrass Theorem (see page ). Alternatively, one can reduce the problem to the Mayer form (as in Section 3.3.2) and then use the previous result. In general, the argument needs to be tailored to a particular type of problem at hand. We will now show in detail how existence of optimal controls can be proved for linear time-optimal control problems, based on compactness--actually, just closedness--of reachable sets. The next result says that compactness and convexity of and a controllability assumption (the existence of some control achieving the desired transfer) is all we need for an optimal control to exist. (As we know from Section 4.4.2, such an optimal control is automatically bang-bang if is a hypercube, or can be chosen to be bang-bang if is an arbitrary convex polyhedron.)

PROOF. Let . The time is well defined because by the theorem's hypothesis the set over which the infimum is being taken is nonempty. (We note that, in view of boundedness of , we have unless .) We will be done if we show that , i.e., that is actually a minimum.4.6 This will mean that there exists a control that transfers to at time , and by the definition of no control does it faster.

By the definition of infimum, there exists a sequence such that for each . Then, by the definition of , for each there is a control such that

The above equation shows that the same point belongs to the reachable sets for different . To be able to use the closedness property of reachable sets (guaranteed by Filippov's theorem), we would rather work with different points belonging to the same reachable set. To this end, let us truncate the trajectories corresponding to the controls at time and define, for each ,

 (4.68)

All these points by construction belong to the same reachable set .

We now claim that the sequence of points converges to . If we establish this fact then the proof will be finished, because the closedness of the reachable set will imply that as needed. To prove the convergence claim, let us write

where we defined and made the substitution . Taking the norm on both sides, we have

 (4.69)

Similarly, we can take the norm on both sides of (4.69) to obtain the bound

which is independent of , implying that the sequence is uniformly bounded. Using this fact in (4.70) and noting that hence also , we conclude that converges to 0 as claimed.

Existence results are also available for other, more general classes of control problems (see Section 4.6 for further information). Although the proofs of such results are usually not constructive, the knowledge that a solution exists rules out the risks suggested by Perron's paradox and provides a basis for applying the maximum principle--which, as we have seen, often allows one to actually find an optimal control.

Next: 4.6 Notes and references Up: 4. The Maximum Principle Previous: 4.4.4 Fuller's problem   Contents   Index
Daniel 2010-12-20