Asymptotic expansions for dynamic programming recursions with general nonnegative matrices

This paper is concerned with the study of the asymptotic behavior of dynamic programming recursions of the form $$x(n + 1) = \mathop {\max }\limits_{P \in \mathcal{K}} Px(n), n = 0,1,2,...,$$ where ? denotes a set of matrices, generated by all possible interchanges of corresponding rows, taken from a fixed finite set of nonnegative square matrices. These recursions arise in a number of well-known and frequently studied problems, e.g. in the theory of controlled Markov chains, Leontief substitution systems, controlled branching processes, etc. Results concerning the asymptotic behavior ofx(n), forn→∞, are established in terms of the maximal spectral radius, the maximal index, and a set of generalized eigenvectors. A key role in the analysis is played by a geometric convergence result for value iteration in undiscounted multichain Markov decision processes. A new proof of this result is also presented.     

Asymptotic properties of penalized objective functions in regular mathematical programming problems

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 117–124, Moscow State University, 1989.     

Asymptotic properties of solutions of certain third-order dynamic equations

In this paper, the well known oscillation criteria due to Hille and Nehari for second-order linear differential equations will be generalized and extended to the third-order nonlinear dynamic equation

(r₂(t)((r₁(t)x^Δ(t))^Δ)^γ)^Δ+q(t)f(x(t))=0     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

Asymptotic properties of dynamic stochastic parameter estimates (III)

In this paper we establish three theorems concerning the asymptotic distributions of ordinary least-squares estimates of the parameters of a stochastic difference equation. We show that, if there is at least one root of the associated characteristic equation with modulus less than one and if all the roots have moduli different from one, the vector of least-squares estimates converges in distribution to a normally distributed vector. The distribution of the limiting vector is degenerate if there is at least one root with modulus greater than one. The results we obtain represent extensions of results proviously obtained by H. B. Mann and A. Wald, H. Rubin, J. S. White, T. W. Anderson, M. M. Rao, T. J. Muench, and the author.     

Cooperative dynamic programming

A many-decision-maker dynamic-control problem under uncertainty is presented as an extension of the standard control problem. It is assumed that only one payoff function exists, identical for all decision makers. The outstanding problem is to find a sequence of several decision rules that optimally coordinate activities both across time and between decision makers. This cooperative dynamic programming problem requires the researcher to consider how to solve large numbers of systems of integral equations.     

Multiobjective dynamic programming

In this paper the method of dynamic programming is carried to recurrence computations of sets of optimal values for discrete dynamic systems and vector-valued objective functions.     

Shape-preserving dynamic programming

Dynamic programming is the essential tool in dynamic economic analysis. Problems such as portfolio allocation for individuals and optimal growth of national economies are typical examples. Numerical methods typically approximate the value function and use value function iteration to compute the value function for the optimal policy. Polynomial approximations are natural choices for approximating value functions when we know that the true value function is smooth. However, numerical value function iteration with polynomial approximations is unstable because standard methods such as interpolation and least squares fitting do not preserve shape. We introduce shape-preserving approximation methods that stabilize value function iteration, and are generally faster than previous stable methods such as piecewise linear interpolation.     

Asymptotic properties of third-order half-linear neutral dynamic equations with mixed arguments

This work is concerned with the asymptotic behavior of a class of third-order half-linear neutral dynamic equations with mixed arguments on a time scale. Some new criteria and an example are presented.     

Intensional dynamic programming. A Rosetta stone for structured dynamic programming

We present intensional dynamic programming (IDP), a generic framework for structured dynamic programming over atomic, propositional and relational representations of states and actions. We first develop set-based dynamic programming and show its equivalence with classical dynamic programming. We then show how to describe state sets intensionally using any form of structured knowledge representation and obtain a generic algorithm that can optimally solve large, even infinite, MDPs without explicit state space enumeration. We derive two new Bellman backup operators and algorithms. In order to support the view of IDP as a Rosetta stone for structured dynamic programming, we review many existing techniques that employ either propositional or relational knowledge representation frameworks.     

Forward differential dynamic programming

The dynamic programming formulation of the forward principle of optimality in the solution of optimal control problems results in a partial differential equation with initial boundary condition whose solution is independent of terminal cost and terminal constraints. Based on this property, two computational algorithms are described. The first-order algorithm with minimum computer storage requirements uses only integration of a system of differential equations with specified initial conditions and numerical minimization in finite-dimensional space. The second-order algorithm is based on the differential dynamic programming approach. Either of the two algorithms may be used for problems with nondifferentiable terminal cost or terminal constraints, and the solution of problems with complicated terminal conditions (e.g., with free terminal time) is greatly simplified.     

On non-serial dynamic programming

New results in the theory of non-serial dynamic programming are described in this paper. Their computational relevance is also pointed out.     

A theorem in nonserial dynamic programming

This note presents a new theorem in nonserial dynamic programming. This theorem, which generalizes a previous one of the authors, allows, in the cases in which it can be employed, cutting down the computational effort for solving the secondary optimization problem.     

Sensitivity analysis in discrete dynamic programming

The problem of characterizing the minimum perturbations to parameters in future stages of a discrete dynamic program necessary to change the optimal first policy is considered. Lower bounds on these perturbations are derived and used to establish ranges for the reward functions over which the optimal first policy is robust. A numerical example is presented to illustrate factors affecting the tightness of these bounds.     

Splines and efficiency in dynamic programming

It is shown how one can use splines, represented in the B-spline basis, to reduce the difficulties of large storage requirements in dynamic programming via approximations to the minimum-return function without the inefficiency associated with using polynomials to the same end.