In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure).

Dynamic Programming is also often used in Convex Optimization. Under the context of Dynamic Programming or in general, does Optimal Substructure implies convexity?

  • $\begingroup$ The question seems too broad. Would you mind to be more specific about the definition of "convexity"? Do you mean here optimization under "convex functions"? There are problems which do not exhibit "Optimal Substructure" (e.g., the Longest Path Problem), yet the costs might be given with a "convex function" thus, refuting your question, doesn't it? $\endgroup$ – Carlos Linares López Apr 25 '16 at 17:35
  • $\begingroup$ I was referring to that the cost or objective function. To be honest, I am so confused about DP. I am still trying to internalize DP tries to revisit all the previous paths and choose the best one, but with help of overlapping sub-problems to help out the calculations. So DP should give a global optimal solution. All the examples I see the cost function is "additive" form sub-problems, then choose the best one. That is why I was thinking if it has anything to imply convexity in the cost function. $\endgroup$ – ETOMG Apr 25 '16 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.