Convergence Rates for the Alternating Minimization Algorithm in Structured Nonsmooth and Nonconvex Optimization
Glaydston C. Bento, Boris S. Mordukhovich, Tiago S. Mota, Antoine Soubeyran · 2026
Read Convergence Rates for the Alternating Minimization Algorithm in Structured Nonsmooth and Nonconvex Optimization by Glaydston C. Bento, Boris S. Mordukhovich, Tiago S. Mota, Antoine Soubeyran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22850.txt.
Introduction
Glaydston C. Bento and three co-authors sharpen the theory of a classic optimization method. The method, alternating minimization, solves a hard problem by fixing one part and improving the other, back and forth. It was set out for structured, non-smooth problems in a noted 2010 work.
The new results give much faster convergence rates under a key condition named in the abstract. In some cases the method can finish in finite steps, or speed up beyond the linear rate known before. Faster guarantees help users trust the method on real problems.
Catalog record
| CREATOR | Glaydston C. Bento, Boris S. Mordukhovich, Tiago S. Mota, Antoine Soubeyran |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-22850
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence Rates for the Alternating Minimization Algorithm in Structured Nonsmooth and Nonconvex Optimization Glaydston C. Bento, Boris S. Mordukhovich, Tiago S. Mota, Antoine Soubeyran Abstract This paper is devoted to developing the alternating minimization algorithm for problems of structured nonconvex optimization proposed by Attouch, Bolté, Redont, and Soubeyran in 2010. Our main result provides significant improvements of the convergence rate of the algorithm, especially under the low exponent Polyak-Łojasiewicz-Kurdyka condition when we establish either finite termination of this algorithm or its superlinear convergence rate instead of the previously known linear convergence. We also investigate the PLK exponent calculus and discuss applications to noncooperative games and behavioral science. MSC Classification]90C26, 49J52, 49J53, 90D10 keywords nonsmooth optimization, alternating minimization algorithm, Polyak-Łojasiewicz-Kurdyka conditions, convergence rates, noncooperative games pacs [ † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. 1 Introduction In this paper, we consider a class of minimization problems for cost functions L:\mathbb{R}^{n}\times\ \mathbb{R}^{m}\to\overline{\mathbb{R}}:=\mathbb{R}\cup\{\infty\} given in the structured form of constrained optimization: \mbox{minimize }\;L(x,y):=f(x)+Q(x,y)+g(y), (1) where f and g are proper lower semicontinuous functions on \mathbb{R}^{n} , not necessarily convex, and where Q is a smooth function that couples the variables x and y . Recall that a function h\colon\mathbb{R}^{n}\to\overline{\mathbb{R}} is proper if {\rm dom}\,h:=\{x\in\mathbb{R}^{n}\;|\;h(x)<\infty\}\neq\emptyset . It has been well recognized that optimization problems in the structural form ( 1 ) appear in many important applications including, in particular, noncooperative games, machine learning, image reconstruction, approximation theory, behavior science, etc.; see attouch2008alternating ; attouch2010proximal ; attouch2007new and the references therein. Our main attention in this paper is paid to the alternative minimization algorithm designed and investigated in attouch2010proximal for nonconvex structured problems of type ( 1 ). The algorithm’s dynamics are described as follows. Let (x_{0},y_{0})\in\mathbb{R}^{n}\times\mathbb{R}^{m} , the sequence is generated iteratively of the form (x_{k},y_{k})\to(x_{k+1},y_{k})\to(x_{k+1},y_{k+1}) by x_{k+1}\in\arg\min\left\{L(u,y_{k})+\frac{1}{2\lambda_{k}}\|u-x_{k}\|^{2}\;\Big|\;u\in\mathbb{R}^{n}\right\}, (2) y_{k+1}\in\arg\min\left\{L(x_{k+1},v)+\frac{1}{2\mu_{k}}\|v-y_{k}\|^{2}\;\Big|\;v\in\mathbb{R}^{m}\right\}. (3) where \{\lambda_{k}\} and \{\mu_{k}\} are positive sequences. This algorithm was originally developed in attouch2008alternating ; attouch2007new for convex and weakly convex problems, while its nonconvex generality explored in attouch2010proximal opened new perspectives and significantly extended the spectrum of important applications to various optimization-related areas. The main results of attouch2010proximal revolve around establishing global convergence and convergence rates of the iterates in ( 2 ) and ( 3 ) under some versions of the ”Kurdyka-Łojasiewicz inequality” as labeled in attouch2010proximal , which we now unify—by following bento2025convergence —under the name of the Polyak-Łojasiewicz-Kurdyka (PLK) conditions ; see Section 2 for the exact formulation, historical remarks, and discussions. Here we provide significant improvements of convergence rates from ( attouch2010proximal , Theorem 11) establishing, in particular, either finite termination or superlinear convergence for the alternating minimization algorithm under the lower exponent PLK condition instead of the linear convergence obtained in attouch2010proximal . Moreover, new convergence rate results are derived for cost function values along the iterative sequence. We also investigate calculus rules for PLK exponents and construct several examples illustrating the revealed phenomena. Finally, some applications to noncooperative games and behavioral science are briefly discussed. The rest of the paper is organized as follows. In Section 2 , we first present the basic assumptions and then formulate and discuss the PLK conditions used in deriving the main results. Section 3 investigates calculus rule for PLK components needed to deal with the structured form ( 1 ). We construct here five examples illustrating some striking PLK phenomena. Section 4 presents our main results about convergence rates of the alternating minimization algorithm under the exponent PLK conditions. Section 5 concerns applications of the main results to some models of noncooperative game theory and behavioral science. 2 Basic Assumptions and PLK Conditions First we formulate the standing assumptions that are used throughout the paper without further mentioning. They are exactly the same as in attouch2010proximal , namely: (\mathcal{H})\begin{cases}L(x,y)=f(x)+Q(x,y)+g(y),&\\ f:\mathbb{R}^{n}\to\overline{\mathbb{R}},&\text{is proper lower semicontinuous,}\\ g:\mathbb{R}^{m}\to\mathbb{R}\to\overline{\mathbb{R}},&\text{is proper lower semicontinuous,}\\ Q:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R},&\text{is a }{\cal C}^{1}-\text{smooth function,}\\ \nabla Q&\hskip-28.45274pt\text{is Lipschitz continuous on bounded subsets of }\mathbb{R}^{n}\times\mathbb{R}^{m},\end{cases} (\mathcal{H}_{1})\begin{cases}\inf_{\mathbb{R}^{n}\times\mathbb{R}^{m}}L>-\infty,\\ \text{the function }L(\cdot,y_{0})\text{ is proper},\\ \text{for some positive }r_{-}<r_{+},\text{ the sequences of stepsizes }\lambda_{k},\mu_{k}\text{ belong to }(r_{-},r_{+}).\end{cases} It is shown in ( attouch2010proximal , Lemma 3.1) that the imposed assumptions ensure that the alternating minimization algorithm in ( 2 ), ( 3 ) is well-defined and enjoys the desired descent property together with other well-posedness properties broadly used in the paper. To present this result, we need to recall the main subdifferential notion for extended-real-valued proper functions used in what follows. Given h\colon\mathbb{R}^{n}\to\overline{\mathbb{R}} and \bar{x}\in{\rm dom}\,h , the limiting/Mordukhovich subdifferential of h at \bar{x} is defined by \partial_{M}h(\bar{x}):=\big\{v\in\mathbb{R}^{n}\;\big|\;\exists x_{k}\stackrel{{\scriptstyle h}}{{\to}}\bar{x},\,v_{k}\in\partial^{F}h(x_{k}),\;v_{k}\to v\big\}, (4) where x_{k}\stackrel{{\scriptstyle h}}{{\to}}\bar{x} means that x_{k}\to\bar{x} and h(x_{k})\to f(x) , and where \partial_{F}h(x):=\Big\{v\in\mathbb{R}^{n}\;\Big|\;\limsup_{u\to x}\frac{h(u)-h(x)-\langle v,u-x\rangle}{\|u-x\|}\geq 0\big\} (5) is known as the regular/Fréchet subdifferential of h at x . It has been realized in variational analysis and optimization that the limiting subdifferential ( 4 ) is a robust construction enjoying comprehensive calculus rules based on variational and extremal principles. On the other hand, the regular subdifferential ( 5 ) doesn’t possess these properties while providing convenient approximation tools for computations. We refer the reader to the monographs mordukhovich2006variational ; mordukhovich2018variational ; rockafellar1998 and the bibliographies therein for variational theories involving ( 4 ), ( 5 ) in finite and infinite dimensions with numerous applications. The aforementioned result of attouch2010proximal is formulated as follows. Lemma 2.1 . Under assumptions (\mathcal{H}) and (\mathcal{H}_{1}) , the sequences \{x_{k}\} and \{y_{k}\} are well-defined. Moreover, the following hold: (i) For all natural numbers k\in\mathbb{N} , we have the inequality L(x_{k},y_{k})+\frac{1}{2\lambda_{k-1}}\|x_{k}-x_{k-1}\|^{2}+\frac{1}{2\mu_{k-1}}\|y_{k}-y_{k-1}\|^{2}\leq L(x_{k-1},y_{k-1}), (6) and therefore the sequence \{L(x_{k},y_{k})\} is not increasing. (ii) We have the convergent series \sum_{k=1}^{\infty}\left(\|x_{k}-x_{k-1}\|^{2}+\|y_{k}-y_{k-1}\|^{2}\right)<\infty, which implies, in particular, that \lim_{k\to\infty}(\|x_{k}-x_{k-1}\|+\|y_{k}-y_{k-1}\|)=0. (iii) For all k\in\mathbb{N} , define (x^{*}_{k},y^{*}_{k}):=\left(\nabla_{x}Q(x_{k},y_{k})-\nabla_{x}Q(x_{k},y_{k-1}),0\right)-\left(\frac{1}{\lambda_{k-1}}(x_{k}-x_{k-1}),\frac{1}{\mu_{k-1}}(y_{k}-y_{k-1})\right). Then we have the inclusion (x^{*}_{k},y^{*}_{k})\in\partial L(x_{k},y_{k}). Furthermore, it follows for any bounded subsequence \{(x_{k_{j}},y_{k_{j}})\} of \{(x_{k},y_{k})\} that (x^{*}_{k_{j}},y^{*}_{k_{j}})\to(0,0)\quad\text{as}\quad k_{j}\to\infty and hence \text{\rm dist}(0,\partial L(x_{k_{j}},y_{k_{j}}))\to 0\quad\text{as}\quad k_{j}\to\infty. Now we are ready to formulate the main conditions for our convergence analysis; cf. attouch2010proximal ; bento2025convergence for more details and references. Definition 2.2 . Let h:\mathbb{R}^{m}\to\overline{\mathbb{R}} be an extended-real-valued lower semicontinuous function. We say that the function h satisfies the (basic) Polyak-Łojasiewicz (PLK) condition at \bar{x}\in{\rm dom}\,h if there exist a number \eta\in(0,\infty) , a neighborhood U of \bar{x} , and a concave continuous function \varphi:[0,\eta]\to[0,\infty) , called the desingularizing function , such that \varphi(0)=0,\quad\varphi\in{\cal C}^{1}(0,\eta),\quad\varphi^{\prime}(s)>0\;\mbox{ for all }\;s\in(0,\eta),\;\mbox{ and }\; (7) \varphi^{\prime}\big(h(x)-h(\bar{x})\big)\mbox{\rm dist}\big(0,\partial h(x)\big)\geq 1\;\mbox{ for all }\;x\in U\cap[h(\bar{x})<h(x)<h(\bar{x})+\eta]. (8) The exponent PLK condition corresponds to ( 7 ) and ( 8 ) where the desingularizing function is chosen as \varphi(t)=Mt^{1-q} with some M>0 and q\in[0,1) . We refer to the case where q\in(0,1/2) as the PLK condition with lower exponents . To the best of our knowledge, the original version of the PLK condition was introduced by Polyak in 1962 (the English translation of his paper was published in polyak1963gradient ), for {\cal C}^{1} -smooth functions h with Lipschitzian gradients in Hilbert spaces, as the inequality \|\nabla h(x)\|\geq(1/2M)|h(x)-h(\bar{x})|^{1/2},\quad M>0. The main motivation and result (Theorem 4 of polyak1963gradient ) were to establish the linear convergence of the classical gradient descent method. Independently, Łojasiewicz Lojasiewicz1963 introduced the inequality‘ \|\nabla h(x)\|\geq b\,|h(x)-h(\bar{x})|^{q},\quad b:=1/M(1-q),\quad q\in[0,1), (9) for analytic functions in the finite-dimensional