Approximation in stochastic optimization

The goal of the project is to study approximations of multi-period stochastic optimization problems as they appear in Financial Management, Energy and Ressource Planning, Supply Chain Management and other areas of decision making under uncertainty. The objective of the work is (1) to study a new distance concept (nested distance) for multistage stochastic programs, find properties and methods of calculating it efficiently, (2) to find good bounds for the error is optimal values between the optimal values of the basic problem and it approximations, (3) to find bounds for the difference of the solution functions of the basic problem - using restriction and extension operators, (4) to use the derived results to develop good scenario generation methods, i.e. methods to find finite tree approximations with small approximation error. As a result, a computable quantitative error estimate and a new method for scenario generation will be developed and implemented.

Multi-stage stochastic optimization is the well-known tool for decision making under uncertainty, which applications include financial and investment planning, inventory control, energy production and trading, electricity generation planning, pension fund management, supply chain management and similar fields. However, theoretical solution of multi-stage stochastic programs can be found explicitly only in very exceptional (i.e. easiest) cases due to the complexity of the functional form of the problems. Therefore, the necessity of numerical solution arises. In this research we deal with approximation techniques that are challenging, important and very often irreplaceable numerical solution methods for multi-stage stochastic optimization programs. In multi-stage stochastic optimization problems the amount of stage-wise available information is crucial: though one cannot predict values of the stochastic process for the future, one needs to find as much available information as possible in order to make better decisions. While some authors deal with filtration distances, in this research we consider the concepts of nested distributions and their distances which allows to keep the setup purely distributional and at the same time to introduce information and information constraints. Also we introduce the distance between stochastic process and a tree and we generalize the concept of nested distance for the case of infinite trees, i.e. for the case of two stochastic processes given by their continuous distributions. We develop a new method for distribution quantization that is the most suitable for multi-stage stochastic optimization programs as it takes into account both the stochastic process and the stage-wise information. The main focus of the research includes following points: Scenario generation In order to generate future scenarios we need to know the probability distribution function of the random variable under consideration and to possess some method of sampling points from this distribution. While the probability distribution function can be estimated from the historical data sets, there are several methods for generation of points from the distribution function (for example, Monte Carlo sampling or optimal quantization), but none of them is created specifically for the multi-stage problems. On the stage-wise basis, the minimization of the well-known Kantorovich distance gives us a result for the optimal quantizers of the distributions at each stage. However, this result does not mean that the nested distance between initial and approximate problems is minimized. The research shows that the quantizers received by the minimization of the nested distance are better (in the sense of minimal distance) than the quantizers received by the stage-wise minimization of the Kantorovich distance and develops the new quantization algorithm (Backtracking Optimal Quantization) specifically for the multi-stage problems. Computational efficiency When dealing with numerical calculation of the nested distance the question of the computational efficiency is of interest. It is necessary to understand how many values should the scenario process have at each stage in order to make the computational time small and at the same time to make the approximation good (i.e. to make the approximation error small). A compromise for this should be found. Applications Stochastic programming offers a huge variety of applications. In the research we focus on the applications in the field of natural hazards risk-management. An essential part of stresses and risks in societies and their environments is imposed by catastrophic events. These stresses and risks can be reduced by the development of a strategy that promotes the adaptation, resilience and resistance of societies to catastrophes and contributes to a decrease of risk and vulnerability. That is why the research, devoted to finding the optimal strategies for risk management of catastrophic events, is motivated by different needs of people on international, national and local policy levels. The goal of this part of the research is to study the problem of catastrophe risk management from the multi-period and multi-hazard points of view by considering it as a multi-stage stochastic optimization program with random variables, describing the catastrophic event by their probability distributions, and to find optimal pre-event and post-event strategies.