An Augmented Lagrangian Decomposition Method for Chance-Constrained Optimization Problems

Xiaodi Bai (), Jie Sun () and Xiaojin Zheng ()
Additional contact information
Xiaodi Bai: School of Management, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, P.R. China
Jie Sun: School of Business, National University of Singapore, Singapore 119245
Xiaojin Zheng: School of Economics and Management, Tongji University, Shanghai 200092, P.R. China

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1056-1069

Abstract: Joint chance-constrained optimization problems under discrete distributions arise frequently in financial management and business operations. These problems can be reformulated as mixed-integer programs. The size of reformulated integer programs is usually very large even though the original problem is of medium size. This paper studies an augmented Lagrangian decomposition method for finding high-quality feasible solutions of complex optimization problems, including nonconvex chance-constrained problems. Different from the current augmented Lagrangian approaches, the proposed method allows randomness to appear in both the left-hand-side matrix and the right-hand-side vector of the chance constraint. In addition, the proposed method only requires solving a convex subproblem and a 0-1 knapsack subproblem at each iteration. Based on the special structure of the chance constraint, the 0-1 knapsack problem can be computed in quasi-linear time, which keeps the computation for discrete optimization subproblems at a relatively low level. The convergence of the method to a first-order stationary point is established under certain mild conditions. Numerical results are presented in comparison with a set of existing methods in the literature for various real-world models. It is observed that the proposed method compares favorably in terms of the quality of the best feasible solution obtained within a certain time for large-size problems, particularly when the objective function of the problem is nonconvex or the left-hand-side matrix of the constraints is random.

Keywords: chance-constrained optimization problem; finite discrete distribution; alternating direction method of multipliers; augmented Lagrangian algorithm; first-order stationary point (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1001 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:3:p:1056-1069

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().