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. 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^[1]^[2]^[3] 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.

Data-based optimization

A different set-up of application of the scenario approach is when the instances of constraints are obtained as observations. In this case, no model of uncertainty is needed, while the theory still provides guaranteeson the robustness of the solution because the theory is ditribution-free and does not require a knowledge of how the instances are generated.

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 constriants is not satisifed 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.^[4] Extensions to more complex, non-convex, set-ups are still objects of investigation.

Along the scenario approach, it is also possible to pursue a risk-return trade-off.^[5]^[6] Paper ^[7] provides a full-fledged method to apply this approach to control. 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.

Recently, a wait-and-judge theory has been developed which shows that an aposteriori assessment of the complexity of the solution (which can be easily measured) allows one to formulate precise evaluations of the risk.^[8] 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.^[9]

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.^[10]^[11]

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.

References

↑ G. Calafiore and M.C. Campi. Uncertain Convex Programs: Randomized Solutions and Confidence Levels. Mathematical Programming, 102: 25–46, 2005.
↑ G. Calafiore and M.C. Campi. "The scenario approach to robust control design," IEEE Transactions on Automatic Control, 51(5). 742-753, 2006.
↑ M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211–1230, 2008.
↑ M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211–1230, 2008.
↑ M.C. Campi and S. Garatti. A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality. Journal of Optimization Theory and Applications, 148, Number 2, 257–280, 2011 (preliminary version published in Optimization Online, 2008).
↑ G.C. Calafiore. Random Convex Programs. SIAM J. on Optimization, 20(6) 3427-3464, 2010.
↑ S. Garatti and M.C. Campi. Modulating Robustness in Control Design: Principles and Algorithms.. IEEE Control Systems Magazine, 33, 36–51, 2013.
↑ M.C. Campi and S. Garatti. Wait-and-judge scenario optimization.. Mathematical Programming, published online, 2016.
↑ G.C. Calafiore. Repetitive Scenario Design. IEEE Transactions on Automatic Control, Vol. 62, Issue 3, March 2017, pp. 1125-1137.
↑ B.K. Pagnoncelli, D. Reich and M.C. Campi. Risk-Return Trade-off with the Scenario Approach in Practice: A Case Study in Portfolio Selection. J. of Optimization Theory and Applications, 155: 707-722, 2012.
↑ G.C. Calafiore. Direct data-driven portfolio optimization with guaranteed shortfall probability. Automatica, 49(2) 370-380, 2013.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.