HOME

TheInfoList



OR:

The scenario approach or scenario optimization approach is a technique for obtaining solutions to
robust optimization Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the ...
and chance-constrained optimization problems based on a sample of the constraints. It also relates to
inductive reasoning Inductive reasoning refers to a variety of method of reasoning, methods of reasoning in which the conclusion of an argument is supported not with deductive certainty, but with some degree of probability. Unlike Deductive reasoning, ''deductive'' ...
in modeling and decision-making. The technique has existed for decades as a
heuristic A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
approach and has more recently been given a systematic theoretical foundation. In
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, 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 A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
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 Randomization is a statistical process in which a random mechanism is employed to select a sample from a population or assign subjects to different groups.Oxford English Dictionary "randomization" The process is crucial in ensuring the random alloc ...
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 Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
(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 In probability theory and statistics, the beta distribution is a family of continuous probability distributions defined on the interval
, 1 The comma is a punctuation mark that appears in several variants in different languages. Some typefaces render it as a small line, slightly curved or straight, but inclined from the vertical; others give it the appearance of a miniature fille ...
or (0, 1) in terms of two positive Statistical parameter, parameters, denoted by ''alpha'' (''α'') an ...
. 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 In probability and statistics, the Dirichlet distribution (after Peter Gustav Lejeune Dirichlet), often denoted \operatorname(\boldsymbol\alpha), is a family of continuous multivariate probability distributions parameterized by a vector of pos ...
, whose marginals are beta distribution. The scenario approach with L_1 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. Moreover, a full-fledged method can be used 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 on the robustness of the solution. These results shed light on deeply-grounded links between the concepts of complexity and risk. 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

Consider a function R_\delta(x) which represents the return of an
investment Investment is traditionally defined as the "commitment of resources into something expected to gain value over time". If an investment involves money, then it can be defined as a "commitment of money to receive more money later". From a broade ...
; 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 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 observations. We set out to solve the scenario optimization program : \max_x \min_ R_(x). \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) This corresponds to choosing a portfolio vector ''x'' so as to obtain the best possible return in the worst-case scenario. After solving (1), an optimal investment strategy x^\ast is achieved along with the corresponding optimal return R^\ast. While R^\ast has been obtained by looking at N possible market states only, the scenario theory tells us that the solution is robust up to a level \varepsilon, that is, the return R^\ast will be achieved with probability 1 - \varepsilon for other market states. In quantitative finance, the worst-case approach can be overconservative. One alternative is to discard some odd situations to reduce pessimism; moreover, scenario optimization can be applied to other risk-measures including CVaR – Conditional Value at Risk – so adding to the flexibility of its use.{{Cite journal , doi=10.1016/j.ejor.2017.11.022, title=Expected shortfall: Heuristics and certificates, year=2018, last1=Ramponi, first1=Federico Alessandro, last2=Campi, first2=Marco C., journal=European Journal of Operational Research, volume=267, issue=3, pages=1003–1013, s2cid=3553018


Application fields

Fields of application include:
prediction A prediction (Latin ''præ-'', "before," and ''dictum'', "something said") or forecast is a statement about a future event or about future data. Predictions are often, but not always, based upon experience or knowledge of forecasters. There ...
,
systems theory Systems theory is the Transdisciplinarity, transdisciplinary study of systems, i.e. cohesive groups of interrelated, interdependent components that can be natural or artificial. Every system has causal boundaries, is influenced by its context, de ...
, regression analysis ( Interval Predictor Models in particular),
Actuarial science Actuarial science is the discipline that applies mathematics, mathematical and statistics, statistical methods to Risk assessment, assess risk in insurance, pension, finance, investment and other industries and professions. Actuary, Actuaries a ...
,
optimal control Optimal control theory is a branch of control theory that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and operations ...
,
financial mathematics Mathematical finance, also known as quantitative finance and financial mathematics, is a field of applied mathematics, concerned with mathematical modeling in the Finance#Quantitative_finance, financial field. In general, there exist two separate ...
,
machine learning Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
,
decision making In psychology, decision-making (also spelled decision making and decisionmaking) is regarded as the cognitive process resulting in the selection of a belief or a course of action among several possible alternative options. It could be either ra ...
,
supply chain A supply chain is a complex logistics system that consists of facilities that convert raw materials into finished products and distribute them to end consumers or end customers, while supply chain management deals with the flow of goods in distri ...
, and
management Management (or managing) is the administration of organizations, whether businesses, nonprofit organizations, or a Government agency, government bodies through business administration, Nonprofit studies, nonprofit management, or the political s ...
.


References

Stochastic optimization Optimal decisions Control theory Mathematical finance