ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs
ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs
复制标题
DOI：
10.1287/opre.2021.2225
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Nan Jiang;Weijun Xie
中科院分区：
文献类型：
--
作者：
Nan Jiang;Weijun Xie
在机会约束规划（CCP）中，决策者寻求违反不确定性约束的概率在预先规定的风险水平内的最佳决策。由于CCP通常是非凸的，并且难以求解到最优性，因此人们致力于开发CCP的凸内逼近，其中条件风险值（CVaR）是十多年来公认的最佳内逼近。本文对Ahmed、Luedtke、SOng和Xie于2017年提出的求解CCP的ALSO-X进行了研究和推广。我们首先表明，aso - x类似于一个双层优化，其中上层问题是从下层问题中找到最佳目标函数值并强制CCP对给定决策的可行性，下层问题是根据上层问题提供的目标函数值的上界最小化约束违反的期望。这种解释促使我们证明，当不确定约束在决策变量中为凸时，so - x总是优于CVaR近似。我们进一步证明了(i) so - x可以恢复CCP的最优解的充分条件；（ii） CCP的等效双线性规划公式，启发我们用收敛交替最小化方法（ALSO-X+）增强ALSO-X；（iii）将ALSO-X和ALSO-X+扩展到∞−Wasserstein模糊集下的分布鲁棒机会约束规划（DRCCPs）。我们的数值研究证明了所提出方法的有效性。
In a chance constrained program (CCP), decision makers 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 in 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+); and (iii) an extension of ALSO-X and ALSO-X+ to distributionally robust chance constrained programs (DRCCPs) under the ∞−Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods.