Dynamic Programming

Dynamic programming is an approach to solving dynamic optimization problems, centred on properties of the value function, that is the minimum cost parameterized by the initial time and state. For the dynamic optimization problems considered in this book the value function is a solution to the Hamilton Jacobi equation (HJE). The central question is, how should we define ‘solution’ in such a manner that the HJE has a unique solution and that this solution coincides with the value function? Other matters of interest opened up by this approach include techniques for verifying the optimality of a putative minimizer, feedback representation of optimal strategies and computational methods, some of which are discussed in this chapter. The goal of representing the value function as the unique solution, appropriately defined, of the HJE has been arrived at along two different paths. The first involves viscosity solutions, as introduced by Crandall and Lions. With this solution concept it is possible to show directly, and without consideration of state trajectories, that the Hamilton Jacobi equation has a unique solution. The second path is system theoretic, in the sense that it is intimately connected with properties of state trajectories; invariance theorems are employed to show that a solution to the Hamilton Jacobi equation provides a lower bound to the cost of an arbitrary state trajectory and this lower bound is achieved by some state trajectory. This chapter is an up to date treatment of dynamic programming that places emphasis on the system theoretic point of view. We consider dynamic optimization problems for which the value function is a, possibly discontinuous, lower semi-continuous function. Various, equivalent, definitions of ‘solution’ of HJE are involved, prominent among which is that of proximal solution of Clarke. The chapter begins with a study of system invariance leading, on the one hand, to conditions under which there exists a state trajectory satisfying a given pathwise constraint and, on the other, to conditions under which all state trajectories have this property. The desired characterization of the value function as the unique proximal solution of the HJE results from applying the invariance theorems to an extended control system with pathwise constraint set constructed from an epigraph set, corresponding to the proximal solution of the HJE under consideration. This link between the value function and proximal solutions to HJE is established for various formulations of the dynamic optimization problem. Problems with finite time horizons, discounted-cost problems with an infinite horizon, minimum time problems and problems with pathwise state constraints all make their appearance. In the earlier literature a full characterization of the value function as the unique lower semi-continuous solution of HJE was achieved only for continuously time-dependent dynamics. A notable feature of theory presented in this chapter, the result of recent research, is that we allow discontinuous time dependence of the dynamics. Other topics are covered in this chapter. These include verification techniques of dynamic programming type and the role of semiconcavity in dynamic programming. A rounded exposition on the subject of dynamic programming necessarily embraces both viscosity solution and system theoretic methods. The final sections include discussion, comparing and contrasting the methods. Finally a simple proof of comparison theorem relating to an infinite horizon problem is given, to convey the flavour of viscosity techniques.