On the Exact Feasibility of Convex Scenario Programs With Discarded Constraints

• 成果类型: Article
• 署名作者: Romao, Licio; Papachristodoulou, Antonis; Margellos, Kostas
• 署名单位: University of Oxford
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3165320
• 发表日期: 2023
• 页码: 1986-2001
• 关键词: Optimization; uncertainty; Random variables; Picture archiving and communication systems; COSTS; linear programming; Algebra; Chance-constrained optimization; probabilistic methods; randomized algorithms; scenario approach

摘要

We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where, at each step, we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems which achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.