Optimization Online


A Hierarchy of Near-Optimal Policies for Multi-stage Adaptive Optimization

Dimitris Bertsimas (dbertsim***at***mit.edu)
Dan Iancu (daniancu***at***mit.edu)
Pablo Parrilo (parrilo***at***mit.edu)

Abstract: In this paper, we propose a new tractable framework for dealing with multi-stage decision problems affected by uncertainty, applicable to robust optimization and stochastic programming. We introduce a hierarchy of polynomial disturbance-feedback control policies, and show how these can be computed by solving a single semidefinite programming problem. The approach yields a hierarchy parameterized by a single variable (the degree of the polynomial policies), which controls the trade-off between the quality of the objective function value and the computational requirements. We evaluate our framework in the context of two classical inventory management applications, in which very strong numerical performance is exhibited, at relatively modest computational expense.

Keywords: robust adaptive optimization, semidefinite programming, sums-of-squares, inventory management

Category 1: Robust Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- OR and Management Sciences (Supply Chain Management )

Citation: submitted for journal publication

Download: [Postscript][PDF]

Entry Submitted: 06/26/2009
Entry Accepted: 06/26/2009
Entry Last Modified: 06/27/2009

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