Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management

• 成果类型: Article
• 署名作者: Chen, Xin; He, Niao; Hu, Yifan; Ye, Zikun
• 署名单位: University System of Georgia; Georgia Institute of Technology; Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Washington; University of Washington Seattle
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0216
• 发表日期: 2025
• 关键词: INVENTORY; allocation; overbooking; decisions; demand; MODEL

摘要

We study a class of stochastic nonconvex optimization in the form of min(x is an element of X) F(x) := E-xi[f (phi(x, xi))], that is, F is a composition of a convex function f and a random function phi. Leveraging an (implicit) convex reformulation via a variable transformation u = E[phi(x, xi)], we develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an epsilon-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 (O) over tilde(epsilon(-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 phi(x, xi) = x boolean AND xi, 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.