Abstract: In this talk, we will discuss a class of nonconvex stochastic optimization that occurs in inventory and revenue management. To address the nonconvexity, we leverage an (implicit) convex reformulation via an (unknown) variable change. We further develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an $\eps$-global optimal solution. Interestingly, our proposed Mirror Stochastic Gradient (MSG) method operates only in the original decision space using gradient estimators of the original nonconvex objective and achieves $\tilde \cO(\eps^{-2})$ sample and gradient complexities, which matches the lower bounds for solving stochastic convex optimization problems. As for applications, 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 demand truncates the booking limit decision. 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. We shall further discuss hidden convex reformulations for other problems.
Bio:
Yifan is a postdoctoral researcher in the Risk Analytics and Optimization Laboratory at EPFL, advised by Prof. Daniel Kuhn and Prof. Andreas Krause. Prior to that, Yifan obtained his PhD in Industrial Engineering from UIUC, jointly advised by Prof. Xin Chen and Prof. Niao He. His research interests lie in stochastic optimization, reinforcement learning, and operations research. Specifically, he is interested in designing efficient algorithms with provable statistical and computational guarantees for general optimization and operations management, i.e., revenue management and inventory problems.