Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management
Xin Chen, Niao He, Yifan Hu, Zikun Ye
Operations Research Β· 2025 Β· Volume 73 Β· Issue 2
Abstract
We study a class of stochastic nonconvex optimization in the form of m i n π₯ β π³ β’ πΉ β‘ ( π₯ ) β πΌ π β‘ [ π β‘ ( π β‘ ( π₯ , π ) ) ] min x β X β’ F β‘ ( x ) β E ΞΎ β‘ [ f β‘ ( Ο β‘ ( x , ΞΎ ) ) ] , that is, F is a composition of a convex function f and a random function π Ο . Leveraging an (implicit) convex reformulation via a variable transformation π’ = πΌ β‘ [ π β‘ ( π₯ , π ) ] u = 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 Μ πͺ β‘ ( π β 2 ) O Λ β‘ ( Ο΅ β 2 ) complexities, matching 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 β§ ΞΎ , that is, 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. Funding: This work was partly supported by the National Science Foundation [Grants CMMI-1761699, CRII-1755829], the ZJU-UIUC Institute Research Program, and NCCR Automation in Switzerland. Supplemental Material: The computer code and data that support the findings of this study are available within this articleβs supplemental material at https://doi.org/10.1287/opre.2022.0216 .
Keywords
Market Analytics and Revenue Management, stochastic nonconvex optimization, hidden convexity, gradient methods, passenger network revenue management, air-cargo network revenue management
Enable JavaScript for citation tools and additional paper interactions.