A hierarchy of near-optimal policies for multi-stage adaptive optimization

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