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