Talk:Dynamic programming/Archive 1

Archive 1

Archive 2

Archive 3

Memoization vs. Dynamic Programming

These are two different approaches, not a tool and a class of problems. This page is perpetuating serious misconceptions. --67.188.230.235 (talk) 19:08, 24 November 2015 (UTC)

I'm not really sure what you mean. In the lede, at least, DP is presented as "a method for solving a complex problem by ...", while memoization is presented as a "technique". (I do agree that memoization, which has its own article, gets a lot of coverage in this one.) QVVERTYVS (hm?) 10:51, 14 February 2016 (UTC)

Memoization can't do the egg dropping puzzle??

This page makes a very bold statement: that there are dynamic programming problems which memoization cannot be used to solve. I supposed there might exist examples of this (though I can't think of any), but the page goes on to claim that the egg dropping puzzle is one of them. The recurrent function is:

W(n,k) = 1 + min{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k }

with base cases at k=1 and n=1. This is straightforwardly (if inefficiently) implemented using a recursive function:

   function W(n,k):
       if n = 1 return 1
       else if k = 1 return k
       else 
           mn = inf
           for x from 1 to k:
               mn = min(mn, max(W(n - 1, x - 1), W(n, k-x)))
           return mn + 1

Thus it's also trivially memoized. What's the issue? What am I missing? — Preceding unsigned comment added by 129.174.124.66 (talk) 16:43, 12 January 2015 (UTC)

The issue is that you did not read the paragraph carefully. It was talking about optimal solutions, specifically algorithms with optimal time complexity (space complexity is usually a secondary concern). Your memoized recursive algorithm is indeed the naive one referred to by the paragraph, which works but does not has optimal time complexity. The section on the egg dropping problem itself gives your solution (though in words rather than pseudo-code) and notes that it takes O(n*k^2) time with a DP solution (which is exactly what yours would take if you use memoization). It even goes on to state how it can be directly improved a little, before giving a faster (but I don't know whether it is optimal) algorithm that uses a totally different parametrization. Lim Wei Quan (talk) 12:50, 9 July 2015 (UTC)

This is misunderstanding perpetuated, unfortunately, by the way CLRS talks about DP. DP is an algorithm design paradigm, not a cure-all. There is no guarantee that the time required by a DP solution be polynomial--indeed, the DP solution to the TSP of Held and Karp (SIAM J., vol. 10 (1962), pp. 196-210) is still the best general TSP algorithm; it is, of course, exponential. I wish CLRS were clearer on this point: it gives the impression that the DP solution, if done right, leads to algorithms in P. I do not understand Lim Wei Quan's reference to "optimal solutions"; how does one know, for example, that the O(n^3) DP solution to matrix chain product is optimal?! I have never seen a proof of that (but would like to). — Preceding unsigned comment added by 73.44.176.246 (talk) 16:02, 18 February 2016 (UTC)

The point I hope was clearly conveyed by the article is that any recursive algorithm is trivially memoized. (In fact some programming languages do that automatically!) As for my statement about optimal solutions, notice that nowhere in the article or on the comments page did I say that any of the presented algorithms are optimal. In my above comment I even expressly state that I do not know whether my solution for the egg-drop puzzle is optimal. But we do know that the naive DP algorithms are often not optimal, and that is the point. In some rare cases we can of course prove optimality, such as if we are required to print out all fibonacci numbers, in which case it is clear that the memoized recursive algorithm takes space and time linear in the output, which is best possible. In many other cases no optimality results are known. Another simple example is finding an element in an n-item sorted list, which requires O(log(n)) key-comparisons, and so binary search is optimal, which is not a memoized recursive algorithm in any reasonably natural way. That is the point of the sentence "Others can be more complicated and cannot be implemented as a recursive function with memoization.". Arguably this sentence is technically false since every algorithm can be written as a recursive function that does not really do any recursion, but it is an attempt to stop students' common misconceptions before they begin, one of which is that DP can solve a lot of problems. No it does not, just as we cannot quite say that recursion solves a lot of problems. They are both just generic techniques and usually need to be used in conjunction with some crucial insights specific to the problem to be solved. I hope that it is all clear now! =) Lim Wei Quan (talk) 10:58, 9 March 2016 (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)

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)