A convex optimization-based method is proposed to numerically solve dynamic programs in continuous state and action spaces. This approach using a discretization of the state space has the following salient features. First, by introducing an auxiliary optimization variable that assigns the contribution of each grid point, it does not require an interpolation in solving an associated Bellman equation and constructing a control policy. Second, the proposed method approximates the optimal value function via convex programming with a uniform convergence property in the case of convex optimal value functions. We also propose a design method for a control policy of which performance converges uniformly to the optimum as the grid resolution becomes finer in this case. Third, when a nonlinear control-affine system is considered, the convex optimization approach provides an approximate control policy with a provable suboptimality bound. Fourth, for general cases, the proposed convex formulation of dynamic programming operators can be simply modified as a nonconvex bi-level program, in which the inner problem is a linear program, without losing uniform convergence properties if a globally optimal solution to this bi-level program can be found. From our convex methods and analyses, we observe that convexity in dynamic programming deserves attention as it can play a critical role in obtaining a tractable and convergent numerical solution.
The second category of discretization methods uses computational grids only for the state space, i.e., this class of methods does not discretize the action space. These approaches have a computational advantage over the methods in the first category, particularly when the action space dimension is large. The state space discretization procedures proposed by Hern ' a ndez-Lerma @cite_31 are shown to have a convergence guarantee with an error bound under Lipschitz continuity conditions on elements of control models. However, they are subject to the issue of local optimality in solving the nonconvex optimization problem over the action space involved in the Bellman equation. Johnson @cite_14 suggests spline interpolation methods, which are computationally efficient in high-dimensional state and action spaces. Unfortunately, these spline-based approaches do not have a convergence guarantee or an explicit suboptimality bound. Furthermore, the Bellman equation approximated by these methods involves nonconvex optimization problems. A careful review on a broader class of methods including approximate value or policy iteration, approximate linear programming and state aggregation can be found in a recent monograph @cite_3 .
@cite_31 @cite_14 @cite_3
2032419970 2078424060
Abstract This paper presents finite-state discretization procedures for discrete-time, infinite horizon, adaptive Markov control processes which depend on unknown parameters. The discretizations are combined with a consistent parameter estimation scheme to obtain uniform approximations to the optimal value function and asymptotically optimal adaptive control policies. The results include adaptive control systems with unknown disturbance distribution. This paper demonstrates that the computational effort required to develop numerical solutions to continuous-state dynamic programs can be reduced significantly when cubic piecewise polynomial functions, rather than tensor product linear interpolants, are used to approximate the value function. Tensor product cubic splines, represented in either piecewise polynomial or B-spline form, and multivariate Hermite polynomials are considered. Computational savings are possible because of the improved accuracy of higher-order functions and because the smoothness of higher-order functions allows efficient quasi-Newton methods to be used to compute optimal decisions. The use of the more efficient piecewise polynomial form of the spline was slightly superior to the use of Hermite polynomials for the test problem and easier to program. In comparison to linear interpolation, use of splines in piecewise polynomial form reduced the CPU time to obtain results of equivalent accuracy by a factor of 250–330 for a stochastic 4-dimensional water supply reservoir problem with a smooth objective function, and factors ranging from 25–400 for a sequence of 2-, 3-, 4-, and 5-dimensional problems. As a result, a problem that required two hours to solve with linear interpolation was solved in a less than a minute with spline interpolation with no loss of accuracy.