Optimization Online


Upper and Lower Bounds for Large Scale Multistage Stochastic Optimization Problems: Decomposition Methods

Pierre Carpentier(pierre.carpentier***at***ensta-paris.fr)
Jean-Philippe Chancelier(jpc***at***cermics.enpc.fr)
Michel De Lara(michel.delara***at***enpc.fr)
François Pacaud(francois.pacaud***at***pm.me)

Abstract: We consider a large scale multistage stochastic optimization problem involving multiple units. Each unit is a (small) control system. Static constraints couple units at each stage. To tackle such large scale problems, we propose two decomposition methods, whether handling the coupling constraints by prices or by resources. We introduce the sequence (one per stage) of global Bellman functions, depending on the collection of local states of all units. We show that every Bellman function is bounded above by a sum of local resource-decomposed value functions, and below by a sum of local price-decomposed value functions --- each local decomposed function having for arguments the corresponding local unit state variables. We provide conditions under which these local value functions can be computed by Dynamic Programming. These conditions are established assuming a centralized information structure, that is, when the information available for each unit consists of the collection of noises affecting all the units. We finally study the case where each unit only observes its own local noise (decentralized information structure).

Keywords: Stochastic Optimization - Dynamic Programming - Decomposition

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/21/2019
Entry Accepted: 12/23/2019
Entry Last Modified: 12/21/2019

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 Optimization Society