Efficient Algorithms for Minimizing Compositions of Convex Functions and Random Functions and Its Applications in Network Revenue Management

MaRDI QIDQ6398191zbMATH OpenFDO

Authors Xin Chen, Niao He, Yifan Hu, Zikun Ye

Publication date 3 May 2022

Abstract: In this paper, we study a class of nonconvex stochastic optimization in the form of $mi{n}_{xinmathcalX}F(x):=mathbb{E}_{x}i[f(phi(x,xi))]$, where the objective function $F$ is a composition of a convex function $f$ and a random function $phi$. Leveraging an (implicit) convex reformulation via a variable transformation $u=mathbbE[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 $ildemathcalO(epsilo{n}^{-2})$ sample and gradient 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 $phi(x,xi)=xwedgexi$, i.e., the random demand $xi$ 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, air-cargo network revenue management, gradient-based algorithms

This page was built for publication: Efficient Algorithms for Minimizing Compositions of Convex Functions and Random Functions and Its Applications in Network Revenue Management

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398191)