A first-order augmented Lagrangian method for constrained minimax optimization

• 成果类型: Article
• 署名作者: Lu, Zhaosong; Mei, Sanyou
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02163-3
• 发表日期: 2025
• 页码: 1063-1104
• 关键词: nonconvex; algorithms; complexity

摘要

In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method developed in this paper. Under some suitable assumptions, an operation complexity of O(epsilon-4log epsilon-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{O}(\varepsilon <^>{-4}\log \varepsilon <^>{-1})$$\end{document}, measured by its fundamental operations, is established for the first-order augmented Lagrangian method for finding an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-KKT solution of the constrained minimax problems.