Successive approximations of Bellman's function (Q1107099)

The convergence of an algorithm of successive approximation of the Bellman function B for a discrete-time control problem \[ J=\sum^{K}_{k=1}f^ 0(k,x(k),u(k))+F(x(K))\to \min,\quad x(k+1)=f(k,x(k),u(k)),\quad x(0)=x^ 0, \] u(k)\(\in U(k,x(k))\), is proved. The j-th step of the algorithm: knowing the j-th approximation \(B_ j\) of B calculate \(u_ j(k,x)=\arg \min \{f(k,x,u)+B_ j(k+1,f(k,x,u)):\) \(u\in U(k,x)\}\), \(B_{j+1}(k,x)=J\) for \(u(i)=u_ j(i,x(i))\), \(i\geq k\), \(x(k)=x.\) The algorithm was considered by \textit{V. V. Kondrat'ev, V. P. Savel'ev} and \textit{O. S. Shorokhov} [Avtom. Telemekh. 1980, No.6, 48-57 (1980; Zbl 0485.93051)] for a narrower class of problems. Results of simulation on a computer are discussed. In particular, it is pointed out that \(u_ 1(k)=u_ 1(k,x(k))\) practically coincides with the precise solution of the traveling salesman problem with \(K=10\) and \(x\in R^ n\), \(n=10\).