Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Scenario optimization
Résumé
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.
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.
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. The scenario approach with regularization has also been considered, and handy algorithms with reduced computational complexity are available.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.