0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908968173961216 |
|---|---|
| author | Zhou, Shenglong Pan, Lili Xiu, Naihua Li, Geoffrey Ye |
| author_facet | Zhou, Shenglong Pan, Lili Xiu, Naihua Li, Geoffrey Ye |
| contents | Sample average approximation (SAA) is a tractable approach for dealing with chance constrained programming, a challenging stochastic optimization problem. The constraint of SAA is characterized by the $0/1$ loss function which results in considerable complexities in devising numerical algorithms. Most existing methods have been devised based on reformulations of SAA, such as binary integer programming or relaxed problems. However, the development of viable methods to directly tackle SAA remains elusive, let alone providing theoretical guarantees. In this paper, we investigate a general $0/1$ constrained optimization, providing a new way to address SAA rather than its reformulations. Specifically, starting with deriving the Bouligand tangent and Fr$\acute{e}$chet normal cones of the $0/1$ constraint, we establish several optimality conditions. One of them can be equivalently expressed by a system of equations, enabling the development of a semismooth Newton-type algorithm. The algorithm demonstrates a locally superlinear or quadratic convergence rate under standard assumptions, along with nice numerical performance compared to several leading solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_11889 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | 0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming Zhou, Shenglong Pan, Lili Xiu, Naihua Li, Geoffrey Ye Optimization and Control Sample average approximation (SAA) is a tractable approach for dealing with chance constrained programming, a challenging stochastic optimization problem. The constraint of SAA is characterized by the $0/1$ loss function which results in considerable complexities in devising numerical algorithms. Most existing methods have been devised based on reformulations of SAA, such as binary integer programming or relaxed problems. However, the development of viable methods to directly tackle SAA remains elusive, let alone providing theoretical guarantees. In this paper, we investigate a general $0/1$ constrained optimization, providing a new way to address SAA rather than its reformulations. Specifically, starting with deriving the Bouligand tangent and Fr$\acute{e}$chet normal cones of the $0/1$ constraint, we establish several optimality conditions. One of them can be equivalently expressed by a system of equations, enabling the development of a semismooth Newton-type algorithm. The algorithm demonstrates a locally superlinear or quadratic convergence rate under standard assumptions, along with nice numerical performance compared to several leading solvers. |
| title | 0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2210.11889 |