论文标题
一类随机隐藏凸优化的有效算法及其在网络收入管理中的应用
Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management
论文作者
论文摘要
我们以$ \ min_ {x \ in \ mathcal {x}} f（x）的形式研究一类随机非convex优化：= \ mathbb {e}_ξ[f（ϕ（x，x，ξ）$，即通过可变转换$ u = \ mathbb {e} [ϕ（x，ξ）] $利用（隐式）凸的重新制定，我们开发了基于随机梯度的算法，并建立了它们的样本和梯度复杂性，以实现$ε$ - $ -Global Optimal Optimal解决方案。有趣的是，我们提出的镜像随机梯度（MSG）方法仅在原始的$ x $ - 空格中使用原始nonConvex物镜$ f $ f $ f $并实现$ \ tilde {\ Mathcal {o}}}（ε^{ - 2}）$复杂性，这使得较低的范围可求解稳定的稳定性问题。在预订限制控制下，我们以随机的二维容量，随机消耗和路由灵活性作为随机非convex优化的特殊情况，以随机的二维容量，随机的能力，随机消耗和路由灵活性来制定空气货车网络收入管理（NRM）问题，其中随机函数$ ϕ（x，x，ξ）= x \ wedge $。广泛的数值实验证明了我们提出的MSG算法的出色性能，用于预订限额控制，收入较高，计算成本较低，而不是基于竞标价格的控制策略，尤其是在随机容量的差异较大时。 关键字：随机非convex优化，隐藏的凸性，梯度方法，乘客网络收入管理，气货网络收入管理
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
