Optimization Online


An information-based approximation scheme for stochastic optimization problems in continuous time

Daniel Kuhn (dkuhn***at***doc.ic.ac.uk)

Abstract: Dynamic stochastic optimization problems with a large (possibly infinite) number of decision stages and high-dimensional state vector are inherently difficult to solve. In fact, scenario tree based algorithms are unsuitable for problems with many stages, while dynamic programming type techniques are unsuitable for problems with many state variables. This article proposes a stage aggregation scheme for stochastic optimization problems in continuous time, thus having an extremely large (i.e., uncountable) number of decision stages. By perturbing the underlying data and information processes, we construct two approximate problems that provide bounds on the optimal value of the original problem. Moreover, we prove that the gap between the bounds converges to zero as the stage-aggregation is refined. If massive aggregation of stages is possible without sacrificing too much accuracy, the aggregate approximate problems can be addressed by means of scenario tree based methods. The suggested approach applies to problems that exhibit randomness in the objective and the constraints, while the constraint functions are required to be additively separable in the decision variables and the random parameters.

Keywords: Stochastic optimization, stochastic control, bounds, time discretization, stage-aggregation

Category 1: Stochastic Programming

Category 2: Infinite Dimensional Optimization

Citation: Working paper, Department of Computing, Imperial College London, November 2007

Download: [PDF]

Entry Submitted: 03/19/2008
Entry Accepted: 03/19/2008
Entry Last Modified: 11/04/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society