Piecewise Constant Functions in Dynamic Optimization Problems

Abstract

We consider a direct method of dynamic optimization to approximate the global extremum. This method is based on splitting the state space into classes (cells) and constructing piecewise constant functions on the partition. Such an approach leads to a generalization of the Euler polygonal method and makes it possible to use shortest path algorithms on graphs. In the suggested algorithm, for each class we construct a path from an initial point to this class. Note that the program remembers only the terminal point of the path, functional value along the path and number of the preceding class. If one found another path with the same boundary conditions but less functional value (for the minimization problem), this path would become the current approximation. We prove that if the partition is sufficiently small, then, by using our method, we obtain the optimal polygon. The suggested approach can also be applied to problems of dynamic optimization with incomplete information (differential games, control of systems with unknown dynamics). In addition, some results of numerical solutions of optimal control problems and differential games are given.