An augmented lagrangian decomposition method for chance-constrained optimization problems
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Language: | English |
| Published: |
INFORMS
2021
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/91428 |
| _version_ | 1848765517903429632 |
|---|---|
| author | Bai, X. Sun, Jie Zheng, X. |
| author_facet | Bai, X. Sun, Jie Zheng, X. |
| author_sort | Bai, X. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T11:36:31Z |
| format | Journal Article |
| id | curtin-20.500.11937-91428 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T11:36:31Z |
| publishDate | 2021 |
| publisher | INFORMS |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-914282023-05-03T07:36:39Z An augmented lagrangian decomposition method for chance-constrained optimization problems Bai, X. Sun, Jie Zheng, X. Science & Technology Technology Computer Science, Interdisciplinary Applications Operations Research & Management Science Computer Science chance-constrained optimization problem finite discrete distribution alternating direction method of multipliers augmented Lagrangian algorithm first-order stationary point ALTERNATING DIRECTION METHOD LINEAR-PROGRAMS DISCRETE-DISTRIBUTIONS CONVEX APPROXIMATIONS ALGORITHM REGULARIZATION RELAXATIONS 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. 2021 Journal Article http://hdl.handle.net/20.500.11937/91428 10.1287/ijoc.2020.1001 English INFORMS fulltext |
| spellingShingle | Science & Technology Technology Computer Science, Interdisciplinary Applications Operations Research & Management Science Computer Science chance-constrained optimization problem finite discrete distribution alternating direction method of multipliers augmented Lagrangian algorithm first-order stationary point ALTERNATING DIRECTION METHOD LINEAR-PROGRAMS DISCRETE-DISTRIBUTIONS CONVEX APPROXIMATIONS ALGORITHM REGULARIZATION RELAXATIONS Bai, X. Sun, Jie Zheng, X. An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title | An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title_full | An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title_fullStr | An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title_full_unstemmed | An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title_short | An augmented lagrangian decomposition method for chance-constrained optimization problems |
| title_sort | augmented lagrangian decomposition method for chance-constrained optimization problems |
| topic | Science & Technology Technology Computer Science, Interdisciplinary Applications Operations Research & Management Science Computer Science chance-constrained optimization problem finite discrete distribution alternating direction method of multipliers augmented Lagrangian algorithm first-order stationary point ALTERNATING DIRECTION METHOD LINEAR-PROGRAMS DISCRETE-DISTRIBUTIONS CONVEX APPROXIMATIONS ALGORITHM REGULARIZATION RELAXATIONS |
| url | http://hdl.handle.net/20.500.11937/91428 |