This project pursues a new solution approach for large multistage stochastic programs. The approach generalizes existing algorithms that have proved successful in nonlinear trajectory optimization.
The well-known primal and dual decomposition methods partition multistage problems into smaller optimization problems that correspond to the nodes or paths of the scenario tree. The resulting vertical or horizontal coupling conditions are then treated iteratively, with independent solution of the local problems in each iteration.
In contrast, the new recursive approach treats the optimization problem globally by primal-dual interior point methods (possibly as QP solver within SQP methods) and exploits the structure of the scenario tree on the linear algebra level by recursive solution of the linear-indefinite KKT systems. Thus inequality constraints and further nonlinearities are treated iteratively whereas the vertical and horizontal coupling of the nodes is always solved explicitly. Convergence is enhanced by a warm start technique that solves a coarse approximation to the problem first and then refines the scenario tree successively.
Several variants of the algorithm have been implemented as C++ class libraries. A problem-specific implementation is being applied for the solution of quadratic financial engineering problems in a Swiss insurance agency. A software tool for the automatic generation of custom implementations has also been developed.
