Complexity Is an Effective Observable to Tune Early Stopping in Scenario Optimization

• 成果类型: Article
• 署名作者: Garatti, Simone; Care, Algo; Campi, Marco Claudio
• 署名单位: Polytechnic University of Milan; University of Brescia
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3153888
• 发表日期: 2023
• 页码: 928-942
• 关键词: complexity theory; optimization; uncertainty; Random variables; decision making; Convex functions; testing; Optimization under uncertainties; randomized methods; scenario optimization

摘要

Scenario optimization is a broad scheme for data-driven decision-making in which experimental observations act as constraints on the feasible domain for the optimization variables. The probability with which the solution is not feasible for a new, out-of-sample, observation is called the risk. Recent studies have unveiled the profound link that exists between the risk and a properly defined notion of complexity of the scenario solution. In the present article, we leverage these results to introduce a new scheme where the size of the sample of scenarios is iteratively tuned to the current complexity of the solution so as to eventually hit a desired level of risk. This new scheme implies a substantial saving of data as compared to previous approaches. This article presents the new method, offers a full theoretical study, and illustrates it on a control problem.