5月18日，经管学院邀请弗吉尼亚理工大学助理教授谢伟君为师生带来题为“Best Submatrix Selection: Strong formulations and effective algorithms”的学术分享。

　　谢伟君是弗吉尼亚理工大学工业和系统工程系助理教授。他于2017年获得佐治亚理工学院运筹学博士学位，主要研究兴趣是随机优化、离散优化和凸优化的理论和应用，曾获得多项奖项，如NSF CAREER Award, Winner of 2020 INFORMS Young Researchers Paper Prize, Third Place in Junior Faculty Interest Group Paper Competition at INFORMS 2018。目前担任INFORMS Optimization Society不确定性优化方向的副主席以及Mathematical Programming和Journal of Global Optimization的副主编。

　　谢伟君首先介绍了最大熵采样问题(MESP)的背景，以及在电路设计、数据降维、社交网络、机器学习等方面的应用。由于MESP是NP-hard的非凸非凹组合优化问题，该问题的求解是较难的。通过对原问题求解两次拉格朗日对偶，发现原问题可重写为一个凸整数规划问题且拉格朗日对偶问题即为原问题的凸松弛。对于凸松弛问题，研究团队计算出目标函数的supgradient，据此设计了Frank-Wolfe算法进行求解并且经过理论分析得出该算法的收敛速度。根据Frank-Wolfe算法给出的最优解，他们提出一种更高效的Sampling Algorithm来获得最优的子集，并给出了该算法的approximation bound。经比较，这个界是现有近似算法中最紧的。同时，根据原问题与凸松弛问题之间的弱对偶关系，研究团队计了局部搜索(Local Search)算法进行近似求解。由于启发式算法很难进行理论分析，该文章首次给出了在MESP问题上局部搜索算法的approximation bound。数值上，相较于经典的Branch & Bound算法，这些近似算法在中等规模以及大规模算例上都能高效地求解出近似最优解，尤其是局部搜索算法在计算时间以及求解精度上表现非常好。