Generalized dynamic programming. General points (Q1342606): Difference between revisions

Extending the ideas of discrete dynamic programming of R. Bellman (1957) the authors try to formalize a general iterative procedure aimed at diminishing the number of computations in a wide spectrum of multidimensional problems ranging from mathematical programming and optimal control to the computation of multidimensional integrals. The extensive applicability area of the procedure is generated by the use of arbitrary mappings, \(P\times {\mathcal F}\ni (p, f(\cdot))\mapsto\underset t{}{\text{con}} (p, f(t))\in W\), called ``convolution operators'' and by the introduction of concepts like: functions of intermediary results (FIR), generalized phase vectors (GPV), variable aggregation, partition and union of convolutions, etc. The method is illustrated by the problem of computing the number \[ J:= \sum_{x\in X} f_1(x_1)\cdots f_6(x_6),\;X:= \{(x_1,\dots, x_6); x_1+ 2x_2+\cdots+ 6x_6\leq 10,000, 0\leq x_i\leq 10,000\}, \] for the direct computation of which some \(2\cdot 10^{18}\) summations are needed, while using the authors' generalized dynamic programming approach only some \(8\cdot 10^7\) summations are sufficient.