Sample Average Approximation for Stochastic Programming with Equality Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909252435574784 |
|---|---|
| author | Lew, Thomas Bonalli, Riccardo Pavone, Marco |
| author_facet | Lew, Thomas Bonalli, Riccardo Pavone, Marco |
| contents | We revisit the sample average approximation (SAA) approach for non-convex stochastic programming. We show that applying the SAA approach to problems with expected value equality constraints does not necessarily result in asymptotic optimality guarantees as the sample size increases. To address this issue, we relax the equality constraints. Then, we prove the asymptotic optimality of the modified SAA approach under mild smoothness and boundedness conditions on the equality constraint functions. Our analysis uses random set theory and concentration inequalities to characterize the approximation error from the sampling procedure. We apply our approach and analysis to the problem of stochastic optimal control for nonlinear dynamical systems under external disturbances modeled by a Wiener process. Numerical results on relevant stochastic programs show the reliability of the proposed approach. Results on a rocket-powered descent problem show that our computed solutions allow for significant uncertainty reduction compared to a deterministic baseline. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_09963 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sample Average Approximation for Stochastic Programming with Equality Constraints Lew, Thomas Bonalli, Riccardo Pavone, Marco Optimization and Control Systems and Control Statistics Theory 90C15, 65C05, 62F99, 60D05, 93E20 We revisit the sample average approximation (SAA) approach for non-convex stochastic programming. We show that applying the SAA approach to problems with expected value equality constraints does not necessarily result in asymptotic optimality guarantees as the sample size increases. To address this issue, we relax the equality constraints. Then, we prove the asymptotic optimality of the modified SAA approach under mild smoothness and boundedness conditions on the equality constraint functions. Our analysis uses random set theory and concentration inequalities to characterize the approximation error from the sampling procedure. We apply our approach and analysis to the problem of stochastic optimal control for nonlinear dynamical systems under external disturbances modeled by a Wiener process. Numerical results on relevant stochastic programs show the reliability of the proposed approach. Results on a rocket-powered descent problem show that our computed solutions allow for significant uncertainty reduction compared to a deterministic baseline. |
| title | Sample Average Approximation for Stochastic Programming with Equality Constraints |
| topic | Optimization and Control Systems and Control Statistics Theory 90C15, 65C05, 62F99, 60D05, 93E20 |
| url | https://arxiv.org/abs/2206.09963 |