近日，数学系徐姿教授团队及其合作者在非凸极小极大优化问题的优化算法领域取得重要进展，相关研究成果以“A unified single-loop alternating gradient projection algorithm for nonconvex–concave and convex–nonconcave minimax problems”为题发表于国际运筹优化顶级期刊《Mathematical Programming》(中科院一区Top，中国数学会T1期刊，运筹优化领域国际三大顶级期刊之一)。该论文徐姿教授为第一作者，古天乐代言太阳集团为第一署名单位。
2021级博士生张慧灵为该论文第二作者，并凭此工作于2023年4月9日获得2023年湘渝沪运筹学联合年会暨学术交流大会优秀研究生论文（博士研究生组）一等奖。
非凸极小极大问题的理论、算法和应用属于数据科学和人工智能中的优化模型、算法设计与分析研究领域，这是 2022 年国家自然科学基金“十四五发展规划中的”优先发展领域。非凸极小极大问题一般是NP-难的。近期，该类的优化算法及复杂度分析，成为优化和机器学习、人工智能等交叉领域国际研究的前沿和热点问题。本项工作提出了求解非凸-凹和凸-非凹极小极大优化问题的一种一致的单循环交替梯度投影（AGP）算法，每一步迭代仅需要计算一个梯度投影步。本工作证明了该算法求解非凸-强凹或者是强凸-非凹的极小极大优化问题得到目标函数一阶近似稳定点的迭代复杂度是-2阶的，而求解一般化的非凸-凹或者凸-非凹极小极大问题的迭代复杂度是-4阶的。目前，对于一般化的（强）凸-非凹极小极大问题，这是第一个具有迭代复杂度保证的算法。本工作还提出了求解更一般化的多块非光滑非凸-（强）凹和（强）凸-非凸极小极大问题的块交替近端梯度（BAPG）算法，且证明了四种情形下该算法的类似迭代复杂度。数值实验结果也表明了算法的有效性。该研究无论从算法还是理论的角度原创性都很强，推动了优化算法在机器学习等领域的发展。
近些年来，徐姿教授团队在最优理论与方法及其在机器学习等领域的应用方面做出了很多创新性的工作，在SIAM Journal on Optimization、IEEE Journal on Selected Areas in Communications、Journal of Global Optimization、Journal of Optimization Theory and Applications、Computational Optimization and Applications等国际权威期刊上发表论文30余篇，研究成果得到英国皇家工程院院士、匈牙利科学院外籍院士L.Hanzo教授，加拿大皇家科学院、工程院两院院士J. Pei教授，加拿大皇家科学院院士Z.-Q. Luo教授，INFORMs主席、国际顶尖期刊Math. Prog. A.共同主编A.Atamturk教授等国际著名专家的公开引用和正面评价。因在运筹优化领域的突出科研成果，2020年徐姿教授荣获中国运筹学会青年科技奖(全国5人)。
本工作得到国家自然科学基金和上海市自然科学基金支持。本项工作由古天乐代言太阳集团徐姿教授、博士生张慧灵、硕士生徐洋、美国佐治亚理工学院Guanghui Lan教授合作完成。
相关链接：https://doi.org/10.1007/s10107-022-01919-z
