Risk and complexity in scenario optimization

• 成果类型: Article
• 署名作者: Garatti, S.; Campi, M. C.
• 署名单位: Polytechnic University of Milan; University of Brescia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01446-4
• 发表日期: 2022
• 页码: 243-279
• 关键词: distributionally robust optimization; safe tractable approximations; interval predictor models; random convex-programs; randomized solutions; solution quality; CHANCE; uncertainty; CLASSIFICATION; feasibility

摘要

Scenario optimization is a broad methodology to perform optimization based on empirical knowledge. One collects previous cases, called scenarios, for the set-up in which optimization is being performed, and makes a decision that is optimal for the cases that have been collected. For convex optimization, a solid theory has been developed that provides guarantees of performance, and constraint satisfaction, of the scenario solution. In this paper, we 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 (as precisely defined in the paper) of the solution. It is shown that the joint probability distribution of risk and complexity is concentrated in such a way that the complexity carries fundamental information to tightly judge the risk. This result is obtained without requiring extra knowledge on the underlying optimization problem than that carried by the scenarios; in particular, no extra knowledge on the distribution by which scenarios are generated is assumed, so that the result is broadly applicable. This deep-seated result unveils a fundamental and general structure of data-driven optimization and suggests practical approaches for risk assessment.