Risk and complexity in scenario optimization (Q2118077)

Scenario optimization is a broad methodology to perform optimization based on empirical knowledge. In this paper the authors open a new direction of investigation: the risk that a performance is not achieved, or that constraints are violated, is studied jointly with the complexity of the solution. The core achievement of this paper is showing that there exists a profound, and quite general, link between the two concepts: risk and complexity. Exploiting this link furnishes fundamental tools to evaluate the risk of scenario solutions, so complementing the heuristic use of data, in decision-making with a solid theory that enables one to certify the dependability of the decision. They show that the joint probability distribution of risk and complexity of scenario optimization problems is concentrated in such a way that the complexity carries fundamental information to tightly judge the risk.