题    目：Online Linear Programming without Nondegeneracy

嘉　宾：张家伟 教授 纽约大学

主持人：曾智宇 助理教授 上海交通大学安泰经济与管理学院

时　间：2026年6月25日（周四）10:00-11:30

地　点：上海交通大学安泰经济与管理学院包兆龙图书馆A507

内容简介：

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.

演讲人简介：

Jiawei Zhang is the Michael Armellino Professor in Business and Professor of Information, Operations and Management Sciences at New York University's Leonard N. Stern School of Business. He joined NYU Stern's Operations Management Group in September 2004. He serves as the academic director of the Master of Science in Data Analytics & Business Computing program.

Professor Zhang's primary research interests include business analytics and optimization, machine learning, supply chain and inventory management, pricing and revenue management, and health care operations. His publications have appeared in Management Science, Mathematics of Operations Research, Mathematical Programming, Manufacturing and Service Operations, Operations Research, SIAM Journal on Computing, etc.

Professor Zhang received Bachelor of Science in Applied Mathematics and his Master of Science degree in Operations Research from Tsinghua University, China, and his PhD in Management Science and Engineering from Stanford University.

欢迎广大师生参加！