Guaranteed bounds for optimal stopping problems using kernel-based non-asymptotic uniform confidence bands

In this paper, we introduce an approach for obtaining probabilistically guaranteed upper and lower bounds on the true optimal value of stopping problems. Bounds of existing simulation-and-regression approaches, such as those based on least squares Monte Carlo and information relaxation, are stochastic in nature and therefore do not come with a finite sample guarantee. Our … Read more

Multi-stage robust optimization problems: A sampled scenario tree based approach

In this paper, we consider multi-stage robust convex optimization problems of the minimax type. We assume that the total uncertainty set is the cartesian product of stagewise compact uncertainty sets and approximate the given problem by a sampled subproblem. Instead of looking for the worst case among the infinite and typically uncountable set of uncertain … Read more

Distributionally robust optimization with multiple time scales: valuation of a thermal power plant

The valuation of a real option is preferably done with the inclusion of uncertainties in the model, since the value depends on future costs and revenues, which are not perfectly known today. The usual value of the option is defined as the maximal expected (discounted) profit one may achieve under optimal management of the operation. … Read more

Multiscale stochastic programming

Real-world multistage stochastic optimization problems are often characterized by the fact that the decision maker may take actions only at specific points in time, even if relevant data can be observed much more frequently. In such a case there are not only multiple decision stages present but also several observation periods between consecutive decisions where … Read more

Stochastic Dynamic Programming Using Optimal Quantizers

Multi-stage stochastic optimization is a well-known quantitative tool for decision-making under uncertainty, which applications include financial and investment planning, inventory control, energy production and trading, electricity generation planning, supply chain management and similar fields. Theoretical solution of multi-stage stochastic programs can be found explicitly only in very exceptional cases due to the complexity of the … Read more

Guaranteed Bounds for General Non-discrete Multistage Risk-Averse Stochastic Optimization Programs

In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such ”infinite” problems are practically impossible to solve as they are formulated and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e. finite … Read more

BOUNDS AND APPROXIMATIONS FOR MULTISTAGE STOCHASTIC PROGRAMS

Consider (typically large) multistage stochastic programs, which are defined on scenario trees as the basic data structure. It is well known that the computational complexity of the solution depends on the size of the tree, which itself increases typically exponentially fast with its height, i.e. the number of decision stages. For this reason approximations which … Read more

Dynamic Generation of Scenario Trees

We present new algorithms for the dynamic generation of scenario trees for multistage stochastic optimization. The different methods described are based on random vectors, which are drawn from conditional distributions given the past and on sample trajectories. The structure of the tree is not determined beforehand, but dynamically adapted to meet a distance criterion, which … Read more

Time Consistency Decisions and Temporal Decomposition of Coherent Risk Functionals

It is well known that most risk measures (risk functionals) are time inconsistent in the following sense: It may happen that today some loss distribution appears to be less risky than another, but looking at the conditional distribution at a later time, the opposite relation holds. In this article we demonstrate that this time inconsistency … Read more

Time-inconsistent multistage stochastic programs: martingale bounds

Abstract. It is well known that multistage programs, which maximize expectation or expected utility, allow a dynamic programming formulation, and that other objectives destroy the dynamic programming character of the problem. This paper considers a risk measure at the final stage of a multistage stochastic program. Although these problems are not time consistent, it is … Read more