arrow
Volume 42, Issue 3
Semi-Proximal Point Method for Nonsmooth Convex-Concave Minimax Optimization

Yuhong Dai, Jiani Wang & Liwei Zhang

J. Comp. Math., 42 (2024), pp. 617-637.

Published online: 2024-04

Export citation
  • Abstract

Minimax optimization problems are an important class of optimization problems arising from modern machine learning and traditional research areas. While there have been many numerical algorithms for solving smooth convex-concave minimax problems, numerical algorithms for nonsmooth convex-concave minimax problems are rare. This paper aims to develop an efficient numerical algorithm for a structured nonsmooth convex-concave minimax problem. A semi-proximal point method (SPP) is proposed, in which a quadratic convex-concave function is adopted for approximating the smooth part of the objective function and semi-proximal terms are added in each subproblem. This construction enables the subproblems at each iteration are solvable and even easily solved when the semiproximal terms are cleverly chosen. We prove the global convergence of our algorithm under mild assumptions, without requiring strong convexity-concavity condition. Under the locally metrical subregularity of the solution mapping, we prove that our algorithm has the linear rate of convergence. Preliminary numerical results are reported to verify the efficiency of our algorithm.

  • AMS Subject Headings

90C30

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-42-617, author = {Dai , YuhongWang , Jiani and Zhang , Liwei}, title = {Semi-Proximal Point Method for Nonsmooth Convex-Concave Minimax Optimization}, journal = {Journal of Computational Mathematics}, year = {2024}, volume = {42}, number = {3}, pages = {617--637}, abstract = {

Minimax optimization problems are an important class of optimization problems arising from modern machine learning and traditional research areas. While there have been many numerical algorithms for solving smooth convex-concave minimax problems, numerical algorithms for nonsmooth convex-concave minimax problems are rare. This paper aims to develop an efficient numerical algorithm for a structured nonsmooth convex-concave minimax problem. A semi-proximal point method (SPP) is proposed, in which a quadratic convex-concave function is adopted for approximating the smooth part of the objective function and semi-proximal terms are added in each subproblem. This construction enables the subproblems at each iteration are solvable and even easily solved when the semiproximal terms are cleverly chosen. We prove the global convergence of our algorithm under mild assumptions, without requiring strong convexity-concavity condition. Under the locally metrical subregularity of the solution mapping, we prove that our algorithm has the linear rate of convergence. Preliminary numerical results are reported to verify the efficiency of our algorithm.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2301-m2022-0099}, url = {http://global-sci.org/intro/article_detail/jcm/23029.html} }
TY - JOUR T1 - Semi-Proximal Point Method for Nonsmooth Convex-Concave Minimax Optimization AU - Dai , Yuhong AU - Wang , Jiani AU - Zhang , Liwei JO - Journal of Computational Mathematics VL - 3 SP - 617 EP - 637 PY - 2024 DA - 2024/04 SN - 42 DO - http://doi.org/10.4208/jcm.2301-m2022-0099 UR - https://global-sci.org/intro/article_detail/jcm/23029.html KW - Minimax optimization, Convexity-concavity, Global convergence, Rate of convergence, Locally metrical subregularity. AB -

Minimax optimization problems are an important class of optimization problems arising from modern machine learning and traditional research areas. While there have been many numerical algorithms for solving smooth convex-concave minimax problems, numerical algorithms for nonsmooth convex-concave minimax problems are rare. This paper aims to develop an efficient numerical algorithm for a structured nonsmooth convex-concave minimax problem. A semi-proximal point method (SPP) is proposed, in which a quadratic convex-concave function is adopted for approximating the smooth part of the objective function and semi-proximal terms are added in each subproblem. This construction enables the subproblems at each iteration are solvable and even easily solved when the semiproximal terms are cleverly chosen. We prove the global convergence of our algorithm under mild assumptions, without requiring strong convexity-concavity condition. Under the locally metrical subregularity of the solution mapping, we prove that our algorithm has the linear rate of convergence. Preliminary numerical results are reported to verify the efficiency of our algorithm.

Yuhong Dai, Jiani Wang & Liwei Zhang. (2024). Semi-Proximal Point Method for Nonsmooth Convex-Concave Minimax Optimization. Journal of Computational Mathematics. 42 (3). 617-637. doi:10.4208/jcm.2301-m2022-0099
Copy to clipboard
The citation has been copied to your clipboard