Title: 

ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs

Abstract: 

Chance constrained programs (CCPs) are generic frameworks for decision-making under uncertain constraints. The objective of a CCP is to find the best decision that violates the uncertainty constraints within the prespecified risk level. A CCP is often nonconvex and is difficult to solve to optimality. 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 state-of-art conditional-value-ta-risk (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 Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods.

Bio:

Dr. Weijun Xie is an Assistant Professor of Industrial and Systems Engineering, Virginia Tech. He obtained his Ph.D. from Georgia Tech in 2017. His research interests lie in theory and applications of stochastic, discrete, and convex optimization. Dr. Xie has won multiple awards including NSF Career Award, INFORMS Optimization Prize for Young Researchers, INFORMS Junior Faculty Interest Group Paper Competition (Third Place), INFORMS George Nicholson Student Paper Competition (Honorable Mention). He currently serves as the Vice Chair of Optimization under Uncertainty at INFORMS Optimization Society and is an associate editor of the Journal of Global Optimization.