Skip to main content

Information Relaxations and Duality in Stochastic Dynamic Programs

Publication ,  Journal Article
Brown, DB; Smith, JE; Sun, P
August 2010

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.

Duke Scholars

Publication Date

August 2010

Volume

58

Issue

4-part-1

Start / End Page

785 / 801
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Brown, D. B., Smith, J. E., & Sun, P. (2010). Information Relaxations and Duality in Stochastic Dynamic Programs, 58(4-part-1), 785–801.
Brown, David B., James E. Smith, and Peng Sun. “Information Relaxations and Duality in Stochastic Dynamic Programs” 58, no. 4-part-1 (August 2010): 785–801.
Brown DB, Smith JE, Sun P. Information Relaxations and Duality in Stochastic Dynamic Programs. 2010 Aug;58(4-part-1):785–801.
Brown, David B., et al. Information Relaxations and Duality in Stochastic Dynamic Programs. Vol. 58, no. 4-part-1, Aug. 2010, pp. 785–801.
Brown DB, Smith JE, Sun P. Information Relaxations and Duality in Stochastic Dynamic Programs. 2010 Aug;58(4-part-1):785–801.

Publication Date

August 2010

Volume

58

Issue

4-part-1

Start / End Page

785 / 801