Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916323591716864 |
|---|---|
| author | Chen, Xin He, Niao Hu, Yifan Ye, Zikun |
| author_facet | Chen, Xin He, Niao Hu, Yifan Ye, Zikun |
| contents | We study a class of stochastic nonconvex optimization in the form of $\min_{x\in\mathcal{X}} F(x):=\mathbb{E}_ξ[f(ϕ(x,ξ))]$, i.e., $F$ is a composition of a convex function $f$ and a random function $ϕ$. Leveraging an (implicit) convex reformulation via a variable transformation $u=\mathbb{E}[ϕ(x,ξ)]$, we develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an $ε$-global optimal solution. Interestingly, our proposed Mirror Stochastic Gradient (MSG) method operates only in the original $x$-space using gradient estimators of the original nonconvex objective $F$ and achieves $\tilde{\mathcal{O}}(ε^{-2})$ complexities, which matches the lower bounds for solving stochastic convex optimization problems. Under booking limits control, we formulate the air-cargo network revenue management (NRM) problem with random two-dimensional capacity, random consumption, and routing flexibility as a special case of the stochastic nonconvex optimization, where the random function $ϕ(x,ξ)=x\wedgeξ$, i.e., the random demand $ξ$ truncates the booking limit decision $x$. Extensive numerical experiments demonstrate the superior performance of our proposed MSG algorithm for booking limit control with higher revenue and lower computation cost than state-of-the-art bid-price-based control policies, especially when the variance of random capacity is large.
KEYWORDS: stochastic nonconvex optimization, hidden convexity, gradient methods, passenger network revenue management, air-cargo network revenue management |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_01774 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management Chen, Xin He, Niao Hu, Yifan Ye, Zikun Optimization and Control We study a class of stochastic nonconvex optimization in the form of $\min_{x\in\mathcal{X}} F(x):=\mathbb{E}_ξ[f(ϕ(x,ξ))]$, i.e., $F$ is a composition of a convex function $f$ and a random function $ϕ$. Leveraging an (implicit) convex reformulation via a variable transformation $u=\mathbb{E}[ϕ(x,ξ)]$, we develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an $ε$-global optimal solution. Interestingly, our proposed Mirror Stochastic Gradient (MSG) method operates only in the original $x$-space using gradient estimators of the original nonconvex objective $F$ and achieves $\tilde{\mathcal{O}}(ε^{-2})$ complexities, which matches the lower bounds for solving stochastic convex optimization problems. Under booking limits control, we formulate the air-cargo network revenue management (NRM) problem with random two-dimensional capacity, random consumption, and routing flexibility as a special case of the stochastic nonconvex optimization, where the random function $ϕ(x,ξ)=x\wedgeξ$, i.e., the random demand $ξ$ truncates the booking limit decision $x$. Extensive numerical experiments demonstrate the superior performance of our proposed MSG algorithm for booking limit control with higher revenue and lower computation cost than state-of-the-art bid-price-based control policies, especially when the variance of random capacity is large. KEYWORDS: stochastic nonconvex optimization, hidden convexity, gradient methods, passenger network revenue management, air-cargo network revenue management |
| title | Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2205.01774 |