An adaptive forward-backward-forward splitting algorithm for solving pseudo-monotone inclusions

Flavia Chorobura, Ion Necoara, Jean-Christophe Pesquet · 2025

Read An adaptive forward-backward-forward splitting algorithm for solving pseudo-monotone inclusions by Flavia Chorobura, Ion Necoara, Jean-Christophe Pesquet (2025) 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-2503-01070.txt.

Introduction

Flavia Chorobura, Ion Necoara, and Jean-Christophe Pesquet present an adaptive splitting algorithm in this 2025 paper. Many optimization tasks reduce to finding a zero of an operator that splits into three parts with different traits. Their target class, pseudo-monotone operators, covers constrained problems such as quadratic programs with smooth convex constraints.

Their method follows a forward-backward-forward pattern with step sizes that adapt on the fly. Under an added smoothness property, they prove a sublinear convergence rate. When the operator is uniformly pseudo-monotone, the rate improves to linear or sublinear depending on a parameter. Early numeric tests show good performance against existing methods and software.

Catalog record

CREATORFlavia Chorobura, Ion Necoara, Jean-Christophe Pesquet
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An adaptive forward-backward-forward splitting algorithm for solving pseudo-monotone inclusions Flavia Chorobura, Ion Necoara, Jean-Christophe Pesquet Abstract In this paper, we propose an adaptive forward-backward-forward splitting algorithm for finding a zero of a pseudo-monotone operator which is split as a sum of three operators: the first is continuous single-valued, the second is Lipschitzian, and the third is maximally monotone. This setting covers, in particular, constrained minimization scenarios, such as problems having smooth and convex functional constraints (e.g., quadratically constrained quadratic programs) or problems with a pseudo-convex objective function minimized over a simple closed convex set (e.g., quadratic over linear fractional programs). For the general problem, we design a forward-backward-forward splitting type method based on novel adaptive stepsize strategies. Under an additional generalized Lipschitz property of the first operator, sublinear convergence rate is derived for the sequence generated by our adaptive algorithm. Moreover, if the sum is uniformly pseudo-monotone, linear/sublinear rates are derived depending on the parameter of uniform pseudo-monotonicity. Preliminary numerical experiments demonstrate the good performance of our method when compared to some existing optimization methods and software. \FUNDING The research leading to these results has received funding from: ITN-ETN project TraDE-OPT funded by the European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skolodowska-Curie grant agreement No. 861137; UEFISCDI, Romania, PN-III-P4-PCE-2021-0720, under project L2O-MOC, nr. 70/2022. keywords Pseudo-monotone operators, forward-backward-forward splitting, adaptive stepsize, convergence analysis, nonconvex optimization. † † manuscriptno: MOOR-0001-2024.00 † † runningauthor: Chorobura, Necoara and Pesquet † † runningtitle: An adaptive forward-backward-forward splitting algorithm for solving pseudo-monotone inclusions † † authors: Automatic Control and Systems Engineering Department, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania and Federal Institute of Education, Science and Technology of Paraná, campus Foz do Iguaçu, Brazil, [email protected] Automatic Control and Systems Engineering Department, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest and Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied Mathematics of the Romanian Academy, 050711 Bucharest, Romania, [email protected] University Paris-Saclay, CentraleSupélec, CVN, Inria, Gif-sur-Yvette, France, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction Let \mathbb{H} be a finite-dimensional real vector space endowed with a scalar product \langle\cdot,\cdot\rangle and the corresponding norm \|\cdot\| . Our goal is to find a zero of a sum of three operators A\colon\mathbb{H}\to\mathbb{H} , B\colon\mathbb{H}\to\mathbb{H} , and C\colon\mathbb{H}\ \to 2^{\mathbb{H}} , that is \displaystyle\text{find}\;\bar{z}\in\mathbb{H}\;\text{such that}\;\;0\in A\bar{z}+B\bar{z}+C\bar{z},\vskip-19.91684pt (1) where A+B+C is pseudo-monotone, and A satisfies some generalized smoothness condition, B is smooth, and C is maximally monotone as detailed in Assumption 3 of Section 3 . Finding a zero of a sum of operators is a very general problem and covers, in particular, constrained optimization, and minimax optimization problems frequently encountered in signal processing [ 25 ] , triangulation in computer vision [ 2 ] , semi-supervised learning [ 15 ] , learning of kernel matrices [ 28 ] , steering direction estimation for RADAR detection [ 20 ] , generative adversarial networks [ 31 ] among others. Previous work. The problem of finding a zero of a sum of operators is considered in many works. For example, [ 8 , 10 , 16 , 17 , 19 , 26 , 39 ] cover the monotone case, while [ 3 , 11 , 35 ] consider the nonmonotone case. In [ 19 , 26 ] all three operators are assumed maximally monotone and, additionally, the first is Lipschitz continuous. Under these settings, algorithms based on resolvent and forward operators, activated one at a time successively, are proposed together with a detailed convergence analysis. Furthermore, finding a zero of a sum of two maximally monotone operators, A+C , such that A is a continuous single-valued operator, is investigated in [ 39 ] and a forward-backward-forward algorithm is proposed (also known as Tseng’s algorithm), where the stepsize is chosen constant when A is Lipschitz or based on an Armijo-Goldstein-type rule, otherwise. Linear rate was derived for this method when A+C is strongly monotone. In [ 3 , 11 , 35 ] , A is assumed Lipschitz continuous, possible nonmonotone, and C is maximally monotone, such that either A+C satisfies the weak Minty condition or a cohypomonotonicity assumption. In particular, [ 35 ] considers an extragradient algorithm with adaptive and constant stepsizes, which reduces, for a specific choice of stepsize, to the forward-backward-forward algorithm in the monotone case. Moreover, [ 11 ] analyzes an optimistic gradient algorithm, while in [ 3 ] algorithms based on classical Halpern and Krasnosel’skii-Mann iterations are analyzed. For all these methods, under suitable assumptions, sublinear rates are derived. Finally, finding a zero of a sum of three operators A+B+C is considered in [ 17 ] , where A,C are maximally monotone and B is Lipschitz continuous and monotone, and asymptotic convergence is proved for an error-tolerant forward-backward-forward algorithm. The forward-backward-forward algorithm was also extended to solve variational inequalities. For example, [ 7 , 38 ] consider a variational inequality, where the operator is Lipschitz continuous, and a (modified) Tseng algorithm is employed with a constant stepsize or an adaptive stepsize, so that it is not necessary to know the Lipschitz constant. Convergence is derived when the operator is pseudo-monotone. Moreover, the Lipschitz assumption on the operator involved in the variational inequality is relaxed in [ 37 ] , the operator being assumed continuous. Then, Tseng’s algorithm is considered with an Armijo-Goldestein rule for the stepsize. Under standard conditions, the weak and strong convergence of the method is obtained in the pseudo-monotone case. Our approach differs from [ 37 ] , as we consider that the operator A satisfies a relaxed Lipschitz condition and we employ Tseng’s algorithm with novel adaptive stepsize rules (e.g., based on the positive root of a polynomial equation). Others methods for solving variational inequalities with a Lipschitz operator in the monotone case were considered e.g., in [ 33 ] and in the nonmonotone case (under weak Minty condition) in [ 21 ] . Furthermore, specific algorithms were also developed for particular classes of variational inequalities, such as convex-concave minimax optimization problems [ 14 , 18 ] . More specifically, these papers address problems of the form: \min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\;\langle Lx,y\rangle+\varphi(x)-\psi(y),\vskip-2.84544pt (2) where \mathcal{X} and \mathcal{Y} are Hilbert spaces, L is a linear operator and \varphi:\mathcal{X}\to\bar{\mathbb{R}}:=\mathbb{R}\cup\{+\infty\} and \psi:\mathcal{Y}\to\bar{\mathbb{R}} are proper, convex, lower semicontinuous functions. For such problems, a primal-dual proximal algorithm is proposed in [ 14 ] for which a sublinear rate is derived in the optimality measure: \displaystyle G(\bar{x},\bar{y})=\max_{y\in\mathcal{Y}}\langle L\bar{x},y\rangle-\psi(y)+\varphi(\bar{x})-\min_{x\in\mathcal{X}}\langle Lx,\bar{y}\rangle+\varphi(x)-\psi(\bar{y}),\vskip-8.5359pt for a given (\bar{x},\bar{y})\in\mathcal{X}\times\mathcal{Y} . An extension of the algorithm from [ 14 ] is given in [ 18 ] , where \varphi is split as \varphi_{1}+\varphi_{2} , with \varphi_{1}:\mathcal{X}\to\mathbb{R} convex, differentiable with a Lipschitz continuous gradient, while \varphi_{2} is a proper, convex, lower semicontinuous function. It is proved that this algorithm converges weakly to a solution to problem ( 2 ) and, if \varphi_{1}=0 , then [ 18 ] recovers the primal–dual algorithm in [ 14 ] . Contributions. In this paper, we propose a method for finding a zero of a sum of three operators, which are not necessarily monotone. For this general problem we design a forward-backward-forward splitting type method based on novel adaptive stepsize strategies and then perform a detailed

Read the complete text