Shape-Constrained Distributional Optimization via Importance-Weighted Sample Average Approximation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929382666272768 |
|---|---|
| author | Lam, Henry Liu, Zhenyuan Singham, Dashi I. |
| author_facet | Lam, Henry Liu, Zhenyuan Singham, Dashi I. |
| contents | Shape-constrained optimization arises in a wide range of problems including distributionally robust optimization (DRO) that has surging popularity in recent years. In the DRO literature, these problems are usually solved via reduction into moment-constrained problems using the Choquet representation. While powerful, such an approach could face tractability challenges arising from the geometries and the compatibility between the shape and the objective function and moment constraints. In this paper, we propose an alternative methodology to solve shape-constrained optimization problems by integrating sample average approximation with importance sampling, the latter used to convert the distributional optimization into an optimization problem over the likelihood ratio with respect to a sampling distribution. We demonstrate how our approach, which relies on finite-dimensional linear programs, can handle a range of shape-constrained problems beyond the reach of previous Choquet-based reformulations, and entails vanishing and quantifiable optimality gaps. Moreover, our theoretical analyses based on strong duality and empirical processes reveal the critical role of shape constraints in guaranteeing desirable consistency and convergence rates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07825 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Shape-Constrained Distributional Optimization via Importance-Weighted Sample Average Approximation Lam, Henry Liu, Zhenyuan Singham, Dashi I. Optimization and Control Methodology Shape-constrained optimization arises in a wide range of problems including distributionally robust optimization (DRO) that has surging popularity in recent years. In the DRO literature, these problems are usually solved via reduction into moment-constrained problems using the Choquet representation. While powerful, such an approach could face tractability challenges arising from the geometries and the compatibility between the shape and the objective function and moment constraints. In this paper, we propose an alternative methodology to solve shape-constrained optimization problems by integrating sample average approximation with importance sampling, the latter used to convert the distributional optimization into an optimization problem over the likelihood ratio with respect to a sampling distribution. We demonstrate how our approach, which relies on finite-dimensional linear programs, can handle a range of shape-constrained problems beyond the reach of previous Choquet-based reformulations, and entails vanishing and quantifiable optimality gaps. Moreover, our theoretical analyses based on strong duality and empirical processes reveal the critical role of shape constraints in guaranteeing desirable consistency and convergence rates. |
| title | Shape-Constrained Distributional Optimization via Importance-Weighted Sample Average Approximation |
| topic | Optimization and Control Methodology |
| url | https://arxiv.org/abs/2406.07825 |