A Proximal Difference-of-Convex Algorithm for Sample Average Approximation of Chance Constrained Programming

Chance constrained programming (CCP) refers to a type of optimization problem with uncertain constraints that are satisfied with at least a prescribed probability level. In this work, we study the sample average approximation (SAA) method for chance constraints, which is an important approach to CCP in the data-driven setting where only a sample of multiple realizations of the random vector in the constraints is available. The SAA method approximates the underlying distribution with an empirical distribution over the available sample. Assuming that the functions in the chance constraints are all convex, we reformulate the SAA of chance constraints into a difference-of-convex (DC) form. Additionally, by assuming the objective function is also a DC function, we obtain a DC constrained DC program. To solve this reformulation, we propose a proximal DC algorithm and show that the subproblems of the algorithm are suitable for off-the-shelf solvers in some scenarios. Moreover, we not only prove the subsequential and sequential convergence of the proposed algorithm, but also derive the iteration complexity for finding an approximate Karush-Kuhn-Tucker point. To support and complement our theoretical development, we show via numerical experiments that our proposed approach is competitive with a host of existing approaches.

History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.

Funding: P. Wang and L. Balzano received financial support from the National Science Foundation [CAREER Award CCF-1845076], the Army Research Office Young Investigator Program [Award W911NF1910027], and the Department of Energy [Award DE-SC0022186]. R. Jiang received financial support from the Major Program of the National Natural Science Foundation of China [Grants 72394360, 72394364] and the Natural Science Foundation of Shanghai [Grant 22ZR1405100].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0648) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0648). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.