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

We study a class of stochastic nonconvex optimization in the form of 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 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.