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

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.{{Cite journal |doi = 10.1137/130928546|title = Scenario Min-Max Optimization and the Risk of Empirical Costs|year = 2015|last1 = Carè|first1 = A.|last2 = Garatti|first2 = S.|last3 = Campi|first3 = M. C.|journal = SIAM Journal on Optimization|volume = 25|issue = 4|pages = 2061–2080|hdl = 11311/979283|hdl-access = free}} The scenario approach with $L\_1$ regularization has also been considered,{{Cite journal |doi = 10.1137/110856204|title = Random Convex Programs with L₁-Regularization: Sparsity and Generalization|year = 2013|last1 = Campi|first1 = M. C.|last2 = Carè|first2 = A.|journal = SIAM Journal on Control and Optimization|volume = 51|issue = 5|pages = 3532–3557}} and handy algorithms with reduced computational complexity are available.{{Cite journal |doi = 10.1287/opre.2014.1257|title = FAST—Fast Algorithm for the Scenario Technique|year = 2014|last1 = Carè|first1 = Algo|last2 = Garatti|first2 = Simone|last3 = Campi|first3 = Marco C.|journal = Operations Research|volume = 62|issue = 3|pages = 662–671| hdl=11311/937164 |hdl-access = free}} 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.{{Cite journal |doi = 10.1007/s10957-010-9754-6|title = A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality|year = 2011|last1 = Campi|first1 = M. C.|last2 = Garatti|first2 = S.|journal = Journal of Optimization Theory and Applications|volume = 148|issue = 2|pages = 257–280|s2cid = 7856112}}{{Cite journal |doi = 10.1137/090773490|title = Random Convex Programs|year = 2010|last1 = Calafiore|first1 = Giuseppe Carlo|journal = SIAM Journal on Optimization|volume = 20|issue = 6|pages = 3427–3464}} Moreover, a full-fledged method can be used to apply this approach to control.{{Cite journal | doi=10.1109/MCS.2012.2234964 | title=Modulating robustness in control design: Principles and algorithms| journal=IEEE Control Systems Magazine| volume=33| issue=2| pages=36–51| year=2013| s2cid=24072721}} 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:{{Cite journal |doi = 10.1007/s10107-016-1056-9|title = Wait-and-judge scenario optimization|year = 2018|last1 = Campi|first1 = M. C.|last2 = Garatti|first2 = S.|journal = Mathematical Programming|volume = 167|pages = 155–189|s2cid = 39523265|hdl = 11311/1002492|hdl-access = free}} 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.{{Cite journal | doi=10.1109/TAC.2016.2575859| title=Repetitive Scenario Design| year=2017| last1=Calafiore| first1=Giuseppe C.| journal=IEEE Transactions on Automatic Control| volume=62| issue=3| pages=1125–1137| arxiv=1602.03796| s2cid=47572451}}

Consider a function $R\_\backslash delta(x)$ which represents the return of an investment; it depends on our vector of investment choices $x$ and on the market state $\backslash 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 $\backslash delta\_1,\; \backslash dots,\; \backslash delta\_N$ (randomization of uncertainty). Alternatively, the scenarios $\backslash delta\_i$ can be obtained from a record of observations.

We set out to solve the scenario optimization program

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

This corresponds to choosing a portfolio vector x so as to obtain the best possible return in the worst-case scenario.{{Cite journal |doi = 10.1007/s10957-012-0074-x|title = Risk-Return Trade-off with the Scenario Approach in Practice: A Case Study in Portfolio Selection|year = 2012|last1 = Pagnoncelli|first1 = B. K.|last2 = Reich|first2 = D.|last3 = Campi|first3 = M. C.|journal = Journal of Optimization Theory and Applications|volume = 155|issue = 2|pages = 707–722|s2cid = 1509645}}{{Cite journal | doi=10.1016/j.automatica.2012.11.012 |title = Direct data-driven portfolio optimization with guaranteed shortfall probability|year = 2013|last1 = Calafiore|first1 = Giuseppe Carlo|journal = Automatica|volume = 49|issue = 2|pages = 370–380| s2cid=5762583 |url = http://porto.polito.it/2503507/}}

After solving (1), an optimal investment strategy $x^\backslash ast$ is achieved along with the corresponding optimal return $R^\backslash ast$. While $R^\backslash 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 $\backslash varepsilon$, that is, the return $R^\backslash ast$ will be achieved with probability $1\; -\; \backslash 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}}

Fields of application include: prediction, systems theory, regression analysis (Interval Predictor Models in particular), Actuarial science, optimal control, financial mathematics, machine learning, decision making, supply chain, and management.

Category:Stochastic optimization

Category:Optimal decisions

Category:Control theory

Category:Mathematical finance