João Carlos

O Souza

Paulo Roberto Oliveira
email: poliveir@cos.ufrj.br

Antoine Soubeyran
email: antoine.soubeyran@gmail.com

Global convergence of a proximal linearized algorithm for difference of convex functions

Keywords: Global optimization, Proximal linearized algorithm, DC functions, Rate of convergence

A proximal linearized algorithm for minimizing difference of two convex functions is proposed. If the sequence generated by the algorithm is bounded it is proved that every cluster point is a critical point of the function under consideration, even if the auxiliary minimizations are performed inexactly at each iteration. Linear convergence of the sequence is established under suitable additional assumptions.

Introduction

It is well known that the class of Proximal Point Algorithm (PPA) is one of the most studied methods for finding zeros of maximal monotone operators and, in particular, it is used to solve convex optimization problems. The classical PPA was introduced into optimization literature by Martinet [START_REF] Martinet | Regularisation d'inéquations variationelles par approximations succesives[END_REF]. It is based on the notion of proximal mapping introduced earlier by Moreau [START_REF] Moreau | Proximité et dualité dans un espace Hilbertien[END_REF]. The PPA was popularized by Rockafellar [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF], who showed that, in the context of maximal monotone operators, the following algorithm 0 ∈ c k T (x k+1 ) + x k+1x k [START_REF] Martinet | Regularisation d'inéquations variationelles par approximations succesives[END_REF] converges to a point satisfying 0 ∈ T (x * ), under mild assumptions, even if the auxiliary minimizations are performed inexactly, which is an important consideration in practice. In particular, if

T (•) = ∂ f (•)
, where f is a convex function, then (1) becomes

x k+1 = arg min x∈R n { f (x) + 1 2c k ||x -x k || 2 } (2)
and the sequence converges to a point x * ∈ arg min f (x). The algorithm is useful, however, only for convex problems, because the idea underlying the results is based on the monotonicity of subdifferential operators of convex functions. Therefore, PPA for nonmonotone operators (or nonconvex functions) has been investigated by many authors in different contexts; see, for instance [START_REF] Kaplan | Proximal point methods and nonconvex optimization[END_REF][START_REF] Hare | Computing proximal points of nonconvex functions[END_REF][START_REF] Otero | Proximal methods in reflexive Banach spaces without monotonicity[END_REF][START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF][START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] and references therein. As remarked in Rockafellar [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF], for a proximal point method to be practical, it is also important that it should work with approximate solutions of the subproblems. Since then, there has been a growing interest in inexact versions of proximal methods and many works appeared, treating the problem under different perspectives; see [START_REF] Iusem | Inexact variants of the proximal point algorithm without monotonicity[END_REF][START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Burachik | A relative error tolerance for a family of generalized proximal point methods[END_REF][START_REF] Solodov | Error bounds for proximal point subproblems and associated inexact proximal point algorithms[END_REF][START_REF] Solodov | A unified framework for some inexact proximal point algorithms[END_REF][START_REF] Zaslavski | Convergence of a proximal point method in the presence of computational errors in Hilbert spaces[END_REF] and references therein. Recently, Bento and Soubeyran [START_REF] Bento | Generalized inexact proximal algorithms: Routine's formation with resistance to change, following worthwhile changes[END_REF] discussed how "generalized" proximal point algorithms can be a nice tools to modelize the dynamics of human behaviours on the context of the "variational rationality approach", Soubeyran [START_REF] Soubeyran | Variational rationality. Human behaviors as worthwhile stay and change transitions, possibly ending in traps, before reaching desires[END_REF]. Sun et al. [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF] proposed a proximal point algorithm for minimization of a class of nonconvex functions called DC functions, i.e., difference of two convex functions, which use convex properties of the two convex functions separately. Moudafi and Maingé [START_REF] Moudafi | On the convergence of an approximate proximal method for d.c. functions[END_REF] proposed an alternative proof of the main result of [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF]. It is also considered in [START_REF] Moudafi | On the convergence of an approximate proximal method for d.c. functions[END_REF] an interesting result in the case where the second component of the DC function is differentiable. Souza and Oliveira [START_REF] Souza | A proximal point algorithm for DC functions on Hadamard manifolds[END_REF] extended this algorithm in the context of Hadamard manifolds considering inexact computations of each proximal iteration. DC functions defined on R n , briefly DC(R n ), form an important class of functions, both from a theoretical point of view (see [START_REF] Hartman | On functions representable as a difference of convex functions[END_REF][START_REF] Bomze | Necessary conditions for local optimality in difference-of-convex programming[END_REF][START_REF] Horst | DC programming: overview[END_REF][START_REF] Hiriart-Urruty | Generalized differentiabity, duality and optimization for problems dealing with difference of convex functions, Convexity and Duality in Optimization[END_REF]) and for algorithmic purposes (see [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF][START_REF] Pham | Algorithms for solving a class of nonconvex optimization problems: methods of subgradient[END_REF][START_REF] Ferrer | Solving DC programs using the cutting angle method[END_REF]). Thus, the interest in the theory of DC functions has much increased in the last years. DC optimization algorithms have been proved to be particularly successful for analyzing and solving a variety of highly structured and practical problems; see, for instance [START_REF] Pham | The DC (Difference of Convex Functions) programming and DCA revisited with DC models of real world nonconvex optimization problems[END_REF][START_REF] Holmberg | A production-transportation problem with stochastic demand and concave production costs[END_REF][START_REF] Chen | Solution of the multisource weber and conditional weber problems by d.c. programming[END_REF].

The aim of the paper is to study global convergence properties of a proximal linearized algorithm for minimizing a nonsmooth DC function. Our algorithm seems to be the first one which considers a convex linear approximation in each proximal subproblem in the context of DC functions.

The organization of this paper is as follows. In Sect. 2 we give some basic definitions and properties of DC functions and nonsmooth analysis. In Sect. 3 we describe our method for minimizing DC functions which has the property that every cluster point of the sequence is a critical point of the DC function. In Sect. [START_REF] Kaplan | Proximal point methods and nonconvex optimization[END_REF] we study the convergence of the whole sequence and its convergence rate for a special case. Finally, in Sect. 5 we establish the convergence results for an inexact algorithm.

Preliminaries

In this section we recall some concepts and basic results from convex analysis and DC programming. For more details about these subjects we refer to [START_REF] Horst | DC programming: overview[END_REF][START_REF] Hiriart-Urruty | Generalized differentiabity, duality and optimization for problems dealing with difference of convex functions, Convexity and Duality in Optimization[END_REF][START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF][START_REF] Rockafellar | Convex analysis[END_REF].

The following notations will be used throughout the paper. Let •, • be the canonical inner product and || • || the corresponding Euclidean norm on R n . The open ball with center x ∈ R n and radius > 0 is denoted by B(x, ) = {y ∈ R n : ||x -y|| < }. Let 0 (R n ) denote the convex cone of all the lower semicontinuous proper (i.e. not identically equal to +∞) convex functions from R n to R := R ∪ {+∞}. The effective domain of a function f , denoted dom( f ), is defined by dom

( f ) = {x ∈ R n : f (x) < +∞}.
A general DC program is of the form α = inf x∈R n { f (x) = g(x)h(x)}, with g, h ∈ 0 (R n ). Such a function f is called a DC function while the convex functions g and h are DC components of f . In DC programming, the convention (+∞)-(+∞) = +∞ has been adopted to avoid the ambiguity (+∞)-(+∞) that does not present any interest. Actually, we are concerned with the following case α = inf x∈dom(h) { f (x) = g(x)-h(x)}, which is equivalent to the last one under the above convention. Moreover, we suppose that dom(g) ∩ dom(h) = ∅.

It is well known that a necessary condition for x ∈ dom( f ) to be a local minimizer of f is ∂h(x) ⊂ ∂g(x). In general, this condition is hard to be reached. So, we will focus our attention on finding points such that ∂h(x) ∩ ∂g(x) = ∅, namely, critical points of f , where ∂ f denotes the subdifferential of f . We will denote by S the set of all critical points of f and throughout the paper S = ∅.

It is worth mentioning the richness of the class of DC functions which is a subspace containing the class of lower-C 2 functions ( f is said to be lower-C 2 if f is locally a supremum of a family of C 2 functions). In particular, DC(R n ) contains the space C 1,1 of functions whose gradient is locally Lipschitz. Properties which help to recognize a DC function can be found, for instance in [START_REF] Hartman | On functions representable as a difference of convex functions[END_REF][START_REF] Ginchev | Characterization and recognition of dc functions[END_REF]. DC(R n ) is closed under the operations usually considered in optimization. For instance, a linear combination, a finite supremum or the product of two DC functions remain DC. Locally DC functions on R n are DC functions on R n (see [START_REF] Hiriart-Urruty | Generalized differentiabity, duality and optimization for problems dealing with difference of convex functions, Convexity and Duality in Optimization[END_REF] and references therein for the details). It is also known that the set of DC functions defined on a compact convex set of R n is dense in the set of continuous functions on this set. Under some caution we can say that DC(R n ) constitutes a minimal realistic extension of 0 (R n ).

Recall that a function f : R n → R is said to be a convex (resp. strongly convex with modulus ρ > 0) function, if for any x, y ∈ R n and λ ∈ [0, 1]

f (λx + (1 -λ)y) ≤ λ f (x) + (1 -λ) f (y) (resp. f (λx + (1 -λ)y) ≤ λ f (x) + (1 -λ) f (y) - ρ 2 λ(1 -λ)||x -y|| 2 ).
We say that f is locally convex at a point x ∈ R n if there exists a neighborhood U of x such that the restriction of f to U is a convex function.

Let F : R n → 2 R n be a multivalued operator with domain

dom(F) = {x ∈ R n : F(x) = ∅}. The operator F is called monotone (resp. strongly monotone with modulus ρ > 0), if for any x, y ∈ R n , u ∈ F(x) and v ∈ F(y) we have v -u, y -x ≥ 0 (resp. v -u, y -x ≥ ρ||x -y|| 2 ). A function f : R n → R is said to be Lipschitz continuous, if there exists a constant L > 0 such that | f (x) -f (y)| ≤ L||x -y|| ∀x, y ∈ R n .
A function is called locally Lipschitz continuous at a point z ∈ R n if the above inequality is satisfied for all x, y ∈ B(z, ) for some L > 0 and > 0. Since convex functions are locally Lipschitz continuous on R n , they are differentiable almost everywhere. The subdifferential of f at a point x ∈ R n is the set

∂ f (x) = {w ∈ R n : f (y) ≥ f (x) + w, y -x ∀y ∈ R n }, if x ∈ dom( f ) and ∂ f (x) = ∅, if x / ∈ dom( f ).
The subdifferential of a convex function f at a point x ∈ dom( f ) is a nonempty, convex and compact set. When f is both convex and differentiable at some point x ∈ dom( f ), then the subgradient is unique and equals to the gradient, i.e., ∂ f (x) = {∇ f (x)}. Furthermore, a lower semicontinuous function f is convex (resp. strongly convex) if and only if ∂ f (•) is a monotone operator (resp. strongly monotone operator).

A sequence

{y k } is called Fejér convergent to a nonempty set U ⊂ R n if ||y k+1 -u|| ≤ ||y k -u||,
for all u ∈ U and k ∈ N.

Proposition 1 If {y k } is Fejér convergent to a nonempty set U ⊂ R n , then {y k } is bounded. Furthermore, if every cluster point y of {y k } belongs to U , then lim k→∞ y k = y.

Proof See [START_REF] Burachik | Full convergence of the steepest descent method with inexact line searches[END_REF].

Proximal linearized Algorithm

Consider f : R n → R a DC function bounded from below, i.e., f (x) = g(x)h(x), with g, h ∈ 0 (R n ). In this section, we present the following proximal linearized algorithm for finding critical points of a DC function f , which considers in each proximal subproblem a linear approximation of f .

Algorithm 1

Step 1: Given an initial point x 0 ∈ dom( f ) and a bounded sequence of positive numbers {λ k } such that lim inf k λ k > 0.

Step 2: Calculate

w k ∈ ∂h(x k ). ( 3
)
Step 3: Compute

x k+1 ∈ arg min x∈R n g(x) -w k , x -x k + 1 2λ k ||x -x k || 2 . ( 4
)
Step 4: If x k+1 = x k , stop. Otherwise, set k := k + 1 and return to Step 2.

The well definition of {w k } and

{x k } is guaranteed if h, g ∈ 0 (R n ).
Note that if h(x) ≡ 0, then Algorithm 1 becomes exactly the classical proximal point algorithm for convex functions (2).

Remark 1 It is worth mentioning that our algorithm and DCA algorithm (see [START_REF] Pham | Algorithms for solving a class of nonconvex optimization problems: methods of subgradient[END_REF]) share the same idea, namely, they linearize some component g(•) or h(•); or both of the DC objective function f (x) = g(x)h(x). However, Algorithm 1 is simpler because linearization is done directly, and not on the dual components, besides the fact that proximal algorithms are more efficient than subgradient algorithms. Recently, Bento and Soubeyran [START_REF] Bento | Generalized inexact proximal algorithms: Routine's formation with resistance to change, following worthwhile changes[END_REF] discussed how "generalized" proximal point algorithms can be a nice tools to modelize the dynamics of human behaviours on the context of the "variational rationality approach" (see Soubeyran [START_REF] Soubeyran | Variational rationality. Human behaviors as worthwhile stay and change transitions, possibly ending in traps, before reaching desires[END_REF]), where the term "generalized" refers to a quasi distance such that not necessarily all the axioms of distance are verified, but preserving the nice properties of convexity, continuity and coercivity of the Euclidean norm. In this "variational rationality approach", costs to be able to change from the current position x k to x k+1 and costs to be able to stay in the current position x k are not necessarily symmetric and equal to zero, respectively. In this context, Algorithm 1 seems to be more appropriate than the algorithm proposed in [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF], because in our algorithm there is no auxiliar sequence working in the quadratic term in (4) while the algorithm in [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF] has. Now we shall establish the convergence of the algorithm. We begin by showing that Algorithm 1 is a descent algorithm.

Theorem 1

The sequence {x k } generated by Algorithm 1 satisfies:

1. either the algorithm stops at a critical point; 2. or f decreases strictly, i.e., f (x k+1 ) < f (x k ), for all k ∈ N.

Proof From (3) and ( 4) we have w k ∈ ∂h(x k ) and

w k ∈ ∂g(x k+1 ) + 1 λ k (x k+1 -x k ), (5)
respectively. If

x k+1 = x k , then w k ∈ ∂h(x k ) ∩ ∂g(x k ), which means that x k is a critical point of f . Now, suppose x k+1 = x k . It follows from (3) and h ∈ 0 (R n ) that h(x k+1 ) ≥ h(x k ) + w k , x k+1 -x k . ( 6
)
On the other hand, from (4), we have

g(x k ) ≥ g(x k+1 ) -w k , x k+1 -x k + 1 2λ k ||x k+1 -x k || 2 . ( 7
)
Adding inequalities ( 6) and ( 7), we obtain

f (x k ) ≥ f (x k+1 ) + 1 2λ k ||x k+1 -x k || 2 . ( 8
)
Since {λ k } is a positive sequence and

x k+1 = x k , then f (x k+1 ) < f (x k ).
Next result is a consequence of Theorem 1 and the lower boundedness of f .

Corollary 1 Consider {x k } generated by Algorithm 1. Then the sequence { f (x k )} is convergent. Furthermore, if f is a continuous function and {x k } is bounded, then lim k→∞ f (x k ) = f (x), for some cluster point x of {x k }.

The following proposition will be useful to prove the convergence theorem.

Proposition 2 Let {x k } be generated by Algorithm 1. Then lim k→+∞ ||x k+1x k || = 0.

Proof From (8), we have that n-1 k=0

1 2λ k ||x k+1 -x k || 2 ≤ f (x 0 ) -f (x n ). Since f is bounded from below and lim inf k λ k > 0, we obtain ∞ k=0 ||x k+1 -x k || 2 < ∞, and it follows that lim k→+∞ ||x k+1 -x k || = 0.
Note that from (3) and convexity of h, if {x k } is bounded, then {w k } is also bounded.

Theorem 2 Suppose that {x k } is bounded. Then every cluster-point of {x k } is a critical point of the function f . Proof Let x * and w * be cluster points of {x k } and {w k }, respectively. Then, there exist two subsequences x k j and w k j converging respectively to x * and w * , i.e., x k j → x * and w k j → w * . Since h is convex and lower semicontinuous, it follows from (3) and the definition of subdifferential, taking j goes to +∞, that w * ∈ ∂h(x * ). Now, we claim that w * ∈ ∂g(x * ). From ( 5), there exists z k j +1 ∈ ∂g(x k j +1 ) such that

||w k j -z k j +1 || = 1 λ k j ||x k j +1 -x k j ||. (9)
Since {λ k } is bounded, combining (9) and Proposition 2, we get that lim j→+∞ w k j = lim j→+∞ z k j +1 = w * . Therefore, since g ∈ 0 (R n ) and combining the definition of the subdifferential and the fact that z k j +1 ∈ ∂g(x k j +1 ), taking j goes to +∞, we have w * ∈ ∂g(x * ). Thus, w * ∈ ∂h(x * ) ∩ ∂g(x * ), which means that x * is a critical point of f .

Remark 2 If f is continuous and {x k } is bounded it can be easily proved that the whole sequence {x k } converges to some critical point x * ∈ S, as long as S satisfies the sharp minima condition; see [START_REF] Polyak | Sharp Minima Institute of Control Sciences Lecture Notes[END_REF]. Recently, finite termination and convergence rate of the proximal point method has been studied under the concept of weak sharp minima, Kurdyka-Lojasiewicz property and subregularity property; see [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Ferris | Weak sharp minima and penalty functions in mathematical programming[END_REF][START_REF] Li | Holder metric subregularity with applications to proximal point method[END_REF]. We hope that this paper may stimulate further research involving proximal linearized algorithm for DC functions and these concepts. The results presented in this section are still true if we consider an approximate version obtained by replacing the exact subdifferential by the approximate one such as in [START_REF] Moudafi | On the convergence of an approximate proximal method for d.c. functions[END_REF].

Global convergence

Let us consider now the special case discussed in [START_REF] Moudafi | On the convergence of an approximate proximal method for d.c. functions[END_REF] where f is a DC function with f (x) = g(x)h(x) and the function h is differentiable. In this context (3) and ( 4) reduce to

x k+1 ∈ arg min x∈R n g(x) -∇h(x k ), x -x k + 1 2λ k ||x -x k || 2 (10)
and x * is a critical point of f if ∇h(x * ) ∈ ∂g(x * ).

Theorem 3 Consider Algorithm 1 with ( 3) and ( 4) replaced by [START_REF] Burachik | A relative error tolerance for a family of generalized proximal point methods[END_REF]. Suppose that g is a strongly convex function (with constant ρ > 0) and ∇h(x) a Lipschitz continuous function (with constant L > 0). If ρ > 2L, then there exists a constant 0 < r < 1 such that

||x k+1 -x * || ≤ r ||x k -x * || ∀x * ∈ S. ( 11
)
Therefore, the whole sequence {x k } converges linearly to a point x * ∈ S.

Proof From (10), there exists z k+1 ∈ ∂g(x k+1 ) such that

∇h(x k ) = z k+1 + 1 λ k (x k+1 -x k ). ( 12
)
Let x * ∈ S be a critical point of f , namely, ∇h(x * ) ∈ ∂g(x * ). By strong monotonicity of ∂g(•) and ( 12), we have

0 ≤ x k+1 -x * , z k+1 -∇h(x * ) -ρ||x k+1 -x * || 2 = x k+1 -x * , x k -x k+1 λ k + ∇h(x k ) -∇h(x * ) -ρ||x k+1 -x * || 2 .
Thus, since λ k > 0, using the Cauchy-Schwarz inequality and the fact that ∇h(•) is a Lipschitz function, we have

0 ≤ 2λ k x k+1 -x * , ∇h(x k ) -∇h(x * ) -2 x k+1 -x * , x k+1 -x k -2λ k ρ||x k+1 -x * || 2 ≤ 2λ k L||x k+1 -x * ||||x k -x * || -||x k+1 -x * || 2 -||x k -x k+1 || 2 +||x k -x * || 2 -2λ k ρ||x k+1 -x * || 2 ≤ 2λ k L(||x k+1 -x * || 2 + ||x k -x * || 2 ) -||x k+1 -x * || 2 -||x k -x k+1 || 2 +||x k -x * || 2 -2λ k ρ||x k+1 -x * || 2 = (1 + 2λ k L)||x k -x * || 2 -[1 + 2λ k (ρ -L)]||x k+1 -x * || 2 -||x k -x k+1 || 2 .
It immediately follows that

[1 + 2λ k (ρ -L)]||x k+1 -x * || 2 ≤ (1 + 2λ k L)||x k -x * || 2 .
The first assertion is proved setting 0 < r :=

(1 + 2λ k L) 1 + 2λ k (ρ -L)
< 1 in the last inequality. The second one follows from Proposition 1 and Theorem 2.

Remark 3 If all the assumptions of Theorem 3 are satisfied and f is lower semicontinuous and locally convex at the limit point x * of {x k }, then there exist a neighborhood U of x * and k 0 ∈ N such that x k ∈ U , for all k ≥ k 0 and the restriction of f to U is a convex function. From (5), we have

1 λ k (x k -x k+1 ) + ∇h(x k ) -∇h(x k+1 ) ∈ ∂g(x k+1 ) -∇h(x k+1 ) ⊂ ∂ f (x k+1 ) that means, f (x) ≥ f (x k+1 ) + 1 λ k (x k -x k+1 ) + ∇h(x k ) -∇h(x k+1 ), x -x k+1
, for all x ∈ U . Having in mind that ∇h(•) is Lipschitz continuous and Proposition 2 it follows from last inequality, taking the lower limit, that x * is a local minimizer of f . This provided a sufficient condition for a limit point of {x k } to be a local minimizer of f .

Inexact version

For the method to be practical, it is important to handle approximate solutions of subproblems. This consideration gives rise to inexact versions of the proximal point algorithm. Now, we present the following inexact algorithm for DC functions.

Algorithm 2

Step 1: Given an initial point x 0 ∈ dom( f ), θ > 0, σ ∈ [0, 1) and a bounded sequence of positive numbers {λ k } such that lim inf k λ k > 0.

Step 2: Calculate

w k ∈ ∂h(x k ). ( 13
)
Step 3: Compute (x k+1 , ξ k+1 ) ∈ R n × R n such that:

g(x k ) -g(x k+1 ) -w k , x k -x k+1 ≥ (1 -σ ) 2λ k ||x k+1 -x k || 2 , ( 14
) with ||ξ k+1 -w k || ≤ θ ||x k+1 -x k ||, (15)
where

ξ k+1 ∈ ∂g(x k+1 ). ( 16
)
Step 4: If x k+1 = x k , stop. Otherwise, set k := k + 1 and return to Step 2. Note that when h(x) = 0 Algorithm 2 becomes exactly the algorithm proposed in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF]. It follows from ( 14) that

g(x k+1 ) -w k , x k+1 -x k + 1 2λ k ||x k+1 -x k || 2 ≤ g(x k ) + k , where 0 ≤ k = σ 2λ k ||x k+1 -x k || 2 .
When k = 0 (it holds by taking σ = 0) (4) implies the weaker condition [START_REF] Bento | Generalized inexact proximal algorithms: Routine's formation with resistance to change, following worthwhile changes[END_REF].

Theorem 4

The sequence {x k } generated by Algorithm 2 satisfies:

1. either the algorithm stops at a critical point; 2. or f decreases strictly, i.e., f (x k+1 ) < f (x k ), for all k ∈ N.

Furthermore, lim k→+∞ ||x k+1x k || = 0.

Proof The proof uses exactly the same argument as the one used to prove Theorem 1 and Proposition 2 having in mind that σ ∈ [0, 1).

Corollary 2 Consider {x k } generated by Algorithm 2. Then the sequence { f (x k )} is convergent. Additionally, if f is a continuous function and {x k } is bounded, then lim k→∞ f (x k ) = f (x), for some cluster point x of {x k }.

Proof The proof uses the same argument as the one used to prove Corollary 1.

Theorem 5 Let {x k } generated by Algorithm 2. Then every cluster point of {x k }, if any, is a critical point of f . Proof Let x * be a cluster point of {x k }. So, consider a subsequence {x k j } of {x k } converging to x * . As mentioned before, we know that {w k } is also bounded. Consider a subsequence {w k j } of {w k } converging to w * . From [START_REF] Sun | Proximal point algorithm for minimization of DC Functions[END_REF] and Theorem 4, we have

lim j→+∞ ξ k j +1 = lim j→+∞ w k j = w * . ( 17
)
From definition of the algorithm w k j ∈ ∂h(x k j ) and ξ k j +1 ∈ ∂g(x k j +1 ). Therefore, h(y) ≥ h(x k j ) + w k j , yx k j ∀y ∈ R n and g(y) ≥ g(x k j +1 ) + ξ k j +1 , yx k j +1 ∀y ∈ R n , respectively. Taking j goes to +∞ in last two inequalities, since h, g ∈ 0 (R n ), we have w * ∈ ∂h(x * ) ∩ ∂g(x * ) and the proof is complete.

Conclusion

Future researches will examine the case where the Euclidean norm in the regularization term is replaced by a generalized quasi distance which is more appropriate to interpret our results in terms of behavioural science. Algorithms for multiobjective DC problems has not been considered yet. An extension of our algorithm to this context will be studied as well as modified versions of the algorithms where linear or quadratic approximations of g will be considered. We expect that the results of this paper become a further step towards solving DC optimization problems. We foresee further progress in this topics in the near future.

Acknowledgments

The authors wish to express their gratitude to the anonymous referees for them helpful comments.

The research of the J. C. Souza was supported in part by CNPq-Ciências sem Fronteiras Grant 203360/2014-1. The P. R. Oliveira was partially supported by CNPq, Brazil.


domain: shs.eco math shs

text:
Glaydston De Carvalho Bento
email: glaydstonc@gmail.com

João Xavier Da Cruz Neto

Antoine Soubeyran
email: antoine.soubeyran@gmail.com

Valdinês Leite De Sousa Júnior
email: valdinesldsj@gmail.com

Boris S Mordukhovich

Glaydston De

Carvalho Bento

João Xavier
email: jxavier@ufpi.edu.br

Cruz Neto

Dual Descent Methods as Tension Reduction Systems

Keywords: Dual descent, Inexact proximal, Worthwhile change, Kurdyka-Lojasiewicz property, Tension systems, Variational rationality Mathematics Subject Classification 90C30, 49M29

In this paper, driven by applications in Behavioral Sciences, wherein the speed of convergence matters considerably, we compare the speed of convergence of two descent methods for functions that satisfy the well-known Kurdyka-Lojasiewicz property in a quasi-metric space. This includes the extensions to a quasi-metric space of both the primal and dual descent methods. While the primal descent method requires the current step to be more or less half of the size of the previous step, the dual approach considers more or less half of the previous decrease in the objective function to be minimized. We provide applications to the famous "Tension systems approach" in Psychology.

Introduction

Driven by applications in Behavioral Sciences, wherein the speed of convergence matters considerably, in this study we compare the speed of convergence of two descent methods for functions that satisfy the well-known Kurdyka-Lojasiewicz property in a quasi-metric space. This includes the extension to a quasi-metric space of the primal descent method in Attouch and Bolte [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF] and that of the dual descent method given by Alaa and Pierre [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF]. The two main conditions (1) and [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] given in this paper are weaker than conditions H1 and H2 considered in Attouch et al. [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF]. Our approach also retrieves the exact proximal point method presented by Moreno et al. [START_REF] Moreno | A proximal algorithm with quasi distance. Application to habit's formation[END_REF], as well as the inexact proximal point method studied by Fuentes et al. [START_REF] Fuentes | Descentwise inexact proximal algorithms for smooth optimization[END_REF].

Dual descent methods consider two types of steps. In [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF], the current step must be more or less half of the size of the previous step. In contrast, the dual approach in [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] considers more or less half of the previous decrease in the objective function to be minimized. Before comparing these dual algorithms, we need to extend them to quasimetric spaces. This is because in Behavioral Sciences (see Soubeyran [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF][START_REF] Soubeyran | Variational rationality. Part 1. Worthwhile stay and change approach-avoidance human dynamics ending in traps[END_REF]for the introduction of quasi-distances in such areas), distances cannot represent specific instances of costs of being able to change from one position to another. They are, most of the time, quasi-distances, where the costs of being able to change from one position to another are different from those of being able to change to go back to the first position. We find that in a large set of cases, dual resolution converges faster than primal resolution. This is caused by behavioral considerations, which imply the different ways in which an agent can choose to reduce the discrepancy between where he is initially (away from an optimal position) and where he wants to be in the near or distal future (the goal, at an optimal position if possible). The primal resolution chooses to reduce the discrepancy, defined as the quasi-distance between where the agent is in the current period and where he wants to be (an optimal position) in the near or distal future. The dual resolution chooses to reduce the discrepancy, defined as the difference between his current dissatisfaction (a disutility, a negative feeling) and his minimal dissatisfaction (tension-free state).

Let us be more explicit on the motivation of this paper. Lewis [START_REF] Lewis | Field theory in Social Science[END_REF] is termed the "father of tension systems" in Psychology. He advocates that life is a constant interplay between tension reduction and tension production phases. In tension reduction phases, when agents have some goals in mind, they try to reduce the discrepancy between where they are (the current status quo) and where they want to be (their goals) in the near or distal future. These periods refer to goal-striving phases. When they succeed in reaching their goals, tensions release. This is a temporary equilibrium phase. Then, in tension production phases, agents need new challenges. They set new goals, creating a discrepancy between where they are in the current period and where they want to be in a near or more distal future. This refers to goal-setting phases. These powerful general ideas give rise to the (not formalized) famous theory of self-regulation in Psychology (goal setting, goal striving, goal revision, goal disen-gagement; see Bandura [START_REF] Bandura | Failures in self-regulation: Energy depletion or selective disengagement?[END_REF], Carver and Scheier [START_REF] Carver | On the structure of behavioral self-regulation[END_REF], Oettingen and Gollwitzer [START_REF] Gabriele Oettingen | Strategies of setting and implementing goals[END_REF], De Ridder and de Wit [START_REF] De Ridder | Self-regulation in health behavior[END_REF]).

This paper, being strongly mathematically oriented, will not consider tension production processes for the following reason. The optimization community emphasizes much more one side of self-regulation processes, the tension reduction processes. They consider a given function to be minimized and a given discrepancy between where an agent is and where he wants to be and try to find a position that minimizes this discrepancy. Possible obstacles to reduce this discrepancy refer to constraints. This is a traditional minimization problem with or without constraints. Mathematicians use step-by-step algorithms to reach such minimization solutions (tension-free positions). Such algorithms abound: descent methods, exact and inexact proximal algorithms, Newton methods, local models of approximation like trust region methods and rejection processes like branch and bound algorithms.

A recent variational rationality (VR) approach of human behaviors (Soubeyran [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF][START_REF] Soubeyran | Variational rationality. Part 1. Worthwhile stay and change approach-avoidance human dynamics ending in traps[END_REF]) offers a general model for tension systems, where tension reduction phases interplay with tension production phases. This model unifies different approaches of human behaviors in Psychology, Economics, Management Sciences, Political Sciences, Game theory, Artificial Intelligence and Mathematics. These include habit-routine formation and breaking processes at the individual level and exploration-exploitation adaptive learning dynamics in organizations. As a direct application, it helps to link the tension reduction aspect of the self-regulation theory in Psychology with traditional optimization problems in Mathematics. The first idea is that tension reduction is a progressive process that cannot reduce discrepancy in one step. Then VR approach poses the following question: How to fill such gaps in an acceptable manner? Because of not being able to do this in a single step, the agent will have to follow a transition defined as a succession of acceptable single steps (change or stay). Then, he will accept to entering into such a transition if acceptable.

The core of the VR approach is to define and modelize an acceptable single change if it is sufficiently worthwhile. This is the case when the motivation to change instead of stay is greater than the resistance to change instead of stay. Motivation to change is the utility of advantages to change, and resistance to change is the disutility of inconveniences to change. Advantages to change refer to the difference between where the agent wants to be or what he wants to have (an intention or its related payoff) and where he is or what he has (the status quo) in the current period. They modelize how tension production (creating a discrepancy) reduces tension, being a descent in Mathematics, bringing the agent closer to the minimum (tension-free state). Inconveniences to change represent the difference between the costs of being able to change and being able to stay. Under mild hypothesis, they are quasi-distances. Then, the VR approach shows how, in a quasi-metric space, a primal descent method [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies kurdyka-Lojasiewicz inequality[END_REF][START_REF] Bento | Generalized inexact proximal algorithms: Routine formation with resistance to change, following worthwhile changes[END_REF] is worthwhile tension reduction process which reduces inconveniences to change. However, while the dual descent method ( [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] and this study) reduces the advantages to change from where the agent is to where he wants to be, the tension-free position, this shows that descent methods belong to tension reduction systems.

Note that in terms of our VR approach, our descent process is also dual to the descent method considered in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] because of the added reason that our stopping rule majorizes the norm of the subgradient by a function of advantages to change, while [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] majorizes the norm of the subgradient by a function of the inconveniences to change.

The mathematical side of the VR approach proposed by Soubeyran [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF] has been further studied in a number of papers with applications to behavioral sciences including psychological modeling in quasi-metric space settings and minimal points, variational principles and variable preferences in set optimization; see Bao et al. [START_REF] Bao | Variational analysis in psychological modeling[END_REF][START_REF] Bao | Minimal points, variational principles, and variable preferences in set optimization[END_REF]. To further clarify how these developments are related to those presented in this paper, we provide, among others, a short list of comparisons. The main point is that the variational rationality approach unifies the majority of algorithms and variational principles used in optimization in terms of descent methods, approximate linear quadratic model-based methods (trust region methods and other variants) and as tension reduction-tension production systems in Psychology. It helps operate different broad classifications among them:

(i) Weak resistance to change aspects (proximal algorithms; see Bento and Soubeyran [START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies kurdyka-Lojasiewicz inequality[END_REF][START_REF] Bento | Generalized inexact proximal algorithms: Routine formation with resistance to change, following worthwhile changes[END_REF]) and strong resistance to change aspects (Ekeland theorem, Caristi theorem and equivalent variational principles; see Bao et al. [START_REF] Bao | Variational analysis in psychological modeling[END_REF][START_REF] Bao | Minimal points, variational principles, and variable preferences in set optimization[END_REF]); (ii) Tension reduction processes with fixed ends (a given optimum for proximal algorithms) and those with moving ends (variational traps and desires for Ekeland and Caristi theorems); (iii) Satisficing processes as tension reduction systems, where each satisficing step refers to a sufficient epsilon reduction in quasi-distance or sufficient epsilon reduction in payoff; (iv) Equivalent proximal formulations in terms of proximal payoffs (profit or utility, minus costs of being able to change) and Ekeland-like worthwhile to change conditions (descent condition, that is, descent conditions where advantages to change, where advantages to change are higher than inconveniences to change); (v) Tension reduction processes with variable and multidimensional preferences; see Cruz and Allende [START_REF] Cruz | A Steepest Descent-Like Method for Variable Order Vector Optimization Problems[END_REF] for a steepest-like descent method and Bao et al. [START_REF] Bao | Variational analysis in psychological modeling[END_REF][START_REF] Bao | Minimal points, variational principles, and variable preferences in set optimization[END_REF] for Ekeland theorem. In this case, all things seem to move, each period. Then, how is it possible for something to stay in the end?

The organization of the paper is as follows. In Sect. 2, the basic definitions used in the paper are presented. In Sect. 3, the main results are stated and proved. In Sect. 4, we present a short VR structure. In Sect. 5, we compare the speed of convergence of the two dual descent methods in a quasi-metric space. The conclusions are presented in Sect. 6.

Preliminaries on Nonsmooth Analysis

In this section, some elements of nonsmooth analysis are presented; see, for instance, [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF][START_REF] Rockafellar | Variational analysis, Grundlehren der Mathematischen Wissenschaften[END_REF]. Let us consider f : R n → R ∪{+∞}, a lower semicontinuous function. The domain of f , denoted by dom f , is the subset of R n on which f is finite valued. The function f is said to be proper when dom f =∅.If T denotes a multivalued mapping on R n , the domain of T is the set of elements x ∈ R n such that T (x) = ∅. Definition 2.1 (i) The Fréchet subdifferential (also known as regular subdifferential) of f at x ∈ R n is defined by

∂ f (x) := ⎧ ⎨ ⎩ x * ∈ R n : lim inf y→x;y =x 1 x -y ( f (y)-f (x)-x * , y -x ) ≥ 0 , if x ∈ dom f, ∅, if x / ∈ dom f.
(ii) The (Mordukhovich or limiting) subdifferential of f at x ∈ R n is defined by

∂ f (x) := x * ∈ R n : ∃x n → x, f (x n ) → f (x), x * n ∈ ∂ f (x n ); x * n → x * , if x ∈ dom f, ∅, if x / ∈ dom f. Note that ∂ f (x) ⊂ ∂ f (x).
In the particular case where

f is differentiable at x (resp. continuously differentiable around x), then ∂ f (x) = {∇ f (x)} (resp. ∂ f (x) = {∇ f (x)}). If f is a convex function, both subdifferentials ∂ f (x) and ∂ f (x) coincide with the usual subdifferential for each x ∈ dom f . Denote Graph ∂ f := {(x, v) ∈ R n × R n : v ∈ ∂ f (x)}. Checking the following closedness property of ∂ f from the definition is straightforward. Let (x k , v k ) k∈N ⊂ R n × R n such that (x k , v k ) ∈ Graph ∂ f for all k ∈ N. If (x k , v k ) k∈N converges to (x, v), and f (x k ) converges to f (x), then (x, v) ∈ Graph ∂ f ; see [3] for more details. A necessary (but not sufficient) condition for x ∈ R n to be a local minimum of f is 0 ∈ ∂ f (x). A point x ∈ R n
satisfying the last inclusion is said to be limiting critical or simply critical.

Dual Descent Methods

In this section, we propose and study an inexact descent method whose full convergence is assured for cost functions that satisfy the Kurdyka-Lojasiewicz property.

Definition 3.1 A mapping q : R n × R n → R + is said to be a quasi-distance iff, for all x, y, z ∈ R n , (i) q(x, y) = q(y, x) = 0 if, only if, x = y; (ii) q(x, y) ≤ q(x, z) + q(z, y).
Given x ∈ R n and ε > 0 fixed, we denote by B q (x, ε) the open ball, with respect to the quasi-distance q, of center x and radius ε > 0, defined as follows: B q (x, ε) = {y ∈ R n : q(x, y) < ε}. In particular, if q is the Euclidian distance, B q (x, ε) will be denoted by B(x, ε).

Throughout this paper, q represents a quasi-distance that satisfies the following assumption:

Assumption 3.1 There exist β 1 , β 2 ∈ R ++ such that β 1 x -y ≤ q(x, y) ≤ β 2 x - y , x, y ∈ R n .
In [START_REF] Moreno | A proximal algorithm with quasi distance. Application to habit's formation[END_REF], the authors present some examples of quasi-distances that satisfy Assumption 3.1.

In the sequel, we consider sequences {x k } satisfying the following conditions (1), (2), which, for convenience, we refer to as follows: Method 3.1 Take x 0 ∈ R n , 0 < λ ≤ λ < +∞, and let a, b, be positive constants.

For each k = 0, 1, . . ., choose λ k ∈ [ λ, λ] and find x k+1 , w k+1 ∈ R n × R n such that (a/λ k ) q 2 x k , x k+1 ≤ f (x k )-f (x k+1 ), (worthwhile to change condition) (1)
w k+1 ∈ ∂ f (x k+1 ), bλ k w k+1 2 ≤ f (x k ) -f (x k+1 ), (curvature condition on the payoff function f) (2)
where q : R n × R n → R + represents a quasi-distance.

Remark 3.1 Note that any sequence generated by the proximal point methods proposed in [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Moreno | A proximal algorithm with quasi distance. Application to habit's formation[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF], as well as those complying with conditions (2.2) and (2.3) in [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF], satisfies conditions ( 1) and ( 2) particularly when quasi-distance is the Euclidean distance and f is a differentiable function. Moreover, ( 1) and ( 2) can be easily seen to imply the following condition:

∃ w k+1 ∈ ∂ f x k+1 : f x k -f x k+1 ≥ √ ab w k+1 q x k , x k+1 , k = 0, 1, . . . , (3)
which is a natural extension to the quasi-metric setting of the discrete implicit angle condition (1.6) in [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] considering the nondifferentiability of f (an explicit version of this condition, in the differentiable case, was considered in Absil et al. [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF]). It is important to note that conditions (1) and ( 2) are less restrictive than conditions H1 and H2 considered in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF], since (1) is equivalent to H1, and H1 and H2 together imply (2) (in the particular case where q is a Euclidean distance).

We can assume, without loss of generality, that x 0 ∈ dom f . Note that if {x k } is a finite sequence, there exists [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] shows that w k+1 = 0, k ≥ k 0 . Then, {x k } terminates at a critical point. In view of this, we can assume that {x k } is an infinite sequence. Unless stated otherwise, in the remainder of this paper, we assume that f is a proper and lower semicontinuous function bounded below and is continuous on dom f , and {x k } is an infinite sequence satisfying the conditions of Method 3.1.

k 0 ∈ N such that f (x k+1 ) = f (x k ), k ≥ k 0 . Hence,

Convergence Analysis

In this section, assuming that f satisfies the Kurdyka-Lojasiewicz property, we show full convergence of the sequence {x k } to a critical point. First, we present a partial convergence result.

Proposition 3.1

The following statements hold.

(i) The sequence { f (x k )} is strictly decreasing; (ii) +∞ k=0 q 2 x k , x k+1 < +∞; (iii) lim k→+∞ q x k , x k+1 = 0; (iv) Each accumulation point of the sequence {x k }, if any, is a critical point of f .
Proof The proofs of items (i), (ii) and (iii) are simple verification. Let us deal with item (iv). Suppose that x ∈ R n is an accumulation point of {x k }, and let {x k j } be a subsequence converging to x. It follows from (i) that x k ∈ dom f . Since f is a proper and lower semicontinuous function, x ∈ dom f , and as f is bounded below and is continuous on dom f , we have from (i) that { f (x k )} converges to f ( x). However, as {x k } is a sequence that satisfies the conditions of Method 3.1, there exists a sequence

{w k+1 } such that w k+1 ∈ ∂ f (x k+1 ), satisfying (2). In view of (2), {w k+1 } converges to zero, because 0 < λ ≤ λ k ≤ λ, k ∈ N, and { f (x k ) -f (x k+1 )} converges to zero. As Graph ∂ f is closed, it follows that 0 ∈ ∂ f ( x), which concludes the proof.
As in [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Moreno | A proximal algorithm with quasi distance. Application to habit's formation[END_REF], our main convergence result is restricted to functions that satisfy the Kurdyka-Lojasiewicz property. This was first introduced by Lojasiewicz [START_REF] Lojasiewicz | Une propriété topologique dessous-ensembles analytiques réels. Les Équations aux DérivéesPartielles[END_REF] to real analytic functions and extended by Kurdyka [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] to differentiable definable functions in an o-minimal structure (for a detailed discussion on o-minimal structures, see Dries and Miller [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]). For extensions of the Kurdyka-Lojasiewicz property, in the Euclidian context, to the class of nonsmooth functions, see Bolte et al. [START_REF] Bolte | The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], Bolte et al. [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF] and Attouch et al. [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF]. For extensions of the Kurdyka-Lojasiewicz property to functions defined on nonlinear spaces, see Kurdyka et al. [START_REF] Kurdyka | Proof of the gradient conjecture of R. Thom[END_REF], Lageman [START_REF] Lageman | Convergence of gradient-like dynamical systems and optimization algorithms[END_REF], Bolte et al. [START_REF] Bolte | Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF], Bento et al. [START_REF] Bento | A New Approach to the Proximal Point Method: Convergence on General Riemannian Manifolds[END_REF] and Hosseini [START_REF] Hosseini | Convergence of nonsmooth descent methods via Kurdyka-Lojasiewicz inequality on Riemannian manifolds[END_REF]. The next formal definition of the Kurdyka-Lojasiewicz property can be found in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF], where finding several examples and a good discussion on important classes of functions that satisfy the mentioned inequality is possible. Definition 3.2 A proper and lower semicontinuous function f : R n → R ∪ {+∞} is said to have the Kurdyka-Lojasiewicz property at x ∈ dom ∂ f iff there exist η ∈]0, +∞], a neighborhood U of x, and continuous concave function ϕ

: [0, η[→ R + such that ϕ(0) = 0, ϕ ∈ C 1 (]0, η[) , ϕ (s) > 0, s ∈]0, η[; (4) ϕ ( f (x) -f ( x)) dist (0, ∂ f (x)) ≥ 1, x ∈ U ∩ [ f ( x) < f < f ( x) + η], (5) -dist(0, ∂ f (x)) := inf{ v : v ∈ ∂ f (x)}, -[η 1 < f < η 2 ] := {x ∈ R n : η 1 < f (x) < η 2 }, η 1 < η 2 .
Remark 3.2 f is known to have the Kurdyka-Lojasiewicz property at any noncritical point; see [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF]. In [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF] the authors considered that f has the Lojasiewicz property at some point x if there exist C > 0 and δ > 0 such that

| f (x) -f ( x)| θ ≤ C w , x ∈ B( x, δ), w ∈ ∂ f (x). ( 6
)
Note that if f has the Lojasiewicz property at some point x, then it has the Kurdyka-Lojasiewicz property at x with

η := δ/2, U := B( x, δ/2), ϕ(s) := (C/(1 -θ))s 1-θ , θ ∈ [0, 1[. (7)
Indeed, assume that there exist C > 0 and δ > 0 satisfying [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF]. Taking η, U and ϕ as defined in [START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF], we can easily see that ϕ satisfies all the requirements in (4) and there holds

ϕ ( f (x) -f ( x)) = C ( f (x) -f ( x)) -θ ≥ w -1 , w ∈ ∂ f (x), x ∈ U ∩ [ f ( x) < f < f ( x) + η],
from which it follows (5) and, in particular, ϕ defined ( 7) satisfies all the conditions of Definition 3.2.

Next, we present the main convergence result.

Theorem 3.1 Let f : R n → R ∪ {+∞} be a function that satisfies the Kurdyka-Lojasiewicz property at some x ∈ R n , and assume that Assumption 3.1 holds. Let U ⊂ R n be a neighborhood of x, η ∈]0, +∞] and ϕ : [0, η[→ R + the objects appearing in Definition 3.2. Let ε > 0 be such that B( x, ε) ⊂ U , and take 0 < ρ <

εβ 1 , C 1 = √ ab/2 -1 and C 2 = 2 λ/ √ a √ 2 -1 satisfying f ( x) < f (x 0 ) < f ( x) + η, (8)
q x, x 0 + λ/a 1/2 + C 2 f (x 0 ) -f ( x) 1/2 + C 1 ϕ f (x 0 ) -f ( x) < ρ. ( 9
)
x k ∈ B q ( x, ρ) ⇒ x k+1 ∈ B q ( x, εβ 1 ) with f (x k+1 ) ≥ f ( x), k = 0, 1, . . . . ( 10
)
Then, the sequence {x k } satisfies

x k ∈ B q ( x, ρ), k = 0, 1, 2, . . . , ( 11
) +∞ k=0 q x k , x k+1 < +∞, (12)
and converges to a point x.

Moreover, x is a critical point of f , f ( x) = f ( x) and f (x k ) → f ( x).
Proof From now on, we can assume, without loss of generality, that f ( x) = 0, since we can change f to ff ( x). First, we need to prove that for each fixed k 0 ∈ N with x k 0 ∈ B q ( x, ρ), we have

q x k 0 , x k 0 +1 ≤ C 1 ϕ f (x k 0 )/2 -ϕ f (x k 0 +1 )/2 + C 2 f (x k 0 ) 1/2 -f (x k 0 +1 ) 1/2 . ( 13
)
Fix any k 0 ∈ N with x k 0 ∈ B q ( x, ρ). In view of ( 8) and ( 10), we have

0 ≤ f (x k 0 +1 ) ≤ f (x k 0 ) ≤ f (x 0 ) < η. ( 14
)
Hence, the quantities ϕ f (x k 0 )/2 and ϕ f (x k 0 +1 )/2 appearing in (13) make sense. Now, we have two possibilities to consider:

(a) f x k 0 +1 > f x k 0 /2; (b) f x k 0 +1 ≤ f x k 0 /2.
Suppose that (a) holds. From concavity of the function ϕ in (4), we obtain the following inequalities:

ϕ f (x k 0 )/2 -ϕ f (x k 0 +1 )/2 ≥ (1/2)ϕ f (x k 0 )/2 f (x k 0 ) -f (x k 0 +1 ) , ( 15
)
ϕ f (x k 0 )/2 ≥ ϕ f (x k 0 +1 ) . ( 16
)
Considering that (3) holds with k = k 0 , from ( 15) and ( 16), we have

ϕ f (x k 0 )/2 -ϕ f (x k 0 +1 )/2 ≥ √ ab/2 ϕ f (x k 0 +1 ) w k 0 +1 q x k 0 , x k 0 +1 , ( 17
)
where w k 0 +1 ∈ ∂ f x k 0 +1 . In view of (1), we have

q x k 0 , x k 0 +1 ≤ λ a f (x k 0 ) 1/2 . ( 18
)
The inequality [START_REF] Cruz | A Steepest Descent-Like Method for Variable Order Vector Optimization Problems[END_REF] and triangle inequality give us

q x, x k 0 +1 ≤ q x, x k 0 + q x k 0 , x k 0 +1 ≤ λ a f (x k 0 ) 1/2 + q x, x k 0 .
As x k 0 ∈ B q ( x, ρ), (10) implies x k 0 +1 ∈ B q ( x, εβ 1 ). However, from Assumption 3.1 there exists β 1 > 0 such that β 1 xx k 0 +1 ≤ q( x, x k 0 +1 ). This tells us that x k 0 +1 ∈ B( x, ε) ⊂ U . In view of ( 14),

x k 0 +1 ∈ U ∩ [0 < f < η].
Hence, as f satisfies the Kurdyka-Lojasiewicz inequality at x, we have 0 / ∈ ∂ f (x k 0 +1 ). Moreover, combining [START_REF] Fuentes | Descentwise inexact proximal algorithms for smooth optimization[END_REF] with the definition of dist (0, ∂ f (x)), we obtain

ϕ f (x k 0 +1 ) w k 0 +1 ≥ ϕ f (x k 0 +1 ) dist 0, ∂ f (x k 0 +1 ) ≥ 1.
Hence, inequality [START_REF] Bao | Minimal points, variational principles, and variable preferences in set optimization[END_REF] becomes

√ ab/2 -1 ϕ f (x k 0 )/2 -ϕ f (x k 0 +1 )/2 ≥ q x k 0 , x k 0 +1 . ( 19
)
As C 2 f x k 0 1/2f x k 0 +1 1/2 is positive, inequality (13) follows immediately from [START_REF] Mordukhovich | Variational analysis and generalized differentiation. I. Basic theory[END_REF]. Now, let us assume that (b) holds. This fact gives us the following inequality:

f x k 0 1/2 ≤ √ 2/ √ 2 -1 f x k 0 1/2 -f x k 0 +1 1/2 .
Hence, from [START_REF] Cruz | A Steepest Descent-Like Method for Variable Order Vector Optimization Problems[END_REF], 13) follows immediately from the last inequality, which completes the proof of the statement. Let us prove [START_REF] Carver | On the structure of behavioral self-regulation[END_REF] by induction on k. First, we are going to prove [START_REF] Carver | On the structure of behavioral self-regulation[END_REF] for k = 0, 1. From ( 9), we have that x 0 ∈ B( x, ρ), and in view of (10), x 1 ∈ B( x, εβ 1 ) and f (x 1 ) ≥ 0. Using (1) with k = 0, we have

q x k 0 , x k 0 +1 ≤ 2 λ/ √ a √ 2 -1 f x k 0 1/2 -f x k 0 +1 1/2 . Because C 1 ϕ f x k 0 /2 -ϕ f x k 0 +1 /2 is positive, (
q 2 x 0 , x 1 ≤ λ a f (x 0 ) -f (x 1 ) ≤ λ a f (x 0 ). ( 20
)
A combination of the last inequality and the triangle inequality gives us

q x, x 1 ≤ q x, x 0 + q x 0 , x 1 ≤ λ a f (x 0 ) 1/2 + q x, x 0 .
Combining the last inequality with (9) implies that x 1 belongs to B q ( x, ρ). Now, take j > 1, and assume that [START_REF] Carver | On the structure of behavioral self-regulation[END_REF] holds for all k = 1, . . . , j -1. In this case, (13) holds for k = 1, . . . , j -1. Then, we obtain

j-1 i=1 q x i , x i+1 ≤ C 1 ϕ( f (x 0 )) -ϕ( f (x j )) + C 2 f x 0 1/2 -f x j 1/2 . ( 21
)
From the triangle inequality, q x, x j ≤ j-1 i=1 q x i , x i+1 + q x 0 , x 1 + q x, x 0 .

Thus, combining the last two inequalities with (20), we have

q x, x j ≤ q x, x 0 + λ a f (x 0 ) 1/2 + C 1 ϕ( f (x 0 )) + C 2 f x 0 1/2 ,
which, from ( 9), conclude the induction proof. Now, inequality [START_REF] De Ridder | Self-regulation in health behavior[END_REF] holds for all k ≥ 0. Then, we have

N j=0 q x k , x k+1 ≤ C 1 ϕ f (x 0 ) + C 2 f x 0 1/2 , N ≥ 0. ( 22
)
Note that ( 12) follows immediately from [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF]. Now, combining the first inequality presented in Assumption 3.1 with ( 12), we conclude that {x k } is a Cauchy sequence and, consequently, converges to some point x. Now, it follows from vi) of Proposition 3.1, that x is a critical point of f . Lastly, let us prove

f ( x) = f ( x) and f (x k ) → f ( x).
As { f (x k )} is strictly decreasing and f is bounded below, we have x k ∈ dom f for all k, and { f (x k )} converges to f = inf k≥0 f (x k ). From ( 10), we have f (x k+1 ) ≥ 0 for all k, which implies that f ≥ 0. Suppose that f > 0. As ϕ is a concave function and x k ∈ U for all k, we obtain

ϕ f w k ≥ ϕ f x k w k ≥ 1, k = 0, 1, . . . , which is impossible, because w k → 0. Hence, f = 0. As f is continuous on dom f , we have x ∈ dom f and f (x k ) → f ( x). Therefore f ( x) = f ( x).
Assumptions ( 8), ( 9) and ( 10) were used in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF], in the particular case where q was the Euclidean distance. Besides, the authors in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] noted that if f satisfies the Kurdyka-Lojasiewicz property at an accumulation point of the sequence {x k }, then assumptions ( 8), ( 9) and ( 10) are dispensable, since they are naturally verified for some x k 0 as a new initial point instead of x 0 . Some papers have dealt with the case where the Kurdyka-Lojasiewicz property is assumed directly at an accumulation point of the sequence {x k }; see, for instance, [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies kurdyka-Lojasiewicz inequality[END_REF]. In [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF] the authors considered sequences that naturally satisfied the conditions of the abstract model investigated in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] and noted that several standard assumptions automatically guarantee the boundedness of the sequence {x k }, hence its convergence. Next, we present a convergence result following the idea presented in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality[END_REF].

Theorem 3.2 Assume that f satisfies the Kurdyka-Lojasiewicz property (5) at each point in the domain of f , and suppose that Assumption 3.1 holds. Then (i) either x k tends to infinity;

(ii) or q x k , x k+1 is l 1 , i. e., +∞ k=0 q x k , x k+1 < +∞, and as a consequence, {x k } converges to a critical point of f . Proof Assume that (i) does not happen, and let x be a limit point of {x k } and U, ρ, η, ϕ the associated objects, as defined in [START_REF] Fuentes | Descentwise inexact proximal algorithms for smooth optimization[END_REF]. Note that Proposition 3.1 implies that x is critical of f . As { f (x k )} is a nonincreasing sequence, we deduce that f (x k ) converges to f ( x) and f (x k ) ≥ f ( x) for all k ≥ 0. Hence, the sequence

b k := q x, x k + λ/a 1/2 + C 2 f (x k ) -f ( x) 1/2 + C 1 ϕ f (x k ) -f ( x)
admits 0 as a cluster point; we obtain the existence of k 0 ∈ N such that ( 8) and ( 9) are fulfilled with x k 0 as a new initial point. Now, let us prove Assumption [START_REF] Bandura | Failures in self-regulation: Energy depletion or selective disengagement?[END_REF]. Take x k ∈ B q ( x, ρ). If necessary, shrink η so that η < a/ λ(εβ 1 -ρ) 2 . From (1), we have

q x k , x k+1 ≤ λ k a f (x k ) -f (x k+1 ) . ( 23
)
Taking into account that

f (x k+1 ) -f (x˜) ≤ f (x k ) -f (x˜) ≤ f (x k 0 ) -f (x˜)<η, k ≥ k 0 ,
we deduce from (23) that q(x k , x k+1 )<εβ 1 -ρ, k ≥ k 0 . Hence, from the triangle inequality,

q(x˜, x k+1 ) ≤ q(x˜, x k ) + q(x k , x k+1 )<ρ + (εβ 1 -ρ) = εβ 1 .
Therefore, Assumption [START_REF] Bandura | Failures in self-regulation: Energy depletion or selective disengagement?[END_REF] holds for all k ≥ k 0 . The conclusion is a consequence of Theorem 3.1.

Remark 3.3

The stopping rule (2) limits the size of the norm of the subgradient as an incentive to stop to change, compared to advantages to change f

(x k ) -f (x k+1 ).
Let us perform a comparison with the stopping rule H2in [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF], using a quasidistance instead of a distance, w k+1 ≤bq(x k , x k+1 ). It shows that the two descent processes are dual in the following two senses. First, our stopping rule majorizes the norm of the subgradient w k+1 by a function of advantages to change, namely, f (x k )f (x k+1 ) /bλ k 1/2 , while [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] majorizes the norm of the subgradient w k+1 by a function of inconveniences to change, namely b q(x k , x k+1 ) 2 1/2 = bq(x k , x k+1 ). Second, duality works also on f (x k+1 ) ≥ f (x k )/2 or the reverse, instead of q(x k , x k+1 ) ≥ q(x k-1 , x k )/2 or the reverse. This shows a great advantage in using concepts of the VR approach (see [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF]) to further understand different descent dynamics in a unified manner. The dual descent method works on advantages to change to limit the norm of the gradient, while the primal descent method [START_REF] Attouch | Convergence of descent methods for semi-algebric and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF] approach works on inconveniences to change.

To establish the rate of convergence of Method 3.1, we assume that ϕ is given as in [START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF] and, for simplification, we consider that (C/(1 -θ)) = 1.

Corollary 3.1 Under the assumptions of Theorem 3.1, there exists

x ∈ dom f such that q x k , x ≤ β 2 β 1 C 1 2 1-θ f x k 1-θ + C 2 f x k 1/2 , k ≥ 0.
Proof As we argued in Theorem 3.1, let us suppose that f ( x) = 0. In view of (11), x k ∈ B q ( x, ρ) for all k ≥ 0, which means ( 13) holds for all k ≥ 0. Using inequality [START_REF] De Ridder | Self-regulation in health behavior[END_REF], considering that ϕ(s) = s 1-θ andf (x N +1 ) < 0, we have

q x k , x N +1 ≤ N j=k q x j , x j+1 ≤ C 1 2 1-θ f x k 1-θ +C 2 f x k 1/2 , N ≥ k ≥ 0,
where the first inequality follows from the triangular inequality. As Assumption 3.1 holds, the last inequality becomes

β 1 x k -x N +1 ≤ C 1 2 1-θ f x k 1-θ + C 2 f x k 1/2 , N ≥ k ≥ 0.
From Theorem 3.1, there exists x ∈ dom f such that lim k→+∞ x k = x. Letting N goes to infinity in the last inequality and using again Assumption 3.1, we obtain

β 1 β 2 q x k , x ≤ C 1 2 1-θ f x k 1-θ + C 2 f x k 1/2 , k ≥ 0,
which proves the desired result. Now, we present an analysis of the rate of convergence.

Theorem 3.3

Under the assumptions of Theorem 3.1, there exists x ∈ dom f satisfying the following statements:

(i) If θ ∈ [0, 1/2], there exists k ∈ N such that q x k , x ≤ μQ k , k ≥ k, ( 24
)
with μ = f (x 0 ) 1/2 β 2 /β 1 C 1 /2 1-θ + C 2 and Q = 1/(1 + b λ/(1 -θ) 2 ) 1/2 ; (ii) If θ ∈]1/2, 1[, there exists C > 0 and k ∈ N such that q x k , x ≤ C ⎛ ⎝ k-1 j= k λ j ⎞ ⎠ (θ-1)/(2θ-1) , k ≥ k. ( 25
)
with C = β 2 /β 1 C 1 /2 1-θ + C 2 τ 1-2θ and τ = min 2 -2θ (2θ -1)b, (2 2θ-1 -1)/ λ .
Proof As we argued before, let us assume that f ( x) = 0. From Theorem 3.1 we have x k ∈ B( x, ρ) for all k ≥ 0 and f (x k ) → 0. This implies that there exists k ∈ N such that

x k ∈ B q ( x, ρ), 0 ≤ f (x k ) ≤ min{η, 1}, k ≥ k.
Considering that B q ( x, ρ) ⊂ B( x, ε), for k ≥ k, we have from ( 5),

(1 -θ) f x k+1 -θ w k+1 ≥ 1, k ≥ k. (26)
Now, let us prove [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF]. We estimate the rate of decay of the sequence { f (x k )}. From (2), we have [START_REF] Bolte | The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], along with the last inequality, gives us

f x k ≥ f x k+1 + bλ k w k+1 2 , k ≥ 0, with w k+1 ∈ ∂ f x k+1 . As λ k > λ,
f x k ≥ f x k+1 + b λ/(1 -θ) 2 f x k+1 2θ , k ≥ k. (27)
As 0 ≤ θ ≤ 1/2, and f

(x k ) ≤ 1, we obtain f x k+1 2θ ≥ f x k+1 , k ≥ k. Hence, (27)
implies

f x k+1 ≤ 1/(1 + b λ/(1 -θ) 2 ) f x k , k ≥ k.
Thus, it is easy to see that

f x k ≤ 1/(1 + b λ/(1 -θ) 2 ) k f x 0 , k ≥ k. (28)
However, from Corollary 3.1, there exists x ∈ dom f such that

q x k , x ≤ β 2 β 1 C 1 2 1-θ f x k 1-θ + C 2 f x k 1/2 , k ≥ k. ( 29
)
As 29), we have

f (x k ) 1-θ ≤ f (x k ) 1/2 , k ≥ k, in view of (
q x k , x ≤ β 2 β 1 C 1 2 1-θ + C 2 f x k 1/2 , k ≥ k. (30)
Combining ( 28) with [START_REF] Bolte | Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF], we obtain

q x k , x ≤ f (x 0 ) 1/2 β 2 β 1 C 1 2 1-θ + C 2 1 1 + b λ/(1 -θ) 2 1/2 k , k ≥ k,
which proves [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF]. Now, let us prove [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. For this purpose, we need to prove that

f x k+1 1-2θ -f x k 1-2θ ≥ τ λ k , k ≥ k, (31)
where τ = min 2 -2θ (2θ -1)b/(1 -θ) 2 , (2 2θ-1 -1)/ λ . For k ≥ k fixed, we have two possibilities:

(a) f (x k+1 ) > f (x k )/2; (b) f (x k+1 ) ≤ f (x k )/2.
Suppose that (a) holds. As the function [0, +∞) t → t 1-2θ is convex,

f x k+1 1-2θ -f x k 1-2θ ≥ (2θ -1) f x k -2θ f x k -f x k+1 . As θ ∈]1/2, 1[, 2 -2θ f (x k+1 ) -2θ < f (x k ) -2θ
. Combining (2) with the last inequality, we obtain

f x k+1 1-2θ -f x k 1-2θ ≥ 2 -2θ (2θ -1) bλ k f x k+1 -2θ w k+1 2 , ( 32
)
where w k+1 ∈ ∂ f (x k+1 ). Taking into account that inequality (26) holds, (32) becomes:

f x k+1 1-2θ -f x k 1-2θ ≥ 2 -2θ (2θ -1) b/(1 -θ) 2 λ k ≥ τ λ k . However, if (b) holds, 2 1-2θ f (x k+1 ) 1-2θ ≥ f (x k ) 1-2θ ; hence, f x k+1 1-2θ -f x k 1-2θ ≥ 2 2θ-1 -1 f x k 1-2θ . As 1/2 < θ < 1 and f (x k ) ≤ 1, we have f (x k ) 1-2θ ≥ 1. Then, f x k+1 1-2θ -f x k 1-2θ ≥ 2 2θ-1 -1 ≥ τ λ ≥ τ λ k .
Hence, (31) holds. Take k ∈ N greater that k. Summing inequality [START_REF] Bento | A New Approach to the Proximal Point Method: Convergence on General Riemannian Manifolds[END_REF] from k to k -1, we obtain

f x k 1-2θ -f x k 1-2θ = k-1 j= k f x j+1 1-2θ -f x j 1-2θ ≥ τ k-1 j= k λ j , k ≥ k.
Taking into account that f (x k ) 1-2θ > 0 and 1 -2θ < 0, last inequality becomes

f x k ≤ ⎛ ⎝ τ k-1 j= k λ j ⎞ ⎠ 1-2θ , k ≥ k. (33)
As f (x k ) 1/2 ≤ f (x k ) 1-θ , we can combine [START_REF] Lageman | Convergence of gradient-like dynamical systems and optimization algorithms[END_REF] with [START_REF] Li | Weak sharp minima on Riemannian manifolds[END_REF] to obtain

q x k , x ≤ β 2 β 1 C 1 2 1-θ + C 2 τ 1-2θ ⎛ ⎝ k-1 j= k λ j ⎞ ⎠ (θ-1)/(2θ-1)
, k ≥ k, and the proof is complete.

Variational Rationality and Discrepancy Reduction

In this section we justify: (i) Why these two descent methods are dual in terms of Behavioral Sciences, and (ii) why we introduce quasi-distances. The structure of the VR approach [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF][START_REF] Soubeyran | Variational rationality. Part 1. Worthwhile stay and change approach-avoidance human dynamics ending in traps[END_REF] defines each period a previous position x = x k and current position y = x k+1 , where a position is an activity, having something or being somewhere.

A change x = x k y = x k+1 is worthwhile if the motivation to change M(x, y) = U [A(x, y)] ∈ R + is sufficiently high compared to the resistance to change R(x, y) = D [I (x, y)] ∈ R + , that is if M(x, y) ≥ ξ R(x,
(x k , x k+1 ) = f (x k ) -f (x k+1 ) ≥ ξ k+1 q 2 (x k , x k+1 ) = ξ k+1 R(x k , x k+1
). It means that the change x k x k+1 is worthwhile. Then, our dual descent must be worthwhile. Condition (2) gives a condition on the curvature of the unsatisfaction function at x k+1 .

Costs of being able to stay are supposed to be zero, C(x, x) = 0 for all x ∈ X . Costs of being able to change, C(x, y) = q(x, y), are quasi-distances (see [START_REF] Soubeyran | Variational rationality. Part 1. Worthwhile stay and change approach-avoidance human dynamics ending in traps[END_REF]) for a precise justification. They are not symmetric. The costs of being able to change from x to y are different from those of being able to change from y to x.

123

The primal descent method [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies kurdyka-Lojasiewicz inequality[END_REF] considers a descent greater than half of the previous distance and quasi-distance, q(x k , x k+1 ) < (1/2)q(x k-1 , x k ), while the dual descent method ( [START_REF] Alaa | Convergence to equilibrium for discretized gradient-like systems with analytic features[END_REF] and this paper) considers a descent greater than half of the previous discrepancy f (x k+1 ) > (1/2) f (x k ).

Comparison of the Dual Speeds of Convergence

In this last section, we compare the speed of convergence of our dual descent method (this paper, Theorem 3.3) with the speed of convergence of the primal descent method [START_REF] Bento | A generalized inexact proximal point method for nonsmooth functions that satisfies kurdyka-Lojasiewicz inequality[END_REF]Theorem 3.12].

MAIN RESULT. The primal and dual descent methods have the same rate of convergence when 0 < θ < 1/2. In the opposite case, where 1/2 < θ < 1, the dual descent method converges faster than the primal descent methods if

λ k ≥ λ > 1 for k ≥ k * .
Proof There are two cases, Case I 0 < θ < 1/2. Then, the two methods give the same rate of convergence

q(x k , x) ≤ cQ k for k ≥ k 0 . Case II 1/2 < θ < 1. Let σ = (1 -θ)/(2θ -1) > 0 and L(k) = k-1 j=k λ j . Then, -the primal descent method gives q P (x k , x) ≤ C P k -σ , -the dual descent method gives q D (x k , x) ≤ C D L(k) -σ .
This shows that the quasi-distance from the current position x k to the limit position x decreases more in the dual descent method than in the primal descent method if

L(k) -σ < k -σ , that is if L(k) = k-1 j=k λ j > k. This is the case when λ j ≥ λ > 1 for all j = k, . . . , k -1. In this situation, (k -1 -k)λ > k is satisfied if k > k * = (λ/(λ -1))(1 + k).
Theorem 3.3 gives us an algebraic interpretation of the speed of convergence of the sequence that satisfies the conditions of Method 3.1. Let us define the speed of convergence as proportional to the size of the quasi-distance between the current point x k and critical point x, q(x k , x). Now, let us look more closely to analyze conditions [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] and [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF] accurately from the viewpoint of the recent VR approach; see Soubeyran [START_REF] Soubeyran | Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors[END_REF][START_REF] Soubeyran | Variational rationality and the nsatisfied man routines and the course pursuit between aspirations, capabilities and beliefs[END_REF][START_REF] Soubeyran | Variational rationality. Part 1. Worthwhile stay and change approach-avoidance human dynamics ending in traps[END_REF]. In item (i), expressions of the constants μ and Q in [START_REF] Kurdyka | On gradients of functions definable in o-minimal structures[END_REF] show that μ decreases when a and b increase, while Q decreases when only b increases. The speed of convergence increases in three situations: (i) First, if a increases, i.e., when being worthwhile to change requires more advantages to change compared to inconveniences to change (see inequality (1)); (ii) Second, if b increases, because a higher b decreases both μ and Q, it decreases Q k even more. A higher b requires, for the same advantage to change f (x k )f (x k+1 ), to get a lower marginal advantage to change. This pushes the agent to stop changing earlier, each period, because, marginally (making one more incremental very small unit change), he will have a lower marginal advantage to change, despite being given the same advantage to change. Then, the size of each step will probably decrease. The effect of a higher b seems to be the most important for increase in the speed of convergence. Then, the stopping rule, which determines the size of each step, plays a major role in the speed of convergence; (iii) Third, the lower the f (x 0 ), the higher is the speed of convergence (the time spent to converge). This is very intuitive, because the gap to fill, f (x 0 )inf f ≥ 0, is smaller. Similarly, the expression of C in [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF] shows us that C will decrease if a or b increases. In both cases, the same comments as above can be applied.

Conclusions

In this paper, we present an abstract descent method in the quasi-metric setting, where the descent condition works on payoffs (half the payoff, each time). The main convergence result is restricted to functions that satisfy the Kurdyka-Lojasiewicz property. An analysis of the rate of convergence is also presented. We also compare the rate of convergence of the primal and dual descent methods, showing that the dual descent method can converge faster in a large domain of cases. The motivation comes from Psychology, where tension reduction processes (goal striving) play a major role. In future research, we intend to investigate our descent method in more general contexts, for example, to the Riemannian context. It is worth noting that in recent years there has been an increasing number of studies proposing extensions of concepts and techniques, as well as methods of mathematical programming pertaining to the linear setting to the Riemannian context. Particularly, Li et al. [START_REF] Li | Weak sharp minima on Riemannian manifolds[END_REF] extended the notion of weak sharp minima and its characterization to the Riemannian setting. As in the linear setting, in the Riemannian context this notion is very instrumental for descent methods. In fact, introducing these notions has been motivated by numerical applications; see, for instance, Bento and Cruz Neto [START_REF] Bento | Finite termination of the proximalpoint method for convex functions on Hadamard manifolds[END_REF]. We foresee further progress in this topic in the near future.

  y), ξ > 0, where, (a) ξ refers to how worthwhile the change is: The higher ξ, the more worthwhile the change is; (b) U [A(x, y)] refers to the utility U [A] of advantages to change A(x, y); (c) A(x, y) = f (x)f (y) is the difference between the dissatisfaction f (x) ∈ R of being again in position x and the possibly reduced dissatisfaction f (y) to be in the new position y; (d) M(x, y) is the positive tension generated by the discrepancy A(x, y) = f (x)f (y) ≥ 0; (e) D [I (x, y)] refers to the disutility D [I ] of inconveniences to change I (x, y); (f) I (x, y) = C(x, y) -C(x, x) ≥ 0 is the difference between costs C(x, y) ∈ R + of being able to change from x to y and costs C(x, x) ∈ R + of being able to stay at x. Our Method 3.1 is a specific instance of a worthwhile change, where U [ A] = A, D [I ] = I 2 , I (x, y) = q(x, y), ξ k+1 = a/λ k > 0. Condition (1) reads M

Acknowledgments

The work was supported by CAPES and CNPq.