近日，数学系徐姿教授团队及其合作者在非凸极小极大优化问题的优化算法领域取得重要进展，相关研究成果以“Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems”为题发表于国际运筹优化顶级期刊《SIAM Journal on Optimization》(中科院一区Top，中国数学会T1期刊，运筹优化领域国际三大顶级期刊之一)。该论文徐姿教授为第一作者，上海大学为第一署名单位。
非凸极小极大问题的理论、算法和应用属于数据科学和人工智能中的优化模型、算法设计与分析研究领域，这是 2022 年国家自然科学基金“十四五发展规划中的”优先发展领域。近期，该类的优化算法及复杂度分析，成为优化和机器学习、人工智能等交叉领域国际研究的前沿和热点问题。非凸极小极大问题一般是NP-难的。如果只有目标函数信息可用，梯度信息不可用，已有的一阶算法不能直接用于求解此类问题。本项工作提出了无导数交替随机梯度投影（ZO-AGP）算法用于求解非凸-凹极小极大问题，并且证明了ZO-AGP算法获得近似稳定点的函数值计算或调用次数的上限。进一步，本项工作还提出了零阶块交替随机邻近梯度(ZO-BAPG)算法求解分块非光滑非凸-凹极小极大问题，并且证明了ZO-BAPG算法获得近似稳定点的函数值计算或调用次数的上限。ZO-AGP和ZO-BAPG是分别求解这两类问题的首个具有迭代复杂度保证的零阶算法。本项研究将推动优化算法在机器学习等领域的发展。
近些年来，徐姿教授团队在最优理论与方法及其在机器学习等领域的应用方面做出了很多创新性的工作，在Mathematical Programming、SIAM Journal on Optimization、Journal of Machine Learning Research、IEEE Journal on Selected Areas in Communications等国际权威期刊上发表论文30余篇，研究成果得到美国科学院和工程院院士M. I. Jordan教授，英国皇家工程院院士、匈牙利科学院外籍院士L. Hanzo教授，加拿大皇家科学院、工程院两院院士J. Pei教授等国际著名专家的公开引用和正面评价。因在运筹优化领域的突出科研成果，2020年徐姿教授曾荣获中国运筹学会青年科技奖。
本项工作得到国家自然科学基金和上海市自然科学基金支持。本项工作由上海大学徐姿教授、硕士生王子琦、硕士生沈晶晶、中国科学院戴彧虹研究员合作完成，相关论文见：Z. Xu, Z. Wang, J. Shen, Y. Dai，Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems, SIAM Journal on Optimization, 34(2):1879-1908, (2024). https://epubs.siam.org/doi/10.1137/23M1568168.