Scenario optimization

The scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on a sample of the constraints. It also relates to inductive reasoning in modeling and decision-making. The technique has existed for decades as a heuristic approach and has more recently been given a systematic theoretical foundation.

Description

In optimization, robustness features translate into constraints that are parameterized by the uncertain elements of the problem. In the scenario method, a solution is obtained by only looking at a random sample of constraints (heuristic approach) called scenarios and a deeply-grounded theory tells the user how “robust” the corresponding solution is related to other constraints. This theory justifies the use of randomization in robust and chance-constrained optimization.

Data-driven optimization

At times, scenarios are obtained as random extractions from a model. More often, however, scenarios are instances of the uncertain constraints that are obtained as observations (data-driven science). In this latter case, no model of uncertainty is needed to generate scenarios. Moreover, most remarkably, also in this case scenario optimization comes accompanied by a full-fledged theory because all scenario optimization results are distribution-free and can therefore be applied even when a model of uncertainty is not available.

Theoretical results

For constraints that are convex (e.g. in semidefinite problems involving LMIs, Linear Matrix Inequalities), a deep theoretical analysis has been established which shows that the probability that a new constraint is not satisfied follows a distribution that is dominated by a Beta distribution. This result is tight since it is exact for a whole class of convex problems.. More generally, various empirical levels have been shown to follow a Dirichlet distribution, whose marginals are beta distribution. The scenario approach with $L_i$ regularization has also been considered, and handy algorithms with reduced computational complexity are available. Extensions to more complex, non-convex, set-ups are still objects of active investigation.

Along the scenario approach, it is also possible to pursue a risk-return trade-off. Paper provides a full-fledged method to apply this approach to control. First $N$ constraints are sampled and then the user starts removing some of the constraints in succession. This can be done in different ways, even according to greedy algorithms. After elimination of one more constraint, the optimal solution is updated, and the corresponding optimal value is determined. As this procedure moves on, the user constructs an empirical “curve of values”, i.e. the curve representing the value achieved after the removing of an increasing number of constraints. The scenario theory provides precise evaluations of how robust the various solutions are.

A remarkable advance in the theory has been established by the recent wait-and-judge approach. One assesses the complexity of the solution (as precisely defined in the referenced article) and from its value formulates precise evaluations of the risk, or robustness of the solution. A related approach, named "Repetitive Scenario Design" aims at reducing the sample complexity of the solution by repeatedly alternating a scenario design phase (with reduced number of samples) with a randomized check of the feasibility of the ensuing solution.

Example

$R_{\delta }(x)$ represents the return of an investment; it depends on our vector of investment choices $x$ and on the market state $\delta$ which will be experienced at the end of the investment period.

Given a stochastic model for the possible market conditions, we consider $N$ of the possible states $\delta _{1},\dots ,\delta _{N}$ (randomization of uncertainty). Alternatively, the scenarios $\delta _{i}$ can be obtained from a record of past observations, in which case we can see them as being “sampled by nature”.

We solve the scenario optimization program

$\max _{x}\min _{i=1,\dots ,N}R_{\delta _{i}}(x).\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

That is, we choose a portfolio vector x so as to give the best possible return in the worst-case scenario of those considered.

After solving (1) we obtain an optimal investment strategy $x^{\ast }$ and the corresponding optimal return $R^{\ast }$ for the worst-case scenario of those considered. The $R^{\ast }$ value has been obtained by looking at $N$ possible market states only and therefore it is guaranteed to be achieved if one of these market states occurs. Further, scenario theory tells us that the solution is robust up to a level $\epsilon$: that is, the return $R^{\ast }$ will be achieved with probability $1-\epsilon$ unconditional on the market state.

Application fields

Fields of application include prediction, systems theory, regression analysis, optimal control, financial mathematics, machine learning, decision making, supply chain, and management.