Information Relaxations and Duality in Stochastic Dynamic Programs

David B. Brown (), James E. Smith () and Peng Sun ()
Additional contact information
David B. Brown: Fuqua School of Business, Duke University, Durham, North Carolina 27708
James E. Smith: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Peng Sun: Fuqua School of Business, Duke University, Durham, North Carolina 27708

Operations Research, 2010, vol. 58, issue 4-part-1, 785-801

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.

Keywords: dynamic programming; duality; inventory control; option pricing (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (72)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0796 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:785-801

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().