Dominikus Noll
email: dominikus.noll@math.univ-toulouse.fr

Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality

Keywords: Non-smooth non-convex optimization, subgradient-oriented descent method, strict model, Kurdyka-Łojasiewicz inequality, upper C 1 function, lower C 1 function AMS Classification: 90C56, 49M37, 93B40

Convergence of non-smooth descent methods using the

Kurdyka-Łojasiewicz inequality.

Introduction

In smooth optimization a sequence of descent directions d j at iterates x j is called gradient-oriented iff the angle between d j and the negative gradient -∇f (x j ) stays uniformly away from 90 • . Convergence of gradient-oriented methods is guaranteed by the Armijo condition in tandem with a safeguard against too small steps [START_REF] Dennis Jr | Numerical Methods for Unconstrained Optimization and Nonlinear Equations[END_REF]. Convergence is apriori understood in the sense of subsequences, but the work of Absil et al. [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF], and subsequent generalizations [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF][START_REF] Noll | Convergence of linesearch and trust-region methods using the Kurdyka-Łojasiewicz inequality[END_REF], assures aposteriori convergence x j → x * to a single critical point x * if f satisfies the Kurdyka-Łojasiewicz inequality.

Here we investigate how similar results may be obtained in non-smooth optimization. We consider the class of subgradient-oriented descent algorithms, where trial steps are generated by successive solving of a convex quadratic tangent program, and acceptance is achieved via a backtracking mechanism, and where the possibility to use bundling techniques to deal with large size problems is included. We prove convergence of subgradient-oriented methods under the KL-inequality for objectives f in the class S of non-smooth functions having a strict standard model in the sense of [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF]. We show that for f ∈ S , convergence can be forced algorithmically by a backtracking mechanism, and we demonstrate by way of an example that convergence to a critical point may fail even for tame convex functions f ̸ ∈ S .

The work of Bolte et al. [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF] is of interest to us. These authors characterize the Kurdyka-Łojasiewicz property for convex C 1,1 -functions by length boundedness of piecewise gradient iterates, and by the existence of an approximate talweg. We show that in the non-smooth case convergence of discrete subgradient trajectories, or of the talweg, is no longer linked to the Kurdyka-Łojasiewicz inequality. Something else is needed, namely, a function f ∈ S . For f ∈ S we obtain convergence in the sense of subsequences of a variant of the talweg, and convergence to a single critical points when the strong Kurdyka-Łojasiewicz property is added. These results are in contrast with the continuous case [START_REF] Bolte | The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], where finite length of the subgradient trajectory automatically implies convergence to a critical point.

Our work is also related to Attouch et al. [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], where an abstract convergence result under the Kurdyka-Łojasiewicz inequality is proved. We investigate whether the sufficient conditions of [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] can be used in a nonsmooth approach where trial steps are generated by a convex quadratic tangent program. The results are discussed in Section 12.

The paper is organized as follows. Sections 2 -5 present the context and introduce subgradientoriented descent methods. In Section 6 we recall the model concept and prove that upper C 1 -functions belong to the class S of functions with a strict standard model. The central Sections 7 -9 prove convergence of subgradient-oriented descent methods for functions f ∈ S . Consequences for the talweg and for discrete gradient trajectories are given in Section 11. Links with the abstract descent result of [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] is discussed in Section 12. Limiting examples appear in Section 13.

Kurdyka-Łojasiewicz Inequality

Following [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF], we shall say that a locally Lipschitz function f : R n → R satisfies the Kurdyka-Łojasiewicz inequality (for short KL-inequality) at x * ∈ R n iff there exists 0 < η < ∞, a neighborhood U of x * , and a concave function κ : [0, η] → [0, ∞[ such that (i) κ(0) = 0, (ii) κ is of class C 1 on ]0, η[, (iii) κ ′ > 0 on ]0, η[, (iv) For every x ∈ U with f (x * ) < f (x) < f (x * ) + η we have

κ ′ (f (x) -f (x * ))dist(0, ∂ L f (x)) ≥ 1.
Here ∂ L (f (x) is the limiting subdifferential of f at x. We shall say that f satisfies the strong KL-inequality at x * if the same estimate holds for the Clarke subdifferential ∂f (x). For strictly differentiable functions we have ∂f (x) = {∇f (x)}, in which case this reduces to the standard definition of the KL-inequality. In Bolte et al. [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]Thm. 11] it is shown that definable functions satisfy the strong KL-inequality, and this class is expected to cover a large variety of practical cases.

Subgradient-oriented Descent

The angle condition does no longer describe a useful set of search directions in a non-smooth setting. The reason is that directions allowing descent form in general not a half-space, but a cone with opening angle < 180 • . That means a direction d with ∠(d, -g -) < 90 • , where g -is the steepest ascent subgradient, need not even allow descent. Fortunately, gradient-orientedness of d j could also be defined in the following equivalent way: each d j is the steepest descent direction at x j with respect to some euclidian norm ∥x∥ 2 j = x ⊤ P j x on R n , such that 0 < λ ≤ λ min (P j ) ≤ λ max (P j ) ≤ Λ < ∞ [START_REF] Dennis Jr | Numerical Methods for Unconstrained Optimization and Nonlinear Equations[END_REF] for all j ∈ N and certain 0 < λ < Λ < ∞. The charm of this second definition is that it carries over reasonably to the non-smooth case. Yet another difference between the smooth and the non-smooth case is that the concept of a descent direction depends on the choice of the subdifferential. We therefore avoid it and simply work with directions which allow descent, i.e., search directions d where f (x + td) < f (x) for some t 0 > 0 and all 0 < t ≤ t 0 . Altogether, this leads to Definition 3.1. A sequence d j of normalized directions allowing descent at x j ∈ R n is called subgradientoriented iff there exist Clarke subgradients g j ∈ ∂f (x j ) such that d j = -Pj gj ∥Pj gj ∥ , with the P j satisfying [START_REF] Dennis Jr | Numerical Methods for Unconstrained Optimization and Nonlinear Equations[END_REF].

We examine under what conditions subgradient-oriented method for non-smooth optimization convergence. We are interested in conditions which can be forced algorithmically.

Discrete Gradient-oriented Flow

Bolte et al. [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF] give a characterization of the Kurdyka-Łojasiewicz condition for convex C 1,1 functions in terms of finite length of discrete gradient flow trajectories. Here discrete gradient flow means sequences x j of iterates satisfying the strong descent condition

β∥∇f (x j )∥∥x j+1 -x j ∥ ≤ f (x j ) -f (x j+1 ). (2)
One can observe that if (2) is to hold for all points on the segment [x j , x j+1 ], then one obtains the condition β∥∇f (x j )∥ ≤ -∇f (x j ) ⊤ d j , which implies cos ∠(-∇f (x j ), d j ) ≥ β > 0. In other words, the sequence d j is then a gradient-oriented sequence of descent directions in the usual smooth sense .

Here we analyze the non-smooth and non-convex analogue of this result, using our definition 3.1. That is, we seek algorithmically verifiable conditions assuring convergence of discrete subgradient trajectories. Our results will be compared to [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF] in Section 11.

Abstract Descent Method

Attouch et al. [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] prove convergence of an abstract non-smooth descent method for functions satisfying the KL-inequality. They require their sequence x j to satisfy the axiom

f (x j ) -f (x j+1 ) ≥ a∥x j -x j+1 ∥ 2 (3)
for some a > 0, and the existence of

g j+1 ∈ ∂ L f (x j+1 ) satisfying ∥g j+1 ∥ ≤ b∥x j -x j+1 ∥ (4)
for some b > 0. While (3) is built along the lines of the usual strong descent condition (2) for subgradientoriented methods and can be forced by backtracking, it is less obvious in which way condition (4) can be forced algorithmically. The goal is to find conditions, which can be forced by a finite process at each iteration j of the algorithm, and which assure validity of (4) for the entire sequence x j .

If it is possible to force (4) algorithmically, then it is natural to also consider a similar condition rooted at x j , i.e., there exists g j ∈ ∂ L f (x j ) and b > 0 such that

∥g j ∥ ≤ b∥x j -x j+1 ∥, ( 5
)
because in tandem with the Kurdyka-Łojasiewicz inequality and tangent program (6), condition ( 5) is also sufficient to imply convergence to a single critical point.

In our framework we shall explain why both (4), ( 5) are difficult to force algorithmically for nonsmooth programs under the restriction that computable local models are used in the tangent program. We show in Section 13 by way of an example that ( 4) and ( 5) may both fail for a convex tame function f ̸ ∈ S .

On the positive side, our approach also shows that for functions f ∈ S , conditions like (4) and ( 5) are not needed. All that is required to prove convergence is a descent condition in the spirit of (3), in tandem with a diligent backtracking strategy (Theorem 9.1). We will get back to this interesting line in Section 12.

The Model Concept

Given a locally Lipschitz function f : R n → R, we call ϕ : R n × R n → R a first-order model of f if ϕ(•, x) is convex for every x ∈ R n and the following axioms are satisfied:

(M 1 ) ϕ(x, x) = f (x) and ∂ 1 ϕ(x, x) ⊂ ∂f (x).
(M 2 ) For every x and every ϵ > 0 there exists δ > 0 such that f (y) ≤ ϕ(y, x) + ϵ∥y -x∥ whenever ∥y -x∥ ≤ δ.

(M 3 ) ϕ is jointly upper semi-continuous, i.e., (y j , x j ) → (y, x) implies lim sup j→∞ ϕ(y j , x j ) ≤ ϕ(y, x).

One notices the similarity of this concept with the Taylor expansion of differentiable functions, which is corroborated by the fact that every locally Lipschitz function has a first-order model, which we call the standard model,

ϕ ♯ (y, x) = f (x) + f • (x, y -x).
Here

f • (x, d) is the Clarke directional derivative of f at x in direction d. For C 1 -functions ϕ ♯ (y, x) = f (x) + ∇f (x)(y -x)
reproduces indeed the Taylor expansion. There is, however, a major difference between the Taylor expansion and the model concept. Taylor expansion wants herself to be unique. The idea of the model concept is the opposite. We wish a given function to have as many models as possible, because every model leads to a different optimization method. for all x, y ∈ B(x, δ). The model ϕ is called strong iff it is strong at every x.

Remark 6.3. One notices the resemblance of ( M 2 ) with the Taylor-Young formula, and that of ( M 2 ) with the Taylor-Lagrange formula.

Remark 6.4. Notice that if a model is strong at x, then it is also strong for every x in a neighborhood of x. Strong models are strict, and strict models are models, but none of these is invertible. For instance, if

f is of class C 1,1 , then its Taylor expansion is strong, while it is strict if f is of class C 1 . So for f ∈ C 1 \ C 1,1 the Taylor expansion is strict but not strong. If we consider f (x) = x 2 sin(x -1 ) with f (0) = 0, then ϕ ♯ is a model, which is not strict at x = 0.
We recall from Spingarn [START_REF] Spingarn | Submonotone subdifferentials of Lipschitz functions[END_REF] and Rockafellar and Wets [START_REF] Rockafellar | Variational Analysis[END_REF] that a locally Lipschitz function f : R n → R is lower C k at x 0 iff there exists a compact space K and a continuous function F : B(x 0 , δ) × K → R for which all partial derivatives of order ≤ k are continuous, such that

f (x) = max y∈K F (x, y), x ∈ B(x 0 , δ). f is called lower C k iff it is lower C k at every x.
Recall that lower C 2 functions are already lower C k for every k ≥ 2 (cf. [START_REF] Rockafellar | Variational Analysis[END_REF]), but the class of lower C 1 functions is substantially larger than the class of lower C 2 functions. Finally, we call

f upper C k if -f is lower C k .
For the following see also [START_REF] Noll | Cutting plane oracles to minimize non-smooth non-convex functions[END_REF].

Proposition 6.5. Let f be locally Lipschitz. If f is upper C 1 , then its standard model ϕ ♯ is strict, and if f is upper C 2 , then ϕ ♯ is strong.

Proof: 1) Let f be upper C 1 at x. Let ϵ > 0. According to Daniilidis and Georgiev [START_REF] Daniilidis | Approximate convexity and submonotonicity[END_REF], there exists δ > 0 such that -f (tx + (1 -t)y)) ≤ -tf (y) -(1 -t)f (x) + ϵt(1 -t)∥x -y∥ for all x, y ∈ B(x, δ) and 0 ≤ t ≤ 1. This can be re-arranged as

f (y) ≤ f (x) + t -1 (f (x + t(y -x)) -f (x)) + ϵ(1 -t)∥x -y∥.
Taking the limit superior t → 0 + readily implies f (y) ≤ f (x)+f • (x, y -x)+ϵ∥x-y∥ = ϕ ♯ (y, x)+ϵ∥x-y∥, hence strictness of ϕ ♯ at x.

2) The proof of the upper C 2 case is similar. □

The following definition is useful for the analysis of the subsequent sections. Definition 6.6. A locally Lipschitz function f belongs to the class S iff its standard model ϕ ♯ is strict.

Remark 6.7. The property f ∈ S , i.e., having a strict standard model ϕ ♯ , seems substantially weaker than upper C 1 . Indeed, from Spingarn [START_REF] Spingarn | Submonotone subdifferentials of Lipschitz functions[END_REF] we know that upper C 1 at x is equivalent to the following: For every ϵ > 0 there exists δ > 0 such that for all x, y ∈ B(x, δ) and every g ∈ ∂f (x) one has -f (y) + f (x) ≥ g ⊤ (y -x) -ϵ∥y -x∥. In contrast, for strictness of ϕ ♯ it suffices that this be true for some g ∈ ∂f (x). We may represent this in a more compact form as follows: f is upper C 1 at x iff for every ϵ > 0 there exists δ > 0 such that for all x, x + td ∈ B(x, δ), ∥d∥ = 1, t > 0, we have

f (x + td) -f (x) t ≤ -f • (x, -d) + ϵ,
whereas strictness of the standard model replaces this by the formally weaker Proof: Let B = B(0, M ) be a bounded disk. We construct a strict model ϕ(•, x) for the x ∈ B. For y ∈ B and g ∈ ∂f (y) let t y,g (•) = f (y) + g ⊤ (• -y) be a tangent to f at y. We define the downshift of t y,g (•) with respect to x as

f (x + td) -f (x) t ≤ f • (x, d) + ϵ. Remark 6.8. If f is convex then ϕ(•, x) = f is a strong
s = s(x, y, g) = [t y,g (x) -f (x)] + + c∥y -x∥ 2 ,
where c > 0 is a fixed constant. Then we put m y,g (•, x) = t y,g (•) -s(x, y, g), which we call the downshifted tangent. Now we define

ϕ(•, x) = max{m y,g (•, x) : y ∈ B, g ∈ ∂f (y)},
and one can check that ϕ is indeed a strict first-order model of f at every x ∈ B. For a more detailed proof see [START_REF] Noll | Cutting plane oracles to minimize non-smooth non-convex functions[END_REF].

□

We have applied bundling techniques to lower C 1 functions quite successfully in the context of automatic control. We refer to [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF][START_REF] Noll | Cutting plane oracles to minimize non-smooth non-convex functions[END_REF][START_REF] Gabarrou | Design of a flight control architecture using a non-convex bundle method[END_REF][START_REF] Noll | Bundle methods for non-convex minimization with inexact subgradient and function values[END_REF][START_REF] Dao | Minimizing the memory of a system[END_REF] for theoretical material supporting this branch of the theory. One may observe that for lower C 1 functions the standard model ϕ ♯ is not the best choice, as more natural strict models ϕ or oracles in the sense of [START_REF] Noll | Cutting plane oracles to minimize non-smooth non-convex functions[END_REF] are available.

Descent Step Finding

In this section we discuss the question how to compute a subgradient-oriented descent step. The difficulty may be condensed to the observation that if g ∈ ∂f (x), then due to non-smoothness, -g may not necessarily allow descent. The directions allowing descent form a cone, not a half-space, and it is therefore harder to find one pointing into this cone. As the general theme of our work is the analysis of gradientoriented methods, we will during the following work with the standard model ϕ ♯ , even though some of the results hold for more general models.

A function

ϕ ♯ k : R n × R n → R is called a first-order working model iff ϕ ♯ k (•, x) is convex, ϕ ♯ k (•, x) ≤ ϕ ♯ (•, x), ϕ ♯ k (x, x) = ϕ ♯ (x, x) = f (x), and ∂ 1 ϕ ♯ k (x, x) ⊂ ∂ 1 ϕ ♯ (x, x) = ∂f (x).
Working models are maintained and updated iteratively during the inner loop (algorithm 1) with counter k by adding cutting planes. Here cutting planes means tangents to ϕ ♯ (•, x) at the various null steps y k . In other words, due to the specific structure of ϕ ♯ , each ϕ ♯ k has the form

ϕ ♯ k (•, x) = sup g∈G k f (x) + g ⊤ (• -x)
for a suitable G k ⊂ ∂f (x). Notice that the standard model itself has the same structure with

G = ∂f (x), i.e., ϕ ♯ (•, x) = sup g∈∂f (x) f (x) + g ⊤ (• -x), which guarantees ϕ ♯ k ≤ ϕ ♯ and ∂ 1 ϕ ♯ k (x, x) ⊂ ∂ 1 ϕ ♯ (x, x).
As we shall see, the management of the sets G k during the inner loop has to respect two basic rules, referred to as cutting planes and aggregation, which we proceed to explain.

Given the current working model ϕ ♯ k (•, x) at x, the step-finding algorithm computes the solution y k of the tangent program

min y∈R n sup g∈G k f (x) + g ⊤ (y -x) + 1 2t k ∥y -x∥ 2 P , (6)
where ∥x∥ 2 P = x ⊤ P x is an euclidian norm fixed during the inner loop at x. The solution y k of ( 6) is called the trial step, t k is called the stepsize, while t -1 k > 0 is sometimes referred to as the proximity control parameter. The necessary optimality condition for (6) implies

0 ∈ ∂ 1 ϕ ♯ k (y k , x) + t -1 k P (y k -x),
or what is the same,

g * k := t -1 k P (x -y k ) ∈ ∂ 1 ϕ ♯ k (y k , x). ( 7
)
We call g * k the aggregate subgradient and

f (x) + g * ⊤ k (• -x) the aggregate plane at y k . Notice that g * k ∈ ∂f (x) due to the specific structure of ϕ ♯ .
Having computed a trial step y k by solving (6), we test acceptance by computing the test parameter

ρ k = f (x) -f (y k ) f (x) -ϕ ♯ k (y k , x)
.

We say that y k satisfies the descent condition if ρ k ≥ γ. If this is the case, we accept x + = y k as the new serious iterate, and the step finding algorithm terminates successfully. On the other hand, if ρ k < γ, then we call y k a null step. In this case the inner loop has to continue, and this requires improving the working model by modifying the set G k , and possibly by shortening the stepsize t k . In the case of a null step y k , we compute

g k ∈ ∂f (x) such that ϕ ♯ (y k , x) = f (x) + g ⊤ k (y k -x)
and include g k in the new set G k+1 . Moreover, we also include the aggregate subgradient g * k in the set G k+1 .

Remark 7.1. Notice that our test ρ k >γ replaces the descent conditions ( 2) and ( 3).

Algorithm 1. Descent step-finding by backtracking.

Input: Current iterate x. Output: Serious iterate x + . Parameters:

0 < γ < γ < 1, 0 < θ < Θ < 1. 1: Initialize. Put counter k = 1, fix t 1 > 0 and g 0 ∈ ∂f (x). Put G 1 = {g 0 }. 2: Tangent program. Given t k > 0, the current G k ⊂ ∂f (x) and working model ϕ ♯ k (•, x) = f (x) + max g∈G k g ⊤ (• -x), compute solution y k of the tangent program (T P ) min y∈R n ϕ ♯ k (y, x) + 1 2t k ∥y -x∥ 2 P . 3: Acceptance test. Compute ρ k = f (x) -f (y k ) f (x) -ϕ ♯ k (y k , x) . If ρ k ≥ γ, then put x + = y k and quit successfully with new serious step. Otherwise, if ρ k < γ, goto step 4. 4: Cutting plane. Pick a subgradient g k ∈ ∂f (x) such that f (x) + g ⊤ k (y k -x) = ϕ ♯ (y k , x), or equiva- lently, f • (x, y k -x) = g ⊤ k (y k -x).
Include g k into the new set G k+1 for the next sweep. 5: Aggregate plane. Include the aggregate subgradient g * k in the new set G k+1 , and allow the inclusion of additional subgradients from ∂f (x). 6:

Step management. Compute the test quotient

ρ k = f (x) -ϕ ♯ (y k , x) f (x) -ϕ ♯ k (y k , x) . If ρ k ≥ γ, then select t k+1 ∈ [θt k , Θt k ]. On the other hand, if ρ k < γ then keep t k+1 = t k . Increment
counter k and go back to step 2.

We mention two specific ways of constructing the working model ϕ ♯ k . The first option is to maintain a finite set G k = {g 0 , . . . , g k-1 }, where at each step k the new cutting plane g k is added. In this case the tangent program has the simple form

min y∈R n max i=0,...,k-1 f (x) + g ⊤ i (y -x) + 1 2t k ∥y -x∥ 2 P , (8)
which can be converted to a convex quadratic program. Here the aggregate subgradient has the form

g * k = k-1 ∑ i=0 λ i g i , λ i ≥ 0, k-1 ∑ i=0 λ i = 1,
and the g i ∈ G k with λ i > 0 are said to be called by the aggregate g * k . Including g * k in the set G k+1 allows us to drop older elements of G k , so that the size of G k can be limited.

The second case of interest is when ϕ ♯ k = ϕ ♯ for all k. Here the test quotient ρ k has constant value 1, so we always reduce the stepsize in case of a null step. Adding cutting planes and aggregate planes has no effect, because they are already included in G = ∂f (x). The only action taken by the algorithm is backtracking. The solution y k of the tangent program has now the specific form y k = x -t k P g -, where g -∈ ∂f (x) is the projection of 0 onto ∂f (x) with respect to the euclidian norm ∥ • ∥ P . In other words, this case covers all non-smooth subgradient-oriented descent method with backtracking linesearch in the sense of definition 3.1.

Theorem 7.2. Let f be locally Lipschitz. Suppose 0 ̸ ∈ ∂f (x). Then after a finite number of trials k the descent step-finding algorithm locates g k ∈ ∂f (x) and a stepsize t k > 0 such that x + = x -t k P -1 g k satisfies the descent condition ρ k ≥ γ.

Proof: 1) We assume, contrary to what is claimed, that the algorithm turns infinitely, generating a sequence y k of trial points which all fail the acceptance test. That means ρ k < γ for all k ∈ N. According to step 5 of the algorithm the step size t k is either kept invariant, or reduced by a factor θ < 1, but it is never increased. We have therefore two cases. Case 1 is when t k → 0, case 2 is when t k is bounded away from 0. The latter means t k = t k0 for some k 0 ∈ N and all k ≥ k 0 . In both cases we will have to achieve a contradiction with the hypothesis 0 ̸ ∈ ∂f (x). Since the norm ∥ • ∥ P is fixed during the entire proof, we may without loss assume P = I during the following in order to simplify the notations.

2) Let us start with the case where t k → 0. By step 5 of the algorithm the step size t k is only reduced to t k+1 ≤ Θt k < t k when ρ k ≥ γ. We deduce that there exists an infinite subset K of N such that ρ k ≥ γ for every k ∈ K.

By the optimality condition [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF] we have

∥y k -x∥ = t k ∥g * k ∥, where g * k is the k th aggregate subgradient. Since ∥g * k ∥ ≤ max{∥g∥ : g ∈ ∂f (x)} < ∞, we must have y k → x. Using the fact that g * k is a subgradient of ϕ ♯ (•, x) at y k , the subgradient inequality implies g * ⊤ k (x -y k ) ≤ ϕ ♯ k (x, x) -ϕ ♯ k (y k , x), which in view of ϕ ♯ k (x, x) = f (x) and g * ⊤ k (x -y k ) = ∥g * k ∥∥x -y k ∥ gives ∥g * k ∥∥x -y k ∥ ≤ f (x) -ϕ ♯ k (y k , x) ≤ g ⊤ 0 (x -y k ), the latter because f (x) + g ⊤ 0 (y -x) ≤ ϕ ♯ k (y, x) for all k. We deduce ϕ ♯ k (y k , x) → f (x). Moreover, since 0 ̸ ∈ ∂f (x), we have ∥g * k ∥ ≥ η > 0 for some η > 0 and all k. That shows f (x) -ϕ ♯ k (y k , x) ≥ η∥x -y k ∥ (9)
for all k.

Next observe that ϕ ♯ k+1 (y k , x) = ϕ ♯ (y k , x) by step 4 of the algorithm. Therefore, expanding the control parameter ρ k , gives

ρ k = ρ k + f (y k ) -ϕ ♯ (y k , x) f (x) -ϕ ♯ k (y k , x) ≤ ρ k + ϵ k ∥x -y k ∥ η∥x -y k ∥ = ρ k + ϵ k /η
for a sequence ϵ k → 0 + . Here we use [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 the fact that y k → x and f (y) -ϕ ♯ (y, x) ≤ o(∥y -x∥) as y → x by the definition of the Clarke subdifferential. But ρ k < γ for all k and ϵ k /η → 0, hence ρ k ≤ γ + ϵ k /η < γ for all k large enough. This contradicts ρ k ≥ γ for the infinitely many k ∈ K, and settles the case where t k → 0.

3) Let us now consider the case where the step size t k is frozen from some counter k 0 onwards, i.e., t k =: t > 0 for all k ≥ k 0 . That means ρ k < γ for all k ≥ k 0 . As in part 2) of the proof we wish to show y k → x, but with the step size frozen this turns out more complicated to verify.

Let us introduce the objective function

ψ k (•, x) = ϕ ♯ k (•, x) + 1 2t ∥ • -x∥ 2 of program (6) for k ≥ k 0 . We know that ϕ ♯ k (y k , x) = f (x) + g * ⊤ k (y k -x
) by step 4 of the algorithm. Therefore

ψ k (y k , x) = f (x) + g * ⊤ k (y k -x) + 1 2t ∥y k -x∥ 2 .
We define the quadratic function

ψ * k (•, x) = f (x) + g * ⊤ k (• -x) + 1 2t ∥ • -x∥ 2 then ψ k (y k , x) = ψ * k (y k , x) (10)
by what we have just seen. By the definition of the aggregate subgradient we have [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF]. This proves the representation

f (x) + g * ⊤ k (• -x) ≤ ϕ ♯ k+1 (•, x), so that ψ * k (•, x) ≤ ψ k+1 (•, x). ( 11
) Notice that ∇ψ k (y, x) = g * k + t -1 (y -x), so that ∇ψ * k (y k , x) = g * k + t -1 (y k -x) = 0 by
ψ * k (y, x) = ψ * k (y k , x) + 1 2t ∥y -y k ∥ 2 . ( 12
)
Now we have

ψ k (y k , x) ≤ ψ * k (y k , x) + 1 2t ∥y k -y k+1 ∥ 2 (using (10)) = ψ * k (y k+1 , x) (using (12))
≤ ψ k+1 (y k+1 , x) (using ( 11)) ( 13)

≤ ψ k+1 (x, x) (y k+1 minimizer of ψ k+1 ) = ϕ ♯ k+1 (x, x) = f (x).
Therefore the sequence ψ k (y k , x) is monotonically increasing and bounded above by f (x), and converges to a value ψ * ≤ f (x). This shows that 1 2t ∥y k -y k+1 ∥ 2 is sandwiched in between two terms with the same limit, ψ * , hence ∥y k -y k+1 ∥ → 0. As ∥ • ∥ is euclidian and the sequence y k is bounded, we deduce

∥y k -x∥ 2 -∥y k+1 -x∥ 2 → 0. (14)
Now using both convergence results, ( 14) and ψ k (y k , x) → ψ * , we deduce

ϕ ♯ k+1 (y k+1 , x) -ϕ ♯ k (y k , x) = ( 15
)
ψ k+1 (y k+1 , x) -ψ k (y k , x) -1 2t ∥y k+1 -x∥ 2 + 1 2t ∥y k -x∥ 2 → 0. Next recall that f (x) + g ⊤ k (• -x) is an affine support function of ϕ ♯ k+1 (•, x) at y k . By the subgradient inequality g ⊤ k (y -y k ) ≤ ϕ ♯ k+1 (y, x) -ϕ ♯ k+1 (y k , x). Since ϕ ♯ k+1 (y k , x) = ϕ ♯ (y k , x), we have ϕ ♯ (y k , x) + g ⊤ k (y -y k ) ≤ ϕ ♯ k+1 (y, x). ( 16
)
Now we expand 16)).

0 ≤ ϕ ♯ (y k , x) -ϕ ♯ k (y k , x) = ϕ ♯ (y k , x) + g ⊤ k (y k+1 -y k ) -ϕ ♯ k (y k , x) -g ⊤ k (y k+1 -y k ) ≤ ϕ ♯ k+1 (y k+1 , x) -ϕ ♯ k (y k , x) + ∥g k ∥∥y k+1 -y k ∥ (using (
But the last term converges to 0 as a consequence of (15), boundedness of the g k , and y k+1 -y k → 0. This proves

ϕ ♯ (y k , x) -ϕ ♯ k (y k , x) → 0. (17)
Let us argue that ϕ

♯ k (y k , x) → f (x). If this is not the case, then lim inf k→∞ ϕ ♯ k (y k , x) = f (x) -η for some η > 0. Choose δ > 0 such that δ < (1 -γ)η. From (17) we know that ϕ ♯ (y k , x) -δ ≤ ϕ ♯ k (y k , x) for all k ≥ k 1 and some k 1 ≥ k 0 . Using ρ k ≤ γ for all k ≥ k 0 in tandem with f (x) > ϕ ♯ k (y k , x) gives f (x) -ϕ ♯ k+1 (y k , x) ≤ γ ( f (x) -ϕ ♯ k (y k , x) ) . Therefore γ ( ϕ ♯ k (y k , x) -f (x) ) ≤ ϕ ♯ k+1 (y k , x) -f (x) = ϕ ♯ (y k , x) -f (x) ≤ ϕ ♯ k (y k , x) + δ -f (x).
Passing to the limit for a subsequence realizing the limit inferior gives

-γη ≤ -η + δ,
contradicting the choice of δ. This shows η = 0 and proves ϕ ♯ k (y k , x) → f (x). From ( 17) we immediately derive ϕ ♯ (y k , x) → f (x). And this is from where we now deduce y k → x. Indeed, from estimate (13) we get

ψ k (y k , x) = ϕ k (y k , x) + 1 2t ∥y k -x∥ 2 ≤ ψ * ≤ f (x), so that ϕ k (y k , x) → f (x) shows 1 2t ∥y k -x∥ 2 → 0 and also ψ * = f (x).
To finish the proof, let us now achieve a contradiction by showing 0 ∈ ∂f (x). Namely, by the subgradient inequality,

t -1 (x -y k ) ⊤ (y -y k ) ≤ ϕ ♯ k (y, x) -ϕ ♯ k (y k , x) ≤ ϕ ♯ (y, x) -ϕ ♯ k (y k , x) (using ϕ ♯ k ≤ ϕ ♯ )
Passing to the limit gives

0 ≤ ϕ ♯ (y, x) -f (x) = ϕ ♯ (y, x) -ϕ ♯ (x, x).
As this is true for every y, we obtain 0 ∈ ∂ 1 ϕ ♯ (x, x) ⊂ ∂f (x), the desired contradiction. That settles the proof of case 2. □ Remark 7.3. The result tells us that if we are not able to find a step which allows descent at x, then 0 ∈ ∂f (x). However, the converse is not true. Even when 0 ∈ ∂f (x), we may still be able to find a descent step. Take for instance f (x) = -|x| at x = 0. Then 0 ∈ ∂f (x). Yet, if we initialize the step finding algorithm with g 0 = 1, then we will immediately get a descent step which passes the acceptance test ρ k ≥γ in step 3. It is therefore recommended to initialize the algorithm with a limiting subgradient

g 0 ∈ ∂ L f (x). When 0 ̸ ∈ ∂ L f (x)
, we increase our chances of finding a step allowing descent.

Remark 7.4. The above algorithm requires a method to compute g ∈ ∂f (x) where the maximum

g ⊤ d = f • (x, d) = max{h ⊤ d : h ∈ ∂f (x)} is attained for a given d.
The existence of such an oracle is a realistic hypothesis.

As an illustration consider eigenvalue optimization, where

f (x) = λ 1 (F (x)) with F : R n → S m of class C 1 and λ 1 : S m → R the maximum eigenvalue function on the space S m of m × m symmetric matrices. Then ∂f (x) = F ′ (x) * ∂λ 1 (F (x)) is computable as soon as F ′ (x) * is, because computation of ∂λ 1 (X) is well-known. More precisely, f • (x, d) = λ ′ 1 (X, D) = λ 1 ( Q ⊤ DQ ) ,
where

X = F (x) ∈ S m , D = F ′ (x)d ∈ S m
, and where the columns of Q form an orthonormal basis of the maximum eigenspace of X.

Then G = QQ ⊤ ∈ ∂λ 1 (X) attains the maximum λ 1 ( Q ⊤ DQ ) = G • D, and g = F ′ (x) * G therefore attains f • (x, d) = g ⊤ d.

Algorithm

In this section we state the main algorithm formally, and give a few comments on its rationale. Recall first that the step finding algorithm 1 combines successive improvement of the working model, achieved by adding cutting planes, with occasional backtracking steps, t k+1 = t k or t k+1 ∈ [θt k , Θt k ]. This means that in the inner loop (algorithm 1) the stepsize is never increased. Therefore, in the outer loop, we allow the stepsize t ♯ j+1 = θ -1 t k to increase if acceptance gives a good ratio ρ k ≥ Γ. If acceptance gives a ratio γ ≤ ρ k < Γ, then me memorize the last stepsize used.

We stress that the following algorithm contains the steepest descent method, and all subgradientoriented descent methods in the sense of definition 3.1, as special cases. On the other hand it is more general because it allows to approximate these methods by an iterative technique, which is implementable numerically. This is beneficial in practical situations, where the full subdifferential ∂f (x) is inaccessible to direct computation. Algorithm 2. Subgradient-oriented descent method.

Parameters: 0 < γ < γ < 1, 0 < γ < Γ < 1, 0 < θ < Θ < 1, 0 < c < C < ∞, 0 ≤ t < t ≤ ∞.
1: Initialize. Put counter j = 1, choose initial guess x 1 , and fix t ♯ 1 > 0. Choose an euclidian norm

∥x∥ 2 1 = x ⊤ P 1 x such that c∥ • ∥ ≤ ∥ • ∥ 1 ≤ C∥ • ∥. 2: Stopping. At counter j, stop if 0 ∈ ∂f (x j ).
Otherwise goto inner loop. 3: Inner loop. Given x j and the euclidian norm

∥ • ∥ j satisfying c∥ • ∥ ≤ ∥ • ∥ j ≤ C∥ • ∥,
such that c∥ • ∥ ≤ ∥ • ∥ j+1 ≤ C∥ • ∥. Then goto step 2.
Notice that step 5 is void if t = 0, and the same for step 6 when t = ∞. This is what we indicate by the term optional. In fact, we wish to avoid these rules in the convergence proofs, even though they are acceptable in practice. For instance, linesearch methods tempting second-order steps always put t = 1. Notice that if t = 0 and t = ∞, then the step length is fully memorized between serious steps, an important option for large scale programs.

In the smooth case, the idea of fully memorizing the steplength has been analyzed in [START_REF] Noll | Convergence of linesearch and trust-region methods using the Kurdyka-Łojasiewicz inequality[END_REF], with the outcome that stepsize may be fully memorized for C 1,1 -functions, whereas this is not possible for C 1 functions. Here the linesearch has to be started at t 1 ≥ t for a threshold t > 0. Since C 1 functions are upper C 1 , and C 1,1 -functions are upper C 2 , we can consider items 2 and 3 of Theorem 9.1 below as non-smooth extensions of Theorems 1, 2 in [START_REF] Noll | Convergence of linesearch and trust-region methods using the Kurdyka-Łojasiewicz inequality[END_REF], and of the results in [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF].

Convergence

In this section we prove convergence in the sense of subsequences of algorithm 2. Convergence to a single critical point will follow if the strong KL-property is satisfied. Theorem 9.1. Suppose f is locally Lipschitz and {x ∈ R n : f (x) ≤ f (x 1 )} is bounded. Let x j be the sequence generated by algorithm 2. Then the following are satisfied:

1. If the standard model ϕ ♯ of f is strict, i.e., f ∈ S , then x j has at least one accumulation point which is critical.

2. If the standard model is strict and algorithm 2 is operated with the small stepsize safeguard rule t > 0, then every accumulation point of x j is critical.

3. If the standard model is strong, then every accumulation point of the x j is critical (and the small step safeguard rule may be dispensed with: t = 0).

4.

If the standard model ϕ ♯ is strict and f satisfies the strong Kurdyka-Łojasiewicz property, then x j converges to a single critical point (and the small stepsize safeguard rule may be dispensed with:

t = 0).
In all these cases the large stepsize safeguard rule may be dispensed with, i. e., t = ∞.

Proof: 1) From the analysis of Section 7 we know that after a finite number of trials k the descent step finding algorithm 1 at serious iterate x j locates a new iterate x j+1 satisfying the acceptance test ρ k ≥ γ, unless we have finite termination due to 0 ∈ ∂f (x j ). Excluding this case, let x j be the infinite sequence of steps generated by algorithm 2. Suppose x j+1 is accepted at inner loop counter k j , i.e., x j+1 = y kj passes the acceptance test, while the y k with k < k j are null steps. This means

f (x j ) -f (x j+1 ) ≥ γ ( f (x j ) -ϕ ♯ kj (x j+1 , x j ) ) . ( 18
)
Now from optimality [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF] we know that g * j = t -1 kj P j (x j -x j+1 ) ∈ ∂ 1 ϕ ♯ kj (x j+1 , x j ), hence the subgradient inequality gives

(x j -x j+1 ) ⊤ t -1 kj P j (x j -x j+1 ) ≤ ϕ ♯ kj (x j , x j ) -ϕ ♯ kj (x j+1 , x j ) = f (x j ) -ϕ ♯ kj (x j+1 , x j ).
In tandem with [START_REF] Noll | Bundle methods for non-convex minimization with inexact subgradient and function values[END_REF], and using ∥u∥ 2 j = u ⊤ P j u, this gives the estimate

t -1 kj ∥x j -x j+1 ∥ 2 j ≤ γ -1 ( f (x j ) -f (x j+1 ) ) . ( 19
)
Summing ( 19) over j = 1, . . . , J -1 on both sides gives

J-1 ∑ j=1 t -1 kj ∥x j -x j+1 ∥ 2 j ≤ γ -1 ( f (x 1 ) -f (x J ) ) ,
and since the algorithm is of descent type and the set of iterates x j is bounded, the right hand side is bounded above, which implies summability of the series

∑ j t -1 kj ∥x j -x j+1 ∥ 2 j .
In particular, this implies t -1 kj ∥x j -x j+1 ∥ 2 j → 0, and since the norms ∥ • ∥ j are uniformly equivalent, t kj ∥x j -x j+1 ∥ 2 → 0. 2) Let us consider an infinite subsequence j ∈ N of N where g * j → 0, j ∈ N . We will show that every accumulation point of the x j , j ∈ N , is critical. Let x * be such an accumulation point, and passing to a subsequence if necessary, assume x j → x * , j ∈ N .

Since g * j is a subgradient of ϕ ♯ kj (•, x j ) at x j+1 = y kj , the subgradient inequality gives for every test vector h:

g * ⊤ j h ≤ ϕ ♯ kj (x j+1 + h, x j ) -ϕ ♯ kj (x j+1 , x j ) ≤ ϕ ♯ (x j+1 + h, x j ) -ϕ ♯ kj (x j+1 , x j ).
As x j+1 = y kj was accepted, we have f (x j ) -ϕ ♯ kj (x j+1 , x j ) ≤ γ -1 ( f (x j ) -f (x j+1 ) ) . Substituting this above gives

g * ⊤ j h ≤ ϕ ♯ (x j+1 + h, x j ) -f (x j ) + f (x j ) -ϕ ♯ kj (x j+1 , x j ) ≤ ϕ ♯ (x j+1 + h, x j ) -f (x j ) + γ -1 ( f (x j ) -f (x j+1 ) ) . Now putting h = x j -x j+1 + h ′ , we obtain g * ⊤ j (x j -x j+1 ) + g * ⊤ j h ′ ≤ ϕ ♯ (x j + h ′ , x j ) -f (x j ) + γ -1 ( f (x j ) -f (x j+1 ) ) .
Passing to the limit j ∈ N , using

x j → x * , boundedness of x j -x j+1 , g * j → 0 and f (x j ) -f (x j+1 ) → 0, we obtain 0 ≤ ϕ ♯ (x * + h ′ , x * ) -f (x * ) = ϕ ♯ (x * + h ′ , x * ) -ϕ ♯ (x * , x * ).
Since h ′ was arbitrary, this implies 0 ∈ ∂ 1 ϕ ♯ (x * , x * ) ⊂ ∂f (x * ), which proves what was claimed.

3) We shall now have to deal with the more complicated case of infinite subsequences J of N satisfying ∥g * j ∥ ≥ η > 0 for all j ∈ J . We first claim that under this assumption, t kj → 0, j ∈ J . Indeed, if t kj ≥ τ > 0 for all j ∈ J , then on passing to a subsequence J ′ ⊂ J , we may assume P j → P , x j -x j+1 → δx, t -1 kj → t -1 ≤ τ -1 , and such that t -1 ∥δx∥ P ≥ η. But at the same time (x j -x j+1 ) ⊤ t -1 kj P j (x j -x j+1 ) → 0 implies t -1 ∥δx∥ 2 P = 0, a contradiction. This shows t kj → 0 for the subsequence j ∈ J . 4) Let us for convenience call infinite sequences J with ∥g * j ∥ ≥ η > 0 for all j ∈ J problematic. We distinguish two types of problematic sequences. The first type are those J 1 where for every j ∈ J 1 the backtracking rule (step 6 of algorithm 1) was applied at least once during the j th inner loop. The second type are those J 2 where the backtracking rule was never applied during the j th inner loop for any one of the j ∈ J 2 . More formally,

J 1 ⊂ {j ∈ N : t ♯ j > t kj }, and J 2 ⊂ {j ∈ N : t ♯ j = t kj }.
Notice that every problematic subsequence J has either subsequences J 1 of type 1, or J 2 of type 2, or both. Subsequences J 1 will be discussed in parts 5) -9) of the proof, subsequences J 2 in part 10). 5) Consider a problematic subsequence j ∈ J 1 of the first type. Despite the fact that t kj → 0, it is conceivable that t ♯ j → ∞ on a subsequence. Fixing a small threshold ϑ > 0, we consider the set B = {x j , y k : k ≤ k j , j ∈ J 1 , t k ≤ ϑ}. On the other hand, for a problematic subsequence j ∈ J 2 we simply choose B = {x j , y k : k ≤ k j , j ∈ J 2 }. We show that in both cases B is bounded.

Observe that the set of all serious iterates is bounded, so the question hinges on whether the null step y k visited during the inner loop at x j remain uniformly bounded. Now let g 0j ∈ ∂f (x j ) be the first subgradient picked in the inner loop, which stays in the set G k at all counters k of the j th inner loop. Then {g 0j : j ∈ J } is bounded by the local boundedness of the Clarke subdifferential. By the subgradient inequality,

g * ⊤ k (x j -y k ) ≤ ϕ ♯ k (x j , x j ) -ϕ ♯ k (y k , x j ) ≤ g ⊤ 0j (
x j -y k ) ≤ ∥g 0j ∥∥x j -y k ∥, and moreover, by the specific structure of the aggregate (see part 2) of the proof of Theorem 7.2),

g * ⊤ k (x j -y k ) = ∥g * k ∥∥x j -y k ∥. We deduce ∥g * k ∥ ≤ ∥g 0j ∥ ≤ M < ∞
for all j and all 1 ≤ k ≤ k j . This shows t -1 k ∥x j -y k ∥ ≤ M for all k, j, and implies boundedness of those y k where t -1 k is bounded away from 0. This applies to those k where t k ≤ ϑ, and proves our claim.

6) Let us consider a problematic subsequence j ∈ J 1 of type 1. Let x be an accumulation point of J 1 . We will show that x is critical. Passing to a subsequence if necessary, we may assume x j → x, j ∈ J 1 .

Suppose that for j ∈ J 1 the backtracking rule was applied for the last time at stage k j -ν j with ν j ≥ 1. In other words,

t kj = t kj -1 = • • • = t kj -νj +1 < t kj -νj , ( 20
)
with t kj = θ kj -νj t kj -νj for some 0 < θ ≤ θ kj -νj ≤ Θ < 1. From the inner loop (algorithm 1) we know that backtracking occurs solely when ρ < γ, ρ ≥ γ. In consequence, we have

ρ kj -νj = f (x j ) -f (y kj -νj ) f (x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) < γ, ρ kj -νj = f (x j ) -ϕ ♯ (y kj -νj , x j ) f (x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) ≥ γ.
From [START_REF] Alber | On the projected subgradient method for nonsmooth convex optimization in a Hilbert space[END_REF] we know that g j := θ -1 kj -νj t -1 kj P j (x j -y kj -νj ) ∈ ∂ 1 ϕ ♯ kj -νj (y kj -νj , x j ). We will show that g j → 0, and subsequently, that this implies 0 ∈ ∂f (x).

By the subgradient inequality we have

(x j -y kj -νj ) ⊤ θ -1 kj -νj t -1 kj P j (x j -y kj -νj ) ≤ ϕ ♯ kj -νj (x j , x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) = f (x j ) -ϕ ♯ kj -νj (y kj -νj , x j ). (21)
Now as t -1 kj → ∞ for problematic subsequences, and by boundedness of the θ kj -νj , and boundedness of the set y k of trial points and serious iterates shown in part 5), we must have y kj-νj -x j → 0. Since x j → x, j ∈ J 1 , we have y kj -νj → x, too.

7) We claim that the g j = θ -1 kj -νj t -1 kj P j (x j -y kj -νj ), j ∈ J 1 , are bounded. This can be seen from ( 21). Indeed, the left hand side behave asymptotically like c∥ g j ∥∥x j -y kj -νj ∥. The right hand side of ( 21) is majorized by f (x j ) -m 0 (y kj -νj , x j ), where m 0 (•, x j ) is the exactness plane of the j th inner loop. Therefore, ( 21) may be transformed into c∥ g j ∥∥x j -y kj -νj ∥ ≤ ∥g 0j ∥∥x j -y kj -νj ∥.

But the g 0j ∈ ∂f (x j ) are bounded due to boundedness of the x j and local boundedness of the Clarke subdifferential operator ∂f , hence the claim.

8) We will now show that g j → 0, j ∈ J 1 . Assume contrary to what is claimed that ∥ g j ∥ ≥ θ > 0 for all j ∈ J 1 . This shows

f (x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) ≥ θ∥x j -y k-νj ∥ ( 22
)
for all j ∈ J 1 . Indeed, from the subgradient inequality,

g ⊤ j (x j -y kj -νj ) ≤ ϕ ♯ kj -νj (x j , x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) = f (x j ) -ϕ ♯ kj-νj (y kj -νj , x j ).
But the left hand side behaves asymptotically like ∥ g j ∥∥x j -y kj -νj ∥, hence the claim [START_REF] Noll | A bundle method for non-smooth and non-convex optimization[END_REF]. 9) This is now the moment where we apply the fact that f has a strict standard model ϕ ♯ . We apply axiom ( M 2 ) to the sequences x j → x and y kj -νj → x. That means there exist ϵ j → 0 such that f (y kj -νj ) -ϕ ♯ (y kj -νj , x j ) ≤ ϵ j ∥x j -y kj -νj ∥.

(

) 23
Now we expand

ρ kj -νj = ρ kj -νj + f (y kj -νj ) -ϕ ♯ (y kj -νj , x j ) f (x j ) -ϕ ♯ kj -νj (y kj -νj , x j ) ≤ ρ kj -νj + ϵ j ∥x j -y kj -νj ∥ θ∥x j -y kj -νj ∥ = ρ kj -νj + ϵ j /θ.
Since ϵ j → 0, this shows lim sup ρ kj -νj ≤ lim sup ρ kj -νj ≤ γ < γ, contradicting the fact that ρ kj -νj ≥ γ for every j ∈ J 1 . This proves g j → 0. Using the argument employed in part 2), we now deduce 0 ∈ ∂f (x).

10) It remains to deal with problematic subsequences J 2 of type 2. This can only be dealt with if the model is strong, or if the small stepsize safeguard rule is applied (that is, t > 0). Namely, in both cases, the existence of problematic subsequences of type 2 can simply be ruled out. For t > 0 this is clear, because then t ♯ j+1 is bounded below, and cannot go to zero. For ϕ ♯ strong this could be obtained from [START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF].

11) Let us now assume that f satisfies the Kurdyka-Łojasiewicz inequality. We have to show that x j converges to a single critical point x * .

We have shown that the sequence x j has at least one accumulation point x * which is critical. Moreover, the set of accumulation points L of x j is closed, as can be proved by a diagonal argument. Since f (x j ) is decreasing, we conclude that f has constant value on the set L.

By assumption, for every x ∈ L, there exists an open neighborhood U (x) of x and a continuous concave function κ

x : [0, η x ] → [0, ∞[ of class C 1 on (0, η x ) with κ x (0) = 0, κ ′ x > 0 on (0, η x ), such that κ ′ x (f (x ′ ) -f (x)) dist (0, ∂f (x ′ )) ≥ 1 whenever x ′ ∈ U (x) satisfies f (x) < f (x ′ ) < f (x) + η x .
Using compactness of L, we find finitely many points x 1 , . . . , x r ∈ L such that the U (x 1 ), . . . , U (x r ) cover L. Choose ϵ > 0 such that V := {x ∈ R n : dist(x, L) < ϵ} ⊂ ∪ r i=1 U (x i ). Put η = min i=1,...,r η xi , and define the function κ ′ (t) = max i=1,...,r κ ′ xi (t), then κ ′ is continuous and decreasing because all the κ ′ xi are. Putting κ(t) = ∫ t 0 κ ′ (τ ) dτ therefore defines a concave class C 1 function on [0, η] with κ(0) = 0 and κ ′ > 0 on (0, η). In addition, κ has the following property: For every x ∈ L and every

x ′ ∈ V = {x ′ : dist(x ′ , L) < ϵ} with f (x) < f (x ′ ) < f (x) + η there holds κ ′ (f (x ′ ) -f (x)) dist (0, ∂f (x ′ )) ≥ 1. (24)
Indeed, to see this let x, x ′ as above. Find x i such that x ′ ∈ U (x i ). Then

1 ≤ κ ′ xi (f (x ′ ) -f (x i )) dist(0, ∂f (x ′ )) ≤ κ ′ (f (x ′ ) -f (x)) dist(0, ∂f (x ′ )), using κ ′ xi ≤ κ ′ and f (x i ) = f (x)
. That proves our claim. Let us for the following assume without loss that f ≡ 0 on L. Recall that the aggregate subgradient

g * j = t -1 kj P j (x j -x j+1 ) satisfies t -1 kj ∥x j -x j+1 ∥ 2 j ≤ γ -1 ( f (x j ) -f (x j+1 ) ) by acceptance ρ ≥ γ. Concavity of κ gives the estimate κ ( f (x j ) ) -κ ( f (x j+1 ) ) ≥ κ ′ ( f (x j ) ) ( f (x j ) -f (x j+1 ) ) whenever 0 < f (x j ) < η, 0 < f (x j+1 ) < η. Combining these twain gives κ ( f (x j ) ) -κ ( f (x j+1 ) ) ≥ κ ′ ( f (x j ) ) γt -1 kj ∥x j -x j+1 ∥ 2 j .
By the strong KL-inequality (24), and using f (x) = 0, we have κ ′ ( f (x j ) ) ≥ ∥g∥ -1 for every Clarke subgradient g ∈ ∂f (x j ). Therefore in particular κ ′ ( f (x j ) ) ≥ ∥g * j ∥ -1 for the aggregate subgradient, which due to the specific form of the Clarke model ϕ ♯ belongs to ∂f (x j ). We deduce

κ ( f (x j ) ) -κ ( f (x j+1 ) ) ≥ γ t -1 kj ∥x j -x j+1 ∥ 2 j t -1 kj ∥P j (x j -x j+1 )∥ ≥ c ′ ∥x j -x j+1 ∥
for some constant c ′ . That proves summability of ∥x j -x j+1 ∥, hence x j is a Cauchy sequence, which converges to x * and L = {x * }. Since L was shown to contain at least one critical point of f , we conclude that x * is critical. That completes the proof of the Theorem. □

Consequences

In this section we present several consequences of the main Theorem 9.1, and give some comments.

The following result is the expected convergence of the steepest descent method. Notice that we obtain algorithmically verifiable criteria for convergence, i.e., conditions which can be forced by a finite procedure, as opposed to conditions like [START_REF] Alber | On the projected subgradient method for nonsmooth convex optimization in a Hilbert space[END_REF]. The price to pay for this is that f has to belong to the class S .

Corollary 10.1. Suppose f is upper C 1 and satisfies the strong KL-inequality. Let {x ∈ R n : f (x) ≤ f (x 1 )} be bounded and let x j be generated by a subgradient-oriented descent method, where the stepsize may be fully memorized. Then x j converges to a critical point of f .

Proof: By Proposition 6.5 we have f ∈ S . Therefore algorithm 2 converges for the special case, where step finding uses algorithm 1 with ϕ ♯ k = ϕ ♯ . Notice that we are in the case t = 0 and t = ∞, so no restriction at all is made on the stepsize, which means it is fully memorized. □

The next result describes a situation where the use of the small stepsize safeguard rule t > 0 may be beneficial. Namely, it gives a satisfactory answer for stopping even when the KL-inequality is not available:

Corollary 10.2. Let f ∈ S and suppose algorithm 2 is operated with t > 0. Suppose {x ∈ R n : f (x) ≤ f (x 1
)} is bounded. Then for every ϵ > 0 there exists j 0 ∈ N such that all iterates x j , j ≥ j 0 , are within distance ϵ of some critical point of f . Proof: Suppose there exist ε > 0 and infinitely many x j , j ∈ J , which have no critical point of f within ε reach. Due to t > 0, this sequence x j , j ∈ J , has an accumulation point, which by Theorem 9.1 is critical, a contradiction. □

The small stepsize safeguard rule is not needed if f has a strong model.

Corollary 10.3. Suppose f is upper C 2 and {x ∈ R n : f (x) ≤ f (x 1
)} is bounded. Then for every ϵ > 0 there exists j 0 ∈ N such that every iterate x j , j ≥ j 0 , is within distance ϵ of some critical point of f .

Proof: Since f has a strong standard model, infinite subsequences x j , j ∈ J 2 , where t ♯ j = t kj → 0 can be excluded. Those were named problematic subsequences of type 2 in the proof of Theorem 9.1. As the proof of Theorem 9.1 shows, all other subsequences (unproblematic, or problematic of type 1), have an accumulation point which is critical, and that proves the result.

□ So far we have never needed the large stepsize safeguard rule t < ∞. There is one specific situation, where this rule is beneficial, because it gives an additional option to converge to a single critical point without the KL-inequality.

Corollary 10.4. Suppose the set K of critical points of f ∈ S is apriori known to be totally disconnected. If algorithm 2 is operated with both safeguard rules, i.e., 0 < t < t < ∞, then the sequence x j converges to a single critical point x * .

Proof: From the proof of Theorem 9.1 we know that t -1 kj ∥x j -x j+1 ∥ → 0. Hypothesis t < ∞ yields t kj ≤ t < ∞, so we deduce x j -x j+1 → 0, j → ∞. As a consequence, by Ostrowski's theorem [START_REF] Ostrowski | Solution of Equations in Euclidean and Banach Spaces[END_REF], the set L of accumulation points of the sequence x j is either a singleton or a nontrivial compact continuum.

Secondly, hypothesis t > 0 assures that every accumulation point of the sequence x j of serious iterates is critical, so that L ⊂ K. Since by hypothesis the only connected components of K are the singletons, L must be singleton, hence x j converges to a single critical point x * . □

Once again we could dispense with t > 0 if f was upper C 2 , respectively, if model ϕ ♯ was strong, and we could dispense with t < ∞ if we knew from other reasons that x j -x j+1 → 0.

Talweg and the Unskilled Skier's Descent

The original motivation for the Kurdyka-Łojasiewicz property was to prove finite length of subgradient trajectories ẋ(t) ∈ -∂f (x(t)). In the continuous case this immediately implies convergence to a critical point [START_REF] Bolte | The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF]. Subgradient-oriented descent may be understood as a discrete form of subgradient trajectories, and in [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF] the authors use indeed finite length of such trajectories to characterize the KL-property. However, as we shall see in Section 13, in the discrete nonsmooth case, finite length of the trajectory does not imply convergence to a critical point. In order to assure convergence to a critical point, we need strictness of ϕ ♯ , i.e., f ∈ S .

In [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF] the authors use yet another discrete construction related to the KL-property, which they call the Talweg. Again, finite length of the Talweg may be used to characterize the KL-property. Here we consider the following slight modification of the Talweg: Algorithm 3. Unskilled skier's descent into the valley

Parameters: 0 < γ < γ < 1, 0 < γ < Γ < 1, 0 < θ < Θ < 1, 0 < c < C < ∞, K > 0.
1: Given the current serious iterate x, stop if 0 ∈ ∂f (x). Otherwise use the step-finding algorithm 1 to find x satisfying the acceptance test ρ ≥ γ. 2: Manage the stepsize t ♯ as in algorithm 2.

3: Given the intermediate iterate x, find the new serious iterate x + on the same level curve, i.e., f

(x + ) = f ( x), such that ∥x + -x∥ ≤ K∥ x -x∥. Then go back to step 1.
The interpretation is as follows. The novice skier, lacking control, starts steepest descent (schuss) downhill from his current position x. Not being able to wedel, this leads him straight to x, with sufficient decrease ρ ≥ γ achieved quickly. Stopping at x is arranged by sitting down on the bottom. In need of some rest, the clumsy skier now puts his skis in parallel with the level line to be stable for a while and then walks some distance along the level curve from x to x + . From here the procedure loops on by another pair of schuss-walk steps. The obvious question is whether the unskilled skier ever reaches the valley, i.e., whether the method converges to a critical point. (Finite length of the trajectory without convergence to a critical point is no consolation for the novice skier, because the ski lodge is at the bottom of the valley at a critical point. Convergence to a non-critical point means St. Bernhard dogs will have to pick him up on the slope a few days later).

We notice that the step from x to x is identical with the serious step of algorithm 2. In [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF] sequences with jumps like x → x + are called piecewise gradient trajectories.

Theorem 11.1. Suppose f is locally Lipschitz and {x ∈ R n : f (x) ≤ f (x 1 )} is bounded. Let x 1 , x 1 , x 2 , x 2 , . . . be the sequence generated by the unskilled skier's descent method. Then the following are satisfied:

1. If the standard model ϕ ♯ is strict, then x j , x j have at least one common accumulation point x * which is critical.

2. If the standard model is strong, then every accumulation point of x j , x j is critical.

3. If the standard model is strict and the small step safeguard rule (t > 0) is used, then every accumulation point of x j , x j is critical.

4. If the standard model is strict, i.e., f ∈ S , and f satisfies the strong KL-inequality, then x j , x j converge to a single critical point x * .

Proof: The argument of Theorem 9.1 shows that ∑ j ∥x j -x j ∥ < ∞. But ∥x j+1 -x j ∥ ≤ K∥ x j -x j ∥, so that ∑ j ∥x j -x j+1 ∥ converges, too. □ Remark 11.2. If f has the strong KL-property, but the standard model of f fails to be strict at x * , then x j , x j still converge to x * , but x * may fail to be critical. An example of this behavior is given in Section 13.

12 Links with Abstract Convergence

We are now in the position to discuss the role of the sufficient conditions (3) and ( 4) in the convergence result of [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 that of the alternative condition [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF].

As we see from part 1) of the proof of Theorem 9.1, our acceptance test ρ ≥ γ forces the descent condition f (x j ) -f (x j+1 ) ≥ γt -1 kj ∥x j -x j+1 ∥ 2 , which is weaker than (3) 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], and coincides with it when the t -1 kj are bounded below. We could force the latter by the large stepsize safeguard rule, i.e., by choosing t < ∞, but we only do this in the situation of Corollary 10.4, because in all other cases it represents an unnecessary limitation. Nonetheless, in the light of our result, condition (3) may be considered reasonable, because in practice we expect t kj to be bounded above most of the time, and more importantly, our analysis shows how (3) can be forced algorithmically.

Let us now focus on condition (4), which is coined on the proximal point algorithm, where a sequence x j is generated iteratively as

x j+1 ∈ argmin x∈R n f (x) + 1 2tj ∥x -x j ∥ 2 . ( 25
)
Here ( 3) is satisfied by construction, and if we suppose in addition that stepsizes stay bounded away from zero, t j ≥ t > 0, then ( 4) is satisfied with b = t -1 and g j+1 = t -1 j (x j -x j+1 ) ∈ ∂f (x j+1 ). Reference [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] presents other cases where (4) is satisfied. In our terminology, (25) corresponds to using f as its own model in the tangent program [START_REF] Noll | Convergence of linesearch and trust-region methods using the Kurdyka-Łojasiewicz inequality[END_REF].

Remark 12.1. The situation becomes more delicate if only a local model ϕ(•, x j ) of f is available in the tangent program min y∈R n ϕ(y, x j ) + 1 2tj ∥y -x j ∥ 2 at step j. Here the optimality condition t -1 j (x j -x j+1 ) ∈ ∂ϕ(x j+1 , x j ) gives only information about ∂ϕ(x j+1 , x j ), which may be difficult, or even impossible, to relate to the information about ∂f (x j+1 ) required in [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF].

To make things worse, if the Armijo condition (3) is not satisfied for stezpsize t j due to the inevitable discrepancy between ϕ(y k , x j ) and f (y k ), then we will have to take shorter steps t j to force (3). This, however, is in conflict with condition (4), which can not be forced by backtracking, as it requires steps to be not too small. So as soon as f has to be replaced by an imperfect local model ϕ(•, x j ), one has to prove that there exists a nonemtpy set of stepsizes t for which both conditions (3) and (4) are true, and one has to provide an algorithm which finds t in this set in finite time. That this may be difficult or even fail can be seen in examples 13.1 and 13.3.

Let us next focus on condition [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF], which we expect to be somewhat weaker than [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF], and therefore easier to verify. This is in parts corroborated by the following Proposition 12.2. Suppose x j is bounded and subgradient-oriented with respect to the norms ∥x∥ 2 j = x T P j x. Let f be upper C 2 at every accumulation point x * of x j . If the sequence x j satisfies condition [START_REF] Bolte | Characterizations of Łojesiewicz inequalities: subgradient flows, talweg, convexity[END_REF], then it also satisfies [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz inequality[END_REF], possibly with a different constant b ′ > 0.

Proof: As a consequence of (1) there exists c > 0 such that ∥x∥ 2 j = x T P j x ≥ c∥x∥∥P j x∥ for all x and all j.

Let us now single out an accumulation point x * and consider a subsequence x j converging to x * . For simplicity call this subsequence x j again. By assumption there exists δ > 0 and K > 0 such that f -K∥ • -x∥ 2 is concave for all x ∈ B(x * , δ). Since x j ∈ B(x * , δ) for j ≥ j 0 , we have

-g T j+1 (x j+1 -x j ) + g T j (x j+1 -x j ) ≥ -K∥x j+1 -x j ∥ 2
for j ≥ j 0 by monotonicity of -f + K∥ • -x j ∥ 2 . That shows

-g T j (x j+1 -x j ) ≤ K∥x j+1 -x j ∥ 2 -g T j+1 (x j+1 -x j ) ≤ K∥x j+1 -x j ∥ 2 + ∥g j+1 ∥∥x j+1 -x j ∥.
Since x j+1 -x j = t j d j with d j = -P j g j /∥P j g j ∥, we have -g T j (x j+1 -x j ) ≥ c∥g j ∥∥x j+1 -x j ∥. Moreover, since (4) holds with b, we have ∥g j+1 ∥ ≤ b∥x j+1 -x j ∥, hence

c∥g j ∥∥x j+1 -x j ∥ ≤ (K + b)∥x j+1 -x j ∥ 2 ,
which shows that ( 5) is true with b ′ = (K + b)/c for j ≥ j 0 . □ Remark 12.3. One consequence of Lemma 12.2 is that it is reasonable to look for descent methods satisfying (3) and ( 5). Not only is there overlap with methods based on (3) and ( 4), which work in situations discussed 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]. Part 11) of the proof of Theorem 7.2 also shows that (3) and ( 5) give convergence under the KL-inequality in their own right, a fact which was first presented in [START_REF] Noll | A bundle method for non-smooth and non-convex optimization[END_REF]. However, the limitations of both approaches become evident in practical situations, when computable local models ϕ(•, x j ) have to be used in the tangent program.

Examples

In this section we consider several limiting examples.

Example 13.1. The following example adapted from [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF] can be used to show the difficulties with non-smooth subgradient-oriented descent. We define a convex piecewise affine function f : R 2 → R as

f (x) = max{f 0 (x), f ±1 (x), f ±2 (x)} where f 0 (x) = -100, f ±1 (x) = ±2x 1 + 3x 2 , f ±2 (x) = ±5x 1 + 2x 2 .
The following plot shows that part of the level curve [f = a] which lies in the upper half plane x 2 > 0.

It consists of the polygon connecting the five points (-a 5 , 0), (-a 11 , 3a 11 ), (0, a 3 ), ( a 11 , 3a 11 ), ( a 5 , 0). We are interested in the lower level set [f ≤ a] which lies inside the polygon, and above the x 1 -axis.

A B x C f 2+ f 2- f 1+ f 1- a 11 a 5 a 3 3a 11 x 2 = -5 2 x 1 + a 2 x 2 = -2 3 x 1 + a 3 ∇f 2+ = (5, 2) ∇f 1+ = (2, 3) ( a 11 , 3a 11 ) -a
We decompose the lower level set [f ≤ a] ∩ [x 2 ≥ 0] into 4 regions where the 4 different branches of f are active, i.e., [f = f 1+ ], [f = f 1-], etc. In the plot we indicate these by the symbols f 1+ , f 1-, etc. The lines

[f 1+ = f 2+ ] and [f 1-= f 2-] connect the origin to the points (± a 11 , 3a 11 ), while [f 1-= f 1+ ] ∩ [x 2 ≥ 0] is the positive x 2 -axis.
We denote the rhombus described by the four points (0, 0), ( a 11 , 3a 11 ), (0, a 3 ), (-a 11 , 3a 11 ) by R a . In the plot this area is shaded gray. Now we consider a current point x on the upper right part of level curve [f = a], that is, a point with x 1 = τ a 11 for some 0 < τ ≤ 1, and with x 2 = -2 3 x 1 + a 3 . In other words, x is on the right upper boundary of the rhombus R a . The steepest descent direction at x is -∇f 1+ = (-2, -3). This is indicated by the blue line parting at x and passing through the points A, B, C. (The two limiting positions for x are the parallel dashed blue lines). Informally, what we now do is the following. We construct an instance of the steepest descent method, where steepest descent steps away from x along the blue line which are accepted by the test ρ ≥ γ lie before the point B. With the exception of the point A, which is also accepted, this means that we will stop at a point x + which is again on the upper part of a rhombus R a + , where a + = f (x + ) < f (x), possibly on the other side of the x 2 -axis. Proceeding in this fashion, we will generate a sequence x, x + , x ++ , . . . which will never escape from the rhombi R f (x) , R f (x + ) , R f (x ++ ) , and will converge to the origin, which is not a critical point of f . Notice that our algorithm would also accept the point A on the positive x 2 axis, and this is indeed the only escape point on the blue line. Once an iterate of the form A is found, the steepest descent direction switches to (0, -3) and we leave the rhombi through the origin. Our argument is that finding the only escape point A on the blue line is not algorithmically feasible, even more so as we have not specified any condition which distinguishes A from the other point accepted by the test ρ ≥ γ. τ a 11

A B

If we plot the function t → f (x + td), where d is the steepest descent direction d = (-2, -3) at x with 0 < x 1 ≤ a 11 , then we get a piecewise linear curve with two kinks corresponding to the points A = (0, a 3 -13 6 x 1 ) and B = ( 13 27 x 1 -2 27 a; -13 9 x 1 + 2 9 a). Finally, the line hits the x 1 -axis at C = ( 13 9 x 1 -2 9 a, 0). The function values at these points are This quotient is independent of a and has its largest value at τ = 1, namely, ρ = 198 242 . Therefore, if we put 1 > γ > 198 242 , then none of the points B is accepted by the test ρ ≥ γ, meaning that the interval of acceptance ]x, x + ] ⊂]x, B[ lies before B, and contains A in its interior. Notice that this interval of acceptance corresponds also to the interval of points accepted by condition [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF]. That means, the new serious iterate x + will have exactly the same properties as discussed for x, now in the rhombus R a + .

f (A) = f 1+ ( 0, a 3 - 13 6 x 1 ) = a - 13 2 x 1 , f (B) = f 1- ( 13
The question is now how convergence criteria (4) and ( 5) from Section 5 behave in this situation. Can we find a point x + on the segment (x, B) where ∥∂f (x + )∥ -≤ b∥x -x + ∥? Since x -x + → 0 and the gradient is constant on the parts [f = f 1-] and [f = f 1+ ], the only candidate to be accepted by ( 4) is A, because here we get a convex combination of two gradients. The Clarke subgradients are t(2, 3) + (1 -t)(-2, 3) = (4t -2, 3), 0 ≤ t ≤ 1. Unfortunately, those are norm bounded below by 3, so A does not work. There is no point on the entire segment [x, B] which is accepted by condition (4). One would at least have hoped that the point A could be accepted, since from A onward the steepest descent direction will pick another track and escape from the rhombus. In fact, the escape line is the positive x 2 -axis. (Recall that our own method does accept the point A, but a linesearch which tries to locate a single point could not claim to work in practice). In contrast, (4) rejects even the escape point A. The same argument shows that condition (5) fails.

We still have to explain why convergence to a critical point fails here. According to our main theorem, this is due to the fact that the Clarke model is not strict at x * = (0, 0). In order to verify this directly, consider points x = (ξ, η), y = (ξ ′ , η ′ ) in the rhombus R a , but with ξ > 0, ξ ′ < 0. If ϕ ♯ (•, (0, 0)) was to be strict, we would have to have f (y) ≤ f (x) + f 0 (x, y -x) + o(∥x -y∥) for (x, y) → (0, 0). But f (y) = -2ξ ′ + 3η ′ , f (x) = 2ξ + 3η, hence strictness requires

-2ξ ′ + 3η ′ ! ≤ 2ξ + 3η + ⟨(2, 3), (ξ ′ -ξ, η ′ -η)⟩ + ϵ∥x -y∥,
where ϵ → 0 as ξ ′ → 0, ξ → 0, η ′ → 0, η → 0. This gives

-2ξ ′ ! ≤ 2ξ ′ + ϵ (|ξ ′ -ξ| + |η ′ -η|)
if we use for simplicity the 1-norm on the right. This must obviously also hold when η ′ = η → 0, so

-4ξ ′ ! ≤ ϵ|ξ ′ -ξ| = ϵ(ξ -ξ ′ ),
as ξ ′ → 0, ξ → 0, the latter because ξ > 0 and ξ ′ < 0. Suppose ξ = -3ξ ′ → 0, then we should have -4ξ ′ ≤ -4ϵξ ′ , which requires ϵ ≥ 1. Therefore ϕ ♯ is not strict at (0, 0). □ Remark 13.2. Observe that the ideal subgradient trajectory ẋ(t) ∈ -∂f (x(t)) a.e. t ≥ 0 switches to the escape line at point A, allowing to leave the rhombus. This leads to the observation that in nonsmooth optimization, and this is in stark contrast with smooth optimization, looking at the continuous trajectory associated with a class of descent methods is useless, because it tells us nothing about the discrete method.

Example 13.3. Consider Nesterov's 2008 non-smooth variant [24] of the Rosenbrock function f (x 1 , x 2 ) = 1 4 (x 1 -1) 2 + |x 2 -2x 2 1 + 1|, a contour plot of which can be seen in Figure 1 (left) of [START_REF] Gürbüzbalaban | On Nesterov's nonsmooth Chebyshev-Rosenbrock functions[END_REF]. The unique global minimizer is x * = [1, 1], f is non-smooth at points on the manifold M = {x ∈ R 2 : x 2 2 -2x 1 + 1 = 0}. For x ̸ ∈ M we have ∥∇ f (x)∥ ≥ 1, so that ∥g j+1 ∥ ≤ b∥x j+1 -x j ∥ for g j+1 ∈ ∂ f (x j+1 ) can only be arranged if ∥x j+1 -x j ∥ ≥ 1/b > 0 for all j where x j+1 ̸ ∈ M . That means, every iterative descent method which tries to satisfy (3) in tandem with either (4) or (5) has only two choices: It must either find the minimum x * in a finite number of steps, or it must stay precisely on the manifold M , i.e., x j ∈ M for all j ≥ j 0 . Since f is not sharp at x * , finite convergence will not occur, not even for the proximal point method, and if the manifold M is not explicitly known to the step-finding routine, identifying iterates x j+1 ∈ M may not be a numerically feasible. For instance, in [START_REF] Gürbüzbalaban | On Nesterov's nonsmooth Chebyshev-Rosenbrock functions[END_REF] the authors have tested a non-smooth version of the BFGS-method, which zig-zags around the manifold M , but does not find iterates on M even though it converges to x * . □ Example 13.4. One may argue that tangent program [START_REF] Gürbüzbalaban | On Nesterov's nonsmooth Chebyshev-Rosenbrock functions[END_REF] is not realistic, because it is just as difficult to solve as the original problem min x∈R n f (x). We might make a concession for non-convex f : Here the use of ( 25) might be justified if the tangent program is convex, hence easier. This requires search for a convexifying (1/2t j )∥ • -x j ∥ 2 at each step j. But this will spoil (4) if f is not lower C 2 . As an example on the real line, define f ′ (x) = -1 for x ≤ 0, and

f ′ (x) = 1 for x ∈ [2 -k , α k ], f ′ (x) = -k for x ∈ (α k , 2 -k+1 ],
where α k = 2 -k (5/4 + 2k)/(1 + k), k = 1, 2, . . . , then the primitive f of f ′ has a unique minimum at x = 0, but in order to convexity f at iterates x j ∈ ∪ ∞ j=1 (α j , 2 -k+1 ], one needs smaller and smaller t j in (25) as x j → 0. Then conditions (4) and ( 5) fail, while the backtracking strategy of Algorithm 2 is still functional. □

Conclusions

We have shown that convergence of subgradient-oriented non-smooth descent methods to critical points relies on two pillars. The Kurdyka-Łojasiewicz condition is sufficient to guarantee summability of ∑ j ∥x j -x j+1 ∥ < ∞ and therefore finite length of the discrete trajectory. Strictness of the standard model assures convergence to critical points in the sense of subsequences. When combined, these two assure convergence to a single critical point.

The present approach, which is particularly useful for large size problems due to the bundling mechanism, can be adapted to deal with constraints e.g. by using the progress function approach of [START_REF] Apkarian | Mixed H 2 /H ∞ control via nonsmooth optimization[END_REF][START_REF] Gabarrou | Design of a flight control architecture using a non-convex bundle method[END_REF], which was developed in [START_REF] Polak | Optimization: algorithms, and consistent approximation[END_REF] for smooth problems, or the improvement function of [START_REF] Sagastizábal | An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or filter[END_REF]. It is also possible to use weighted maxima as in [START_REF] Apkarian | Nonsmooth optimization for multiband frequency domain control design[END_REF].

It remains open whether the Kurdyka-Łojasiewicz property can also be brought to work for bundle methods based on more general and more practical oracles, like downshifted tangents [START_REF] Gabarrou | Design of a flight control architecture using a non-convex bundle method[END_REF], tilted tangents [START_REF] Sagastizábal | An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or filter[END_REF], or to nonstandard models used e.g. in eigenvalue optimization [START_REF] Apkarian | A trust region spectral bundle method for nonconvex eigenvalue optimization[END_REF]. Substantially new techniques of proof will have to be brought forward to settle these cases. Fortunately, results like Corollary 10.2 can be extended to these cases and give a satisfactory convergence theory for practical purpose even without the KL-inequality.

  model in the sense of Definition 6.2. We say that a convex function is its own strong model. Since f has also a standard model ϕ ♯ , we see that a function f will in general have several models. Remark 6.9. Every convex composite function f = g •F with g convex and F of class C 1 has the natural strict model ϕ(•, x) = g(F (x) + F ′ (x)(• -x)). Convergence theory for natural models was developed in[START_REF] Apkarian | A trust region spectral bundle method for nonconvex eigenvalue optimization[END_REF][START_REF] Apkarian | A proximity control algorithm to minimize non-smooth and nonconvex semi-infinite maximum eigenvalue functions[END_REF][START_REF] Noll | A proximity control algorithm to minimize non-smooth nonconvex functions[END_REF].In the same vein, if f is lower C 2 , then given a bounded convex set B, we can find µ > 0 such that for everyx ∈ B, f + µ∥ • -x∥ 2 is convex on B. In consequence, ϕ(•, x) = f + µ∥ • -x∥2 is a strong first-order model of f on B. Notice that descent directions based on the natural model or the lower C 2 model are in general not subgradient-oriented, and it is open whether the KL-property applies in this setting.

	The model concept extends even to lower C 1 -function:
	Proposition 6.10. Let f be locally Lipschitz and lower C 1 . Then f has a strict first-order model on
	every bounded set B.

  use the step-finding algorithm with proximity control (algorithm 1) started at stepsize t ♯ j to find a stepsize t k > 0 such that the k th trial point y k satisfies ρ k ≥ γ. Put x j+1 = y k and goto step 4. 4: Updating stepsize. Check whether ρ k ≥ Γ at acceptance x j+1 = y k . If this is the case, put t ♯ j+1 = θ -1 t k , otherwise put t ♯ j+1 = t k . Goto step 5. 5: Small stepsize safeguard rule (Optional). Replace t ♯ j+1 by max{t ♯ j+1 , t}. 6: Large stepsize safeguard rule (Optional). Replace t ♯ j+1 by min{t, t ♯ j+1 }.

7: Updating norm. Choose a new P j+1