非凸极小极大问题的优化算法与复杂度分析  

Optimization algorithms and their complexity analysis for non-convex minimax problems

作　　者：徐姿[1] 张慧灵 XU Zi;ZHANG Huiling(Department of Mathematics,College of Sciences,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学理学院数学系,上海200444

出　　处：《运筹学学报》2021年第3期74-86,共13页Operations Research Transactions

基　　金：国家自然科学基金(Nos.12071279,11771208);上海市自然科学基金(No.20ZR1420600)。

摘　　要：非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点,包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果,但非凸极小极大问题不同于凸-凹极小极大问题,是有其自身结构的非凸非光滑优化问题,理论研究和求解难度都更具挑战性,一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。The non-convex minimax problem is an important research front and hot spot in the cross-fields of optimization,machine learning,signal processing,etc.Some key scientific issues in frontier research directions such as adversarial learning,reinforcement learning,and distributed non-convex optimization,all belong to this type of problem.Internationally,the research on convex-concave minimax problems has achieved good results.However,the non-convex minimax problem is different from the convex-concave minimax problem,and it is a non-convex and non-smooth optimization problem with its own structure,for which,the theoretical analysis and the algorithm design are more challenging than that of the convex-concave minimax problem,and it is generally NPhard.This paper focuses on the latest developments in optimization algorithms and complexity analysis for non-convex minimax problems.

关 键 词：极小极大优化问题 复杂度分析 一阶算法 (随机)梯度下降上升算法 交替梯度投影算法 非凸优化 机器学习 

分 类 号：O221.2[理学—运筹学与控制论]