A dynamic programming successive approximations technique with convergence proofs

This paper discusses a successive approximations technique based on dynamic programming. The basic idea of the method is to break up a problem containing several control variables into a number of subproblems containing only one control variable. Each subproblem has fewer state variables than the original problem; in the case where there are as many control variables as state variables, each subproblem has only one state variable. Because the computational requirements of dynamic programming increase exponentially with the number of state variables, this technique is capable of producing extremely large reductions in computational difficulty.The paper is divided into two parts. The first part describes the method in detail and works out an illustrative example. Other applications of the method, including the optimization of a multipurpose multi-reservoir water-resource system and an airline scheduling problem with 100 state variables, are discussed.The major drawback to the use of this method is the difficulty in ascertaining whether or not the true optimum solution is obtained. The second part of this paper presents proofs that the method converges to the true optimum solution for three important classes of problems, all of which are related to certain convex programming problems. Cet article discute d'une technique d'approximations successives basee sur la programmation dynamique. L'idee fondamentale de la methode consiste i? subdiviser un probleme contenant plusieurs variables de commande en un certain nombre de sous-problemes contenant une seule variable de commande. Chaque sous-probleme contient moins de variables d'etat que le probleme original; dans le cas ou il y a autant de variables de commande que de variables d'etat, chaque sous-probleme ne possede qu'une variable d'etat. Etant donne que les exigences de calcul de la programmation dynamique augmentent exponentiellement avec le nombre de variables d'etat, cette technique est susceptible de donner lieu i? de tres grandes reductions de la difficulte du calcul.L'article est divise en deux parties. La premiere partie decrit la methode en detail et elabore un exemple de son illustration. L'article discute d'autres applications de la methode comprenant l'optimalisation d'un systeme hydraulique i? buts et i? reservoirs multiples et un probleme de planification d'une ligne aerienne avec 100 variables d'etat. Behandelt wird eine Technik sukzessiver Approximationen, die auf der dynamischen Programmierung beruht. Die Grundidee der Methode liegt in der Zerlegung eines Problems mit einer Reihe von Variablen in eine Reihe von Subproblemen mit jeweils nur einer Regelvariablen. Jedes Subproblem besitzt weniger Zustandsvariablen als das Originalproblem. In dem Fall, wo die Zahl der Regelvariablen die gleiche ist wie die Zahl der Zustandsvariablen, besitzt jedes Subproblem nur eine Zustandsvariable. Weil der Rechenaufwand bei der dynamischen Programmierung exponentiell mit der Zahl der Zustandsvariablen anwachst, ist diese Technik in der Lage, die rechnerischen Schwierigkeiten in auiserordentlichem Maise zu reduzieren.Im vorliegenden ersten Teil der Arbeit wird die Methode im einzelnen beschrieben und durch ein Beispiel veranschaulicht. Andere Anwendungen der Methode, die die Optimierung eines aus vielen Speichern bestehenden und fur viele Zwecke dienenden Wasserzufluissystems bzw. die eines Flugverkehr-Fahrplans mit 100 Zustandsvariablen betrifft, werden diskutiert. C?a??? pacc?a?p??ae? ?e????y ?oc?e?o?a?e????? ?p?????e??? oc?o?a??y? ?a ???a???ec?o? ?po?pa???po?a???. Cy?? ?e?o?a coc?o?? ? pa??e?e??? ?po??e?? co?ep?a?e? ?ec?o???o ?oop???a? y?pa??e???. ?a??a? cy?-?po??e?a co?ep??? ?e???e ?oop???a? coc?o???? ?e? ?ep?o?a?a???a? ?po??e?a; ? c?y?ae ?o??a ??ee?c? c?o???o ?e ?oop???a? y?pa??e??? c?o???o ?oop???a? coc?o????, ?a??a? cy?-?po??e?a o??a?ae? ???? o??o? ?oop???a?o? coc?o????. Ta? ?a? ????c???e????e ?pe?o?a??? ???a???ec?o?o ?po?pa???po?a??? pac?y? ?o?a?a?e???o c ??c?o? ?oop???a? coc?o????, ??a ?e????a ?o?e? ?p??ec?? ? o?e?? ?o????? co?pa?e???? ????c???e???o? ?py??oc??.C?a??? pa??e?e?a ?a ??e ?ac??. ?sep?a? ?ac?? o??c??ae? ?e?o? ? ?e?a??? ? ??pa?a???ae? ?p??ep e?o ????c?pa???. C?a??? o?cy??ae? ?py??e ?p??e?e??? ?e?o?a ?????a???e o??????a??? ???pa????ec?o? c?c?e?? c ??o?o??c?e????? ?e???? ? pe?ep?yapa?? ? ?po??e?y ??a??po?a??? ca?o?e??o? ????? c 100 ?oop???a?a?? coc?o????.