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 backwards 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.