This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Powell, W. Articles by Topaloglu, H. Search for Related Content

Learning Algorithms for Separable Approximations of Discrete Stochastic Optimization Problems

Warren Powell, Andrzej Ruszczyski, Huseyin Topaloglu

Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Department of Management Science and Information Systems, Rutgers University, 94 Rockefeller Road, Piscataway, New Jersey 08854
Department of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853
powell{at}princeton.edu
rusz{at}business.rutgers.edu
topaloglu{at}orie.cornell.edu

We propose the use of sequences of separable, piecewise linear approximations for solving nondifferentiable stochastic optimization problems. The approximations are constructed adaptively using a combination of stochastic subgradient information and possibly sample information on the objective function itself. We prove the convergence of several versions of such methods when the objective function is separable and has integer break points, and we illustrate their behavior on numerical examples. We then demonstrate the performance on nonseparable problems that arise in the context of two-stage stochastic programming problems, and demonstrate that these techniques provide near-optimal solutions with a very fast rate of convergence compared with other solution techniques.

Key Words: stochastic programming; dynamic programming
History: Received: August 5, 2002; revision received: November 6, 2003;revision received: November 28, 2003;

This article has been cited by other articles:

				W. T. Huh, G. Janakiraman, J. A. Muckstadt, and P. Rusmevichientong An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand Mathematics of Operations Research, May 1, 2009; 34(2): 397 - 416. [Abstract] [PDF]

				W. T. Huh and P. Rusmevichientong A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand Mathematics of Operations Research, February 1, 2009; 34(1): 103 - 123. [Abstract] [PDF]

				J. M. Nascimento and W. B. Powell An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem Mathematics of Operations Research, February 1, 2009; 34(1): 210 - 237. [Abstract] [PDF]

				S. Kunnumkal and H. Topaloglu Using Stochastic Approximation Methods to Compute Optimal Base-Stock Levels in Inventory Control Problems Operations Research, May 1, 2008; 56(3): 646 - 664. [Abstract] [PDF]

				S. Kunnumkal and H. Topaloglu Exploiting the Structural Properties of the Underlying Markov Decision Problem in the Q-Learning Algorithm INFORMS Journal on Computing, January 1, 2008; 20(2): 288 - 301. [Abstract] [PDF]

				R. Levi, R. O. Roundy, and D. B. Shmoys Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models Mathematics of Operations Research, November 1, 2007; 32(4): 821 - 839. [Abstract] [PDF]

				H. Topaloglu and W. Powell Incorporating Pricing Decisions into the Stochastic Dynamic Fleet Management Problem Transportation Science, August 1, 2007; 41(3): 281 - 301. [Abstract] [PDF]

				H. Topaloglu and W. B. Powell Dynamic-Programming Approximations for Stochastic Time-Staged Integer Multicommodity-Flow Problems INFORMS Journal on Computing, January 1, 2006; 18(1): 31 - 42. [Abstract] [PDF]