A dynamic programming successive approximations technique with convergence proofs

Abstract

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 basée sur la programmation dynamique. L'idée fondamentale de la méthode consiste à subdiviser un problème contenant plusieurs variables de commande en un certain nombre de sous-problèmes contenant une seule variable de commande. Chaque sous-problème contient moins de variables d'état que le problème original; dans le cas où il y a autant de variables de commande que de variables d'état, chaque sous-problème ne possède qu'une variable d'état. Étant donné que les exigences de calcul de la programmation dynamique augmentent exponentiellement avec le nombre de variables d'état, cette technique est susceptible de donner lieu à de très grandes reductions de la difficulté du calcul. L'article est divisé en deux parties. La première partie décrit la méthode en détail et élabore un exemple de son illustration. L'article discute d'autres applications de la méthode comprenant l'optimalisation d'un système hydraulique à buts et à reservoirs multiples et un problème de planification d'une ligne aérienne avec 100 variables d'état. 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 anwächst, ist diese Technik in der Lage, die rechnerischen Schwierigkeiten in außerordentlichem Maße 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 für viele Zwecke dienenden Wasserzuflußsystems 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ти. Пepв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лëтнoй линии c 100 кoopдинaтaми cocтoяния.