M. Davidson

Primal-Dual Constraint Aggregation With Application to Stochastic Programming

Moscow State University, Faculty of Computational Math. and Cybernetics; the work was supported by postdoctoral stipendium of Graduiertenkolleg "Mathematische Optimierung", University of Trier, and the INTAS-97 project N 1050.


The special constraint structure and large dimension are characteristic for multistage stochastic optimization. This results from modelling future uncertainty via branching process or scenario tree. Most efficient algorithms for solving this type of problems use certain decomposition schemes, and often only a part of the whole set of scenarios is taken into account in order to make the problem tractable.
We propose a primal-dual method based on constraint aggregation, which constructs a sequence of iterates converging to a solution of the initial problem. At each iteration, however, only a reduced subproblem with smaller number of aggregate constraints has to be solved. Number of aggregates and their composition are determined by user, and the procedure for calculating aggregates can be parallelized. The method provides a posteriory estimates of the quality of the current solution approximation in terms of the objective function value and the residual.
Results of numerical tests for a portfolio allocation problem with quadratic utility function are presented.

Key words: Constraint aggregation, decomposition, multistage stochastic programming
AMS 1991 Subject Classification: 90C15, 90C06, 90C25