报告题目：Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees
报告人：谢伟君 （弗吉尼亚理工大学）
报告时间：2022年5月18日(周三) 10:00-11:30
Zoom 会议号：881 1430 7102 入会密码：80087
内容摘要
This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing and data science. We derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP.
主讲人简介
Dr. Weijun Xie is an Assistant Professor in the Department of Industrial and Systems Engineering at Virginia Tech. Dr. Xie obtained his Ph.D. in Operations Research at Georgia Institute of Technology in 2017. His research interests are in theory and applications of stochastic, discrete, and convex optimization. His works have received multiple awards, including the 2021 NSF CAREER Award, Winner of 2020 INFORMS Young Researchers Paper Prize, Third Place in Junior Faculty Interest Group Paper Competition at INFORMS 2018. He currently serves as the Vice-Chair of Optimization under Uncertainty at INFORMS Optimization Society and Associate Editor of Mathematical Programming and Journal of Global Optimization.
