论文标题
关于凸面方案的确切可行性，带有丢弃的约束
On the exact feasibility of convex scenario programs with discarded constraints
论文作者
论文摘要
我们重新审查了所谓的抽样和丢弃方法，用于量化某些原始样本被丢弃时违反解决方案的约束违反解决方案的可能性。由具有分析解决方案的两个方案程序的动机以及对场景程序的现有界限并不紧密的事实，我们分析了一个由一系列优化问题组成的删除方案，在每个步骤中，我们在每个步骤中删除了主动约束的超级集。通过依靠压缩学习理论的结果，我们表明，这种删除方案的限制可能比现有的范围少了。我们还表明，提出的界限是通过表征达到给定上限的一类优化问题而紧密的。涉及资源共享线性程序的示例说明了所提出方法的性能改进。
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 that achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.
