Online Linear Programming without Nondegeneracy
讲座通知 2026 年 6 月 24 日（星期三）， 下午 13:30 - 15:00 信息管理与工程学院308室 上海市杨浦区武东路100号 主题 Online Linear Programming without Nondegeneracy 主讲人 Jiawei Zhang New York University Jiawei Zhang is a Professor of Operations Management at the Stern School of Business, New York University. He received a B.S. degree in Applied Mathematics and an M.S. degree in Operations Research from Tsinghua University, and a Ph.D. in Operations Research from Stanford University. His research interests include Cost Allocation in Supply Chain Management, Deterministic and Stochastic Optimization, and Approximation Algorithms. He has published in journals that include Operations Research, Mathematics of Operations Research, Psychometrika, SIAM Journal on Computing, Mathematical Programming, etc. 讲座简介 Online linear programming is a fundamental model for sequential resource allocation. Requests arrive over time, each request generates a reward and consumes limited resources if accepted, and decisions must be made online relative to an offline hindsight benchmark. Existing results establish constant regret guarantees for finite-type models, and logarithmic regret bounds for continuous-distribution models under regularity conditions on the standard fluid LP and its dual, such as a unique nondegenerate optimal basis, dual uniqueness, or second-order growth conditions. This talk presents a line of recent work on online linear programming without the standard nondegeneracy assumptions used in the literature. We first introduce a semi-fluid-relaxation-based algorithm for network revenue management with continuous rewards and show that it achieves log-squared regret under the only assumption that the reward density is bounded away from zero. We then develop a Bellman-certificate approach to prove a matching lower bound. The lower bound shows that the log-squared rate reflects an intrinsic separation between degenerate and nondegenerate regimes suggesting that some form of nondegeneracy is necessary for the previously known logarithmic bounds. Finally, we extend the model to allow random and continuously distributed resource consumption, and develop new policies and analyses that obtain tight sublinear regret guarantees in this more general setting.
上海财经大学（武东路校区）
