提出新方法求解复杂约束下的非凸非凹极小极大问题。
A first-order method for constrained nonconvex-nonconcave minimax optimization
- 通过重构问题并利用局部KL条件，建立光滑性新性质。
- 设计可计算近似梯度的迭代算法，实现收敛速率保证。
- 适合研究极小极大优化或需处理复杂约束的学者使用。
我们研究一类带有复杂约束的非凸非凹极小极大优化问题。在一种新的提升型极小极大重构下，假设内层问题满足局部Kurdyka-Lojasiewicz（KL）条件，证明原问题的极大函数具备局部广义霍尔德光滑性。进一步提出一种序列凸规划（SCP）方法求解约束优化问题，并在局部KL条件下建立其收敛速率。基于此，开发了一种求解原极小极大问题的不精确邻近梯度法，其中极大函数的近似梯度通过针对局部KL结构子问题的SCP方法计算。最后，建立了该方法在求解原问题近似驻点时的复杂度保证。
原文摘要 · Abstract (English)
We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-Lojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local generalized Hölder smoothness property. We also propose a sequential convex programming (SCP) method for solving constrained optimization problems and establish its convergence rate under a local KL condition. Leveraging these results, we develop an inexact proximal gradient method for the original minimax problem, where the inexact gradient of the maximal function is computed via the SCP method applied to a locally KL-structured subproblem. Finally, we establish complexity guarantees for the proposed method in computing an approximate stationary point of the original minimax problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。