×
Kong, Weiwei; Monteiro, Renato D. C.

An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. (English) Zbl 07421056

SIAM J. Optim. 31, No. 4, 2558-2585 (2021).
Summary: This paper presents smoothing schemes for obtaining approximate stationary points of unconstrained or linearly constrained composite nonconvex-concave min-max (and hence nonsmooth) problems by applying well-known algorithms to composite smooth approximations of the original problems. More specifically, in the unconstrained (resp., constrained) case, approximate stationary points of the original problem are obtained by applying, to its composite smooth approximation, an accelerated inexact proximal point (resp., quadratic penalty) method presented in a previous paper by the authors. Iteration complexity bounds for both smoothing schemes are also established. Finally, numerical results are given to demonstrate the efficiency of the unconstrained smoothing scheme.

Cited in 12 Documents

MSC:

47J22 Variational and other types of inclusions
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C47 Minimax problems in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
65K10 Numerical optimization and variational techniques

Keywords:

quadratic penalty method; composite nonconvex problem; iteration complexity; inexact proximal point method; first-order accelerated gradient method; minimax problem

Software:

NC-OPT
Cite Review PDF
Full Text: DOI arXiv

References:

[1] K. Arrow, L. Hurwicz, and H. Uzawa, Studies in Linear and Non-Linear Programming, Cambridge University Press, Cambridge, UK, 1958. · Zbl 0091.16002
[2] A. Beck, First-order methods in optimization, SIAM, 2017. · Zbl 1384.65033
[3] J. V. Burke and J. J. Moré, On the identification of active constraints, SIAM J. Numer. Anal., 25 (1988), pp. 1197-1211. · Zbl 0662.65052
[4] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, Accelerated methods for nonconvex optimization, SIAM J. Optim., 28 (2018), pp. 1751-1772. · Zbl 1400.90250
[5] D. Davis and D. Drusvyatskiy, Stochastic model-based minimization of weakly convex functions, SIAM J. Optim., 29 (2019), pp. 207-239. · Zbl 1415.65136
[6] D. Davis, D. Drusvyatskiy, K. J. MacPhee, and C. Paquette, Subgradient methods for sharp weakly convex functions, J. Optim. Theory Appl., 179 (2018), pp. 962-982. · Zbl 1461.65140
[7] D. Drusvyatskiy and C. Paquette, Efficiency of minimizing compositions of convex functions and smooth maps, Math. Program., 178 (2019), pp. 503-558. · Zbl 1431.90111
[8] J. C. Duchi and F. Ruan, Stochastic methods for composite and weakly convex optimization problems, SIAM J. Optim., 28 (2018), pp. 3229-3259. · Zbl 06989166
[9] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Science & Business Media, New York, 2007.
[10] S. Ghadimi and G. Lan, Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156 (2016), pp. 59-99. · Zbl 1335.62121
[11] Y. He and R. D. C. Monteiro, An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems, SIAM J. Optim., 26 (2016), pp. 29-56. · Zbl 1329.90179
[12] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms II, Springer, Berlin, 1993. · Zbl 0795.49002
[13] O. Kolossoski and R. D. C. Monteiro, An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems, Optim. Methods Softw., 32 (2017), pp. 1244-1272. · Zbl 1375.90236
[14] W. Kong, Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems, arXiv preprint, arXiv:2104.09685 [math.OC], 2021, https://arxiv.org/abs/2104.09685.
[15] W. Kong, J. G. Melo, and R. D. C. Monteiro, Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs, SIAM J. Optim., 29 (2019), pp. 2566-2593. · Zbl 1504.90101
[16] W. Kong, J. G. Melo, and R. D. C. Monteiro, An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems, Comput. Optim. Appl., 76 (2020), pp. 305-346. · Zbl 1443.90282
[17] T. Lin, C. Jin, and M. Jordan, Near-Optimal Algorithms for Minimax Optimization, arXiv preprint, arXiv:2002.02417 [math.OC], 2020, https://arxiv.org/abs/2002.02417.
[18] S. Lu, I. Tsaknakis, and M. Hong, Block alternating optimization for non-convex min-max problems: Algorithms and applications in signal processing and communications, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, pp. 4754-4758.
[19] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.
[20] R. D. C. Monteiro and B. F. Svaiter, Convergence Rate of Inexact Proximal Point Methods with Relative Error Criteria for Convex Optimization, preprint, Optimization Online, 2010.
[21] A. Nemirovski, Prox-method with rate of convergence \(O(1/t)\) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15 (2004), pp. 229-251. · Zbl 1106.90059
[22] A. Nemirovski and D. Yudin, Cesari convergence of the gradient method of approximating saddle points of convex-concave functions, Dokl. Akad. Nauk, 239 (1978), pp. 1056-1059. · Zbl 0402.90099
[23] Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102
[24] M. Nouiehed, M. Sanjabi, T. Huang, J. Lee, and M. Razaviyayn, Solving a class of non-convex min-max games using iterative first order methods, in Advances in Neural Information Processing Systems, 2019, pp. 14905-14916.
[25] D. M. Ostrovskii, A. Lowy, and M. Razaviyayn, Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems, arXiv preprint, arXiv:2002.07919 [math.OC], 2020, https://arxiv.org/abs/2002.07919. · Zbl 1480.91016
[26] H. Rafique, M. Liu, Q. Lin, and T. Yang, Weakly-convex-concave min-max optimization: Provable algorithms and applications in machine learning, Optim. Methods Sofw., in press. · Zbl 1502.90194
[27] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[28] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Science & Business Media, New York, 2009. · Zbl 0888.49001
[29] M. Sion, On general minimax theorems., Pacific J. Math., 8 (1958), pp. 171-176. · Zbl 0081.11502
[30] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh, Efficient algorithms for smooth minimax optimization, in Advances in Neural Information Processing Systems, 2019, pp. 12680-12691.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.