A primal-dual decomposition-based interior point approach to two-stage
stochastic linear programming
Arjan Berkelaar, Cees Dert, Bart Oldenkamp, Shuzhong Zhang
Decision making under uncertainty is a challenge faced by many
decision makers. Stochastic programming is a major tool developed to
deal with optimization with uncertainties that has found applications
in, e.g. finance, such as asset-liability and bond-portfolio
management. Computationally however, many models in stochastic
programming remain unsolvable because of overwhelming
dimensionality. For a model to be well solvable, its special structure
must be explored. Most of the solution methods are based on
decomposing the data. In this paper we propose a new decomposition
approach for two-stage stochastic programming, based on a direct
application of the path-following method combined with the homogeneous
self-dual technique. Numerical experiments show that our decomposition
algorithm is very efficient for solving stochastic programs. In
particular, we apply our deompostition method to a two-period
portfolio selection problem using options on a stock index. In this
model the investor can invest in a money-market account, a stock
index, and European options on this index with different
maturities. We experiment our model with market prices of options on
the S&P500.
Econometric Institute Report EI-9918/A,
Erasmus University Rotterdam,
P.O. Box 1738,
3000 DR Rotterdam,
The Netherlands.
April, 1999.
Contact: [email protected]