Information relaxations and duality in stochastic dynamic programs
Abstract
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.
Type
Journal articlePermalink
https://hdl.handle.net/10161/4435Published Version (Please cite this version)
10.1287/opre.1090.0796Publication Info
Brown, 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.
Collections
More Info
Show full item recordScholars@Duke
David B. Brown
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 is within the field of operations research and focuses
broadly on the design and analysis of solution methods for large-scale optimization
problems involving uncertainty. This work entails the use of techniques from opti
James E. Smith
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.
Peng Sun
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.

Articles written by Duke faculty are made available through the campus open access policy. For more information see: Duke Open Access Policy
Rights for Collection: Scholarly Articles
Works are deposited here by their authors, and represent their research and opinions, not that of Duke University. Some materials and descriptions may include offensive content. More info