Duality and optimality in multistage stochastic programming

A model of multistage stochastic programming over a scenario tree is developed, in which the evolution of information states, as represented by the nodes of a scenario tree, is supplemented by a dynamical system of state vectors controlled by recourse decisions. A dual problem is obtained in which multipliers associated with the primal dynamics are price vectors that are propagated backward in time through a dual dynamical system involving conditional expectation. A format of Fenchel duality is employed in order to have immediate specialization not only to linear programming but also to extended linear-quadratic programming. The resulting optimality conditions support schemes of decomposition in which a separate optimization problem is solved at each node of the scenario tree.