Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty
Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty
复制标题
用于不确定性优化的采样凸规划的最坏情况违规
DOI：
10.1007/s10957-011-9923-2
复制
发表时间：
2012
影响因子：
1.9
通讯作者：
Takafumi Kanamori and Akiko Takeda
中科院分区：
文献类型：
--
作者：
Said Hanafi,橋本英樹,野々部宏司,Michel Vasquez;Yannick Vimont,柳浦睦憲;中邨良樹,大宮望,大場允晶,山本久志,丸山友希夫;Takafumi Kanamori and Akiko Takeda
最近提出了一种称为鲁棒优化的确定性方法来处理包括不精确数据的优化问题，即，不确定性鲁棒优化的基本思想是寻求一个解决方案，保证执行良好的可行性和近最优性方面的所有可能实现的不确定输入数据。为了解决鲁棒优化问题，Calafiore和Campi提出了一种基于约束采样的随机化方法，其中确定样本的数量，使得只有一小部分原始约束被随机化解决方案违反。我们主要关心的不仅是违反的概率，而且是违反的程度，即，最坏的违规行为。本文给出了抽样凸规划的最坏破坏概率的上界，并讨论了破坏概率与最坏破坏概率之间的关系。当随机样本数足够大时，违规概率和违规程度同时受一个给定值的限制。此外，当目标函数中包含不确定性时，得到了最优值的置信区间。我们的方法不仅适用于有界的不确定性集，也适用于无界的。因此，我们的方法的范围包括随机抽样以下的无界分布，如正态分布。
A deterministic approach called robust optimization has been recently proposed to deal with optimization problems including inexact data, i.e., uncertainty. The basic idea of robust optimization is to seek a solution that is guaranteed to perform well in terms of feasibility and near-optimality for all possible realizations of the uncertain input data. To solve robust optimization problems, Calafiore and Campi have proposed a randomized approach based on sampling of constraints, where the number of samples is determined so that only a small portion of the original constraints is violated by the randomized solution. Our main concern is not only the probability of violation, but also the degree of violation, i.e., the worst-case violation. We derive an upper bound of the worst-case violation for the sampled convex programs and consider the relation between the probability of violation and the worst-case violation. The probability of violation and the degree of violation are simultaneously bounded by a prescribed value when the number of random samples is large enough. In addition, a confidence interval of the optimal value is obtained when the objective function includes uncertainty. Our method is applicable to not only a bounded uncertainty set but also an unbounded one. Hence, the scope of our method includes random sampling following an unbounded distribution such as the normal distribution.