Information relaxations and duality in stochastic dynamic programs
Repository Usage Stats
We describe a general technique for determining upper bounds on maximal values (or lower bounds on minimal costs) in stochastic dynamic programs. In this approach, we relax the nonanticipativity constraints that require decisions to depend only on the information available at the time a decision is made and impose a "penalty" that punishes violations of nonanticipativity. In applications, the hope is that this relaxed version of the problem will be simpler to solve than the original dynamic program. The upper bounds provided by this dual approach complement lower bounds on values that may be found by simulating with heuristic policies. We describe the theory underlying this dual approach and establish weak duality, strong duality, and complementary slackness results that are analogous to the duality results of linear programming. We also study properties of good penalties. Finally, we demonstrate the use of this dual approach in an adaptive inventory control problem with an unknown and changing demand distribution and in valuing options with stochastic volatilities and interest rates. These are complex problems of significant practical interest that are quite difficult to solve to optimality. In these examples, our dual approach requires relatively little additional computation and leads to tight bounds on the optimal values. © 2010 INFORMS.
Published Version (Please cite this version)10.1287/opre.1090.0796
Publication InfoBrown, DB; Smith, JE; & Sun, P (2010). Information relaxations and duality in stochastic dynamic programs. Operations Research, 58(4 PART 1). pp. 785-801. 10.1287/opre.1090.0796. Retrieved from https://hdl.handle.net/10161/4435.
This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.
More InfoShow full item record
Professor of Business Administration
David B. Brown is a professor at the Fuqua School of Business at Duke University. He has been at Fuqua as a member of the Decision Sciences area since receiving his Ph.D. in Electrical Engineering and Computer Science from MIT in 2006. Professor Brown’s research focuses on the development of effective methods for dealing with uncertainty in large-scale decision-making problems. This includes systems in which information is revealed sequentially over time and ones in which error
J.B. Fuqua Professor of Business Administration in the Fuqua School of Business
James E. Smith is J.B. Fuqua Professor in the Decision Sciences area at the Fuqua School of Business, Duke University. Professor Smith's research interests lie primarily in the areas of decision analysis and focus on developing methods for studying dynamic decision problems and valuing risky investments. Smith was awarded the Frank P. Ramsey Medal for distinguished contributions to decision analysis in 2008. At Duke, he teaches probability and statistics and decision modeling. <
This author no longer has a Scholars@Duke profile, so the information shown here reflects their Duke status at the time this item was deposited.
J.B. Fuqua Distinguished Professor of Business Administration
Peng Sun is a Professor in the Decision Sciences area at the Fuqua School of Business, Duke University. He researches mathematical theories and models for resource allocation decisions under uncertainty, and incentive issues in dynamic environments. His work spans a range of applications areas, from operations management, economics, finance, marketing, to health care and sustainability. He serves an Associate Editor at Operations Research, and an Associate Editor at Management Science, two leadi
Alphabetical list of authors with Scholars@Duke profiles.