演讲人: 李国凯博士，香港中文大学（深圳）

时间: 2025年7月3日 13：30

地点: 同济大厦A楼408教室

讲座摘要:

在线线性规划（OLP）因其在在线拍卖、网络收益管理、订单履约与广告投放等众多领域中的广泛应用，近年来引起了学术界和业界的高度关注。现有的OLP算法主要分为两类：基于线性规划（LP-based）的方法和非线性规划（LP-free）的方法。前者通常具有更好的性能表现，甚至可以实现常数级的最优性差距-遗憾（regret），但需要频繁求解大量线性规划问题，计算成本较高；而后者仅依赖一阶计算，计算效率更高，但在性能上存在不足，无法保证常数级遗憾上界。本文提出一种性能优良的算法，仅在少数特定时刻求解线性规划（流模型），其余时刻采用一阶计算，从而在两类方法之间取得平衡。具体而言，对于需求来源于未知有限支持的分布的情形，所提出的算法即使在“退化”的困难情形下，也能实现常数级遗憾，并且在整个时间区间 T 内仅需求解 O(log log T) 次线性规划。此外，在只能求解 M 次线性规划时，我们设计了相应的重求解时刻安排，使得算法可以保证接近 O(T^(1/2)^(M-1)) 的遗憾上界。本文强调了在时间周期起始阶段与结束阶段进行重求解的重要性，并提出了一个新的分析框架，用于在不同的低频重求解机制下证明算法性能保证。进一步地，当到达概率在初始已知时，我们的算法在仅进行 O(log log T) 次LP求解的情况下即可实现常数遗憾；而若仅允许求解 M 次LP，则遗憾界近似为 O(T^(1/2)^M)。最后，我们通过数值实验验证了所提出算法的有效性。

演讲嘉宾简介:

李国凯博士即将前往麦吉尔大学和女王大学担任博士后研究员，合作导师包括 Stefanus Jasin 教授、Murray Lei 教授和 Alys Liang 教授。他本科毕业于西安交通大学工业工程专业，博士毕业于香港中文大学（深圳）数据科学专业。李博士的研究兴趣包括在线资源分配、收益管理以及运营与营销交叉领域。他的研究成果已发表于 M&SOM、WINE 会议（CCF-A）以及 NRL。他曾获得 POMS-HK 学生论文竞赛（入围奖）和 中国运筹学会数据科学与运筹智能分会（筹）学生论文竞赛（精选论文）等研究奖项，同时也担任 OR、M&SOM 和 POM 等多个顶级期刊的审稿人。