Accuracy and Comp. Efficiency in Multi-Stage Stoch. Opt.

Nowadays, governments and people, companies and technologies in our fast-developing and changing world face situations and problems, where they need to take decisions under uncertainty in multi-period environment. The multi-stage stochastic optimization is a well-known mathematical tool for the solution of multi-period decision-making problems under uncertainty. However, the explicit theoretical solution of a multi-stage optimization program may be impossible to obtain due to its functional form. Our goal is to study numerical methods for the solution of the problem by the use of approximation techniques, that are challenging, important and, very often, irreplaceable solution methods in multi-stage stochastic optimization. As soon as the decisions need to be taken in the multi-period environment with time-series data available only for the past, we work with stochastic processes, which possible future scenarios should be approximated. The focus is on the approximation methods of stochastic processes by scenario trees. Most of existing scenario approximation algorithms are forward procedures that start with the root of approximate tree and go up to its leaves, assigning values and probabilities to the nodes conditionally on the past (e.g. stage-wise optimal quantization, Monte-Carlo generation etc.). However, all these algorithms lose a part of crucial information by neglecting possible future scenarios at every node of the tree. Nevertheless, in order to minimize the approximation error it is not enough to generate scenarios based only on the past, but it is necessary to introduce information about possible future scenarios. We propose a study on backtracking scenario approximation that implements both information about the past and available information about future scenarios by the combination of the forward procedure with the backward step on the scenario tree. For the correct measurement of the approximation error, we base our research on the concept of tree (nested) distances, which can be extended to the case of continuous-state stochastic processes. The focus is on the backtracking optimal quantization algorithms, which minimize the nested distance between continuous-state stochastic process and tree. Our aim is to study theoretical and practical aspects of scenario approximation and to develop numerical algorithms for backtracking scenario quantization that combine high approximation quality (small approximation error) with computational efficiency (small computational time). Backtracking scenario approximation can be applied in a huge variety of areas (e.g. financial planning, energy production and trading, electricity generation planning, supply chain management etc.). Moreover, the multi-stage stochastic approximation is lying on the forefront of the search engine research, web-spam detection and signal processing. In the research we would like to focus on the applications in the field of probabilistic machine leaning for search engine spam detection, as well as in the field of natural hazards risk-management (with the focus on flood events in Austria and in Europe).

Nowadays, governments and people, companies and technologies in our fast-developing and changing world face situations and problems, where they need to take decisions under uncertainty in multi-period environment. The multi-stage stochastic optimization is a well- known mathematical tool for the solution of multi-period decision-making problems under uncertainty. However, the explicit theoretical solution of a multi-stage optimization program may be impossible to obtain due to its functional form. The project J3674-N26 Accuracy and Computational Efficiency in Multi-Stage Stochastic Optimization studies numerical methods for the solution of the problem by the use of approximation techniques, that are challenging, important and, very often, irreplaceable solution methods in multi-stage stochastic optimization. As soon as the decisions need to be made in the multi-period environment with time-series data available only for the past, the research is focused on stochastic processes, which possible future scenarios should be approximated. The focus is on the approximation methods of stochastic processes by scenario trees. Most of existing scenario approximation algorithms are forward procedures that start with the root of approximate tree and go up to its leaves, assigning values and probabilities to the nodes dependently on the past but independently of the possible future scenarios (e.g. optimal stage-wise quantization). Furthermore, very efficient algorithms are often independent of the past scenario information as well (e.g. random generation). Not surprisingly, all these algorithms lose a part of crucial information by neglecting possible future scenarios at every node of the tree. However, in order to minimize the approximation error and to improve the accuracy of an approximation it is not enough to generate scenarios based only on the past, but it is necessary to introduce information about possible future scenarios. In the project J3674-N26 Accuracy and Computational Efficiency in Multi-Stage Stochastic Optimization, we combine backtracking Dynamic Programming with optimal scenario approximation methods that allows us to implement both information about the past and available information about future scenarios by merging the forward quantization procedure with the backward solution step on the scenario tree. For the correct measurement of the approximation error, we base our research on the concept of tree (nested) distances, which can be extended to the case of continuous-state stochastic processes. The focus is on the optimal quantization algorithms, which bound the nested distance between continuous-state stochastic process and tree. Approximation methods in stochastic optimization can be applied in a huge variety of areas (e.g. financial planning, energy production and trading, electricity generation planning, supply chain management etc.). Moreover, the multi-stage optimization is lying on the forefront of the search engine research, web-spam detection and signal processing. In our research we focus on the applications in the field of robust search engine ranking, as well as in the field of natural hazards risk-management (with the focus on flood and drought events in Austria and in Europe).