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 ,

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

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.