Talk:Dynamic programming

Example

I (FvdP 21:51 Oct 22, 2002 (UTC)) had begun an example but do not feel the motivation to finish it cleanly right now (and perhaps not in the immediate future either). Here is it if anyone wants to complete it::

Suppose that we have to compute the product of n matrices A₁.A₂. ... .A_n, and we want to minimize the total number of operations by executing the matrix products in the best possible order.

The product of two matrices of size i × j and j × k

........

---

This example is published in Cormen's Introduction to Algorithms textbook. Will we run into copyright issues by putting it here?

Absolutely not! Ideas cannot be copyrighted, only a particular way of expressing those ideas. CLRS itself based this section on various papers. In other words, we can write an explanation of the problem and its solution in our own words, but should be careful not to copy text or even the precise presentation of the problem. Derrick Coetzee 20:09, 5 Oct 2004 (UTC)

Confusion

The first paragraph of the second part and the article on algorithms states that dynamic programming is a bottom-up approach, but later this article says dynamic programming may use bottom-up or top-down approaches. --zeno 11:46, 9 Feb 2004 (UTC)

I've revised that section. It was very vague and somewhat incorrect. I hope there's less confusion now. Derrick Coetzee 20:18, 5 Oct 2004 (UTC)

Discrete vs Continous, Deterministic vs. Stohastic

If I remember well from the courses I took long time ago dynamic programming comes in different flavors: discrete vs. continuous and stohastic vs. deterministic. Usually, in computer science we just reduce dynamic programming to the deterministic, discrete case.

An example of the continuous dynamic programming that I would like to see in Wikipedia is the solution of the problem of landing on the Moon where one has to minimize the amount of rocket fuel for lunar landing of a space ship. Tomo 12:38, 16 Apr 2005 (UTC)

It's been sometime since the proposal of adding emphasis or an example for continuous problems treated by dynamic programming, but I support this.Hardmath (talk) 14:34, 3 April 2016 (UTC)

Mild correction of pseudocode.

The article's pseudocode was inconsistent. At times, it used a Python-like indenting to represent the code structure. But it also included brackets at times. I have added brackets so that the pseudocode follows a C-like syntax: if the result of a loop, conditional, or whatnot is longer than one line, it is surrounded by brackets.

A more aggressive editor might prefer that no brackets be used. I don't know whether a bracket-less pseudocode would be clearer, but any consistent use of brackets would be clearer than what was there. (Would always using brackets be clearer -- for people who use a text-to-speech synthesizer, for example -- or would it just put in too much punctuation?) Chip Unicorn

In pseudocode I like to prefer indentation to braces where it's not unclear, to avoid eye-clutter, but I don't disagree with your changes - it's still sparse enough to be readable. Deco 01:10, 23 Jun 2005 (UTC)

I tried it without braces, and it looks visually clearer. If Wikipedia gets complaints that this is un-understandable by some group. we can put in some way to distinguish the levels. Chip Unicorn 12:41, 23 Jun 2005 (UTC)

Weirdness

The page says "i dont know" in those terms, which is not only weirdly misplaced, but also improperly formatted. Someone check.

Smith-Waterman Algorithm

I don't see any mention of the Smith-Waterman algorithm, which is a dynamic programming algorithm just like the Needleman-Wunsch. Would it be appropriate to add that one as well? --scskowron 13:57 , 13 December 2006 (UTC)

Misplaced section

The part following "The steps for using dynamic program goes as follows:" is out of place. Out of nowhere the article starts using terms like 'gap penalties' and 'sequence alignment.' Seems like this was copied from some article on a specific application, such as protien sequencing. Anon, Wed Jul 11 14:11:43 EDT 2007

too many examples

This is not a textbook. One good example would suffice. Even worse, many of them are just too long (and boring). Put them in wikibooks. Unfortunately, any attempt to fix this article would be blocked as "vandalism". Way to go, Wikipedia!

Assessment comment

The comment(s) below were originally left at Talk:Dynamic programming/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

The current Wikipedia page on the subject of Dynamic Programming ignores the fact that it has been used a long time before Richard Bellman 'invented' it, by Pierre Masse, Head of Electricite de France' as early as 1944,and has also been applied by JDC Little for optinization of the Grand Coulee Dam's operation, also before Bellman first published papers about Dynamic Programming.

Last edited at 13:34, 15 July 2008 (UTC). Substituted at 13:57, 29 April 2016 (UTC)

Dr. Bambi's comment on this article

Dr. Bambi has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

As it stands, the article is more on Dynamic Programming Algorithm than on Dynamic Programming.

The introduction to the article is really biased in this sense and, therefore, misleading.

Broadly speaking, dynamic programming is an analytical method to solve multi-stage problems. This method can be used in 1) continuous time or discrete time models; (e.g. Fleming and Rishel [1]) 2) deterministic or stochastic models (e.g. Fleming and Rishel [1], and Yong and Zhou [3]); 3) finite or infinite dimensional models (e.g. Li and Yong [6], and Fabbri and Gozzi [2]). To be noticed that applications in economics, biology, demography etc. exist for all the combinations of these groups of models.

The introduction and, really, the whole article focus on discrete time deterministic models. In addition, the emphasis is on how to implement such a method using a computer even though that is not necessarily important to understand the method itself.

Overall the article gives a very partial view of what dynamic programming really means.

In my opinion, the introduction is also quite obscure and too much rich of details for a reader who has never heard of this method before.

In the article, there is no reference to the theory on dynamic programming. For example a clear explanation of the Bellman Principle and the Bellman Equation is missing. In fact, some of these concepts pop up during the applications but are not previously discussed or clarified to the reader.

There is also a MISTAKE at the very beginning of the Introduction, i.e. "dynamic programming (also known as dynamic optimization)" is clearly incorrect. Dynamic optimization is an area of mathematics which includes several methods of optimization and dynamic programming is one of these.

Regarding this last point, it could be nice to see the advantages or drawbacks in using the dynamic programming approach instead of, for example, the maximum principle which is another method to solve optimal control problem in continuous time models. A discussion about this issue could be found, for example, in the introduction of Bambi et al. [4].

Therefore the article could be drastically improved by: 1) Rewriting completely the introduction without the emphasis on the algorithm and the computational details. 2) Explain carefully that dynamic programming can be applied not only to solve discrete time, finite dimensional deterministic models but also to solve models where time can be continuous (reference), and which could be stochastic and infinite dimensional. 3) Introduce and explain the main theoretical concepts and results of the dynamic programming approach.

TO UPDATE: The example: Economic Optimization, should be updated. After the last paragraph, starting with “We see that it is optimal…” the following sentence should be added. “The same problem has been investigated by Bambi et al. [4] and [5] in continuous time and under the assumption that capital takes time to become productive. With this two features a dynamic programming approach for solving infinite dimensional continuous time and deterministic model is used.”

REFERENCES: 1) Fleming, W. H. and Rishel, R. W. (1975). Deterministic and stochastic optimal control. Springer. 2) Fabbri, G. and Gozzi, F. (2016). Stochastic optimal control in infinite dimensions: dynamic programming and HJB equations. Springer (forthcoming). 3) Yong, J. and Zhou, X.Y. (1999). Stochastic Controls. Springer. 4) Bambi, M., Fabbri, G. and Gozzi, F. (2012). “Optimal policy and consumption smoothing effects in the time-to-build AK model”. Economic Theory, 50(3), 635-669. 5) Bambi, M., Di Girolami, C., Federico, S. and Gozzi, F. (2016). “On the consequences of generically distributed investments on flexible projects in an endogenous growth model”. Economic Theory (forthcoming).

6) Li, X. and Yong, J. (1995). Optimal control theory for infinite dimensional systems. Springer.

We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.

Dr. Bambi has published scholarly research which seems to be relevant to this Wikipedia article:

• Reference : Mauro Bambi & Cristina Di Girolami & Salvatore Federico & Fausto Gozzi, 2014. "On the Consequences of Generically Distributed Investments on Flexible Projects in an Endogenous Growth Model," Discussion Papers 14/15, Department of Economics, University of York.

ExpertIdeasBot (talk) 18:17, 27 June 2016 (UTC)

Broadly speaking, the assertion "dynamic programming is an analytical method to solve multi-stage problems" is false. Rather, this is only one of the senses in which dynamic programming is now used, and very far from the sense that it is widely used in computer science. —David Eppstein (talk) 00:53, 28 June 2016 (UTC)

Dr. Fabbri's comment on this article

Dr. Fabbri has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

I would like first of all the clarify that I give some comments on this Wikipedia article only because I have been invited in doing so and I feel a little embarassed in criticising the work of other people that spent generously their time for the community.

My overall impression is that the article is well done but it only concerns a part of the story (and, to tell the truth, the part on which I am less expert).

The dynamic programming (expression that is not equivalent to "dynamic optimization" as stated in the second line) can aso be applyed to continuous time optimisation problems both in a deterministic and in a stochastic framework, both in finite and infinite dimensions.

The use of dynamic programming for continous time optimization problem is strictly related to the study of the Hamitlon-Jacobi-Bellman (HJB) equation associated to the problem. If the problem is deterministic (resp. stochastic) the HJB equation is of the frst (resp. second) order. Under suitable hypotheses the value function of the optimization problem can be identified with the solution of the HJB equation. A particolarly suited notation of solution for HJB equations appear to be that of viscosity solution.

I mention some books on the subjet:

Deterministic problems, finite dimension:

- M. Bardi and I. Capuzzo-Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Systems and Control: Foundations and Appli- cations, Birkhäuser, Boston, 1997.

- W. H. Fleming and R. W. Rishel, Deterministic and stochastic optimal control, Ap- plications of Mathematics, vol. 1, Springer, Berlin, 1975. (also stochastic)

Stochastic problems, finite dimension:

- J. Yong and X. Y. Zhou, Stochastic controls, Hamiltonian systems and HJB equa- tions, Applications of Mathematics, vol. 43, Springer, New York, 1999.

Deterministic problems, infinite dimensions:

- X. J. Li and J. M. Yong, Optimal control theory for infinite-dimensional systems, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 1995.

Stochastic problems, infinite dimensions

Stochastic Optimal Control in Infinite Dimensions: Dynamic Programming and HJB Equations (to appear).

This said, again, I wuold not like to give marks to anybody. I love Wikipedia and I only need to thank the people that work for it.

Kind regards

We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.

We believe Dr. Fabbri has expertise on the topic of this article, since he has published relevant scholarly research:

• Reference : Bambi, Mauro & Fabbri, Giorgio & Gozzi, Fausto, 2009. "Optimal policy and consumption smoothing effects in the time-to-build AK model," MPRA Paper 17128, University Library of Munich, Germany.

ExpertIdeasBot (talk) 16:07, 11 July 2016 (UTC)

Factual accuracy tag

This article has beed tagged for factual accuracy, yet there is no discussion in the talk page. I've introduced this section to allow for such conversation.--Work permit (talk) 19:06, 5 November 2016 (UTC)

Lead rewrite needed

Having read some of the above comments, and clicked on a few things, it strikes me that the material at Bellman equation is far more appropriate for the lead than what we presently have. The present lead almost seems to suggest that dynamic programming is a specialized form of divide and conquer, but I personally regard its core motivation as something quite different.

The present leads dives into memoization rather briskly, which I regard as primarily an accounting trick. Neither the word "discrete" nor the word "continuous" is presently found in the lead. Yuck.

If someone wishes to rewrite the lead from scratch, beginning with a short statement of what characterized the problem class as motivated from the Bellman page, then provides a paragraph about discrete/continuous, deterministic/stochastic, finite/infinite domain distinctions, and only then dives into the accounting trick of memoization and other algorithmically motivated material, consider this my earnest vote to fill your boots. — MaxEnt 20:46, 12 November 2016 (UTC)

The material from Bellman equation is suitable only for the economic/engineering version of dynamic programming. It does not even approximate the way dynamic programming is taught in computer science. —David Eppstein (talk) 21:22, 12 November 2016 (UTC)

As an academic with a foot in Computater Science and another in Management Science/Operations Research I tend to agree with MaxEnt about the fact that the original motivation of dynamic programming has little to do with divide and conquer, memoization, or dynamic programming algorithms taught in computer science. Probably there should be different pages: dynamic programming (computer science) and dynamic programming (management science). The term programming in dynamic programming is clearly linked to the origins of other programming techniques such as linear programming and stochastic programming. As Dijkstra explains in Reminiscences about the origins of linear programming the term programming is related to mathematical formulations (linear or otherwise) of military programs, i.e. plans for allocating resources, scheduling operations, etc. In his seminar work (Bellman 1957) Bellman is also mainly concerned with multi-stage (deterministic or stochastic) decision problems and their applications in "economics, physics, biology, or otherwise" (page 7); for instance, the book at page 3 begins with a motivating example involving a multi-stage resource allocation process. Most importantly, Bellman explicitly states at page 7, that [...] we must realise that the essential purpose in formulating many of these mathematical models [...], is not so much to calculate numbers [...] but rather to determine the structure of the solution and also at page ix The problem is not to be considered solved in a mathematical sense until the structure of the optimal policy is understood. With this statement, Bellman clearly positions his research in the same club as the one carried out in the previous decade by Dijkstra, Arrow and von Neumann. The structural properties Bellman is interested are mostly analytical characterisations of the optimal policy for a given system (e.g. Scarf 1960, "The optimality of (S,s) policies in the dynamic inventory problem"), rather than efficient numerical procedures. In Chapter I, Section 4, page 7-9, Bellman illustrates the essence of a backward recursion algorithm, he then goes on and states that "a digital computer may be programmed to print out the sequence of values" (i.e. the value function and the policy function). Bellman is aware of the computational advantages, and he mentions them, but he seems to be also clearly aware of the curse of dimensionality. He believes numerical approaches should be used only to gain insights. His chief concern is ultimately to determine analytically the structure of the optimal policy for a given class of problems, so that closed form solutions can be obtained, or dedicated algorithms - not necessarily dynamic programming ones - can be developed. --Dr.roberto.rossi (talk) 23:55, 27 March 2017 (UTC)