Hedy Attouch
email: attouch@math.univ-montp2.fr

Jérôme Bolte
email: jerome.bolte@tse-eu.fr

Benar Fux Svaiter

Benar Fux

Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods

Keywords: 2010 Mathematics Subject Classification: 34G25, 47J25, 47J30, 47J35, 49M15, 49M37, 65K15, 90C25, 90C53 Nonconvex nonsmooth optimization, semi-algebraic optimization, tame optimization, Kurdyka-Lojasiewicz inequality, descent methods, relative error, sufficient decrease, forward-backward splitting, alternating minimization, proximal algorithms, iterative thresholding, block-coordinate methods, o-minimal structures

Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods

Introduction

Being given a proper lower semicontinuous function f : R n → R ∪ {+∞}, we consider descent methods that generate sequences (x k ) k∈N complying with the following conditions: 1 -for each k ∈ N, f (x k+1 ) + a x k+1x k 2 ≤ f (x k ); -for each k ∈ N, there exists w k+1 ∈ ∂f (x k+1 ) such that

w k+1 ≤ b x k+1 -x k ;
where a, b are positive constants and ∂f (x k+1 ) denotes the set of limiting subgradients of f at x k+1 (see Section 2.1 for a definition). The first condition is intended to model a descent property: since it involves a measure of the quality of the descent, we call it a sufficientdecrease condition (see [START_REF] Burke | Descent methods for composite nondifferentiable optimization problems[END_REF] for an early paper on this subject, [START_REF] Attouch | Local search proximal algorithms as decision dynamics with costs to move, Set Valued and Variational Analysis[END_REF] for an interpretation of this condition in decision sciences, and [START_REF] Lewis | A proximal method for composite minimization[END_REF] for a discussion on this type of condition in a particular nonconvex nonsmooth optimization setting). The second condition originates from the well-known fact that most algorithms in optimization are generated by an infinite sequence of subproblems which involve exact or inexact minimization processes. This is the case of gradient methods, Newton's method, forward-backward algorithm, Gauss-Seidel method, proximal methods... The second set of conditions precisely reflects relative inexact optimality conditions for such minimization subproblems.

When dealing with descent methods for convex functions, it became natural to expect that the algorithm will provide globally convergent sequences (i.e., for arbitrary starting point, the algorithm generates a sequence that converges to a solution). The standard recipe to obtain the convergence is to prove that the sequence is (quasi-)Fejér monotone relative to the set of minimizers of f . This fact has also been used intensively in the study of algorithms for nonexpansive mappings (see e.g. [START_REF] Combettes | Quasi-Fejerian analysis of some optimization algorithms, in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications[END_REF]). When the functions under consideration are not convex (or quasiconvex), the monotonicity properties are in general "broken", and descent methods may provide sequences that exhibit highly oscillatory behaviors. Apparently this phenomenon was first observed by Curry (see [START_REF] Curry | The method of steepest descent for non-linear minimization problems[END_REF]); in the framework of differential equations similar behaviors occur, in [START_REF] Palis | Geometric theory of dynamical systems. An introduction[END_REF] a nonconverging bounded curve of a 2-dimensional gradient system of a C ∞ function is provided, this example was adapted in [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF] to gradient methods.

In order to circumvent such behaviors, it seems necessary to work with functions that present a certain structure. This structure can be of an algebraic nature, e.g. quadratic functions, polynomial functions, real analytic functions, but it can also be captured by adequate analytic assumptions, e.g. metric regularity [START_REF] Aragon | Convergence of the proximal point method for metrically regular mappings[END_REF][START_REF] Lewis | Alternating projection on manifolds[END_REF][START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], cohypomonotonicity [START_REF] Pennanen | Local convergence of the proximal point algorithm and multiplier methods without monotonicity[END_REF][START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF], selfconcordance [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF], partial smoothness [START_REF] Lewis | Active sets, nonsmoothness and sensitivity[END_REF][START_REF] Wright | Identifiable surfaces in constrained optimization[END_REF]. In this paper, our central assumption for the study of such algorithms is that the function f satisfies the (nonsmooth) Kurdyka-Lojasiewicz inequality, which means, roughly speaking, that the functions under consideration are sharp up to a reparametrization (see Section 2.2). The reader is referred to [START_REF] Lojasiewicz | Une propriété topologique des sous-ensembles analytiques réels[END_REF][START_REF] Lojasiewicz | Sur la géométrie semi-et sous-analytique[END_REF][START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] for the smooth cases, and to [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF] for nonsmooth inequalities. Kurdyka-Lojasiewicz inequalities have been successfully used to analyze various types of asymptotic behavior: gradient-like systems [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Haraux | Convergence of solutions of second-order gradient-like systems with analytic nonlinearities[END_REF][START_REF] Huang | Convergence in gradient-like systems which are asymptotically autonomous and analytic[END_REF][START_REF] Lageman | Pointwise convergence of gradient-like systems[END_REF], PDE [START_REF] Simon | Asymptotics for a class of non-linear evolution equations, with applications to geometric problems[END_REF][START_REF] Chill | Convergence to steady states in asymptotically autonomous semilinear evolution equations[END_REF], gradient methods [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF][START_REF] Nesterov | Accelerating the cubic regularization of Newton's method on convex problems[END_REF], proximal methods [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF], projection methods or alternating methods [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Bolte | Alternating proximal algorithm for blind image recovery[END_REF].

In the context of optimization, the importance of Kurdyka-Lojasiewicz inequality is due to the fact that many problems involve functions satisfying such inequalities, and it is often elementary to check that such an inequality is satisfied; real semi-algebraic functions provide a very rich class of functions satisfying the Kurdyka-Lojasiewicz, see [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF] for a thorough discussion on these aspects, and also Section 2.2 for a simple illustration.

Many other functions, that are met in real world problems, and which are not semialgebraic, satisfy very often the Kurdyka-Lojasiewicz inequality. An important class is given by functions definable in an o-minimal structure. The monographs [START_REF] Coste | An introduction to o-minimal geometry[END_REF][START_REF] Van Den Dries | Tame topology and o-minimal structures[END_REF] are good references on o-minimal structures; concerning Kurdyka-Lojasiewicz inequalities in this context the reader is referred to [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]. Functions definable in o-minimal structures or functions whose graphs are locally definable are often called tame functions. We do not give a precise definition of definability in this work, but the flexibility of this concept is briefly illustrated in Example 5.4(b). Functions that are not necessarily tame but that satisfy Lojasiewicz inequality are given in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF], basic assumptions involve metric-regularity and transversality (see also [START_REF] Lewis | Alternating projection on manifolds[END_REF][START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF] and Example 5.5).

From a technical viewpoint, our work blends the approach to nonconvex problems provided in [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF][START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF] with the relative error philosophy developed in [START_REF] Solodov | A hybrid projection-proximal point algorithm[END_REF][START_REF] Solodov | A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator[END_REF][START_REF] Solodov | A unified framework for some inexact proximal point algorithms[END_REF][START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF]. A valuable guideline for the error aspects is the development of an inexact proximal algorithm for equations governed by a monotone operator, and which is based on an estimation of the relative error, see [START_REF] Solodov | A hybrid projection-proximal point algorithm[END_REF][START_REF] Solodov | A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator[END_REF][START_REF] Solodov | A unified framework for some inexact proximal point algorithms[END_REF]. Related results without monotonicity (with a control on the lack of monotonicity) have been obtained in [START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF].

Thus, in summary, this article aims at:

-providing a unified framework for the analysis of classical descent methods, -relaxing exact descent conditions, -extending convergence results obtained in [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF][START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Solodov | A hybrid projection-proximal point algorithm[END_REF][START_REF] Solodov | A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator[END_REF][START_REF] Solodov | A unified framework for some inexact proximal point algorithms[END_REF][START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF] to richer and more flexible algorithms, -providing theorems which cover general nonsmooth problems under easily verifiable assumptions (e.g. semi-algebraicity).

Let us proceed with a more precise description of the contents of this article.

In Section 2, we consider functions satisfying the Kurdyka-Lojasiewicz inequality. We first give the definition and a brief analysis of this basic property. Then in subsection 2.3, we provide an abstract convergence result for sequences satisfying the sufficient-decrease condition and the relative inexact optimality condition mentioned above.

This result is then applied to the analysis of several descent methods with relative error tolerance.

We recover and improve previous works on the question of gradient methods (Section 3) and proximal algorithms (Section 4). Our results are illustrated through semi-algebraic feasibility problems by means of an inexact version of the averaged projection method.

We also provide, in Section 5, an in-depth analysis of forward-backward splitting algorithms in a nonsmooth nonconvex setting. Setting aside the convex case, we did not find any general convergence results for this kind of algorithm, also, the results we present here seem to be new. These results can be applied to general semi-algebraic problems (or tame problems) and to nonconvex problems presenting a well-conditioned structure. An important and enlightening consequence of our study is that the bounded sequences (x k ) k∈N generated by the nonconvex gradient projection algorithm

x k+1 ∈ P C x k - 1 2L ∇h(x k )
are convergent sequences so long as C is a closed semi-algebraic subset of R n and h : R n → R is C 1 semi-algebraic with L-Lipschitz gradient (see [START_REF] Beck | A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems[END_REF] for some applications in signal processing). As an application of our general results on forward-backward splitting, we consider the following type of problem

(P ) min λ x 0 + 1 2 Ax -b 2 : x ∈ R n
where λ > 0 and • 0 is the counting norm (or the ℓ 0 norm), A is an m × n real matrix and b ∈ R m . We recall that for x in R n , x 0 is the number of nonzero components of x. This kind of problem is central in compressive sensing [START_REF] Donoho | Compressed Sensing[END_REF]. In [START_REF] Blumensath | Iterative Thresholding for Sparse Approximations[END_REF][START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF] this problem is tackled by using a "hard iterative thresholding" algorithm

x k+1 ∈ prox γ k λ • 0 x k -γ k (A T Ax k -A T b) ,
where (γ k ) k∈N is a sequence of stepsizes evolving in a convenient interval (the definition of the proximal mapping prox λf is given in Section 4). The convergence results the authors obtained involve different assumptions on the linear operator A: they either assume that A < 1 [START_REF] Blumensath | Iterative Thresholding for Sparse Approximations[END_REF]Theorem 3] or that A satisfies the restricted isometry property [START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF]Theorem 4]. Our results show that convergence actually occurs for any linear map so long as the sequence (x k ) k∈N is bounded. We also consider iterative thresholding with ℓ p "norms" for sparse approximation (in the spirit of [START_REF] Chartrand | Exact Reconstruction of Sparse Signals via Nonconvex Minimization[END_REF]) and hard-constrained feasibility problems; in both cases convergence of the bounded sequences is established.

In a last section, we study the proximal regularization of a p blocks alternating method (with p ≥ 2). This method has been introduced by Auslender [START_REF] Auslender | Asymptotic properties of the Fenchel dual functional and applications to decomposition problems[END_REF] for convex minimization; see also [START_REF] Grippo | Globally convergent block-coordinate techniques for unconstrained optimization[END_REF] in a nonconvex setting. Convergence results for such methods are usually stated in terms of cluster points. To our knowledge, the first convergence result in a nonconvex setting, under fairly general assumptions, was obtained in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF] for a two-blocks exact version. Our generalization is twofolds: we consider methods involving an arbitrary numbers of blocks, and we provide a proper convergence result.

An abstract convergence result for inexact descent methods

The Euclidean scalar product of R n and its corresponding norm are respectively denoted by

•, • and • .

Some definitions from variational analysis

Standard references are [START_REF] Clarke | Nonsmooth analysis and control theory[END_REF][START_REF] Rockafellar | Variational Analysis[END_REF][START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF].

If F : R n ⇉ R m is a point-to-set mapping its graph is defined by Graph F := {(x, y) ∈ R n × R m : y ∈ F (x)},
while its domain is given by dom F := {x ∈ R n : F (x) = ∅}. Similarly, the graph of a real-extended-valued function f : R n → R ∪ {+∞} is defined by

Graph f := {(x, s) ∈ R n × R : s = f (x)},
and its domain by dom f := {x ∈ R n : f (x) < +∞}. The epigraph of f is defined as usual as

epi f := {(x, λ) ∈ R n × R : f (x) ≤ λ}.
When f is a proper function, i.e. when dom f = ∅, the set of its global minimizers, possibly empty, is denoted by argmin

f := {x ∈ R n : f (x) = inf f } .
The notion of subdifferential plays a central role in the following theoretical and algorithm developments.

For each x ∈ dom f , the Fréchet subdifferential of f at x, written ∂f (x), is the set of vectors v ∈ R n which satisfy

lim inf y = x y → x 1 x -y [f (y) -f (x) -v, y -x ] ≥ 0.
When x / ∈ dom f , we set ∂f (x) = ∅. The limiting processes used in an algorithmic context necessitate the introduction of the more stable notion of limiting-subdifferential ( [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF]) (or simply subdifferential) of f . The subdifferential of f at x ∈ dom f , written ∂f (x), is defined as follows

∂f (x) := {v ∈ R n : ∃x k → x, f (x k ) → f (x), v k ∈ ∂f (x k ) → v}.
It is straightforward to check from the definition the following closedness property of ∂f :

Let (x k , v k ) k∈N be a sequence in R n × R n such that (x k , v k ) ∈ Graph ∂f for all k ∈ N. If (x k , v k ) converges to (x, v), and f (x k ) converges to f (x) then (x, v) ∈ Graph ∂f .
These generalized notions of differentiation give birth to generalized notions of critical point. A necessary (but not sufficient) condition for x ∈ R n to be a minimizer of f is ∂f (x) ∋ 0.

(

A point that satisfies (1) is called limiting-critical or simply critical.

We end this section by some words on an important class of functions which are intimately linked to projection mappings: the indicator functions. Recall that if C is a closed subset of R n , its indicator function i C is defined by

i C (x) = 0 if x ∈ C, +∞ otherwise,
where x ranges over R n . Being given x in C, the limiting subdifferential of i C at x is called the normal cone to C at x, it is denoted by N C (x) (for x / ∈ C we set N C (x) = ∅). The projection on C, written P C , is the following point-to-set mapping:

P C : R n ⇉ R n x → P C (x) := argmin { x -z : z ∈ C}.
When C is nonempty, the closedness of C and the compactness of the closed unit ball imply that P C (x) is nonempty for all x in R n .

Kurdyka-Lojasiewicz inequality: the nonsmooth case

We begin this section by a brief discussion on real semi-algebraic sets and functions which will provide a very rich class of functions satisfying the Kurdyka-Lojasiewicz.

Definition 2.1. (a) A subset S of R n is a real semi-algebraic set if there exists a finite number of real polynomial functions P ij , Q ij : R n → R such that

S = p j=1 q i=1 { x ∈ R n : P ij (x) = 0, Q ij (x) < 0}. (b) A function f : R n → R ∪ {+∞} (resp. a point-to-set mapping F : R n ⇉ R m ) is called semi-algebraic if its graph {(x, λ) ∈ R n+1 : f (x) = λ} (resp. {(x, y) ∈ R n+m : y ∈ F (x)}) is a semi-algebraic subset of R n+1 (resp. R n+m ).
One easily sees that the class of semi-algebraic sets is stable under the operation of finite union, finite intersection, Cartesian product or complementation and that polynomial functions are, of course, semi-algebraic functions.

The high flexibility of the concept of semi-algebraic sets is captured by the following fundamental theorem known as Tarski-Seidenberg principle.

Theorem 2.2 (Tarski-Seidenberg). Let A be a semi-algebraic subset of R n+1 , then its canonical projection on R n , namely

{(x 1 , . . . , x n ) ∈ R n : ∃z ∈ R, (x 1 , . . . , x n , z) ∈ A} is a semi-algebraic subset of R n .
Let us illustrate the power of this theorem by proving that max functions associated to polynomial functions are semi-algebraic. Let S be a nonempty semi-algebraic subset of R m and g : R n × R m → R a real polynomial function. Set f (x) = sup{g(x, y) : y ∈ S} (note that f can assume infinite values). Let us prove that f is semi-algebraic.

Using the definition and the stability with respect to finite intersection, we see that the set

{(x, λ, y) ∈ R n × R × S : g(x, y) > λ} = {(x, λ, y) ∈ R n × R × R m : g(x, y) > λ} (R n × R × S) , is semi-algebraic. For (x, λ, y) in R n × R × R m
, define the projection Π(x, λ, y) = (x, λ) and use Π to project the above set on R n × R. One obtains the following semi-algebraic set

{(x, λ) ∈ R n × R : ∃y ∈ S, g(x, y) > λ}.
The complement of this set is

{(x, λ) ∈ R n × R : ∀y ∈ S, g(x, y) ≤ λ} = epi f. Hence epi f is semi-algebraic. Similarly hypo f := {(x, µ) : f (x) ≥ µ} is semi-algebraic hence Graph f = epi f ∩ hypo f is semi-algebraic.
Of course, this result also holds when replacing sup by inf. As a byproduct of these stability results, we recover the following standard result which will be useful for further developments. Lemma 2.3. Let S be a nonempty semi-algebraic subset of R m , then the function

R m ∋ x → dist (x, S) 2 is semi-algebraic.
Proof. It suffices to consider the polynomial function g(x, y) = xy 2 for x, y in R m and to use the definition of the distance function.

The facts that the composition of semi-algebraic mappings gives a semi-algebraic mapping or that the image (resp. the preimage) of a semi-algebraic set by a semi-algebraic mapping is a semi-algebraic set are also consequences of the Tarski-Seidenberg principle. The reader is referred to [START_REF] Benedetti | Real Algebraic and Semialgebraic Sets[END_REF][START_REF] Bochnak | Real Algebraic Geometry[END_REF] for those and many other consequences of this principle.

As already mentioned in the introduction, a prominent feature of semi-algebraic functions is that they admit locally a sharp reparametrization, leading to what we call here Kurdyka-Lojasiewicz inequality. The most fundamental works on this subject are of course due to Lojasiewicz [START_REF] Lojasiewicz | Une propriété topologique des sous-ensembles analytiques réels[END_REF] (1963) and Kurdyka [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] (1998).

We proceed now to a formal definition of this inequality. Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function. For

η 1 , η 2 such that -∞ < η 1 < η 2 ≤ +∞, we set [η 1 < f < η 2 ] = {x ∈ R n : η 1 < f (x) < η 2 } .
The following definition is taken from [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF] (see also [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity[END_REF]). Definition 2.4 (Kurdyka-Lojasiewicz property). (a) The function f : R n → R ∪ {+∞} is said to have the Kurdyka-Lojasiewicz property at x * ∈ dom ∂f if there exist η ∈ (0, +∞], a neighborhood U of x * and a continuous concave function ϕ : [0, η) → R + such that:

(i) ϕ(0) = 0, (ii) ϕ is C 1 on (0, η), (iii) for all s ∈ (0, η), ϕ ′ (s) > 0, (iv) for all x in U ∩ [f (x * ) < f < f (x * ) + η], the Kurdyka-Lojasiewicz inequality holds ϕ ′ (f (x) -f (x * )) dist (0, ∂f (x)) ≥ 1. ( 2
)
(b) Proper lower semicontinuous functions which satisfy the Kurdyka-Lojasiewicz inequality at each point of dom ∂f are called KL functions.

Remark 2.5. (a) One can easily check that the Kurdyka-Lojasiewicz property is automatically satisfied at any non critical point x * ∈ dom ∂f , see for example Lemma 2.1 and Remark 3.2 (b) of [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF]. (b) When f is smooth, finite-valued, and f (x * ) = 0, inequality (2) can be rewritten as

∇(ϕ • f )(x) ≥ 1,
for each convenient x in R n . This inequality may be interpreted as follows: up to the reparametrization of the values of f via ϕ, we face a sharp function. Since the function ϕ is used here to turn a singular region -a region in which the gradients are arbitrarily small-into a regular region, i.e. a place where the gradients are bounded away from zero, it is called a desingularizing function for f . For theoretical and geometrical developments concerning this inequality, see [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity[END_REF]. (c) The concavity assumption imposed on the function ϕ does not explicitly belong to the usual formulation of the Kurdyka-Lojasiewicz inequality. However this inequality holds in many instances with a concave function ϕ, see [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF] for illuminating examples.

(d) It is important to observe that the KL inequality implies that the critical points lying in

U ∩ [f (x * ) < f < f (x * ) + η] have the same critical value f (x * ).
Among real-extended-valued lower-semicontinuous functions, typical KL functions are semi-algebraic functions or more generally functions definable in an o-minimal structure, see [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Bolte | A nonsmooth Morse-Sard theorem for subanalytic functions[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]. References on functions definable in an o-minimal structure are [START_REF] Coste | An introduction to o-minimal geometry[END_REF][START_REF] Van Den Dries | Tame topology and o-minimal structures[END_REF]. Such examples are abundantly commented in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF], and they strongly motivate the present study. Other types of examples based on more analytical assumptions like uniform convexity, transversality or metric regularity can be found in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF], inequality (8.7) of [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], and Remark 3.6.

An inexact descent convergence result for KL functions

In this section, a and b are fixed positive constants. Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function. In the sequel, we consider sequences (x k ) k∈N which satisfy the following conditions, which we will subsequently refer to as H1, H2, H3:

H1. (Sufficient decrease condition). For each k ∈ N, f (x k+1 ) + a x k+1 -x k 2 ≤ f (x k );
H2. (Relative error condition). For each k ∈ N, there exists w k+1 ∈ ∂f (x k+1 ) such that

w k+1 ≤ b x k+1 -x k ;

H3. (Continuity condition).

There exists a subsequence (x k j ) j∈N and x such that

x k j → x and f (x k j ) → f (x), as j → ∞.
The next sections feature several important methods that force the sequences to satisfy the three conditions. Conditions H1 and H2 have been commented in the introduction; concerning condition H3, it is important to note that f itself is not required, in general, to be continuous or even continuous on its domain. Indeed, as we will see in the next sections, the nature of some algorithms (e.g. forward-backward splitting, Gauss-Seidel methods) forces the sequences to comply with condition H3 under a simple lower semicontinuity assumption.

The following abstract result is at the core of our convergence analysis.

Lemma 2.6. Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function which satisfies the Kurdyka-Lojasiewicz property at some x * ∈ R n . Denote by U , η and ϕ : [0, η) → R + the objects appearing in the Definition 2.4 of the KL property at x * . Let δ, ρ > 0 be such that B(x * , δ) ⊂ U with ρ ∈ (0, δ).

Consider a sequence (x k ) k∈N which satisfies conditions H1, H2. Assume moreover that

f (x * ) ≤ f (x 0 ) < f (x * ) + η, (3)
x

* -x 0 + 2 f (x 0 ) -f (x * ) a + b a ϕ(f (x 0 ) -f (x * )) < ρ, (4)
and ∀k ∈ N, x k ∈ B(x * , ρ) ⇒ x k+1 ∈ B(x * , δ) with f (x k+1 ) ≥ f (x * ). (5)
Then, the sequence

(x k ) k∈N satisfies ∀k ∈ N, x k ∈ B(x * , ρ), +∞ k=0 x k+1 -x k < +∞, f (x k ) → f (x * ), as k → ∞,
and converges to a point

x ∈ B(x * , δ) such that f (x) ≤ f (x * ).
If the sequence (x k ) k∈N also satisfies condition H3, then x is a critical point of f , and

f (x) = f (x * ).
Proof. The key point is to establish the following claim: for j = 1, 2, . . .

x j ∈ B(x * , ρ), (6)
and

j i=1 x i+1 -x i + x j+1 -x j ≤ x 1 -x 0 + b a ϕ(f (x 1 ) -f (x * )) -ϕ(f (x j+1 ) -f (x * )) . ( 7
)
Concerning the above claim, first note that condition H1 implies that the sequence (f (x k )) k∈N is nonincreasing, which by (3) gives f (x j+1 ) ≤ f (x 0 ) < f (x * ) + η. On the other hand, by assumption (5), the property

x j ∈ B(x * , ρ) implies f (x j+1 ) ≥ f (x * ). Hence, the quantity ϕ(f (x j+1 ) -f (x * )) appearing in (7) makes sense.
Let us observe beforehand that, for all k ≥ 1, the set ∂f (x k ) is nonempty, and therefore x k belongs to dom f . As we already noticed, condition H1 implies that the sequence (f (x k )) k∈N is nonincreasing, and it immediately yields

x k+1 -x k ≤ f (x k ) -f (x k+1 ) a , ∀k ∈ N. ( 8
) Fix k ≥ 1. We claim that if f (x k ) < f (x * ) + η and x k ∈ B(x * , ρ), then 2 x k+1 -x k ≤ x k -x k-1 + b a ϕ(f (x k ) -f (x * )) -ϕ(f (x k+1 ) -f (x * )) . (9)
If x k+1 = x k this inequality holds trivially. So, we assume that x k+1 = x k . In this case, using ( 5) and ( 8), we conclude that f (x k ) > f (x k+1 ) ≥ f (x * ) which, combined with KL inequality and H2 shows that w k = 0 and x k-1 = x k . Since w k ∈ ∂f (x k ), using (again) KL inequality and H2, we obtain

ϕ ′ (f (x k ) -f (x * )) ≥ 1 w k ≥ 1 b x k -x k-1 .
The concavity assumption on ϕ, ϕ ′ > 0, [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF], and H1 imply

ϕ(f (x k ) -f (x * )) -ϕ(f (x k+1 ) -f (x * )) ≥ϕ ′ (f (x k ) -f (x * ))(f (x k ) -f (x k+1 )) ≥ϕ ′ (f (x k ) -f (x * ))a x k+1 -x k 2 .

Direct combination of the two above inequalities yields

b a ϕ(f (x k ) -f (x * )) -ϕ(f (x k+1 ) -f (x * )) ≥ x k+1 -x k 2 x k -x k-1 .
Multiplying this inequality by x kx k-1 , taking the square root on both sides and using inequality 2 √ αβ ≤ α + β, we conclude that inequality ( 9) is satisfied.

Let us prove claims ( 6), ( 7) by induction on j. From ( 5) with k = 0, we obtain that x 1 ∈ B(x * , δ) and f (x 1 ) ≥ f (x * ). Using now [START_REF] Auslender | Asymptotic properties of the Fenchel dual functional and applications to decomposition problems[END_REF] with k = 0, we have

x 1 -x 0 ≤ f (x 0 ) -f (x 1 ) a ≤ f (x 0 ) -f (x * ) a . (10)
Combining the above equation with assumption (4), and using the triangle inequality we obtain

x * -x 1 ≤ x * -x 0 + x 0 -x 1 ≤ x * -x 0 + f (x 0 ) -f (x * ) a < ρ,
which expresses that x 1 belongs to B(x * , ρ). Direct use of ( 9) with k = 1 shows that (7) holds with j = 1. Suppose that ( 6) and ( 7) hold for some j ≥ 1. Then, using the triangle inequality and (7) we have

x * -x j+1 ≤ x * -x 0 + x 0 -x 1 + j i=1 x i+1 -x i ≤ x * -x 0 + 2 x 0 -x 1 + b a ϕ(f (x 1 ) -f (x * )) -ϕ(f (x j+1 ) -f (x * )) .
Using the above inequality, [START_REF] Benedetti | Real Algebraic and Semialgebraic Sets[END_REF] and assumption (4) we conclude that x j+1 ∈ B(x * , ρ). Hence, (9) holds with k = j + 1, i.e.

2 x (j+1)+1 -x j+1 ≤ x j+1 -x j + b a ϕ(f (x j+1 ) -f (x * )) -ϕ(f (x (j+1)+1 ) -f (x * )) .
Adding the above inequality with (7) (with k = j) yields ( 7) with k = j + 1, which completes the induction proof.

Direct use of [START_REF] Attouch | Local search proximal algorithms as decision dynamics with costs to move, Set Valued and Variational Analysis[END_REF] shows that j i=1

x i+1 -x i ≤ x 1 -x 0 + b a ϕ(f (x 1 ) -f (x * )).
Therefore, ∞ i=1

x i+1x i < +∞ which implies that the sequence (x k ) k∈N converges to some x. From H2 and (5) (note that ϕ concave yields ϕ ′ decreasing) we infer that w k → 0 and f

(x k ) → β ≥ f (x * ). If β > f (x * )
then using Definition 2.4, (2) we have

ϕ ′ (β -f (x * )) w k ≥ 1, k = 0, 1, . . . which is absurd, because w k → 0. Therefore β = f (x * ) and, since f is lower semicontinuous, f (x) ≤ β = f (x * ).
To end the proof, note that if the sequence (x k ) k∈N satisfies H3, then x = x, x is critical and f

(x) = lim k→∞ f (x k ) = f (x * ).
Corollary 2.7. Let f , x * , ρ, δ be as in the previous Lemma. For q ≥ 1, consider a finite family x 0 , . . . , x q which satisfies H1 and H2, conditions (3), ( 4) and

∀k ∈ {0, . . . , q}, x k ∈ B(x * , ρ) ⇒ x k+1 ∈ B(x * , δ) with f (x k+1 ) ≥ f (x * ) .
Then x j ∈ B(x * , ρ) for all j = 0, . . . , q.

Proof. Simply reproduce the beginning of the proof of the previous lemma.

Corollary 2.8. If we replace the assumption (5) in Lemma 2.6 by the set of assumptions,

η < a(δ -ρ) 2 , (11)
f (x k ) ≥ f (x * ), ∀k ∈ N, (12)
the conclusion remains unchanged.

Proof. It suffices to prove that ( 11) and ( 12) implies [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF]. Let x k ∈ B(x * , ρ). By H1, we have

x k+1 -x k ≤ f (x k ) -f (x k+1 ) a ≤ η a < δ -ρ. Hence x k+1 -x * ≤ x k+1 -x k + x k -x * < δ.
Lemma 2.6 and its corollaries have several important consequences that we now proceed to discuss. Theorem 2.9 (Convergence to a critical point). Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function. Consider a sequence (x k ) k∈N that satisfies H1, H2, and H3.

If f has the Kurdyka-Lojasiewicz property at the cluster point x specified in H3 then the sequence (x k ) k∈N converges to x = x as k goes to infinity, and x is a critical point of f . Moreover the sequence (x k ) k∈N has a finite length, i.e.

+∞ k=0

x k+1x k < +∞.

Proof. Let x = x be a cluster point of (x k ) k∈N as given by H3 (i.e., x k j → x and f (x k j ) → f (x)). Since (f (x k )) k∈N is a nonincreasing sequence (a direct consequence of H1), we deduce that f (x k ) → f (x) and f (x k ) ≥ f (x) for all integers k. The function f has the KL property around x, hence there exist ϕ, U, η as in Definition 2.4. Let δ > 0 be such B(x, δ) ⊂ U , ρ ∈ (0, δ). If necessary, shrink η so that η < a(δρ) 2 . Use the continuity property of ϕ to obtain the existence of an integer k 0 such that:

f (x k ) ∈ [f (x), f (x) + η) for all k ≥ k 0 and x -x k 0 + 2 f (x k 0 ) -f (x) a + b a ϕ(f (x k 0 ) -f (x)) < ρ.
Since f (x k ) ≥ f (x) for all integers k, the conclusion follows by applying Corollary 2.8 to the sequence (y k ) k∈N defined by y k = x k 0 +k for all integers k. As it will be shown later on, sequences complying with conditions H1, H2 and H3 are not necessarily generated by a local model (see Section 6) and therefore the proximity of the starting point x 0 with a local minimizer x * does not imply, in general, that the limit point of the sequence lies in a neighbourhood of x * .

However, under the following specific assumption, we can establish a convergence result to a local minimizer.

H4: For any δ > 0 there exist 0 < ρ < δ and ν > 0 such that

x ∈ B(x * , ρ), f (x) < f (x * ) + ν y / ∈ B(x * , δ) ⇒ f (x) < f (y) + a y -x 2 .
Theorem 2.10 (Local convergence to local minima). Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function which has the KL property at some local minimizer x * . Assume that H4 holds at x * . Then, for any r > 0, there exist u ∈ (0, r) and µ > 0 such that the inequalities

x 0 -x * < u, f (x * ) < f (x 0 ) < f (x * ) + µ,
imply that any sequence (x k ) k∈N starting from x 0 , that satisfies H1, H2 has the finite length property, remains in B(x * , r) and converges to some

x ∈ B(x * , r) critical point of f with f (x) = f (x * ).
Proof. Take r > 0. Since x * is a local minimum (hence critical) and f satisfies the Kurdyka-Lojasiewicz property, there exist η 0 ∈ (0, +∞], δ ∈ (0, r), and a continuous concave function ϕ : [0, η 0 ) → R + such that:

ϕ(0) = 0, -ϕ is C 1 on (0, η 0 ), -for all s ∈ (0, η 0 ), ϕ ′ (s) > 0.

for all x in B(x

* , δ) ∩ [f (x * ) < f < f (x * ) + η 0 ], the Kurdyka-Lojasiewicz inequality holds ϕ ′ (f (x) -f (x * )) dist (0, ∂f (x)) ≥ 1. ( 13
)
for all x in B(x

* , δ), f (x) ≥ f (x * ). ( 14
)
We infer from assumption H4 that there exist ρ ∈ (0, δ) and ν > 0 such that

x ∈ B(x * , ρ), f (x) < f (x * ) + ν y / ∈ B(x * , δ) ⇒ f (x) < f (y) + a y -x 2 . ( 15
)
Set η = min{η 0 , ν} and let k ∈ N. If x k is such that f (x k ) < f (x * ) + η and x kx * < ρ then H4, together with H1, implies that x k+1 ∈ B(x * , δ), and thus that f (x k+1 ) ≥ f (x * ) (recall that x * is a local minimizer on B(x * , δ)). That's precisely property (5) of Lemma 2.6. Choose u, µ > 0 such that

u < ρ/3, µ < η, 2 µ a + b a ϕ(µ) < 2ρ 3 .
If x 0 satisfies the set of inequalities x 0x * < u and f (x * ) < f (x 0 ) < f (x * ) + µ we therefore have

x * -x 0 + 2 f (x 0 ) -f (x * ) a + b a ϕ(f (x 0 ) -f (x * )) < ρ.
which is precisely property (4) of Lemma 2.6. Using Lemma 2.6 we conclude that the sequence (x k ) k∈N has the finite length property, remains in B(x * , ρ), converges to some x ∈ B(x

* , δ), f (x k ) → f (x * ) and f (x) ≤ f (x * ). Since f (x * ) is the minimum value of f in B(x * , δ), f (x) = f (x *
) and the sequence (x k ) k∈N has also property H3. So, x is a critical point of f .

Remark 2.11. Let us verify that Condition H4 is satisfied when x * ∈ dom f is a local minimum and the function f satisfies the following global growth condition:

f (y) ≥ f (x * ) - a 4 y -x * 2 for all y ∈ R n . ( 16
)
Let δ > ρ and ν be positive real numbers. Take y ∈ R n such that yx * ≥ δ and x ∈ R n such that xx * ≤ ρ and f (x) < f (x * ) + ν. From ( 16), and the triangle inequality we infer

f (y) ≥ f (x) -ν - a 4 y -x * 2 ≥ f (x) -ν - a 2 y -x * 2 + a 4 y -x * 2 ≥ f (x) -ν -a y -x 2 -a x -x * 2 + a 4 y -x * 2 ≥ f (x) -ν -a y -x 2 -aρ 2 + a 4 δ 2 .
Hence

f (y) + a y -x 2 ≥ f (x) + -ν -aρ 2 + a 4 δ 2 for all y ∈ R n . (17)
We conclude by noticing that -νaρ 2 + a 4 δ 2 is nonnegative for ρ and ν sufficiently small. We end this section by a result on the convergence toward a global minimum similar to [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF], Theorem 3.3. Observe that, in this context, the set of global minimizers may be a continuum.

Theorem 2.12 (Local convergence to global minima). Let f : R n → R ∪ {+∞} be a lower semicontinuous function which has the KL property at some x * , a global minimum point of f .

For each r > 0, there exist u ∈ (0, r), µ > 0 such that the inequalities

x 0 -x * < u, min f < f (x 0 ) < min f + µ
imply that any sequence (x k ) k∈N that satisfies H1, H2 and which starts from x 0 satisfies

(i) x k ∈ B(x * , r), ∀k ∈ N, (ii) x k converges to some x and +∞ k=1 x k+1 -x k < +∞, (iii) f (x) = min f .
Proof. It is a straightforward variant of Theorems 2.9 and 2.10.

Inexact gradient methods

The first natural domain of application of our previous results concerns the simplest firstorder methods, namely the gradient methods. As we shall see, our abstract framework (Theorem 2.9) allows to recover some of the results of [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF]. In order to illustrate the versatility of our algorithmic framework, we also consider a fairly general semi-algebraic feasibility problem, and we provide, in the line of [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], a local convergence proof for an inexact averaged projection method.

General convergence result

Let f : R n → R be a C 1 function whose gradient is Lipschitz continuous with constant L (or L-Lipschitz continuous). We consider the following algorithm.

Algorithm 1 Take some positive parameters a, b with a > L. Fix x 0 in R n . For k = 0, 1, . . . consider:

∇f (x k ), x k+1 -x k + a 2 x k+1 -x k 2 ≤ 0, ( 18
) ∇f (x k ) ≤ b x k+1 -x k . ( 19
)
To illustrate the variety of dynamics covered by Algorithm 1, let us show how variable metric gradient algorithms can be cast in this framework. Consider a sequence (A k ) k∈N of symmetric positive definite matrices in R n×n such that for each k ∈ N the eigenvalues

λ k i of A k satisfy 0 < λ ≤ λ k i ≤ λ,
where λ and λ are given thresholds. For each integer k, consider the following subproblem built on a second-order model of f around the point

x k : minimize ∇f (x k ), u -x k + 1 2 A k (u -x k ), u -x k : u ∈ R n .
This type of quadratic models arises, for instance, in trust-region methods (see [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF] which is also connected to Lojasiewicz inequality). When solving the above problem exactly, we obtain the following method

x k+1 = x k -(A k ) -1 ∇f (x k ), which satisfies ∇f (x k ), x k+1 -x k + λ x k+1 -x k 2 ≤ 0, ( 20
) ∇f (x k ) ≤ λ x k+1 -x k . ( 21
)
So long as λ > L 2 , the sequence (x k ) k∈N falls into the general category delineated by Algorithm 1.

For the convergence analysis of Algorithm 1, we shall of course use the elementary but important descent lemma (see for example [START_REF] Ortega | Iterative solutions of nonlinear equations in several variables[END_REF] 3.2.12). Lemma 3.1 (Descent lemma). Let f : R n → R be a function and C a convex subset of R n with nonempty interior. Assume that f is C 1 on a neighborhood of each point in C and that ∇f is L-Lipschitz continuous on C. Then, for any two points x, u in C,

f (u) ≤ f (x) + ∇f (x), u -x + L 2 u -x 2 . ( 22
)
We then have the following result:

Theorem 3.2. Assume that f : R n → R is a C 1 function with L-Lipschitz continuous gradient, and that f is bounded from below. If f is a KL function, then each bounded sequence (x k ) k∈N generated by Algorithm 1 converges to some critical point x of f . Moreover, the sequence (x k ) k∈N has a finite length, i.e. k x k+1x k < +∞.

Proof. Applying the descent lemma at points u = x k+1 and x = x k , inequality (18) becomes

f (x k+1 ) -f (x k ) + a -L 2 x k+1 -x k 2 ≤ 0.
Since a > L, condition H1 of Theorem 2.9 is satisfied. To see that H2 is satisfied, use the Lipschitz continuity property of ∇f and ( 19) to obtain

∇f (x k+1 ) ≤ ∇f (x k+1 ) -∇f (x k ) + ∇f (x k ) ≤ (L + b) x k+1 -x k .
The sequence (x k ) k∈N has been assumed to be bounded. Thus it admits a converging subsequence, and, by continuity of f , H3 is trivially fulfilled. We can therefore apply theorem 2.9 to conclude.

Remark 3.3. The conclusion of Theorem 3.2 remains unchanged if the assumption that ∇f is Lipschitz continuous on R n and f is a KL function are replaced by the assumptions: There exists a closed subset S of R n such that (i) ∇f is L-Lipschitz continuous on co S;

(ii) x k ∈ S for all k ∈ N;

(iii) f satisfies the KL inequality at each point of S,

where co S denotes the convex envelope of S. The result is evident from the proof. Just notice that the L-Lipschitz continuity of ∇f on co S is needed in order to apply the descent lemma.

Prox-regularity

When considering nonconvex feasibility problems, we are led to consider squared distance functions to nonconvex sets. Contrary to what happens in the standard convex setting, such functions may fail to be differentiable. If we want to handle feasibility problems through gradient methods (e.g. Algorithm 1), this lack of regularity causes serious trouble. The key concept of prox-regularity provides a characterization of the local differentiability of these functions and, as we will see in the next section, it allows in turn to design averaged projection methods with interesting converging properties.

A closed subset F of R n is prox-regular if its projection operator P F is single-valued around each point x in F (see [53, Theorem 1.3, (a) ⇔ (f )]). Prominent examples of prox-regular sets are closed convex sets and C 2 submanifolds of R n (see [START_REF] Poliquin | Local differentiability of distance functions[END_REF] and references therein).

Set g(x) = 1 2 dist (x, F ) 2 and assume that F is prox-regular. Let us gather the following definition/properties concerning F that are fundamental for our purpose.

Theorem 3.4 ([53]

). Let F be a closed prox-regular set. Then for each x in F there exists r > 0 such that: (a) The projection P F is single-valued on B(x, r), (b) the function g is C 1 on B(x, r) and ∇g(x) = x -P F (x), (c) the gradient mapping ∇g is 1-Lipschitz continuous on B(x, r).

Item (c) is not explicitly developed in [START_REF] Poliquin | Local differentiability of distance functions[END_REF], a proper proof can be found in [42, Proposition 8.1].

Averaged projections for feasibility problems

Let F 1 , . . . , F p be nonempty closed semi-algebraic, prox-regular subsets of R n such that

p i=1 F i = ∅.
A classical approach to the problem of finding a common point to the sets F 1 , . . . , F p is to find a global minimizer of the function f : R n → [0, +∞)

f (x) := 1 2 p i=1 dist (x, F i ) 2 , (23)
where dist (•, F i ) is the distance function to the set F i .

As one can easily verify, in the convex case, the averaged projection method corresponds exactly to an explicit gradient method applied to the function 1 p f . In a nonconvex setting, we are thus led to study the following algorithm: Inexact averaged projection algorithm Take θ ∈ (0, 1), α < 1 2 and M > 0 such that

1 -α θ > 1 2 . ( 24
)
Given a starting point x 0 in R n , consider the following algorithm

x k+1 ∈ (1 -θ) x k + θ 1 p p i=1 P F i (x k ) + ǫ k , (25)
where (ǫ k ) k∈N is a sequence of errors which satisfies

ǫ k , x k+1 -x k ≤ α x k+1 -x k 2 (26)
ǫ k ≤ M x k+1 -x k (27)
for all k ∈ N.

We then have the following result.

Theorem 3.5 (Inexact averaged projection method). Let F 1 , . . . , F p be semi-algebraic, and prox-regular subsets of R n which satisfy

p i=1 F i = ∅.
If x 0 is sufficiently close to p i=1 F i , then the inexact averaged projection algorithm reduces to the gradient method

x k+1 = x k - θ p ∇f (x k ) + ǫ k ,
with f being given by [START_REF] Clarke | Nonsmooth analysis and control theory[END_REF], which therefore defines a unique sequence. Moreover, this sequence has a finite length and converges to a feasible point x, i.e. such that

x ∈ p i=1 F i .
Proof. Let us first observe that the function f (given by ( 23)) is semi-algebraic, because the distance function to any nonempty semi-algebraic set is semi-algebraic (see Lemma 2.3 or [START_REF] Van Den Dries | Tame topology and o-minimal structures[END_REF][START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF]). This implies in particular that f is a KL function (see the end of Section 2.2). Take a point x * in ∩ p 1 F i and use Theorem 3.4 to obtain δ > 0 such that, for each i = 1, . . . , p, (a) the projection P F i is single-valued on B(x * , δ),

(b) the function g i := 1 2 dist (•, F i ) 2 is C 1 on B(x * , δ) and ∇g i (x) = x -P F i (x),
(c) the gradient mapping ∇g i is 1-Lipschitz continuous on B(x * , δ).

Since the function f has the KL property around x * , there exist ϕ, U, η as in Definition 2.4. Shrinking δ if necessary, we may assume that B(x * , δ) ⊂ U . Take ρ ∈ (0, δ) and shrink η so that η <

1 -2α 2p (δ -ρ) 2 . ( 28
)
Choose a starting point x 0 such that: 0 = f (x * ) ≤ f (x 0 ) < η and

x * -x 0 + 2 f (x 0 ) a + b a ϕ(f (x 0 )) < ρ. ( 29
) Introduce a = p( 1-α θ -1 2 ) > 0 (cf (24)) and b = p 1 + 1+M θ .
Let us prove by induction that the averaged projection algorithm defines a unique sequence that satisfies:

-Conditions H1 and H2 of Section 2.3 with respect to the function f and the constants a, b,

-x k ∈ B(x * , ρ) for all integers k ≥ 0.
The case k = 0 follows from [START_REF] Donoho | Compressed Sensing[END_REF]. Before proceeding, note that, if a point x belongs to B(x * , δ), we have

∇f (x) = p i=1 (x -P F i (x)).
Using Cauchy-Schwarz inequality (one may as well use the convexity of • 2 ), we obtain

∇f (x) 2 ≤ p i=1 x -P F i (x) 2 (30)
≤ p p i=1 x -P F i (x) 2 = 2pf (x).
Let k ≥ 0. Assume now that x k ∈ B(x * , ρ) and properties H1, H2 hold for the k + 1-uple x 0 , . . . , x k . Using Theorem 3.4, the inclusion (25) defining x k+1 may be rewritten as follows

x k+1 = x k - θ p ∇f (x k ) + ǫ k ,
hence x k+1 is uniquely defined. The above equality yields (note that θ ∈ (0, 1) and p ≥ 1)

x k+1 -x k 2 -2 x k+1 -x k , ǫ k + ǫ k 2 ≤ ∇f (x k ) 2 ,
thus, in view of ( 26), ( 28) and ( 30),

x k+1 -x k 2 ≤ 2p 1 -2α f (x k ) ≤ (δ -ρ) 2 . ( 31
)
Since x k+1x * ≤ x k+1x k + x kx * , this implies that x k+1 ∈ B(x * , δ). Using ( 26) and ( 27), let us verify that property H1 is satisfied for x 0 , x 1 , . . . , x k+1 . We have

∇f (x k ), x k+1 -x k = p θ (x k -x k+1 ) + ǫ k , x k+1 -x k ≤ - p θ (1 -α) x k+1 -x k 2 .
By Theorem 3.4, we know that ∇f is p-Lipschitz on B(x * , δ); we can thus combine the above inequality with the descent lemma to obtain

f (x k+1 ) + 2 p θ (1 -α) -p 2 x k+1 -x k 2 ≤ f (x k ), that is f (x k+1 ) + a x k+1 -x k 2 ≤ f (x k ),
which is exactly property H1. On the other hand we have

∇f (x k+1 ) ≤ ∇f (x k+1 ) -∇f (x k ) + ∇f (x k ) ≤ p x k+1 -x k + p θ ( x k+1 -x k + ǫ k ) ≤ p 1 + 1 + M θ x k+1 -x k , = b x k+1 -x k
where the second inequality comes from the Lipschitz property of ∇f and the definition of the sequence, while the last one follows from the error stepsize inequality, namely [START_REF] Curry | The method of steepest descent for non-linear minimization problems[END_REF]. Property H2 is therefore satisfied. Applying now Corollary 2.7, we get x k+1 ∈ B(x * , ρ) and our induction proof is complete. As a consequence, the algorithm defines a unique sequence that satisfies the assumption of Lemma 2.6 (or Theorem 3.2), hence it generates a finite length sequence which converges to a point x such that f (x) = 0. Remark 3.6. In [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], a paper that inspired the above development, the authors establish similar results for sets F i having a linearly regular intersection at some point x, an important concept that originates from [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF]Theorem 2.8]. A linearly regular intersection at x means that the equation

p i=1 y i = 0, with y i ∈ N F i (x)
admits y i = 0, ∀i = 1, . . . , p as a unique solution.

An important fact, tightly linked to the convergence result for averaged projections given in [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF]Theorem 7.3], is that the objective f (x) :=

1 2 i dist (x, F i ) 2 satisfies the inequality ∇f (x) 2 ≥ cf (x),
where x is in a neighborhood of x and with c being a positive constant (see [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF]Proposition 8.6]). One recognizes the Lojasiewicz inequality with a desingularizing function of the form ϕ(s) = 2 √ c √ s with s ≥ 0.

Inexact proximal algorithm

Let us first recall the exact version of the proximal algorithm for nonconvex functions [START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF][START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF]. Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function which is bounded from below, and λ a positive parameter. It is convenient to introduce formally the proximal correspondence prox λf : R n ⇉ R n , which is defined through the formula

prox λf x := argmin f (y) + 1 2λ y -x 2 : y ∈ R n .
Note that for any µ > 0, we have prox λ(µf ) = prox (λµ)f , so that these objects may be simply denoted by prox λµf .

In view of the assumption inf f > -∞, the lower semicontinuity of f and the coercivity of the squared norm imply that prox λf has nonempty values. Observe finally that, contrary to the case when f is convex, we generally do not face here a single-valued operator.

The classical proximal algorithm writes

x k+1 ∈ prox λ k f (x k ), ( 32
)
where λ k is a sequence of stepsize parameters lying in an interval [λ, λ] ⊂ (0, +∞), and

x 0 ∈ R n .
Writing successively the definition of the proximal operator and the associated first optimality condition (use the sum rule [START_REF] Rockafellar | Variational Analysis[END_REF]), we obtain

f (x k+1 ) + 1 2λ k x k+1 -x k 2 ≤ f (x k ) ( 33
)
w k+1 ∈ ∂f (x k+1 ); ( 34
)
λ k w k+1 + x k+1 -x k = 0. ( 35
)

Convergence of an inexact proximal algorithm for KL functions

Let us introduce an inexact version of the proximal point method. Consider the sequence (x k ) k∈N generated by the following algorithm:

Algorithm 2: Take x 0 ∈ R n , 0 < λ ≤ λ < ∞, 0 ≤ σ < 1, 0 < θ ≤ 1. For k = 0, 1, . . . , choose λ k ∈ [λ, λ], and find x k+1 ∈ R n , w k+1 ∈ R n such that f (x k+1 ) + θ 2λ k x k+1 -x k 2 ≤ f (x k ) ( 36
)
w k+1 ∈ ∂f (x k+1 ); ( 37
)
λ k w k+1 + x k+1 -x k 2 ≤ σ( λ k w k+1 2 + x k+1 -x k 2 ). ( 38
)
The error criterion ( 38) is a particular case of the error criterion considered in [START_REF] Solodov | A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator[END_REF], but here, contrary to [START_REF] Solodov | A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator[END_REF], we are not dealing with a maximal monotone operator and no extra-gradient step is performed. In our setting, condition [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] can be replaced by a weaker condition: for some positive b > 0

λ k w k+1 ≤ b x k+1 -x k . ( 39
)
The fact that Algorithm 2 is an inexact version of the proximal algorithm is transparent: the first inequality [START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF] reflects the fact that a sufficient decrease of the value must be achieved, while the last lines [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF], [START_REF] Lageman | Pointwise convergence of gradient-like systems[END_REF] both correspond to an inexact optimality condition.

The following elementary Lemma is useful for the convergence analysis of the algorithm.

x + y 2 ≤ σ( x 2 + y 2 ), (40)
then 1 -σ 2 ( x 2 + y 2 ) ≤ -x, y .
Assuming moreover σ ∈ (0, 1)

1 -1 -(1 -σ) 2 1 -σ y ≤ x ≤ 1 + 1 -(1 -σ) 2 1 -σ y .
Proof. Note that ( 40) is equivalent to

x 2 + 2 x, y + y 2 ≤ σ( x 2 + y 2 ).
Direct algebraic manipulation of the above inequality yields the first inequality. For proving the second and third inequalities, combine the above inequality with Cauchy-Schwarz inequality to obtain

(1 -σ) x 2 -2 x y + (1 -σ) y 2 ≤ 0
Viewing the left-hand side of the above inequality as a quadratic function of x y yields the conclusion.

The main result of this section is the following theorem. Theorem 4.2 (Inexact proximal algorithm). Let f : R n → R ∪ {+∞} be a proper lower semicontinuous KL function which is bounded from below. Assume that the restriction of f to its domain is a continuous function. If a sequence (x k ) k∈N generated by Algorithm 2 (or by [START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF], [START_REF] Kruger | About regularity of collections of sets[END_REF] and (39)) is bounded, then it converges to some critical point x of f . Moreover the sequence (x k ) k∈N has a finite length, i.e. k x k+1x k < +∞.

Proof. First use Lemma 4.1 to conclude that condition [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] implies [START_REF] Lageman | Pointwise convergence of gradient-like systems[END_REF]. Therefore, we assume that (36), ( 37) and (39) holds. If (x k ) k∈N is bounded, there exists a subsequence (x k j ) and x such that

x k j → x as j → ∞.
Since f is continuous on its effective domain and f (x

k j ) ≤ f (x 0 ) < +∞ for all j, we conclude that f (x k j ) → f (x) as j → ∞.
We can now apply Theorem 2.9, and thus obtain the convergence of the sequence (x k ) k∈N to a critical point of f .

A variant for convex functions

When the function under consideration is convex and satisfies the Kurdyka-Lojasiewicz property, Algorithm 2 can be simplified while its convergence properties are maintained. Let f : R n → R ∪ {+∞} be a proper lower semicontinuous convex function. Consider the sequence (x k ) k∈N generated by the following algorithm.

Algorithm 2bis: Take 0 < λ ≤ λ < ∞, 0 ≤ σ < 1. For k = 0, 1, . . . , choose λ k ∈ [λ, λ] and find x k+1 ∈ R n , w k+1 ∈ R n such that w k+1 ∈ ∂f (x k+1 ), (41)
λ k w k+1 + x k+1 -x k 2 ≤ σ( λ k w k+1 2 + x k+1 -x k 2 ). (42)
Before stating our main results, let us establish some elementary inequalities. We claim that for each k

f (x k+1 ) + 1 -σ 2λ x k+1 -x k 2 + (1 -σ)λ 2 w k+1 2 ≤ f (x k ), (43)
and

w k+1 ≤ 1 + 1 -(1 -σ) 2 λ(1 -σ) x k+1 -x k . (44)
For proving [START_REF] Lewis | A proximal method for composite minimization[END_REF], use the convexity of f and inclusion (41) to obtain

f (x k ) ≥ f (x k+1 ) + x k -x k+1 , w k+1 .
Using the above inequality, the algebraic identity

x k -x k+1 , w k+1 = 1 2λ k [ λ k w k+1 2 + x k+1 -x k 2 -λ k w k+1 + x k+1 -x k 2 ]
and [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], we obtain

f (x k ) ≥ f (x k+1 ) + 1 -σ 2 λ k w k+1 2 + 1 λ k x k+1 -x k 2 . ( 45
)
Combining this inequality with the assumption λ ≤ λ k ≤ λ yields [START_REF] Lewis | A proximal method for composite minimization[END_REF]. Equation [START_REF] Lojasiewicz | Une propriété topologique des sous-ensembles analytiques réels[END_REF] follows from Lemma 4.1, inequality [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF] and assumption λ ≤ λ k ≤ λ.

Theorem 4.3. Let f : R n → R ∪ {+∞} be a proper convex lower semicontinuous. Assume that f is a KL function which is bounded from below and let (x k ) k∈N be a sequence generated by Algorithm 2bis.

If (x k ) k∈N is bounded, then it converges to a minimizer of f and the sequence of values f (x k ) converges to the program value min f . Moreover, the sequence has a finite length, i.e.

k x k+1 -x k < +∞.
Proof. Since f is bounded from below, it follows from (43) and σ < 1 that

+∞ k=1 x k+1 -x k 2 < +∞, +∞ k=1 w k 2 < +∞. Therefore w k → 0 as k → +∞.
Since (x k ) has been assumed to be bounded, there exists a subsequence (x k j ) which converges to some x. By [START_REF] Lewis | A proximal method for composite minimization[END_REF] and σ < 1, we also see that the sequence (f (x k )) is decreasing. From this property and the lower semicontinuity of f , we deduce that

f (x) ≤ lim inf j→∞ f (x k j ) = lim k→∞ f (x k ).
Using the convexity of f and the inclusion w k ∈ ∂f (x k ) for k ≥ 1, we obtain

f (x) ≥ f (x k j ) + x -x k j , w k j , j = 2, 3, . . . .
Passing to the limit, as j → ∞, in the above inequality we conclude that

f (x) ≥ lim k→∞ f (x k ). Therefore f (x) = lim k→∞ f (x k ) = lim j→∞ f (x k j ).
Then use ( 43), ( 44) and Theorem 2.9 to obtain the convergence of the sequence (x k ) to x. From w k ∈ ∂f (x k ), w k → 0 as k → +∞, and the closedness property of ∂f , we deduce that ∂f (x) ∋ 0, which expresses that x is a minimizer of f . Remark 4.4. (a) As mentioned in the introduction, many functions encountered in finitedimensional applications are of semi-algebraic (or tame) nature and are thus KL functions. So are in particular many convex functions: this fact was a strong motivation for the above result.

(b) Building a convex function that does not satisfy the Kurdyka-Lojasiewicz property is not easy. It is however possible to do so in dimension 2 (see [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity[END_REF]), but such functions must somehow have an highly oscillatory collection of sublevel sets (a behavior which is unlikely as far as applications are concerned).

Inexact forward-backward algorithm

Let f : R n → R ∪ {+∞} be a proper lower semicontinuous function which is bounded from below, and which satisfies the Kurdyka-Lojasiewicz property. We assume that f is a structured function that can be split as

f = g + h (46)
where h : R n → R is a C 1 function whose gradient ∇h is Lipschitz continuous (note that this is not a restrictive assumption on f , one can for example take h = 0 and g = f ). The Lipschitz constant of ∇h is denoted by L. This kind of structured problem occurs frequently, see for instance [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Attouch | A parallel splitting method for coupled monotone inclusions[END_REF] and Example 5.4.

We consider sequences generated according to the following algorithm:

Algorithm 3: Take a, b > 0 with a > L. Take x 0 ∈ dom g. For k = 0, 1, . . . , find

x k+1 ∈ R n , v k+1 ∈ R n such that g(x k+1 ) + x k+1 -x k , ∇h(x k ) + a 2 x k+1 -x k 2 ≤ g(x k ); (47)
v k+1 ∈ ∂g(x k+1 ); (48)
v k+1 + ∇h(x k ) ≤ b x k+1 -x k . ( 49
)
This section is divided into three distinct parts. In a first part, we recall what is the classical forward-backward algorithm and explain how Algorithm 3 provides an inexact version of the latter; the special case of projection methods is also discussed. In a second part, we provide a general convergence result for KL functions. We end this section by providing illustrations of our results through problems coming from compressive sensing, and hardconstrained feasibility problems.

The forward-backward splitting algorithm for nonconvex functions

Let us further assume that g is bounded from below. Being given a sequence of positive parameters γ k that satisfies

0 < γ < γ k < γ < 1 L
where γ and λ are given thresholds, the forward-backward splitting algorithm reads

x k+1 ∈ prox γ k g (x k -γ k ∇h(x k )). ( 50
)
An important observation here is that the sequence is not uniquely defined since prox γ k g may be multivalued; a surprising fact is that this freedom in the choice of the sequence does not impact the convergence properties of the algorithm (see Theorem 5.1).

Let us show how this algorithm fits into the general framework of Algorithm 3. By definition of the proximal operator we have

γ k g(x k+1 ) + 1 2 x k+1 -x k + γ k ∇h(x k ) 2 ≤ γ k g(x k ) + 1 2 γ k ∇h(x k ) 2 ,
which after simplification gives

γ k g(x k+1 ) + 1 2 x k+1 -x k 2 + γ k ∇h(x k ), x k+1 -x k ≤ γ k g(x k ). Thus g(x k+1 ) + ∇h(x k ), x k+1 -x k + 1 2γ x k+1 -x k 2 ≤ g(x k ),
so that the sufficient-decrease condition [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF] holds (that's where we precisely use γ < 1 L ). Writing down the optimality condition yields

γ k v k+1 + γ k ∇h(x k ) + x k+1 -x k = 0
where v k+1 ∈ ∂g(x k+1 ). Dividing by γ k , we end up with

v k+1 + ∇h(x k ) = 1 γ k x k+1 -x k ≤ 1 γ x k+1 -x k ,
which is the inexact optimality conditions announced in [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF].

As for the proximal algorithm, the inexact version offers some flexibility in the choice of x k+1 by relaxing both the descent condition and the optimality conditions.

Gradient projection algorithm Let us specialize the forward-backward splitting algorithm to functions of the form i C + h (where C is a nonempty closed subset of R n ). For all positive λ, we have the elementary equality prox λ i C x = P C (x).

We thus find the nonconvex nonsmooth gradient-projection method

x k+1 ∈ P C (x k -γ k ∇h(x k )). ( 51
)

Convergence of an inexact forward-backward splitting algorithm

Let us now return to the general inexact forward-backward splitting Algorithm 3, and show the following convergence result.

Theorem 5.1 (Nonconvex nonsmooth forward-backward splitting). Let f = g + h : R n → R ∪ {+∞} be a proper lower semicontinuous KL function which is bounded from below. Assume further that h : R n → R is finite valued, differentiable, has a L-Lipschitz continuous gradient, and that the restriction of g to its domain is continuous. If (x k ) k∈N is a bounded sequence generated by Algorithm 3, then it converges to some critical point of f = g + h.

Moreover, the sequence (x k ) k∈N has a finite length, i.e. k x k+1x k < +∞. Proof. Using the descent lemma for the C 1 function h at x k+1 and x k , and the sufficient decrease property [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF] of Algorithm 3, we obtain

g(x k+1 ) + h(x k+1 ) + a -L 2 x k+1 -x k 2 ≤g(x k+1 ) + h(x k ) + x k+1 -x k , ∇h(x k ) + a 2 x k+1 -x k 2 ≤g(x k ) + h(x k ). Therefore, setting ã = a -L > 0 we have f (x k+1 ) + ã 2 x k+1 -x k 2 ≤ f (x k ). ( 52
)
Define

w k+1 = v k+1 + ∇h(x k+1 ).
The classical derivation rule for the sum, see [START_REF] Rockafellar | Variational Analysis[END_REF], and property (48) of Algorithm 3 yield

w k+1 ∈ ∂f (x k+1 ). (53)
Moreover, by property (49) of Algorithm 3, and the triangle inequality, we obtain

w k+1 ≤ v k+1 + ∇h(x k ) + ∇h(x k+1 ) -∇h(x k ) ≤b x k+1 -x k + L x k+1 -x k .
We are precisely in the case which has been examined in Theorem 4.2 (continuous functions on their domain).

Remark 5.2. (a) For the exact forward-backward splitting algorithm the continuity assumption concerning g is useless. Indeed in that case, we have for all u in R n

γ k g(x k+1 ) + 1 2 x k+1 -x k + γ k ∇h(x k ) 2 ≤ γ k g(u) + 1 2 u -x k + γ k ∇h(x k ) 2 , so that g(x k+1 ) + 1 2γ k x k+1 -x k 2 + x k+1 -x k , ∇h(x k ) ≤ g(u) + 1 2γ k u -x k 2 + u -x k , ∇h(x k ) .
(54) Let x k j be a subsequence of x k which converges to x. Take u = x, k = k j in (54) and let j → +∞. Since x k+1x k → 0, we obtain lim sup k→+∞ g(x k+1 ) ≤ g(x), and, since g is lower semicontinuous, lim g(x k j ) = g(x). The end of the proof is the same that the one of Theorem 5.1.

(b) Forward-backward splitting algorithms have many applications to parallel splitting of coupled systems. For applications involving monotone operators one may consult [START_REF] Attouch | A parallel splitting method for coupled monotone inclusions[END_REF].

An important consequence of the above result is a general convergence result for gradient projection methods. Theorem 5.3 (Nonconvex gradient projection method). Let h : R n → R be a differentiable function whose gradient is L-Lipschitz continuous, and C a nonempty closed subset of R n . Being given ǫ ∈ (0, 1 2L ) and a sequence of stepsizes γ k such that ǫ < γ k < 1 Lǫ, we consider a sequence (x k ) k∈N that complies with

x k+1 ∈ P C (x k -γ k ∇h(x k )), with x 0 ∈ C. If the function h + i C is a KL function and if (x k ) k∈N is bounded, then the sequence (x k ) k∈N converges to a point x * in C such that ∇h(x * ) + N C (x * ) ∋ 0. Proof. It is a direct consequence of Remark 5.2 (a).
As mentioned in the Introduction and in Section 2.2, the assumption that h + i C is a KL function is very general. For instance, when h is C 1 semi-algebraic and C is a nonempty closed semi-algebraic set, h+i C is a KL function and the above result applies. Let us also emphasize here that our convergence result, contrary to those of Theorem 3.5 and [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF], do not rely on any regularity properties of the set C (in the sense of variational analysis). In particular, C does not need to be prox-regular so that the projection mapping may be multi-valued in any neighborhood of C.

Examples

Example 5.4 (Forward-backward splitting for compressive sensing). (a) The central issue in compressive sensing is to recover sparse solutions of under-determined linear systems (see [START_REF] Donoho | Compressed Sensing[END_REF]). The model problem is the following (P ) min{ x 0 : Ax = b} where • 0 is the counting norm (or the ℓ 0 norm), A = 0 is an m × n real matrix and b ∈ R m . We recall that for x in R n , x 0 is the number of nonzero components of x.

As in [START_REF] Blumensath | Iterative Thresholding for Sparse Approximations[END_REF], we proceed in the spirit of Tikhonov regularization for the least squares method. Fix a parameter λ > 0. We aim at solving the nonsmooth nonconvex problem:

(P ′ ) min{λ x 0 + 1 2 Ax -b 2 }.
If we set g(x) = λ x 0 and h(x) =1 2 Axb 2 , it is straightforward to check that the topological assumptions of Remark 5.2(a) are satisfied (observe indeed that • 0 is lower semicontinuous). To see that g + h is a KL function, we simply note that h is a polynomial function and that • 0 has a piecewise linear graph, hence the sum g + h is semi-algebraic. Consider now the proximal operator prox γλ • 0 ( 1 ). When n = 1, the counting norm is denoted by | • | 0 ; in that case one easily establishes that

prox γλ|•| 0 u =    u if |u| > √ 2γλ {0, u} if |u| = √ 2γλ 0 otherwise.
When n is arbitrary, trivial algebraic manipulations yield, with u = (u 1 , . . . , u

n ) ∈ R n , prox γλ • 0 u = (prox λγ|•| 0 u 1 , . . . , prox γλ|•| 0 u n ),
and thus prox γλ • 0 is a perfectly known object. Let • F denote the Frobenius norm in R m×n . Applying the previous result (Remark 5.2(a)) to the bounded sequences generated by the thresholding process

x k+1 ∈ prox γ k λ • 0 x k -γ k (A T Ax k -A T b) where 0 < γ < γ k < γ < 1 ||A T A|| F , shows that the sequence (x k ) k∈N converges to a critical point of λ x 0 + 1 2 Ax -b 2 , i.e. towards a point x * that satisfies (A T Ax * ) i = (A T b) i ,
for all i such that x * i = 0. As mentioned in the introduction, these results offer a complementary view to the theoretical develoments of [START_REF] Blumensath | Iterative Thresholding for Sparse Approximations[END_REF][START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF]. They also provide at the same time a very general convergence result which can be immediately generalized to compressive sensing problems involving semialgebraic or real-analytic nonlinear measurements.

(b) Alternative approaches to (P ) are based on the following approximation

(P ′′ ) min{λ x p + 1 2 Ax -b 2 },
where p is in (0, 1) and x p = n 1 |x i | p (see [START_REF] Chartrand | Exact Reconstruction of Sparse Signals via Nonconvex Minimization[END_REF]). Some encouraging numerical results have been reported in [START_REF] Chartrand | Exact Reconstruction of Sparse Signals via Nonconvex Minimization[END_REF]. In [START_REF] Bredies | Minimization of non-smooth, non-convex functionals by iterative thresholding[END_REF] some theoretical results in the framework of Hilbert spaces are announced but, even when the space is finite dimensional, no convergence result and no estimate result are provided.

Using the separable structure of • p , the computation of the proximal operator prox γλ • p can be reduced to the one dimensional minimization problem: for u ∈ R, find x solution of min 2γλ|x| p + (xu) 2 : x ∈ R , that can be solved numerically by standard methods. Thus the forward-backward splitting algorithm may be run in a simple way. To obtain convergence, the only nontrivial fact that has to be checked is that f = λ x p + 1 2 Axb 2 is a KL function. For this, we recall that there exists a (polynomially bounded) o-minimal structure that contains the family of functions {x α : x > 0, α ∈ R} and restricted analytic functions (see [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]Example (5), p. 505 and Property 5.2 p. 513]). As a consequence, the results of [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF] apply and f is a KL function with a desingularizing function of the form ϕ(s) = cs θ where c > 0, θ ∈ [0, 1). Hence the previous convergence and estimate results apply to the algorithm

x k+1 ∈ prox λγ k • p (x k -γ k (A T Ax k -A T b)),
and to its inexact counterparts (note that g(•) = • p is continuous and that γ k is taken as in remark (a) above).

Example 5.5 (Hard-constrained feasibility problems). Let F, F 1 , . . . , F p be a finite collection of nonempty closed subsets of R n , and assume that F 1 , . . . , F p are convex sets. The hard constraint F is not supposed to be convex. We consider the following minimization problem min 1 2

p i=1 ω i dist (x, F i ) 2 : x ∈ F ,
where ω i are positive constants such that i ω i = 1. By applying the forward-backward splitting algorithm to this problem, we aim at finding a point which satisfies the hard constraints modelled by F , while the other constraints are satisfied in a possibly weaker sense (see [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] and references therein). Set

h(x) = 1 2 p i=1 ω i dist (x, F i ) 2 .
By a standard convex analysis result, each function h i (x) = 1 2 dist (x, F i ) 2 is C 1 convex, and its gradient, equal to ∇h i (x) = x -P F i (x), is Lipschitz continuous with Lipschitz constant equal to 1. By convex combination, the same property holds true for h, and we can take L = 1 as a Lipschitz constant of ∇h. Thus the forward-backward splitting algorithm (gradient-projection) (50) reads: Take 0 < θ < θ < 1. Take x 0 ∈ R n . For k = 0, 1, ...,

x k+1 ∈ P F (1 -θ k )x k + θ k p i=1 P F i (x k ) , (55)
where

θ k ∈ [θ, θ].
Let us consider successively the convergence properties of this algorithm in two different situations, which are based respectively on the concepts of semi-algebraic sets, and linear regular intersection.

Theorem 5.6. Assume that the sets F, F 1 , . . . , F p are semi-algebraic. Let (x k ) k∈N be a sequence generated by the forward-backward splitting algorithm [START_REF] Simon | Asymptotics for a class of non-linear evolution equations, with applications to geometric problems[END_REF]. If (x k ) k∈N is bounded, and x 0 is sufficiently close to the intersection of the sets F, F 1 , . . . , F p , then the sequence (x k ) k∈N converges to a point which lies in the intersection of the sets F, F 1 , . . . , F p .

Proof. The proof relies on the fact that the underlying function

f (x) = i F (x) + 1 2 p i=1 ω i dist (x, F i ) 2 , x ∈ R n , (56)
is a KL function. This follows immediately from the fact that the distance function to a semialgebraic set is semi-algebraic (see Lemma 2.3) and hence satisfies KL. Then apply Theorem 5.1 to obtain the finite length property and the convergence of the sequence (x k ) k∈N to a critical point of f . Then by direct application of the local convergence to global minima Theorem 2.12, we obtain the convergence of the sequence (x k ) k∈N to a point which lies in the intersection of the sets F, F 1 , . . . , F p .

Let us now consider the KL analysis in the regular intersection case (see definition in Remark 3.6). To this end, we will use the following result [START_REF] Lewis | Local linear convergence for alternating and averaged nonconvex projections[END_REF]Proposition 8.5] (based itself on a characterization given in [START_REF] Kruger | About regularity of collections of sets[END_REF]).

Lemma 5.7. Let C 1 , . . . , C m be closed subsets of R n whose intersection is nonempty. Let x ∈ ∩ i C i . Assume that the intersection of C 1 , . . . , C m is linearly regular at x. Then, there exists a positive constant α such that for each x sufficiently close to x, we have:

α m i=1 y i 2 ≤ m i=1 y i , ∀(y 1 , . . . , y m ) ∈ N C 1 (x) × . . . × N Cm (x). ( 57
)
We shall see below that this property entails that the function

f (x) = i F (x) + 1 2 p i=1 dist (x, F i ) 2 , x ∈ R n , (58)
satisfies the KL inequality. Thus, in that case, we are led to consider the algorithm obtained by applying to f the forward-backward splitting algorithm [START_REF] Ortega | Iterative solutions of nonlinear equations in several variables[END_REF], which gives: Take 0 < θ < θ < 1 p . Take x 0 ∈ R n . For k = 0, 1, ...,

x k+1 ∈ P F (1 -θ k )x k + θ k p i=1 P F i (x k ) , (59)
where θ k ∈ [θ, θ].

Theorem 5.8. Assume that the sets F, F 1 , . . . , F p have a linearly regular intersection around a point x and that one of them is a compact set. If x 0 is sufficiently close to x, then the sequence (x k ) k∈N generated by the algorithm (59) converges to a point which lies in the intersection of the sets F, F 1 , . . . , F p .

Proof. The convergence proof can be obtained like in Theorem 5.1 by using Theorem 2.12.

We simply need to verify that the function f , as defined by [START_REF] Solodov | A unified framework for some inexact proximal point algorithms[END_REF], satisfies the KL inequality.

Let K be a compact neighborhood of x on which (57) holds. Take x in K; we have

∂ f (x) = N F (x) + p i=1 (x -P F i (x)).
For each i = 1, . . . , p, set y i = (x -P F i (x)) and observe that y i ∈ N F i (x). If x is in dom ∂ f where c is a positive constant. This shows that f is a KL function.

6 An inexact regularized Gauss-Seidel method Fix an integer p ≥ 2, and let n 1 , . . . , n p be positive integers. The current vector x belongs to the product space R n 1 × . . . × R np , it is denoted by x = (x 1 , . . . , x p ), where each x i belongs to R n i . We are concerned with the minimization of functions f : R n 1 × . . . × R np → R ∪ {+∞} having the following structure

f (x) = Q(x 1 , . . . , x p ) + p i=1 f i (x i ), ( 60
)
where Q is a C 1 function with locally Lipschitz continuous gradient, and f i : R n i → R∪{+∞} is a proper lower semicontinuous function, i = 1, 2, ..., p.

For each i in {1, . . . , p}, we consider a bounded sequence of symmetric positive definite matrices (B k i ) k∈N of size n i . We assume that the eigenvalues of the matrices {B k i : k ∈ N, i ∈ {1, . . . , p}} are bounded away from zero. Our model algorithm is the following.

A proximal modification of the Gauss-Seidel method (see [START_REF] Auslender | Asymptotic properties of the Fenchel dual functional and applications to decomposition problems[END_REF]) Take a starting point x 0 = (x 0 1 , . . . , x 0 p ) in R n 1 × . . . × R np and consider the alternating with a fixed byte-length. We provided practical examples where the approximated solution of the minimization subproblems within the proposed error tolerance is feasible in a single step. Moreover, we also supplied stopping criteria for the solution of the minimization subproblems in general. The computational implementation of the methods analyzed in this paper, as well as these stopping rules are topics for future research.

Lemma 4 . 1 .

 41 Let σ ∈ (0, 1]. If x, y ∈ R n , and

α min{ z 2 + m i=1 y i 2 :

 2 (i.e., ∂ f (x) = ∅), use Lemma 5.7 and inequality (57) to obtain dist (0, ∂ f (x)) = min{ z + m i=1 y i : z ∈ N F (x)} ≥ z ∈ N F (x)}

Recall that prox γλ • 0 = prox (γλ) • 0 = prox γ(λ • 0 )

Partially supported by CNPq grants 474944/2010-7, 303583/2008-8, FAPERJ grant E-26/102.821/2008 and PRONEX-Optimization.

minimizing procedure. For x k being given in R n 1 × . . . × R np construct x k+1 as follows

Successively for i = 2, . . . , p -1:

Set x k+1 = (x k+1 1 , . . . , x k+1 p ).

Remark 6.1. When B k i = 0 for all integers i and k, which is not allowed in our framework, one recovers the classical Gauss-Seidel model. When B k i = α k I where α k is a positive real number and I is the identity matrix, we recover the exact methods studied in [START_REF] Auslender | Asymptotic properties of the Fenchel dual functional and applications to decomposition problems[END_REF][START_REF] Grippo | Globally convergent block-coordinate techniques for unconstrained optimization[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality[END_REF]. Some ingredients of our approach (like the sufficient decrease condition) can be found in [START_REF] Wright | Accelerated block-coordinate relaxation for regularized optimization[END_REF], where a block-coordinate relaxation method with proximal linearized subproblems is used for solving similar structured minimization problems.

Let us now introduce an inexact version of the above alternating method.

Algorithm 4 Take 0 < λ < λ < ∞. For each i in {1, . . . , p}, take a sequence of symmetric positive definite matrices (A k i ) k∈N of size n i such that the eigenvalues of each

. Take some positive parameters b i (i = 1, . . . , p). Take a starting point

where i ranges over {1, . . . , p}.

Elementary computations show that the model algorithm ( 61)-( 62)-( 63) is a special instance of Algorithm 4.

Convergence analysis of the regularized Gauss-Seidel method

Using the differentiation rules for separable functions, we obtain

Assume that the sequence (x k ) k∈N is bounded, and denote by L the Lipschitz constant of ∇Q on a product of balls B1 × . . . × Bp containing the sequence (x k ) k∈N . For all i = 1, . . . , p, we have

Therefore, for some M > 0,

Summing inequalities of the type (64) from i = 1 to i = p, and using the inequalities λ u 2 ≤ A k i u, u for all integers i and k, we conclude that

We are in position to apply Theorem 2.9 to obtain Theorem 6.2 (Proximal regularization of Gauss-Seidel method). Assume that f defined in ( 60) is a KL function which is bounded from below. Let (x k ) k∈N be a sequence generated by Algorithm 4. If (x k ) k∈N is bounded, then it converges to some critical point x of f . Moreover the sequence (x k ) k∈N has a finite length, i.e. k x k+1x k < +∞.

Remark 6.3 (Convex minimization).

Observe that this result is new even in the context of convex optimization where this problem was considered first (see the seminal work [START_REF] Auslender | Asymptotic properties of the Fenchel dual functional and applications to decomposition problems[END_REF] and the recent study [START_REF] Attouch | Alternating Proximal Algorithms for Weakly Coupled Convex Minimization Problems. Applications to Dynamical Games and PDE's[END_REF]). Indeed it allows both to choose a general smooth convex coupling term Q and to adapt the geometry of the proximal operators (through the choice of a metric A k i ) to the geometry of the problem. Due to the fact that a convex function has at most one critical value, the bounded sequences generated by the above algorithms converge to a global minimizer.

Conclusion

Very often, iterative minimization algorithms rely on inexact solution of minimization subproblems, whose exact solution may be almost as difficult to obtain as the solution of the original minimization problem.

Even when the minimization subproblem can be solved with high accuracy, its solutions are mere approximations of the solution of the original problems. In these cases, over-solving the minimization subproblems would increase the computational burden of the method, and may slow down the final computation of a good approximation of the solution. On the other hand, under-solving the minimization subproblems may result in a breakdown of the algorithm, and convergence to a solution may be lost.

In this paper we gave theoretical basis for the application of numerical methods for minimizing a class of functions (which satisfies the KL inequality). In particular our abstract scheme was designed to handle relative errors because practical methods always involve numerical approximation, e.g., the representation of a real number in floating points numbers