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