9月12日下午，应数学科学学院邀请，北京航空航天大学夏勇教授在弘文楼B-413作了题为“绝对值方程组的离散势函数优化：从指数到多项式的突破”的学术报告。报告会由焦红伟副院长主持，学院部分教师、研究生、本科生等60余人参加。

绝对值方程组是数学优化与科学计算中的一类重要非光滑问题，其一般求解具有较高的计算复杂度。报告中，夏勇教授围绕绝对值方程组的离散势函数优化展开介绍。针对传统方法大多在连续变量空间中求解、而已有符号一致算法最坏情形需要指数级迭代的问题，他介绍了定义在符号向量集合上的离散势函数优化框架，并阐释了在一定矩阵范数条件下，绝对值方程组的解与离散势函数全局最优解之间的对应关系。在此基础上，报告进一步介绍了统一的符号翻转算法多项式时间分析框架，包括最陡下降、Gauss-Southwell等单点翻转规则以及与经典广义牛顿法相对应的全翻转更新，并讨论了通过对角缩放放宽相关条件以及随机多点翻转算法的复杂度结果。最后，夏勇教授介绍了将线性互补问题等价转化为绝对值方程组的思路，由此将离散势函数优化框架推广至线性互补问题，为经典迭代方法和主元型方法建立多项式迭代复杂度分析提供了新的视角，实现了相关算法理论从指数复杂度向多项式复杂度的突破。

报告结束后，与会师生围绕绝对值方程组的复杂度分析、符号翻转算法、离散优化方法及其与线性互补问题的联系等内容与夏勇教授进行了深入交流。本次报告从经典非光滑方程组出发，将离散优化建模、算法设计与复杂度理论有机结合，展示了数学优化中从问题结构出发改进经典算法理论界限的研究思路，进一步拓宽了与会师生对非凸优化和计算复杂度相关问题的认识。

专家简介：夏勇，北京航空航天大学教授，博士生导师，数学科学学院副院长。2002年毕业于北京大学，2007年毕业于中国科学院，师从袁亚湘院士，研究方向为非凸优化，2013年北京青年英才，2018年国家优青，在Math.ProgramSIAM J.Optim.等期刊发表SCI论文70篇。中国运筹学会理事、中国运筹学会数学规划分会常务理事、北京运筹学会理事，中国运筹学会会刊JORSC期刊编委。 代表性工作包括针对经典的二次指派问题提出新模型，被中、美、加、德、意、西班牙等国际国内同行命名为Xia-Yuan线性化，其松弛被称为Xia-Yuan界。

（图片/黄冰迪 撰稿/黄冰迪 初审/田小霞 复审/焦红伟 终审/董瑞）