论文标题
还有-X和-X+：偶然限制程序的更好凸近近似
ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs
论文作者
论文摘要
在偶然的限制计划（CCP）中，决策者旨在寻求最佳决定，其违反不确定性约束的可能性在预先指定的风险水平之内。由于CCP通常是非convex，并且难以解决最佳性，因此已经为CCP开发了凸内部近似值，其中已知有条件的价值（CVAR）在十多个以上是最好的。本文研究并概括了Ahmed，Luedtke，Song和Xie（2017）最初提出的有关CCP的X。我们首先表明，也表明X类似于二元优化，其中高级问题是找到最佳的客观函数值，并在下层问题中实现CCP对给定决策的可行性，而下层问题是最小化受上限问题的上限范围的约束违规行为的期望。这种解释促使我们证明，当决策变量中不确定的约束是凸时，也X始终优于CVAR近似。我们进一步显示了（i）足够的条件，其中-x也可以恢复到CCP的最佳解决方案； （ii）CCP的等效双线性编程公式，激发我们使用收敛交替的最小化方法（也是-x+）增强X； （iii）在$ \ infty $ -Wasserstein模棱两可的情况下，也可以解决分布稳健的机会约束程序（DRCCP）的扩展。我们的数值研究证明了所提出的方法的有效性。
In a chance constrained program (CCP), the decision-makers aim to seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional value-at-risk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSO-X, originally proposed by Ahmed, Luedtke, SOng, and Xie (2017), for solving a CCP. We first show that the ALSO-X resembles a bilevel optimization, where the upper-level problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lower-level problem, and the lower-level problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upper-level problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSO-X always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSO-X can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation of a CCP, inspiring us to enhance ALSO-X with a convergent alternating minimization method (ALSO-X+); (iii) extensions of ALSO-X and ALSO-X+ to solve distributionally robust chance constrained programs (DRCCPs) under $\infty$-Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods.
