Submerged specific gravity

The scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on randomization of the constraints. 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 in the uncertain elements of the problem. The scenario method simply consists in extracting at random some instances of the uncertainty, and then finding the optimal solution of a problem where only the constraints associated to the extracted uncertainty instances are considered. The theory tells the user how “robust” this solution is, that is whether and to what extent the found solution satisfies the constraints occurring for other unseen instances of the uncertainty. Thus, this theory justifies at a solid theoretical level the use of randomization in robust and chance-constrained optimization.

When the constraints are convex (e.g. in semidefinite problems involving LMIs, Linear Matrix Inequalities), the theoretical results are tight. This means that the number $N$ of constraints that need be sampled as prescribed by the theory is provably the smallest possible number to achieve the desired robustness level. Extensions to more complex, non-convex, set-ups is still object of investigation.

Along the scenario approach, it is also possible to pursue a risk-return trade-off, see Figure 1. First $N$ constraints are sampled and then the user starts removing some of them 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 on-the-go the “curve of values”, i.e. the curve representing the value achieved after removing of an increasing number of constraints, while the scenario theory provides precise evaluations of how robust the various solutions are. The final outcome is a risk (robustness) vs. return (optimization value) graph as depicted in Figure 1, from which the user can choose his favorite risk-return compromise.

Example

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

Assuming we have at our disposal a stochastic model for the possible market conditions, we extract $N$ conditions ${\delta }_1,\dots ,{\delta }_N$ (randomization of uncertainty) and solve the scenario optimization program

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

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”.

After solving (1) we obtain an optimal investment strategy $x^{\ast }$ and the corresponding optimal return $R^{\ast }$. The $R^{\ast }$ value has been obtained by looking at $N$ market conditions only and therefore it is guaranteed for these market conditions. On the other hand, the scenario theory tells us that the solution is robust up to a level $ϵ$, that is return $R^{\ast }$ is guaranteed with probability $1-ϵ$ also for situations that have not been seen in our record of extractions.

Addendum: Why this example can be seen as an optimization program with uncertain constraints?

To better relate this investment problem to the previous discussion where optimization problems with uncertain constraints were considered, note that $(1)$ is equivalent to problem:

${\max }_{x,R}R$

subject to: $R_{{\delta }_i}(x)\ge R.$

Application fields

Prediction, systems theory, regression, control, financial mathematics, machine learning, decision making, supply chain, management.