Jérôme Bolte

Edouard Pauwels

Curiosities and counterexamples in smooth convex optimization

Counterexamples to some old-standing optimization problems in the smooth convex coercive setting are provided. We show that block-coordinate, steepest descent with exact search or Bregman descent methods do not generally converge. Other failures of various desirable features are established: directional convergence of Cauchy's gradient curves, convergence of Newton's flow, finite length of Tikhonov path, convergence of central paths, or smooth Kurdyka-Lojasiewicz inequality. All examples are planar. These examples are based on general smooth convex interpolation results. Given a decreasing sequence of positively curved C k convex compact sets in the plane, we provide a level set interpolation of a C k smooth convex function where k ≥ 2 is arbitrary. If the intersection is reduced to one point our interpolant has positive definite Hessian, otherwise it is positive definite out of the solution set. Furthermore, given a sequence of decreasing polygons we provide an interpolant agreeing with the vertices and whose gradients coincide with prescribed normals.

Introduction 1.Questions and method

One of the goals of convex optimization is to provide a solution to a problem with stable and fast algorithms. The quality of a method is generally assessed by the convergence of sequences, rate estimates, complexity bounds, finite length of relevant quantities and other quantitative or qualitative ways.

Positive results in this direction are numerous and have been the object of intense research since decades. To name but a few: gradient methods e.g., [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF][START_REF] Nesterov | [END_REF][START_REF] Boyd | Convex optimization[END_REF], proximal methods e.g., [START_REF] Bauschke | Convex analysis and monotone operator theory in Hilbert spaces[END_REF], alternating methods e.g., [START_REF] Beck | First-order methods in optimization[END_REF][START_REF] Wright | Coordinate descent algorithms[END_REF], path following methods e.g., [START_REF] Auslender | Penalty and barrier methods: a unified framework[END_REF][START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF], Tikhonov regularization e.g. [START_REF] Golub | Tikhonov regularization and total least squares[END_REF], semi-algebraic optimization e.g., [START_REF] Borwein | Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets[END_REF][START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF], decomposition methods e.g., [START_REF] Bauschke | Convex analysis and monotone operator theory in Hilbert spaces[END_REF][START_REF] Beck | First-order methods in optimization[END_REF], augmented Lagrangian methods e.g., [START_REF] Bertsekas | Convex optimization algorithms[END_REF] and many others.

Despite this vast literature, some simple questions remain unanswered or just partly tackled, even for smooth convex coercive functions. Does the alternating minimization method, aka Gauss-Seidel method, converge? Does the steepest descent method with exact line search converge? Do mirror descent or Bregman methods converge? Does Newton's flow converge? Do central paths converge? Is the gradient flow directionally stable? Do smooth convex functions have the Kurdyka-Lojasiewicz property?

In this article we provide a negative answer to all these questions.

Our work draws inspiration from early works of de Finetti [START_REF] De Finetti | Sulle stratificazioni convesse[END_REF], Fenchel [START_REF] Fenchel | Convex Cones, Sets and Functions[END_REF], on convex interpolation, but also from Torralba's PhD thesis [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF] and the more recent [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF], where some counterexamples on the Tikhonov path and Lojasiewicz inequalities are provided. The convex interpolation problem, see [START_REF] De Finetti | Sulle stratificazioni convesse[END_REF], is as follows: given a monotone sequence of convex sets1 may we find a convex function interpolating each of these sets, i.e., having these sets as sublevel sets? Answers to these questions for continuous convex functions were provided by de Finetti, and improved by Fenchel [START_REF] Fenchel | Convex Cones, Sets and Functions[END_REF], Kannai [START_REF] Kannai | Concavifiability and constructions of concave utility functions[END_REF], and then used in [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF][START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF] for building counterexamples.

We improve this work by providing, for k ≥ 2 arbitrary, a general C k interpolation theorem for positively curved convex sets, imposing at the same time the positive definiteness of its Hessian out of the solution set. An abridged version could be as follows.

Theorem (Smooth convex interpolation2 ). Let (T i ) i∈Z be a sequence of compact convex subsets of R 2 , with positively curved C k boundary, such that T i ⊂ int T i+1 for all i in Z. Then there exists a C k convex function f having the T i as sublevel sets with positive definite Hessian outside of the set:

argmin f = i∈Z T i .
We provide several additional tools (derivatives computations) and variants (status of the solution set, Legendre functions, Lipschitz continuity). Whether our result is generalizable to general smooth convex sequences, i.e., with vanishing curvature, seems to be a very delicate question whose answer might well be negative.

Our central theoretical result is complemented by a discrete approximate interpolation result "of order one" which is particularly well adapted for building counterexamples. Given a nested collection of polygons, one can indeed build a smooth convex function having level sets interpolating its vertices and whose gradients agree with prescribed normals.

Our results are obtained by blending parametrization techniques, Minkovski summation, Bernstein approximations and convex analysis.

As sketched below, our results offer the possibility of building counterexamples in convex optimization by restricting oneself to the construction of countable collections of nested convex sets satisfying some desirable properties. In all cases failures of good properties are caused by some curvature oscillations.

A digest of counterexamples

Counterexamples provided in this article can be classified along three axes: structural counterexamples 3 , counterexamples for convex optimization algorithms and ordinary differential equations.

In the following, the term "nonconverging" sequence or trajectory means, a sequence or a trajectory with at least two distinct accumulation points. Unless otherwise stated, convex functions have full domain.

The following results are proved for C k convex functions on the plane with k ≥ 2.

Structural counterexamples

(i) Kurdyka-Lojasiewicz: There exists a C k convex function whose Hessian is positive definite outside its solution set and which does not satisfy the Kurdyka-Lojasiewicz inequality. This is an improvement on [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF].

(ii) Tikhonov regularization path: There exists a C k convex function f such that the regularization path x(r) = argmin f (y) + r y 2 : y ∈ R 2 , r ∈ (0, 1) has infinite length. This strengthens a theorem by Torralba [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF].

(iii) Central path: There exists a continuous Legendre function h : [-1, 1] 2 → R, C k on the interior, and c in R 2 such that the central path x(r) = argmin { c, y + rh(y) : y ∈ D} does not have a limit as r → 0.

Algorithmic counterexamples:

(iv) Gauss-Seidel method (block coordinate descent): There exists a C k convex function with positive definite Hessian outside its solution set and an initialization (u 0 , v 0 ) in R 2 , such that the alternating minimization algorithm

u i+1 = argmin u∈R f (u, v i ) v i+1 = argmin v∈R f (u i+1 , v)
produces a bounded nonconverging sequence ((u i , v i )) i∈N .

(v) Gradient descent with exact line search: There exists a C k convex function f with positive definite Hessian outside its solution set and an initialization x 0 in R 2 , such that the gradient descent algorithm with exact line search

x i+1 = argmin t∈R f (x i + t∇f (x i ))
produces a bounded nonconvergent sequence.

(vi) Bregman or mirror descent method: There exists a continuous Legendre function h : [-1, 1] 2 → R, C k on the interior, a vector c in R 2 and an initialization x 0 in (-1, 1) 2 such that the Bregman recursion

x i+1 = ∇h * (∇h(x i ) -c)
produces a nonconverging sequence. The couple (h, c, • ) satisfies the smoothness properties introduced in [START_REF] Bauschke | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF].

Continuous time ODE counterexamples:

(vii) Continuous time Newton method: There exists a C k convex function with positive definite Hessian outside its solution set, and an initialization x 0 in R 2 such that the continuous time Newton's system ẋ(t) = -∇ 2 f (x(t)) -1 ∇f (x(t)), t ≥ 0,

x(0) = x 0 has a solution approaching argmin f which does not converge.

(viii) Directional convergence for gradient curves: There exists a C k convex function with 0 as a unique minimizer and a positive definite Hessian on R 2 \ {0}, such that for any non stationary solution to the gradient system ẋ(t) = -∇f (x(t))

the direction x(t)/ x(t) does not converge.

(ix) Hessian Riemannian gradient dynamics: There exists a continuous Legendre function h : [-1, 1] 2 → R, C k on the interior, a linear function f and a nonconvergent solution to the following system

ẋ(t) = -∇ H f (x(t)),
where H = ∇ 2 h is the Hessian of h and ∇ H f = H -1 ∇f is the gradient of f in the Riemannian metric induced by H on (-1, 1) 2 .

Pathological sequences and curves Our counterexamples lead to sequences or paths in R 2 which are related to a function f by a certain property (see examples above) and have a certain type of pathology. For illustration purposes, we provide sketches of the pathological behaviors we met in Figure 1. Convergence with infinite length corresponds to counterexample (ii), finite length jiggling corresponds to counterexample (viii) (recall that gradient curves have to be selfcontractant as well, see [START_REF] Daniilidis | Asymptotic behaviour of selfcontracted planar curves and gradient orbits of convex functions[END_REF]), nonconvergent jiggling corresponds to counterexamples (iii), (vi), (vii), (ix) and nonconvergent spiraling corresponds to counterexamples (iv), (v) and somehow (i).

Preliminaries

Let us set N * = N \ {0}. For p in N * , the Euclidean scalar product in R p is denoted by Throughout this note, the assertion "g is C k on D" where D is not an open set is to be understood as "g is C k on an open neighborhood of D". Given a map G : X → A × B for some space X, [G] 1 : X → A denotes the first component of G.

•, • ,

Continuous convex interpolations

We consider a sequence of compact convex subsets of R p , (T i ) i∈Z such that T i+1 ⊂ int T i . Finding a continuous convex interpolation of (T i ) i∈Z is finding a convex continuous function which makes the T i a sequence of level sets. We call this process continuous convex interpolation. This questioning was present in Fenchel [START_REF] Fenchel | Convex Cones, Sets and Functions[END_REF] and dates back to de Finetti [START_REF] De Finetti | Sulle stratificazioni convesse[END_REF], let us also mention the work of Crouzeix [START_REF] Crouzeix | Conditions for convexity of quasiconvex functions[END_REF] revolving around this issue.

Such constructions have been shown to be realizable by Torralba [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF], Kannai [START_REF] Kannai | Concavifiability and constructions of concave utility functions[END_REF], using ideas based on Minkowski sum. The validity of this construction can be proved easily using the result of Crouzeix [START_REF] Crouzeix | Conditions for convexity of quasiconvex functions[END_REF] which was already present under different and weaker forms in the works of de Finetti and Fenchel.

Theorem 1 (de Finetti-Fenchel-Crouzeix). Let f : R p → R be a quasiconvex function.

The functions

F x : λ → sup { z, x : f (z) ≤ λ}
are concave for all x in R p , if and only f is convex.

Our goal is to build smooth convex interpolation for sequences of smooth convex sets. To make such a construction we shall use nonlinear Minkowski interpolation between level sets.

We shall also rely on Bernstein approximation which we now describe.

Bernstein approximation

We refer to the monograph [START_REF] Lorentz | Bernstein polynomials[END_REF] by G.G. Lorentz.

The main properties of Bernstein polynomials to be used in this paper are the following:

-Bernstein approximation is linear in its functional argument f and "monotone" which allows to construct an approximation using only positive combination of a finite number of function values.

-There are precise formulas for derivatives of Bernstein approximation. They involve repeated finite differences. So approximating piecewise affine function with high enough degree leads to an approximation for which corner values of derivatives are controlled while the remaining derivatives are vanishing (up to a given order).

-Bernstein approximation is shape preserving, which means in particular that approximating a concave function preserves concavity.

The main idea to produce a smooth interpolation which preserves level sets is depicted in Figure 2 where we use Bernstein approximation to interpolate smoothly between three points and controlling the successive derivatives at the end points of the interpolation. We consider at first three points, to which we add four extra points to control derivatives at the junctions. We then build a concave, piecewise linear function and make a Bernstein approximation between the first two original points and the last two original points.

Let us now be specific. Given f defined on the interval [0, 1], the Bernstein polynomial of order d ∈ N * associated to f is given by

B d (x) = B d,f (x) = d k=0 f k d d k x k (1 -x) d-k , for x ∈ [0, 1]. ( 1
)
Derivatives and shape preservation: For any h in (0, 1) and

x in [0, 1 -h], we set ∆ 1 h f (x) = f (x + h) -f (x) and recursively for all k in N * , ∆ k h f (x) = ∆ ∆ k-1 h f (x) . We fix d = 0 in N and for h = 1 d write ∆ k h = ∆ k .
Then for any m ≤ d, we have

B d (x) (m) = d(d -1) . . . (d -m + 1) d-m k=0 ∆ m f k d d -m k x k (1 -x) d-k-m , (2)
for any x in [0, 1]. If f is increasing (resp. strictly increasing), then ∆ 1 f (x) ≥ 0 (resp. ∆ 1 f (x) > 0) for all x and B d is positive (resp. strictly positive) and B d is increasing (resp. strictly increasing). Similarly, if f is concave, then ∆ 2 f (x) ≤ 0 for all x so that B

d ≤ 0 and B d is concave. From (2), we infer

B d (x) (m) ≤ d(d -1) . . . (d -m + 1) sup k∈{0,...,d-m} ∆ m f k d (3) for x in [0, 1].

Approximation of piecewise affine functions:

The following lemma will be extensively used throughout the proofs.

Lemma 1 (Smoothing of piecewise lines in R p ). Let q 0 , q 1 ∈ R p , λ -< λ 0 < λ 1 < λ + and 0 < e 1 , e 0 < 1. Set Θ = (q 0 , q 1 , , λ -, λ 0 , λ 1 , λ + , e 0 , e 1 ) and define γ

Θ : [0, 1] → R p through γ Θ (t) =        q 0 1 + e 0 λ 0 -λ -(t(λ + -λ -)) if 0 ≤ t ≤ λ 0 -λ - λ + -λ - q 0 (1 + e 0 ) λ 1 -λ --t(λ + -λ -) λ 1 -λ 0 + q 1 (1 -e 1 ) λ --λ 0 +t(λ + -λ -) λ 1 -λ 0 if λ 0 -λ - λ + -λ -≤ t ≤ λ 1 -λ - λ + -λ - q 1 1 + (t-1)(λ + -λ -)e 1 λ + -λ 1 if λ 1 -λ - λ + -λ -≤ t ≤ 1.
The curve γ Θ in R p+1 is the affine interpolant between the points q 0 , (1 + e 0 )q 0 , (1 -e 1 )q 1 and q 1 . For any m in N, we choose d in N * such that

m d ≤ min λ 0 -λ - λ + -λ - , 1 - λ 1 -λ - λ + -λ - . (4)
We consider a Bernstein-like reparametrization of γΘ given by

γΘ : [λ -, λ + ] → R p λ → d k=0 γΘ k d d k λ -λ - λ + -λ - k 1 - λ -λ - λ + -λ - d-k
.

Then the following holds, for any

2 ≤ l ≤ m, γΘ is C m and γΘ (λ -) = q 0 γΘ (λ + ) = q 1 γ Θ (λ -) = e 0 λ 0 -λ- q 0 γ Θ (λ + ) = e 1 λ + -λ 1 q 1 γ(l) Θ (λ -) = 0 γ(l) Θ (λ + ) = 0.
Furthermore, if γ Θ has monotone coordinates (resp. strictly monotone, resp. concave, resp. convex), then so has γΘ .

Proof : Note that the dependence of γΘ in (q 0 , q 1 ) is linear so that the dependence of γΘ in (q 0 , q 1 ) is also linear. Hence γΘ is of the form λ → a(λ)q 0 + b(λ)q 1 . We can restrict ourselves to p = 1 since the general case follows from the univariate case applied coordinatewise.

If p = 1, then γΘ = B f Θ,d • A, where A : λ → λ-λ - λ + -λ -. We have γΘ (0) = q 0 , γΘ (1) = q 1 and ∆ 1 f Θ (0) = λ + -λ - λ 0 -λ - e 0 d q 0 , ∆ 1 f Θ 1 -1 d = λ + -λ - λ + -λ 1 e 1 d q 1 and ∆ (l) f Θ (0) = ∆ (l) f Θ 1 -l d = 0.
The results follow from the expressions in (1) and (2) and the chain rule for γΘ = B f Θ,d •A.

The last property of γΘ is due to the shape preserving property of Bernstein approximation and the fact that γΘ = B f Θ,d • L.

Remark 1. (a) [Affine image]

Using the notation of Lemma 1, if (λ -, q 0 ), (λ 0 , (1+e 0 )q 0 ), (λ 1 , (1-e 1 )q 1 ) and (λ + , q 1 ) are aligned, then the interpolation is actually an affine function. (b) [Degree of the interpolants] Observe that the degree of the Bernstein interpolant is connected to the slopes of the piecewise path λ by (4).

Smooth convex interpolation

Being given a subset S of R p , we denote by int(S) its interior, S its closure and bd S = S \ int(S) its boundary. Let us recall that the support function of S is defined through

σ S (x) = sup { y, x : y ∈ S} ∈ R ∪ {+∞}.

Smooth parametrization of convex rings

A convex ring is a set of the form C 1 \ C 2 where C 1 ⊂ C 2 are convex sets. Providing adequate parameterizations for such objects is key for interpolating C 1 and C 2 by some (regular) convex function.

The following assertion plays a fundamental role.

Assumption 1. Let T -, T + ⊂ R 2 be convex, compact with C k boundary (k ≥ 2) and positive curvature. Assume that, T -⊂ int(T + ) and 0 ∈ int(T -).
The positive curvature assumption ensures that the boundaries can be parametrized by their normal, that is, for i = -, +, there exists c i : R/2πZ → bd (T i ) such that the normal to T i at c i (θ) is the vector n(θ) = (cos(θ), sin(θ)) T and ċi (θ) = ρ i (θ)τ (θ) where ρ i > 0 and τ (θ) = (-sin(θ), cos(θ)). In this setting, it holds that c i (θ) = argmax y∈T i n(θ), y . The map c i is the inverse of the Gauss map and is C k-1 (see [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF] Section 2.5).

Lemma 2 (Minkowski sum of convex sets with positive curvature). Let T -, T + be as in Assumption 1 with normal parametrizations as above. For a, b ≥ 0 with a + b > 0 set T = aT -+ bT + .

Then T has positive curvature and its boundary is given by bd

T = {a c -(θ) + b c + (θ) : θ ∈ R/2πZ}, with the natural parametrization R/2πZ θ → a c -(θ) + b c + (θ).
Proof : We may assume ab > 0 otherwise the result is obvious. Let x be in bd T and denote by n(θ) the normal vector at x for a well chosen θ, so that x = argmax { y, n(θ) } : y ∈ T }. Observe that the definition of the Minkowski sum yields max y∈T y, n(θ) = max

(v,w)∈T -×T + av + bw, n(θ) = a max v∈T - v, n(θ) + b max w∈T + w, n(θ) so that x, n(θ) = a c -(θ), n(θ) + b c + (θ), n(θ) = ac -(θ) + bc + (θ), n(θ)
which implies by extremality of x that x = ac -(θ) + bc + (θ). Conversely, for any such x, n(θ) defines a supporting hyperplane to T and x must be on the boundary of T . The other results follow immediately.

In the following fundamental proposition, we provide a smooth parametrization of the convex ring T + \ int T -. The major difficulty is to control tightly the derivatives at the boundary so that the parametrizations can be glued afterward to build smooth interpolants.

Proposition 1 (C k parametrization of convex rings). Let T -, T + be as in Assumption 1 with their normal parametrization as above. Fix k ≥ 2, λ -< λ 0 < λ 1 < λ + and 0 < e 0 , e 1 < 1. Choose d in N * , such that

k d ≤ min λ 0 -λ - λ + -λ - , 1 - λ 1 -λ - λ + -λ - .
Consider the map

G : [λ -, λ + ] × R/2πZ → R 2 (λ, θ) → γΘ (λ) (5)
with Θ = (c -(θ), c + (θ), λ -, λ 0 , λ 1 , λ + , e 0 , e 1 ) and γ as given by Lemma 1. Assume further that:

(M) For any θ ∈ R/2πZ, λ → G(λ, θ), n(θ) has strictly positive derivative on [λ -, λ + ]. Then the image of G is R := T + \ int(T -), G is C k and satisfies, for any 2 ≤ l ≤ k and any m in N * , ∂ m G ∂θ m (λ -, θ) = c (m) -(θ) ∂ m G ∂θ m (λ + , θ) = c (m) + (θ) ∂ m+1 G ∂λ∂θ m (λ -, θ) = c (m) -(θ) e 0 λ 0 -λ - ∂ m+1 G ∂λ∂θ m (λ + , θ) = c (m) + (θ) e 1 λ + -λ 1 ∂ l+m G ∂λ l ∂θ m (λ -, θ) = 0 ∂ l+m G ∂λ l ∂θ m (λ + , θ) = 0.
Besides G is a diffeomorphism from its domain on to its image. Set R x → (f (x), θ(x)) to be the inverse of G. Then f is C k and in addition, for all x in R,

∇f (x) = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) n(θ(x)) ∇θ(x) = 1 ∂G ∂θ (f (x), θ(x)), τ (θ(x)) τ (θ(x)) - ∂G ∂λ (f (x), θ(x)), τ (θ(x)) ∂G ∂λ (f (x), θ(x)), n(θ(x)) ∂G ∂θ (f (x), θ(x)), τ (θ(x)) n(θ(x)) ∇ 2 f (x) = ∂G ∂θ (f (x), θ(x)), τ (θ(x)) ∂G ∂λ (f (x), θ(x)), n(θ(x)) ∇θ(x)∇θ(x) T - ∂ 2 G ∂λ 2 (f (x), θ(x)), n(θ(x)) ∂G ∂λ (f (x), θ(x)), n(θ(x)) ∇f (x)∇f (x) T , (6)
where all denominators are positive.

Remark 2. Note that G is actually well defined and smooth on an open set containing its domain. As we shall see it is also a diffeomorphism from an open set containing its domain onto its image. Assume that λ < λ , using the monotonicity assumption (M), we have for any θ, θ ,

n(θ ), G(λ, θ) ≤ sup y∈T λ n(θ ), y = n(θ ), G(λ, θ ) < n(θ ), G(λ , θ ) so that G(λ, θ) = G(λ , θ ). Furthermore, we have by definition of G(λ , θ ) G(λ, θ) ∈ θ ∈R/2πZ {y, y, n(θ ) ≤ n(θ ), G(λ , θ ) } = T λ ,
where the equality follows from the convexity of T λ . By convexity and compactness, this entails that

T λ = conv(bd (T λ )) ⊂ int T λ .
Let us show that the map G is bijective, first consider proving surjectivity. Let f be defined on

T + \ int(T -) through f : x → inf {λ : λ ≥ λ -, x ∈ T λ = a(λ)T -+ b(λ)T + } . (7)
Since a(λ + ) = 0, b(λ + ) = 1 this function is well defined and by compactness and continuity the infimum is achieved. It must hold that x belongs to bd (T

f (x) ), indeed, if f (x) = λ -, then x belongs to bd (T -) and otherwise, if x is in int(T λ ) for λ > λ -, then f (x) < λ .
We deduce that x is of the form G(f (x), θ) for a certain value of θ, so that G is surjective.

As for injectivity, we have already seen a first case, the monotonicity assumption (M) ensures that λ = λ implies G(λ, θ) = G(λ , θ ) for any θ, θ . Furthermore, we have the second case, for any λ in [λ -, λ + ] and any θ, G(λ, θ) = arg max y∈T λ y, n(θ

) so that θ = θ implies G(λ, θ) = G(λ, θ ). So in all cases, (λ, θ) = (λ , θ ) implies that G(λ, θ) = G(λ , θ )
and G is injective.

Let us now show that the map G is a local diffeomorphism by estimating its Jacobian map.

Since 0 ∈ int(T -), we have for any λ, θ,

0 < sup y∈T - y, n(θ) = G(λ -, θ), n(θ) ≤ a(λ) c -(θ), n(θ) + b(λ) c + (θ), n(θ) ,
and both scalar products are positive so that a(λ) + b(λ) > 0. Hence, for any θ in R/2πZ,

∂G ∂θ (λ, θ) = (a(λ)ρ -(θ) + b(λ)ρ + (θ))τ (θ), (8)
with a(λ)ρ -(θ) + b(λ)ρ + (θ) > 0. Furthermore by assumption λ → max y∈T λ y, n(θ) = G(λ, θ), n(θ) has strictly positive derivative in λ, whence

∂G ∂λ (λ, θ), n(θ) > 0.
We deduce that for any fixed θ, in the basis (n(θ), τ (θ)), the Jacobian of G, denoted J G , is triangular with positive diagonal entries. More precisely fix λ, θ and set x = G(λ, θ) such that λ = f (x), θ = θ(x). In the basis (n(θ), τ (θ)), we deduce from ( 8) that the Jacobian of G is of the form

J G (λ, θ) = α 0 γ β , where α = ∂G ∂λ (λ, θ), n(θ) > 0 β = ∂G ∂θ (λ, θ), τ (θ) = a(λ)ρ -(θ) + b(λ)ρ + (θ) > 0 γ = ∂G ∂λ (λ, θ), τ (θ) .
It is thus invertible and we have a local diffeomorphism. We deduce that

J G (λ, θ) -1 = α -1 0 -γ αβ β -1 .
We have J G (λ, θ) -1 = J G -1 (x) so that the first line is ∇f (x) and second line is ∇θ(x), which proves the claimed expressions for gradients.

We also have dn(θ)/dθ = τ (θ) so that

J n•θ (x) = τ (θ(x))∇θ(x) T .
Differentiating the gradient expression, we obtain (∇ denotes gradient with respect to x):

∇ 2 f (x) = ∂ ∂x 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) n(θ(x)) = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) J n•θ (x) + n(θ(x))∇ 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) T = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) J n•θ (x) -n(θ(x))∇ ∂G ∂λ (f (x), θ(x)), n(θ(x)) T 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) 2 = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) τ (θ)∇θ(x) T -∇f (x)∇ ∂G ∂λ (f (x), θ(x)), n(θ(x)) T .
We have

= ∇ ∂G ∂λ (f (x), θ(x)), n(θ(x)) T = ∂G ∂λ (f (x), θ(x)) T J n•θ (x) + n(θ(x)) T J ∂G ∂λ (f (x), θ(x))J G -1 (x) = ∂G ∂λ (f (x), θ(x)), τ (θ(x)) ∇θ(x) T + n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) ∇f (x) T ,
where, for the last identity, we have used the fact that

n(θ(x)) T J∂G ∂λ (f (x), θ(x)) = n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) n(θ(x)) T + n(θ(x)), ∂ 2 G ∂λ∂θ (λ, θ) τ (θ(x)) T = n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) n(θ(x)) T n(θ(x)) T J G -1 (x) = n(θ(x)) T J G (f (x), θ(x)) -1 = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) n(θ(x)) T = ∇f (x) T .
We deduce that

∇ 2 f (x) = 1 ∂G ∂λ (f (x), θ(x)), n(θ(x)) τ (θ(x))∇θ(x) T - ∂G ∂λ (f (x), θ(x)), τ (θ(x)) ∇f (x)∇θ(x) T -∇f (x)∇f (x) T n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) .
We have

τ (θ(x))∇θ(x) T - ∂G ∂λ (f (x), θ(x)), τ (θ(x)) ∇f (x)∇θ(x) T = τ (θ(x)) - ∂G ∂λ (f (x), θ(x)), τ (θ(x)) ∂G ∂λ (f (x), θ(x)), n(θ(x)) n(θ(x)) ∇θ(x) T = (a(λ)ρ -(θ) + b(λ)ρ + (θ))∇θ(x)∇θ(x) T
So that we actually get

∇ 2 f (x) ∂G ∂λ (f (x), θ(x)), n(θ(x)) = (a(λ)ρ -(θ) + b(λ)ρ + (θ))∇θ(x)∇θ(x) T -n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) ∇f (x)∇f (x) T = ∂G ∂θ (λ, θ), τ (θ(x)) ∇θ(x)∇θ(x) T -n(θ(x)), ∂ 2 G ∂λ 2 (λ, θ) ∇f (x)∇f (x) T .
This concludes the proof.

Smooth convex interpolation of smooth positively curved convex sequences

In this section, we consider an indexing set I with either I = N or I = Z, and an increasing sequence of compact convex sets (T i ) i∈I such that for any i in I, the couple T + := T i+1 , T -:= T i satisfies Assumption 1. In particular, for each i in I, T i is compact, convex with C k boundary and positive curvature. We denote by c i the corresponding parametrization by the normal, T i ⊂ int T i+1 . With no loss of generality we assume 0 ∈ ∩ i∈I T i . This is our main theoretical result.

Theorem 2 (Smooth convex interpolation). Let I = N or I = Z and (T i ) i∈I such that for any i ∈ I, T i ⊂ R 2 and the couple T + := T i+1 , T -:= T i satisfies Assumption 1. Then there exists a C k convex function

f : T := int i∈I T i → R such that (i) T i is a sublevel set of f for all i in I.
(ii) We have

argmin f = I T i if I = Z {0} if I = N.
(iii) ∇ 2 f is positive definite on T \argmin f , and if I = N, it is positive definite throughout T .

Proof :

Preconditionning. We have that 0 ∈ ∩ i∈I int(T i ). Hence for any i in I and 0 ≤ α < 1,

αT i ∈ int(T i ). Furthermore, for α > 0, small enough, (1 + α)T i ⊂ (1 -α)int(T i+1 ). Set α 0 such that (1 + α 0 )T 0 ⊂ (1 -α 0 )int(T 1 )
. By forward (and backward if I = Z) induction, for all i in I, we obtain α i > 0 such that

(1 + α i )T i ⊂ (1 -α i )int(T i+1 ).
Setting for all i in

I, i+1 = min{α i , α i+1 } ( 0 = α 0 if I = N), we have for all i in I (1 + i )T i ⊂ (1 + α i )T i ⊂ (1 -α i )int(T i+1 ) ⊂ (1 -i+1 )int(T i+1 ).
For all i in I, we introduce

S 3i = T i , S 3i+1 = (1 + i )T i S 3i+2 = (1 -i+1 )T i+1 .
We have a new sequence of strictly increasing compact convex sets (S i ) i∈I .

Value assignation. For each i in I, we set

K i = max x =1 σ S i+1 (x) -σ S i (x) σ S i (x) -σ S i-1 (x) ∈ (0, +∞) .
Note that for all i in I, K 3i = 1. We choose λ 1 = 2, λ 0 = 1 and for all i in I,

λ i+1 = λ i + K i (λ i -λ i-1 ). ( 9
)
By construction, we have for all i in I and all θ ∈ R/2πZ,

σ S i+1 (n(θ)) -σ S i (n(θ)) λ i+1 -λ i ≤ σ S i (n(θ)) -σ S i-1 (n(θ)) λ i -λ i-1 . If I = Z, this entails 0 < λ i -λ i-1 ≤ λ 1 -λ 0 σ S 1 (n(θ)) -σ S 0 (n(θ)) (σ S i (n(θ)) -σ S i-1 (n(θ))),
and the right-hand side is summable over negative indices i ≤ 0, so that λ i → λ ∈ R as i → -∞. In all cases (λ i ) i∈I is an increasing sequence bounded from below.

Local interpolation. We fix i in I and consider the function G i described in Proposition 1 with

T + = S 3i+3 = T i+1 , T -= S 3i = T i , λ + = λ 3i+3 , λ 1 = λ 3i+2 , λ 0 = λ 3i+1 , λ -= λ 3i , e 0 = i , e 1 = i+1
. By linearity, we have for any (λ, θ)

∈ [λ -, λ + ] × R/2πZ, G i (λ, θ), n(θ) = γΘ (λ)
where γΘ is as in Lemma 1 with input data

q 0 = c 3i (θ), n(θ) = σ S 3i (n(θ)), q 1 = c 3i+3 (θ), n(θ) = σ S 3i+3 (n(θ))
, and λ -, λ 0 , λ 1 , λ + , e 1 , e 0 as already described. This corresponds to the Bernstein approximation of the piecewise affine interpolation between the points

(λ 3i , σ S 3i (n(θ))) λ 3i+1 , σ S 3i+1 (n(θ)) , λ 3i+2 , σ S 3i+2 (n(θ)) , (λ 3i+3 , σ 3i+3 (n(θ))), (10)
By construction of (K i ) i∈I , we have for all θ,

0 < σ S 3i+3 (n(θ)) -σ S 3i+2 (n(θ)) λ 3i+3 -λ 3i+2 ≤ σ S 3i+2 (n(θ)) -σ S 3i+1 (n(θ)) λ 3i+2 -λ 3i+1 ≤ σ S 3i+1 (n(θ)) -σ S 3i (n(θ)) λ 3i+1 -λ 3i .
Whence the affine interpolant between points in ( 10) is strictly increasing and concave, and by using the shape preserving properties of Bernstein polynomials, G i (λ, θ), n(θ) has strictly positive derivative. As a consequence G i is a diffeomorphism and its derivatives are as in Proposition 1. Furthermore

λ → G i (λ, θ), n(θ) is a C k concave function of λ. Global interpolation. Recall that λ = inf i∈I λ i > -∞ and set λ = sup i∈I λ i ∈ (-∞, +∞].
For any λ ∈ (λ, λ), there exists a unique

i λ ∈ I such that λ ∈ [λ 3i λ , λ 3i λ +3 ). Define G : (λ, λ) × R/2πZ → R 2 (λ, θ) → G i λ (λ, θ). Fix i in I. The boundary of T i+1 is given by G i+1 (λ 3i+3 , R/2πZ) = G i (λ 3i+3 , R/2πZ) with actually G i+1 (λ 3i+3 , θ) = G i (λ 3i+3 , θ), for all θ in R/2πZ. (11)
Since K 3i = 1, we have

λ 3i+1 -λ 3i = λ 3i -λ 3i-1 .
The expressions of the derivatives in Proposition 1 and [START_REF] Bertsekas | Convex optimization algorithms[END_REF] ensure that the derivatives of G i+1 and G i agree on λ 3i+3 × R/2πZ up to order k. Hence G is a local diffeomorphism. Bijectivity of each G i ensure that G is also bijective and thus G is a diffeomorphism. Furthermore

λ → G(λ, θ), n(θ)
is C k piecewise concave and thus concave.

Extending G. If I = N, we may assume without loss of generality that S 0 = B the Euclidean ball and S 1 = 5/3S 0 , which corresponds to 0 = 2/3, eventually after adding a set in the list and rescaling. Let φ denote the function described in Lemma 10 and G -1 be described as in Lemma 11. This allows to extend G for λ ∈ [0, 1], G is then C k on (0, λ) × R/2πZ by using Lemma 11 and Proposition 1. This does not affect the differentiability, monotonicity and concavity properties of G.

Defining the interpolant f . We assume without loss of generality that λ = 0. We set f to be the first component of the inverse of G so that it is defined on G -1 (0, λ) × R/2πZ . We extend f as follows:

• f (0) = 0 if I = N, • f = 0 on ∩ i∈I T i if I = Z.
Since G is C k and non-singular on (0, λ) × R/2πZ, the inverse mapping theorem ensures that f is C k on int(T ) \ arg min T f .

Convexity of f . For any θ in R/2πZ, (0, λ) → R + λ → sup z∈[f ≤λ] n(θ) T z is equal to G(λ, θ), n(θ)
which is concave. It can be extended at λ = 0 by continuity. This preserves concavity hence, using Theorem 1, we have proved that f is convex and

C k on T \ argmin T f .
Smoothness around the argmin and Hessian positivity. If I = N, then the interpolant defined in Lemma 11 ensures that f is proportional to the norm squared around 0. Hence it is C k around 0 with positive definite Hessian. We may compose f with the function g : t → √ t 2 + 1 + t which is increasing and has positive second derivative. This ensures that the resulting Hessian is positive definite outside argmin f and thus everywhere since

∇ 2 g • f = g ∇ 2 f + g ∇f ∇f T
is positive definite thanks to the expressions for the Hessian of f in Proposition 1

If I = Z, we let all the derivatives of f vanish around the solution set. The smoothing Lemma 14 applies and provides a function φ with positive derivative on (0, +∞), such that φ • f is convex, C k with prescribed sublevel sets. Furthermore, we remark that

∇ 2 φ • f = φ ∇ 2 f + φ ∇f ∇f T .
We may compose φ • f with the function g : t → √ t 2 + 1 + t which is increasing with positive second derivative, the expressions for the Hessian of f in Proposition 1 ensure that the resulting Hessian is positive definite out of argmin f . Remark 3 (Interpolation of symmetric rings). In view of Remark 1, if we have T i+1 = αT i for some 0 < α < 1 and i in Z, then the interpolated level sets between T i and T i+1 are all of the form sT i for α ≤ s ≤ 1.

Remark 4 (Strict convexity). Recall that strict convexity of a differentiable function amounts to the injectivity of its gradient. In Theorem 2 if there is a unique minimizer, then the invertibility of the Hessian outside argmin f ensures that our interpolant is strictly convex (note that this is automatically the case if I = N).

Considerations on Legendre functions

The following proposition provides some interpolant with additional properties as global Lipschitz continuity and finiteness properties for the dual function. At this stage these results appear as merely technical but they happen to be decisive in the construction of counterexamples involving Legendre functions. The properties of Legendre functions can be found in [START_REF] Rockafellar | Convex analysis[END_REF]Chapter 6]. We simply recall here that, given a convex body

C of R p , a convex function h : C → R is Legendre if it is differentiable on int C and if ∇h defines a bijection from int C to ∇h(int C) with in addition lim x ∈ int C x → z ∇h(x) = +∞,
for all z in bd C. We also assume that epi

f := {(x, λ) : f (x) ≤ λ} is closed in R p+1 . The Legendre conjugate or dual function of h is defined through h * (z) = sup { z, x -h(x) : x ∈ C} ,
for z in R p , and its domain is D := {z ∈ R p : h(z) < +∞} . The function h * is differentiable on the interior of D, and the inverse of ∇h

: int C → int D is ∇h * : int D → int C.
We start with a simple technical lemma on the compactness of the domain of a Legendre function.

Lemma 3. Let h : R 2 → R be a globally Lipschitz continuous Legendre function, and set D = int(dom(h * )) where h * : R 2 → R is the conjugate of h. For each λ ≥ min R 2 h let σ λ be the support function associated to the set {z ∈ R 2 , h(z) ≤ λ}. The following are equivalent (i) h * (x) ≤ 0 for all x ∈ D.

(ii) For all y ∈ R 2 , σ h(y) (∇h(y)) ≤ h(y).

In both cases h * has compact domain.

Proof : Let us establish beforehand the following formula

h * (z) = σ h(y) (∇h(y)) -h(y), (12)
with y = ∇h * (z) and y ∈ R 2 . Since h * is Legendre, we have for all y in D,

h * (z) = sup y∈R 2 z, y -h(y) = z, ∇h * (z) -h(∇h * (z)).
We have, setting y = ∇h * (z)

z, ∇h * (z) = ∇h(y), y = σ h(y) (∇h(y))
because ∇h(y) is normal to the sublevel set of h which contains y in its boundary. Hence we have h * (z) = σ h(y) (∇h(y))-h(y) with y = ∇h * (z), that is (12) holds. Since ∇h * : D → R 2 is a bijection, the equivalence follows. In this case the domain of h * is closed because h * is bounded and lower semicontinuous. The domain is also bounded by the Lipschitz continuity of h, whence compact.

Proposition 2 (On Legendre interpolation). Let (S i ) i∈N be such that for any i in I, T -= S i , T + = S i+1 satisfy Assumption 1 and there exists a sequence ( i ) i∈N in (0, 1) such that for all i ≥ 1, (1

-i ) -1 S 3i-1 = (1 + i ) -1 S 3i+1 = S 3i .
Assume in addition that,

inf x =1 σ S i (x) -σ S i-1 (x) = 1 + O 1 i 3 (non degeneracy), (13)
sup

x =1 σ S i+1 (x) -σ S i (x) σ S i (x) -σ S i-1 (x) -1 = O 1 i 3 (moderate growth). ( 14
)
Then there exists a convex C k function h : R 2 → R, such that

• For all i in N, S 3i is a sublevel set of h,

• h has positive definite Hessian,

• h is globally Lipschitz continuous,

• h * has a compact domain D and is C k and strictly convex on int(D).

Proof : The construction of h follows the exact same principle as that of Theorem 2. This ensures that the first two points are valid. Note that equation [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] implies that the sets sequence grows by at least a fixed amount in each direction as i grows. Hence we have T = R 2 .

Global Lipschitz continuity of h: The values of h are defined through

λ i+1 -λ i = K i (λ i -λ i-1 ), ∀i ∈ N * K i = max x =1 σ S i+1 (x) -σ S i (x) σ S i (x) -σ S i-1 (x) ∈ (0, +∞) ,
so that K i = 1 + O(1/i 3 ) thanks to equation [START_REF] Bolte | Barrier operators and associated gradientlike dynamical systems for constrained minimization problems[END_REF]. Note that the moderate growth assumption entails

sup i∈N σ S i+1 (x) -σ S i (x) = O i∈N * K i = O(1). ( 15
) For i ≥ 1, one has λ i+1 -λ i = 1≤j≤i K j (λ 1 -λ 0 ). ( 16
)
On the other hand using the bounds ( 14), [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] and the identity ( 16), there exists a constant κ > 0 such that for all i ≥ 1, all θ in R/2πZ,

σ S i+1 (n(θ)) -σ S i (n(θ)) λ i+1 -λ i = σ S i+1 (n(θ)) -σ S i (n(θ)) i j=1 K j (λ 1 -λ 0 ) ≥ κ > 0. ( 17
)
By the interpolation properties described in Lemma 1 the function G(λ, θ), n(θ) constructed in Theorem 2 has derivative with respect to λ greater than κ. Recalling the expression of the gradient as given in Proposition 1 (and the concavity of G with respect to λ), this shows that ∇h(x) ≤ 1 κ for all x in R 2 , and by the mean value theorem, h is globally Lipschitz continuous on R 2 .

Properties of the dual function: h is Legendre, its conjugate h * is therefore Legendre. From the definiteness of ∇ 2 h and the fact that ∇h : R 2 → int(D) is a bijection, we deduce that h * is C k by the inverse mapping theorem. So the only property which we need to establish is that h * has a compact domain, in other words, using Lemma 3, it is sufficient to show that sup x∈intD h * (x) ≤ 0.

Using the notation of the proof of Theorem 2, we will show that it is possible to verify that, for all λ, θ in the domain of G n(θ), G(λ, θ)

∂G ∂λ (λ, θ), n(θ) ≤ λ. (18)
Equation ( 18) is indeed the coordinate form of the characterization given in Lemma 3.

Let us observe that

∂ ∂λ n(θ), G(λ, θ) -λ ∂G ∂λ (λ, θ), n(θ) = -λ ∂ 2 G ∂λ 2 (λ, θ), n(θ) , (19)
and since G is concave, the right hand side is positive.

Assume that we have proved that,

λ → sup θ -λ ∂ 2 G ∂λ 2 (λ, θ), n(θ) (20)
has finite integral as λ → ∞. Since the function

θ → λ ∂ 2 G ∂λ 2 (λ, θ), n(θ) (21)
is continuous on R/2πZ for any λ, Lebesgue dominated convergence theorem would ensure that

θ → λ≥λ 0 -λ ∂ 2 G ∂λ 2 (λ, θ), n(θ) dλ
is continuous in θ, so that:

sup θ lim λ→∞ n(θ), G(λ, θ) -λ ∂G ∂λ (λ, θ), n(θ) < +∞.
Shifting values if necessary, we could assume that this upper bound is equal to zero to obtain equation [START_REF] Crouzeix | Conditions for convexity of quasiconvex functions[END_REF]. The latter being the condition required in Lemma 3, we would have reached a conclusion.

Let us therefore establish that ( 19) is integrable over R + . Recall that G is constructed using the Bernstein interpolation given in Lemma 1 between successive values of λ. As a result, for a fixed θ, the function n(θ), G(λ, θ) is the interpolation of the piecewise affine function interpolating

(λ 3i , σ S 3i (n(θ))) λ 3i+1 , σ S 3i+1 (n(θ)) , λ 3i+2 , σ S 3i+2 (n(θ)) , (λ 3i+3 , σ 3i+3 (n(θ))), (22)
as in equation ( 10). This interpolation is concave and increasing.

Assumption [START_REF] Bolte | Barrier operators and associated gradientlike dynamical systems for constrained minimization problems[END_REF] ensures that

K j = 1 + O(1/j 3 ). Then m j=1 K j = K + O(1/j 2 )
where K is the finite, positive limit of the product (we can for example perform integral series comparison after taking the logarithm).

The recursion on the values writes for all i ≥ 1

λ i+1 = λ i + K i (λ i -λ i-1 ), so that λ i+1 -λ i = (λ 1 -λ 0 ) i j=1 K i = (λ 1 -λ 0 ) K + O(1/i 2 ).
This means that the gap between consecutive values tends to be constant. Thus by (4) in Lemma 1, see also Remark 1, the degree of the Bernstein interpolants is bounded. Using this bound together with inequality (3), providing bounds for the derivatives of Bernstein's polynomial, ensure that, for all λ in [λ 3i , λ 3i+3 ):

∂ 2 G ∂λ 2 (λ, θ), n(θ) = O max j=3i+2,3i+1 σ S j+1 (n(θ)) -σ S j (n(θ)) λ j+1 -λ j - σ S j (n(θ)) -σ S j-1 (n(θ)) λ j -λ j-1 .
Now for any j = 3i + 2, 3i + 1,

σ S j+1 (n(θ)) -σ S j (n(θ)) λ j+1 -λ j - σ S j (n(θ)) -σ S j-1 (n(θ)) λ j -λ j-1 = 1 λ j+1 -λ j (σ S j+1 (n(θ)) -σ S j (n(θ))) - λ j+1 -λ j λ j -λ j-1 (σ S j (n(θ)) -σ S j-1 (n(θ)) ) = 1/((λ 1 -λ 0 ) K) + O(1/i 2 ) × (σ S j+1 (n(θ)) -σ S j (n(θ))) -(1 + O(1/i 2 ))(σ S j (n(θ)) -σ S j-1 (n(θ)) ) = 1/((λ 1 -λ 0 ) K) + O(1/i 2 ) × (σ S j+1 (n(θ)) -σ S j (n(θ))) -(σ S j (n(θ)) -σ S j-1 (n(θ)) )
where the last identity follows from the triangle inequality because using σ S j (n(θ))σ S j-1 (n(θ)) = O(1) in [START_REF] Borwein | Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets[END_REF]. Hence

∂ 2 G ∂λ 2 (λ, θ), n(θ) = 1/((λ 1 -λ 0 ) K) + O(1/i 2 ) × O max j=3i+2,3i+1 σ S j+1 (n(θ)) -σ S j (n(θ)) -(σ S j (n(θ)) -σ S j-1 (n(θ))) = 1/((λ 1 -λ 0 ) K) + O(1/i 2 ) × O max j=3i+2,3i+1 σ S j (n(θ)) -σ S j-1 (n(θ)) × σ S j+1 (n(θ)) -σ S j (n(θ)) σ S j (n(θ)) -σ S j-1 (n(θ)) -1 = O(1/i 3 ),
where the last inequality follows from ( 15) and ( 14). Now as i → ∞, λ 3i ∼ λ 3i+3 ∼ ic for some constant c > 0 and

sup λ∈[λ 3i ,λ 3i+3 ],θ∈[0,2π] -λ ∂ 2 G ∂λ 2 (λ, θ), n(θ) = O(1/i 2 ) and sup θ∈[0,2π] -λ ∂ 2 G ∂λ 2 (λ, θ), n (θ)
has finite integral as λ → ∞. This implies [START_REF] Dragomir | Optimal complexity and certification of Bregman first-order methods[END_REF] and it concludes the proofs.

Smooth convex interpolation for sequences of polygons

Given a sequence of points A 1 , . . . , A n , we denote by A 1 . . . A n the polygon obtained by joining successive points ending the loop with the segment [A n , A 1 ]. In the sequel we consider mainly convex polygons, so that the vertices A 1 , . . . , A n are also the extreme points.

The purpose of this section is first to show that polygons can be approximated by smooth convex sets with prescribed normals under weak assumptions. Figure 3 illustrates the result we would like to establish: given a target polygon with prescribed normals at its vertices, we wish to construct a smooth convex set interpolating the vertices with the desired normals and whose distance to the polygon is small.

Then given a sequence of nested polygons, we provide a smooth convex function which interpolates the polygons in the sense described just above.

Given a closed nonempty convex subset S of R p and x in S, we recall that the normal cone to S at x is N S (x) = {z ∈ R p : z, y -x ≤ 0, ∀y ∈ S} .

Such vectors will often simply called normals (to S) at x.

Smooth approximations of polygons

Lemma 4. For any r -, r + > 0, t -> 0, t + < 0 and > 0, m ∈ N, m ≥ 3, there exists a strictly concave polynomial function p : [0, 1] → [0, ] such that

p(0) = 0 p(1) = 0 p (0) = t - p (1) = t + p (0) = -r - p (1) = -r + .
p (q) (0) = 0 q ∈ {3, . . . , m}.

Proof : Let us begin with preliminary remarks. Consider for any a, b in R, the function

f : t → a(t -b) 2 .
For any t in R, q in N, q > 2, and any c > 0, we have

f (t + c) -f (t) = ∆ 1 c f (t) = ac(2(t -b) + c) f (t + 2c) -2f (t + c) + f (t) = ∆ 2 c f (t) = ac(2(t + c -b) + c -2(t -b) -c) = 2ac 2 ∆ q c f (t) = 0 ( 23
)
Choosing the degree d and constructing the polynomial. For any d in N, d ≥ 2m + 1, we set

a -(d) = -dr - 2(d -1) < 0 b -(d) = 1 2d 1 + 2t - d -1 r - > 0 a + (d) = -dr + 2(d -1) < 0 b + (d) = 1 + 1 2d -1 + 2t + d -1 r + < 1, (24)
and define the functions

f d : s → a -(d)((s -b -(d)) 2 -b -(d) 2 ) if s ≤ b -(d) -a -(d)b -(d) 2 if s ≥ b -(d)
g d : t → a + (d)((s -b + (d)) 2 -(1 -b + (d)) 2 ) if s ≥ b + (d) -a + (d)(1 -b + (d)) 2 if s ≤ b + (d).
Furthermore, we set with constants that do not depend on d. Note also that f (0) = 0 < g(0) and g(1) = 0 < f (1). We choose d ≥ 2m + 1 such that

f : t →      r - 2 t - r - 2 -s -t - r - 2 if s ≤ t - r - r - 2 t - r - 2 if s ≥ t - r - g : t →      r + 2 t + r + 2 -s -1 -t + r + 2 if s ≥ 1 + t + r + r + 2 t + r + 2 if s ≤ 1 + t + r + . Note that b -(d) → t -/r -, b + (d) → 1 + t + /r + , a -(d) → -
f d m d ≤ min , g d m d g d 1 - m d ≤ min , f d 1 - m d . (25)
d(d -1)∆ 2 h(0) = d(d -1)∆ 2 f d (0) = d(d -1) 2a -(d) d 2 = -r - d∆h(0) = d∆f d (0) = a -(d) 1 d -2b -(d) = t - ∆ q h(0) = 0 = ∆ q f d (0) ∀m ≥ q ≥ 3 d(d -1)∆ 2 h 1 - 2 d = d(d -1)∆ 2 g d 1 - 2 d = d(d -1) 2a + (d) d 2 = -r + d∆h 1 - 1 d = d∆g d 1 - 1 d = a + (d) -1 d + 2(1 -b + (d)) = t + ∆ q h 1 - m d = ∆ q g d 1 - m d = 0 ∀m ≥ q ≥ 3.
From the concavity of h and the derivative formula (2), we deduce that the polynomial B h,d satisfies the desired properties. Numerical estimations of the first and second order derivatives at 0 and 1 match the required values up to 3 precision digits. The polynomial is strongly concave, however, this is barely visible because the strong concavity constant is extremely small.

We deduce the following result Lemma 5. Let a > 0, r > 0, > 0, and an integer m ≥ 3. Consider two unit vectors: v -with strictly positive entries and v + with first entry strictly positive and second entry strictly negative. Then there exists a

C m curve γ : [0, M ] → R 2 , such that 1. γ = 1.
2. γ(0) = (-a, 0) := A and γ(1) = (0, a) := B.

3. γ (0) = v -and γ (1) = v + .

4. γ (0) = γ (-1) = r.

5. det(γ , γ ) < 0 along the curve.

6. γ (q) (0) = γ (q) (1) = 0 for any 3 ≤ q ≤ m.

dist(γ([0, M ]), [A, B]) ≤ .

Proof : Consider the graph of a polynomial as given in Lemma 4 with t

-= v -[2]/v -[1] > 0, t + = v + [2]/v + [1] < 0 and r -= r 2a (1 + t 2 -) 3 2 , r + = r 2a (1 + t 2 + )
3 2 and /2a as an approximation parameter. This graph is parametrized by t. It is possible to reparametrize it by arclength to obtain a C m curve γ 0 whose tangents at 0 is T -, at 1 is T + , and whose curvature at 0 and 1 is -r 2a . Furthermore, γ 0 has strictly negative curvature whence item 5. Consider the affine transform: x → 2a(x -1/2), y → 2ay. This results in a C m curve γ, parametrized by arclength which satisfies the desired assumptions.

Lemma 6 (Normal approximations of polygons by smooth convex sets). Let S = A 1 ...A n be a convex polygon. For each i, let V i be in N S (A i ) such that the angle between V i and each of the two neighboring faces is within π 2 , π . Then for any > 0 and any m ≥ 2, there exists a compact convex set C ⊂ R 2 such that (i) the boundary of C is C m with non vanishing curvature, (ii) S ⊂ C, (iii) for any i = 1, . . . , n, A i in bd (C) and the normal cone to C at A i is given by V i , (iv) max y∈C dist(y, S) ≤ .

Proof : We assume without loss of generality that A 1 , . . . , A n are ordered clockwise. For i = 1, . . . , n -1, and each segment [A i , A i+1 ], we may perform a rotation and a translation to obtain A i = -(a, 0) and A i+1 = (a, 0). Working in this coordinate system, using the angle condition on V i , we may choose v - i , v + i+1 satisfying the hypotheses of Lemma 5 respectively orthogonal to V i and V i+1 . Choosing r = 1, we obtain γ i : [0, M i ] → R 2 as given by Lemma 5. Rotation and translations affect only the direction of the derivatives of curves, not their length. Hence, it is possible to concatenate curves (γ i ) n-1 i=1 and to preserve the C m properties of the resulting curve. At end-points, tangents and second order derivatives coincide while higher derivatives vanish. Furthermore the curvature has constant sign and does not vanish. We obtain a closed C m curve which defines a convex set which satisfies all the requirements of the lemma.

Remark 5 (Bissector). Given any polygon, choosing normal vectors as given by the direction of the bissector of each angles ensure that the above assumptions are satisfied. Hence all our approximation results hold given polygon without specifying the choice of outer normals.

Smooth convex interpolants of polygonal sequences

Definition 1 (Interpolability). For n ≥ 3, let A 1 . . . A n be a convex polygon S and V i be in N S (V i ) for i = 1, . . . , n. We say that (A i , V i ) n i=1 is interpolable if for each i = 1, . . . , n, the angle between V i and each of the two neighboring faces of the polygon is in π 2 , π . The collection (A i , V i ) n i=1 is called a polygon-normal pair.

We start with the following preparation proposition related to the Legendre interpolation of Proposition 2.

Lemma 7. Let (P N i ) i∈N * be a strictly increasing sequence of interpolable polygon-normal pairs. Setting for i in N * , P N i = (A j,i

) n i j=1 , (V j,i ) n i j=1
where n j is in N * and denoting by T i the polygon A 1,i . . . A n i ,i , we assume that

T i = 3iP, ∀i ∈ N * ,
where P is a fixed polygon which contains the unit Euclidean disk. Then for any l in N, l ≥ 2, there exists a strictly increasing sequence of sets (S i ) i∈N, i≥2 , such that for j ≥ 1,

• S 3j interpolates the normals of P N j in the sense of Lemma 6 with dist(S 3j , T j ) ≤ 1/(4(3j + 2) l )

• S 3j-1 = 3j-1 3 j S 3j • S 3j+1 = 3j+1 3 j S 3j
This sequence has the following properties

• there exists c > 0, such that for all j in N, j ≥ 3 and for all unit vector x,

c ≥ σ S j+1 (x) -σ S j (x) ≥ 1 - 1 (j + 1) l . ( 26
)
• for all unit vector x,

σ S j+1 (x) -σ S j (x) σ S j (x) -σ S j-1 (x) -1 ≤ 1 j l , ∀j ≥ 3. ( 27
)
Proof : Set for all j in N * , δ j = 1 4(3j+2) l and let S 3j be the δ j interpolant of T j = 3jP as given by Lemma 6 so that dist(S 3j , 3jP ) ≤ δ j . Since P contains the unit ball, 3jP ⊂ S 3j ⊂ (3j + δ j )P. [START_REF] Lorentz | Bernstein polynomials[END_REF] Now set

S 3j-1 = 3j -1 3 j S 3j S 3j+1 = 3j + 1 3 j S 3j .
For any j in N * , it is clear that S 3j-1 ⊂ int(S 3j ) and S 3j ⊂ int(S 3j+1 ). Furthermore, by [START_REF] Lorentz | Bernstein polynomials[END_REF], we have S 3j+1 ⊂ 3j + 1 3j (3j + δ j )P ⊂ ((3j + 1) + 2δ j )P ⊂ int((3j + 2)P ) ⊂ int(S 3j+2 ) so that we indeed have a strictly increasing sequence of sets. We obtain from the construction, for any j in N * , and any unit vector x,

σ S 3j (x) -σ S 3j-1 (x) = σ S 3j+1 (x) -σ S 3j (x) = 1 3j σ S 3j (x) ∈ σ P (x), 1 + δ j 3j σ P (x) ⊂ 1, 1 + δ j 3j σ P (x) σ S 3j+2 (x) -σ S 3j+1 (x) ≤ σ P (x)(3j + 2) 1 + δ j+1 3j + 3 -σ P (x)(3j + 1) σ S 3j+2 (x) -σ S 3j+1 (x) ≥ σ P (x)(3j + 2) -σ P (x)(3j + 1) 1 + δ j 3j = σ P (x) 1 -δ j 3j + 1 3j ≥ 1 -δ j 4 3 ≥ 1 - 1 (3j + 2) l (29)
This proves [START_REF] Kurdyka | Proof of the gradient conjecture of R. Thom[END_REF]. We deduce that for all j in N * ,

σ S 3j+1 (x) -σ S 3j (x) σ S 3j (x) -σ S 3j-1 (x) = 1, for all nonzero vector x, max x =1 σ S 3j+2 (x) -σ S 3j+1 (x) σ S 3j+1 (x) -σ S 3j (x) ≤ (3j + 2) 1 + δ j+1 3j + 3 -(3j + 1) = 1 + 3j + 2 3j + 3 δ j+1 ≤ 1 + 1 (3j + 1) l , min x =1 σ S 3j+2 (x) -σ S 3j+1 (x) σ S 3j+1 (x) -σ S 3j (x) ≥ (29)
1 -δ j 3j+1 3j

1 +

δ j 3j ≥ 1 -δ j 3j + 1 3j 1 - δ j 3j ≥ 1 -δ j 3j + 1 3j + 1 3j ≥ 1 -δ j 5 3 ≥ 1 - 1 (3j + 1) l .
Furthermore, using the fact that t → 1+t 1-t is increasing on (-∞, 1) and the fact that

δ j+1 ≤ δ j , max x =1 σ S 3j+3 (x) -σ S 3j+2 (x) σ S 3j+2 (x) -σ S 3j+1 (x) ≤ (29) 1 + δ j+1 3j+3
1 -(3j + 1)

δ j 3j ≤ 1 + (3j + 1) δ j 3j
1 -(3j + 1)

δ j 3j ≤ 1 + δ j 4 3 1 -δ j 4 3 . ( 30
)
Proof : Since P is a polygon and contains the unit Euclidean disk, the gauge function of 3P is polyhedral with full domain R 2 , call it ω. Denote by P • the polar of P . This is a polytope and since ω is the gauge of P , we actually have ω = σ P It can be easily seen from the proof of Proposition 2 that λ i = αi + r i with r(i) = O(1) as i → ∞. Without loss of generality, we may suppose that α = 1 (this is a simple rescaling) so that there is a positive constant c such that |λ i -i| ≤ c for all i.

Let h be given as in Theorem 3, fix i ≥ 1 and

x ∈ R 2 such that λ i-1 ≤ h(x) ≤ λ i . We have in R 2 {y : ω(y) ≤ i -1} ⊂ {y : h(y) ≤ λ i-1 } ⊂ {y : h(y) ≤ λ i } ⊂ {y : ω(y) ≤ i + 1}
and hence

i -1 ≤ ω(x) ≤ i + 1
and we deduce that

ω(x) -2 -c ≤ i -1 -c ≤ λ i-1 ≤ h(x) ≤ λ i ≤ i + c ≤ ω(x) + c + 1.
Since i was arbitrary, this shows that there exists a constant C > 0 such that |h(x) -

ω(x)| ≤ C for all x ∈ R 2 . Recall that z → sup y∈R 2 y, z -ω(y) is the indicator function of P • , hence, z ∈ P • ⇒ sup y∈R 2 y, z -ω(y) = 0 ⇒ sup y∈R 2 y, z -h(y) ≤ C < +∞ z ∈ P • ⇒ sup y∈R 2 y, z -ω(y) = +∞ ⇒ sup y∈R 2 y, z -h(y) = +∞
which shows that the domain of h * is actually P • which is a polytope. Now, h * is convex and lower semicontinuous on P • , invoking the results of [START_REF] Gale | Convex functions on convex polytopes[END_REF], it is also upper semicontinuous on B * and finally it is continuous on B * .

Corollary 3 (A pathological Legendre function). For any θ ∈ -π 4 , π 4
there exists a Legendre function h : R 2 → R whose domain is a closed square, continuous on this domain and C k on its interior, such that for all i ∈ N * , ∇h * (i, 0) is proportional to (cos(θ), (-1) i sin(θ)).

Proof : For x = (u, v), set x 1 = |u| + |v|, and let P = {x ∈ R 2 , x 1 ≤ 2}. Let us construct a strictly increasing sequence of interpolable polygon-normal pairs (P N i ) i∈N * as follows, we fix θ ∈ -π 4 , π 4 and set for all i ∈ N * :

• T i = 3iP , the polygon associated to the i-th term P N i of the sequence,

• except at the rightmost corner, consider the normals given by the canonical basis vectors and their opposite,

• at the rightmost corner, (6i, 0), one chooses the normal given by the vector (cos(θ), (-1) i sin(θ)).

We now invoke Theorem 3 to obtain a Lipschitz continuous Legendre function, denoted h * , with full domain having all the T i as sublevel sets and satisfying the hypotheses of the corollary. Rescaling by a factor 6 and setting h = h * * gives the result.

Counterexamples in continuous optimization

We are now in position to apply our interpolation results to build counterexamples to classical problems in convex optimization. We worked on situations ranging from structural questions to qualitative behavior of algorithms and ODEs. Through 9 counterexamples we tried to cover a large spectrum but there are many more possibilities that are left for future research. Some example are constructed from decreasing sequences of convex sets, they can be interpolated using Theorem 2 with I = Z, indexing the sequence with negative indices and adding artificially additional sets for positive indices. Nonetheless we sometimes depart from the notations of the first sections and index these sequences by N even though they are decreasing for simplification purposes.

Kurdyka-Lojasiewicz inequality may not hold

The following result is proved in [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF], it was crucial to construct a C 2 convex function which does not satisfy Kurdyka-Lojasiewicz (KL) inequality. Lemma 35] There exists a decreasing sequence of compact convex sets (T i ) i∈N such that for any i in N, T -= T i+1 and T + = T i satisfy Assumption 1 and

Lemma 8. [12,

+∞ i=0 dist(T i , T i+1 ) = +∞
As a corollary, we improve the counterexample in [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF] and provide a C k convex counterexamples for any k ≥ 2 in N.

Corollary 4 (Smooth convex functions are not KL in general). There exists a C k convex function f : R 2 → R which does not satisfy KL inequality. More precisely, for any r > inf f and ϕ : [inf f, r] → R continuous and differentiable on (inf f, r) with ϕ > 0 and ϕ(inf f ) = 0, we have

inf{ ∇(ϕ • f )(x) : x ∈ R 2 , inf f < f (x) < r} = 0.
Proof : Using [35, Theorem 1.8.13], each T i can be approximated up to arbitrary precision by a polygon. Hence we may assume that all T i are polygonal while preserving the property of Lemma 8 as well as Assumption 1. Furthermore, using Lemma 6 and Remark 5 each T i can in turn be approximated with arbitrary precision by a convex set with C k boundary and positive curvature. Hence we may also assume that all T i satisfy both the result of Lemma 8 and have C k boundary with nonvanishing curvature. Reversing the order of the sets and adding additional sets artificially, we are in the conditions of application of Theorem 2 with I = Z and the resulting f follows from the same argument as in [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF]Theorem 36]. The following polygonal construction is illustrated in Figure 5. For any n ≥ 2 in N, we set

Block coordinate descent may not converge

= 3 i = 2 r = 1.2 C n B n D n E n A n 1.0 x y -3 -2 -1 1 2 3 4 -3 -2 -1 1 2 3 scale
A n = 1 4 + 1 n , 1 4 + 1 n B n = 1 4 + 1 2(n -1) + 1 2n , 1 4 + 1 2n + 1 2(n + 1) C n = 1 4 + 1 n , - 1 4 - 1 n
D n = - 1 4 - 1 n , - 1 4 - 1 n E n = - 1 4 - 1 n , + 1 4 + 1 n .
This defines a convex polygon. We may choose the normals at A n , C n , D n , E n to be bisectors of the corresponding corners and the normal at B n to be horizontal (see Figure 5). Rotating by an angle of -nπ 2 and repeating the process indefinitely, we obtain the sequence of polygons depicted in Figure 5. It can be checked that the polygons form a strictly decreasing sequence of sets, as for n > 1, the polygon

A n B n C n D n E n is contained in the interior of the square A n-1 C n-1 D n-1 E n-1 .
This fulfills the requirement of Corollary 1.

Corollary 5. There exists a C k convex function f : R 2 → R and an initialization x 0 = (u 0 , v 0 ) such that the recursion, for i ≥ 1

u i+1 ∈ argmin u f (u, v i ) v i+1 ∈ argmin v f (u i+1 , v)
produces a non converging sequence

(x i ) i∈N = ((u i , v i )) i∈N .
Proof : We apply Corollary 1 to the proposed decreasing sequence and by choosing (u 0 , v 0 ) = B 2 for example. This requires to shift indices (start with i = 2) and use Theorem 2 with I = Z. Note that the optimality condition for partial minimization and the fact that level sets have nonvanishing curvature ensure that the partial minima are unique.

In the nonsmooth convex case cyclic minimization is known to fail to provide the infimum value, see e.g., [3, p. 94]. Smoothness is sufficient for establishing value convergence (see e.g. [START_REF] Beck | On the convergence of block coordinate descent type methods[END_REF][START_REF] Wright | Coordinate descent algorithms[END_REF] and references therein), whether it is enough or not for obtaining convergence was an open question. Our counterexample closes this question and shows that cyclic minimization does not yield converging sequences even for C k convex functions. This result also closes the question for the more general nonconvex case for which we are not aware of a nontrivial counterexample for convergence of alternating minimization. Let us mention however Powell's example [START_REF] Powell | On search directions for minimization algorithms[END_REF] which shows that cyclic minimization with three blocks does not converge for smooth functions.

It would also be interesting to understand how our result may impact dual methods and counterexamples in that field, as for instance the recent three blocks counterexample in [START_REF] Chen | The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[END_REF].

Gradient descent with exact line search may not converge

Gradient descent with exact line search is governed by the recursion:

x + ∈ argmin {f (y) : y = x -t∇f (x), t ∈ R} ,
where x is a point in the plane.

Observe that the step coincides with partial minimization when the gradient ∇f (x) is colinear to one of the axis of the canonical basis. From the previous section, we thus deduce the following.

Corollary 6 (Failure of gradient descent with exact line search). There exists a C k convex function f : R 2 → R and an initialization z 0 in the plane such that the recursion, for i ≥ 1

x i+1 ∈ argmin {f (y) : y = x i -t∇f (x i ), t ∈ R}
produces a well defined non converging sequence (x i ) i∈N .

-0.50 -0.25 0.00 0.25 0.50

-0.3 0.0 0.3 0.6 x y -3 -2 -1 1 2 3 4 5 6 7 -3 -2 -1 1 2 3
i = 1 P scale = 2 B n r = 1.5 C n A n E n D n N n A n M n
Figure 6: Illustration of the Tikhonov regularization example, on the left in gray, polygons used to build the sublevel sets of the constructed f and the corresponding solutions to [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF] for some values of r (solutions are joined by dotted lines). On the right the normal to be chosen to apply Lemma 6 (for n = 1, see main text for details). The point P represents x, it sits on the x-axis and is constantly contained in the normal cone at B n for any n ≥ 1.

Convergence failure for gradient descent with exact line search is new up to our knowledge. Let us mention that despite non convergence, the constructed sequence satisfy sublinear convergence rates in function values [START_REF] Beck | On the convergence of block coordinate descent type methods[END_REF].

Tikhonov regularization path may have infinite length

Following [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF], we consider for any r > 0

x(r) = argmin f (x) + r x -x 2 2 : x ∈ R 2 (31)
where f is C k convex and where x is any anchor point. We would like to show that the curve r → x(r) may have infinite length. Torralba provided a counterexample in his PhD Thesis for continuous convex functions, see [START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF]. This work extends his result to smooth

C k convex functions in R 2 .
For any n in N * , we set

A n = 2 n , 2 n B n = 2 n + 1 n 2 , - 1 n C n = 2 n , - 2 n D n = - 2 n , - 2 n E n = - 2 n , 2 n .
This is depicted in Figure 6. For all n ≥ 1, denote by M n the point on the x axis above B n and N n , the intersection of the normal cone at B n and the x axis. We have

M n N n M n B n = n × M n N n = A n B n A n A n = 3/n 1/n 2 = 3n,
so that for all n ≥ 1, M n N n = 3 and N n = (3 + 2/n + 1/n 2 , 0). Choosing P = (7, 0), since for n ≥ 1, 3 + 2/n + 1/n 2 ≤ 6 < 7 , this shows that P constantly belongs to the interior of the normal cone at B n for all n ≥ 1. The sequence of level sets is constructed as in Figure 6 by considering alternating symmetries with respect to the x-axis of the sequence of polygons above. It can be checked that the polygons form a strictly decreasing sequence of sets, as for n > 1, the polygon

A n B n C n D n E n is contained in the interior of the square A n-1 C n-1 D n-1 E n-1 .
We choose the normal at A n , C n , D n , E n to belong to the bisector at the corner and the normal at B n to be proportional to the vector B n P . Applying Corollary 1, we construct f and choose x = P in [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF] to obtain the following:

Corollary 7 (A bounded infinite length Tikhonov path). There exists a C k strictly convex function f : R 2 → R and x ∈ R 2 such that the curve x((0, 1)) given by (31) has infinite length.

Proof : We apply Corollary 1 with I = Z and revert the indices set to match the sequence that we have described. For any n ≥ 1 there exists a value of λ n such that f (B n ) = λ n and ∇f (B n ) is colinear to the vector B n P . Set

r = ∇f (B n ) 2B n P
we have ∇f (B n ) + 2r(B n -P ) = 0 which is the optimality condition in (31) with x = P . Hence we have shown that there exists a value of r such that B n is the solution to [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF].

Since n was arbitrary this is true for all n and the curve r → x(r) has to go through a sequence of points whose second coordinate is of the form (-1) n /n for all n ≥ 1. Since this sequence is not absolutely summable, the curve has infinite length.

This result is in contrast with the definable case for which we have finite length by the monotonicity lemma, since the whole trajectory is definable and bounded.

Secants of gradient curves at infinity may not converge

Thom's gradient conjecture and Kurdyka-Mostowski-Parusinski's theorem A theorem of Lojasiewicz [START_REF] Lojasiewicz | Sur les trajectoires du gradient d'une fonction analytique[END_REF] asserts that bounded solutions to the gradient system ẋ(t) = -∇f (x(t))

converge when f is a real analytic potential. Thom conjectured in [START_REF] Thom | Problèmes rencontrés dans mon parcours mathématique : un bilan[END_REF] that this convergence should occur in a stronger form: trajectories converging to a given x should admit a tangent at infinity, that is

x(t) -x x(t) -x (32)
should have a limit as t → ∞. Lines passing through x and having (32) as a slope are called secants of x at x. This conjecture was proved to be true in [START_REF] Kurdyka | Proof of the gradient conjecture of R. Thom[END_REF]. In the convex world, it is well known that solutions to the gradient system converge for general potentials (this is a Féjer monotonicity argument due to Bruck); see also the original approaches by Manselli and Pucci [START_REF] Manselli | Maximum length of steepest descent curves for quasi-convex functions[END_REF] and Daniilidis et al. [START_REF] Daniilidis | Asymptotic behaviour of selfcontracted planar curves and gradient orbits of convex functions[END_REF]. It is then natural to wonder whether this convergence satisfies higher order rigidity properties as in the analytic case. The answer turns out to be negative in general yielding a quite mysterious phase portrait.

- Absence of tangential convergence for convex potentials The construction given in this paragraph is more complex than the previous ones, we start with a technical lemma which will be the basic building block for our counterexample.

Lemma 9. Let S be a convex set with C k boundary interpolating ABCDEF in Figure 7 and let g be the gauge function associated to S. The function g is differentiable outside the origin. Consider any initialization x 0 in [BC] with corresponding trajectory solution and by integration

-v, x(t) ≥ -v, y(t) + -v, x 0 -B = -v, y(t) . (36)
Hence, in the coordinate system (C -B, -v), which is orthogonal, for all t in [0, t], x(t) has larger coordinates than y(t).

The trajectory y(t), of equation t → B -tw is the line going from B to C . From equations [START_REF] Powell | On search directions for minimization algorithms[END_REF]

ẋ(t) = -∇f (x(t))
is such that

x(t) -x x(t) -x
does not have a limit as t → ∞.

The function f has a positive definite Hessian everywhere except at 0.

Proof : We assume without loss of generality that x = O is the origin. Writting x(t) = (r(t), θ(t)) in polar coordinate, we will construct a function f such that each solution to the ODE produces nonconverging trajectories θ(t).

We start with an interpolating set S 0 = ABCDE as in Lemma 9 and let S 1 = A B C D E be its scaled version as described in Figure 7.

Let α be the value of the angle BOC and m = 2π α + 1. We have 2π m < α.

To obtain S 2 , we rotate S 0 by an angle 2π/m, we denote S 0 the resulting set. We rescale S 0 by a factor β in (0, 1) so that βS 0 lies in the interior of S 1 . Call the resulting set S 2 and S 3 is obtained from S 2 exactly the same way as S 1 is obtained from S 0 . We repeat the same process indefinitely to obtain a strictly decreasing sequence of C k sets. Note that for any k in N, S 2km and S 2km+1 are homothetic to S 0 .

We now invoke Corollary 1 (with I = Z and revert the indices) to obtain a C k function f with those prescribed level sets. Using Remark 3 it turns out that the level sets of f between S 0 and S 1 are simple scalings of S 0 . Hence the gradient curves of f and those of the gauge function of S are the same between S 0 and S 1 , up to time reparametrization.

Using Lemma 9 any trajectory crossing [BC] in Figure 7, must also be crossing [CC ] and leave the triangle BOC in finite time. The same statement holds after scaling the level sets and since for all k in N, S 2km and S 2km+1 are homothetic to S 0 , this shows that no solution stays indefinitely in the triangle BOC.

Lemma 9 still holds after rotations and by our construction, for any triangle T obtained by rotating BOC by a multiple of 2π/m, no trajectory stays indefinitely within T . Since 2π/m < α, the union of these triangles U contains O in its interior.

Note first that any gradient curve converges to x. Let us argue by contradiction and assume that there exists a continuous gradient curve t → z(t) distinct from the stationary solution x, such that z(t) -x z(t) -x converges. This exactly means that the angle θ(t) of the curve has a limit in [0, 2π) as t goes to infinity. There is a rotation of BOC by a multiple of 2π/m whose interior intersects the half line given by the direction θ, call this triangle T . The directional convergence entails that there exists t 0 ≥ 0 such that z(t) belongs to T for all t ≥ t 0 . Hence z can not be a gradient curve. To complete the proof, we may add disks of increasing size to the list of sets to obtain a full domain function and invoke Theorem 2 with I = Z.

Newton's flow may not converge

Given a twice differentiable convex function f , we define the open set Ω := {x ∈ R 2 : ∇ 2 f is invertible} and we consider maximal solutions to the differential equation

ẋ(t) = -∇ 2 f (x(t)) -1 ∇f (x(t)), (37)
on Ω. This is the continuous counterpart of Newton's method, it has been studied in [START_REF] Aubin | Differential inclusions: set-valued maps and viability theory[END_REF] and [START_REF] Alvarez | A dynamical system associated with Newton's method for parametric approximations of convex minimization problems[END_REF]. Let x 0 be in Ω, there exists a unique maximal nontrivial interval I containing 0 and a unique solution x to (37) on I with x(0) = x 0 . Equation (37) may be rewritten as

d dt ∇f (x(t)) = -∇f (x(t))
and thus for all t in I, we have ∇f (x(t)) = e -t ∇f (x 0 ).

If we could ensure that I = R and f has oscillating gradients close to its minimum, then [START_REF] Thom | Problèmes rencontrés dans mon parcours mathématique : un bilan[END_REF] entails that the direction of the gradient is constant along the solution, which requires oscillations in space to compensate for gradient oscillations.

Corollary 9 (A bounded Newton's curve that oscillates at infinity). For any k ≥ 2, there exists a C k convex coercive function f : R 2 → R and an initial condition x 0 in R 2 such that the solution to (37) is bounded, defined on R and has at least two distinct accumulation points.

x y -3 -2 -1 1 2 3 4 -3 -2 -1 1 2 3 scale = 3 i = 2 r = 1.2 C n B n D n E n A n
Figure 8: Illustration of the continuous time Newton's dynamics. On the left, the "skeletons" of the sublevel sets in gray and a sketch of the corresponding curve. On the right, the normals to be chosen in order to apply Lemma 6.

The counterexample is sketched in Figure 8, the construction is the same as for Corollary 5 but instead of doing quarter rotations, we use symmetry with respect to the first axis. We can then call for Corollary 1 to construct the function f and equation [START_REF] Thom | Problèmes rencontrés dans mon parcours mathématique : un bilan[END_REF] ensures that the solution interval is unbounded.

Bregman descent (mirror descent) may not converge

The mirror descent algorithm was introduced in [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF] as an efficient method to solve constrained convex problems. In [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF], this method is shown to be equivalent to a projected subgradient method, using non-Euclidean projections. It plays an important role for some categories of constrained optimization problem; see e.g., [START_REF] Bauschke | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF] for recent developments and [START_REF] Dragomir | Optimal complexity and certification of Bregman first-order methods[END_REF] for a surprising example.

Let us recall beforehand some definitions. Given a Legendre function h with domain dom h, define the Bregman distance4 associated to h as D h (u, v) = h(u)-h(v)-∇h(v), uv where u is in dom h and v is in the interior of dom h.

Given a smooth convex function f that we wish to minimize on dom h, we consider the Bregman method

x i+1 = argmin ∇f (x i ), u -x i + λD h (u, x i ) : u ∈ R 2 ,
where x 0 is in int dom h and λ > 0 is a step size. When the above iteration is well defined, e.g. when dom h is bounded, it writes:

x i+1 = ∇h * (∇h(x i ) -λ∇f (x i )) .
In [START_REF] Bauschke | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF] the authors identified a generalized smoothness condition which confers good min-imizing properties to the above method:

Lh -f convex, (39) λ ∈ (0, L). (40)
The corollary below shows that such an algorithm may not converge, even though we assume the cost to satisfy [START_REF] Wright | Coordinate descent algorithms[END_REF], the step to satisfy (40), and the Legendre function to have a compact domain.

Corollary 10 (Bregman or mirror descent may not converge). There exists a Legendre function h : D → R, defined on a closed square D, continuous on D, a vector c in R 2 , and x 0 in R 2 such that the Bregman descent recursion

x i+1 = ∇h * (∇h(x i ) -c) ,
produces a bounded sequence (x i ) i∈N which has at least two distinct accumulation points.

Proof : We fix θ ∈ -π 4 , π 4 , θ = 0, and consider h constructed in Corollary 3 and choose c = (-1, 0). In this case the Bregman descent recursion writes for all i in N, ∇h(x i+1 ) -∇h(x i ) = -c so that we actually have ∇h(x i ) -∇h(x 0 ) = ∇h(x i ) = -ic and thus x i = ∇h * (-ic) = ∇h * (i, 0). By Corollary 3, we have for all i ∈ N that ∇h * (i, 0) proportional to (cos(θ), (-1) i sin(θ)). Since the norm of the gradient of h * cannot vanish at infinitiy (no flat direction) and is bounded, this proves that the sequence (x i ) i∈N has at least two accumulation points which is the desired result.

Central paths of Legendre barriers may not converge

where D is a subset of R 2 and c. Given a Legendre function h on D, we introduce the h central path through

x(r) = argmin c, x + rh(x) : x ∈ R 2 (42)
where r > 0 is meant to tend to 0. Central paths are one of the essential tools behind interior point methods, see e.g., [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF][START_REF] Auslender | Penalty and barrier methods: a unified framework[END_REF] and references therein.

Note that the accumulation points of x(r) as r → 0, have to be in the the solution set of (41). It is even tempting to think that the convergence of the path to some specific minimizer could occur, as it is the case for many barriers, see e.g. [START_REF] Auslender | Penalty and barrier methods: a unified framework[END_REF]. We have however:

Proof : Consider a C ∞ function g 0 : R → [0, 1] such that g 0 = 1 on (-∞, -1), g 0 = 0 on (1, +∞) (for example convoluting the step function with a smooth bump function). Set g(t) = 1 2 (g 0 (t) + 1 -g 0 (-t)) we have that g is C ∞ , g = 1 on (-∞, -1), g = 0 on (1, +∞) and g(t) + g(-t) = 1 for all t. We have where P denotes all partitions of {1, . . . , m}, the product is over subsets of {1, . . . , m} given by the partition π and | • | denotes the number of elements of a set. We rewrite this as follows

∂ m m l=1 ∂x i l g • f (x) = m k=1 π∈P k g (k) (f (x)) B∈π ∂ |B| f m l=1 ∂x i l (x),
where P k denotes all partitions of size k of {1, . . . , m}.

Lemma 13. From [12, Lemma 45] Let h in C 0 (0, r 0 ], R * + be an increasing function. Then there exists a function ψ in C ∞ (R, R + ) such that ψ = 0 on, R -and 0 < ψ(s) ≤ h(s) for any s in (0, r 0 ] and ψ is increasing on R Lemma 14 (High-order smoothing near the solution set). Let D ⊂ R p be a nonempty compact convex set and f : D → R convex, continuous on D and C k on D \ argmin D f . Assume further that argmin D f ⊂ int(D), k ≥ 1, with min D f = 0. Then there exists φ : R → R + , C k , convex and increasing with positive derivative on (0, +∞), such that φ • f is convex and C k on D.

Proof : By a simple translation, we may assume that min D f = 0 and max D f = 1. Any convex function is locally Lipschitz continuous on the interior of its domain so that f is globally Lipschitz continuous on D and its gradient is bounded. Hence, f 2 is C 1 and convex on D. We now proceed by recursion. For any m = 1, . . . , k, we let Q m denote the m-order tensor of partial derivatives of order m. Fix m in {1, . . . , k}. Assume that f is C m throughout D while it is C m+1 on D \ arg min D f . Note that all the derivatives up to order m are bounded. We wish to prove that f is globally C m+1 .

Consider the increasing function

h : (0, 1] → R * + s → s 1 + sup s≤f (x)≤1 Q m+1 (x) ∞
and set ψ as in Lemma 13. Recall that ψ is C ∞ and all its derivative vanish at 0 and ψ ≤ h on (0, 1]. Let φ denote the anti-derivative of ψ such that φ(0) = 0. φ is C ∞ and convex increasing on R and, since its derivatives at 0 vanish as well, one has, for any q in N, φ (q) (z) = o(z). Consider the function φ • f . It is C m on D and it has bounded derivatives up to order m. Furthermore, it is C m+1 on D \ argmin D f . Let ȳ in argmin D f . If ȳ in int(argmin D f ), then f and φ • f have derivatives of all order vanishing at ȳ. Assuming that ȳ in argmin D f \ int(argmin D f ). By the induction assumption and Lemma 12, we have for any indices i 1 , . . . , i m ∈ {1, . . . , p} and any h in R p :

∂ m m l=1 ∂x i l (φ • f )(ȳ + z) - ∂ m m l=1 ∂x i l (φ • f )(ȳ) = ∂ m m l=1 ∂x i l (φ • f )(ȳ + z) = m q=1 π∈Pq φ (q) (f (ȳ + z)) B∈π ∂ |B| f m l=1 ∂x i l (ȳ + z).
All the derivatives of f are of order less or equal to m and thus remain bounded as z → 0. Further more f is Lipschitz continuous on D so that f (ȳ + z) = O( z ) near 0, and, for any q in N, φ (q) (f (ȳ + z)) = o( z ). Hence φ • f has derivative of order m + 1 at ȳ and it is 0. where the inequality follows from the construction of φ. The third step follows using the definition of h and the fact that, for any q ≥ 2, 1. Each partition of {1, . . . , m + 1} of size q contains subsets of size at most m. Thus in the product, the terms ∂ |B| f correspond to bounded derivatives of f by the induction hypothesis.

2. φ (q) (a) = o(a) as a → 0.

The last step stems from the fact that the ratio has asbolute value less than 1. This shows that the derivatives of order m + 1 of φ • f are decreasing to 0 as j → ∞ and φ • f is actually C m+1 and convex on D. The result follows by induction up to m = k and by the fact that a composition of increasing convex functions is increasing and convex.

Figure 1 :

 1 Figure 1: Rough sketches of pathological behavior for curves in the plane; for sequences similar figures would be obtained. Red colors indicate proximity with the solution set.Convergence with infinite length corresponds to counterexample (ii), finite length jiggling corresponds to counterexample (viii) (recall that gradient curves have to be selfcontractant as well, see[START_REF] Daniilidis | Asymptotic behaviour of selfcontracted planar curves and gradient orbits of convex functions[END_REF]), nonconvergent jiggling corresponds to counterexamples (iii), (vi), (vii), (ix) and nonconvergent spiraling corresponds to counterexamples (iv), (v) and somehow (i).

  otherwise stated the norm is denoted by • . Given subsets S, T in R p , and x in R p , we define dist(x, S) := inf { x -y : y ∈ S} , and the Hausdorff distance between S and T , dist(S, T ) = max sup x∈S dist(x, T ), sup x∈T dist(x, S) .

Figure 2 :

 2 Figure2: Illustration of Bernstein's smooth interpolation. We consider at first three points, to which we add four extra points to control derivatives at the junctions. We then build a concave, piecewise linear function and make a Bernstein approximation between the first two original points and the last two original points.

Proof:

  Note that by construction, we have G(λ, θ) = a(λ)c -(θ) + b(λ)c + (θ) for some polynomials a and b which are nonnegative on [λ -, λ + ]. The formulas for the derivatives follow easily from this remark, the form of a and b and Lemma 1. Set, for any λ in [λ -, λ + ], T λ = a(λ)T -+ b(λ)T + . The resulting set T λ is convex and has a positive curvature by Lemma 2, and for λ fixed G(λ, •) is the inverse of the Gauss map of T λ , which constitutes a parametrization by normals of the boundary.

Figure 3 :

 3 Figure3: Arrows designate the prescribed normals. We construct a strictly convex set with smooth boundary entirely contained in the auxiliary (blue) polygon. This set interpolates the normals and the distance to the original (red) polygon can be chosen arbitrarily small. The degree of smoothness of the boundary can be chosen arbitrarily high.

  r -/2 and a + (d) → -r + /2 as d → ∞ so that f d → f and g d → g uniformly on [0, 1]. For any d, f d is concave increasing and g d is concave decreasing and all of them are Lipschitz continuous on [0, 1]

Such a d

  always exists because in both cases, the left hand side converges to 0 and the right hand side converges to a strictly positive term as d tends to ∞. For such a d, we set h : s → min {f d (s), g d (s), }. By construction, h is concave, agrees with f d on 0, m d ⊂ [0, 1/2] and with g d on 1 -m d , 1 ⊂ [1/2, 1]. Using equation (23) with c = 1/d, we deduce that

Figure 4 :

 4 Figure4: Illustration of the approximation result of Lemma 4 with = 0.1, m = 3, t -= 0.7, t + = -2.2, r -= 2 and r + = 0.2. The resulting polynomial is of degree 66. Numerical estimations of the first and second order derivatives at 0 and 1 match the required values up to 3 precision digits. The polynomial is strongly concave, however, this is barely visible because the strong concavity constant is extremely small.

Figure 5 :

 5 Figure 5: Illustration of the alternating minimization (resp. exact line search) example: on the left, the sublevel sets in gray and the corresponding alternating minimization (resp. exact line search) sequence in dashed lines. On the right the interpolating polygons together with their normal vectors as in Lemma 6.

Figure 7 :

 7 Figure 7: A = (-5, 0), B = -5 3 -25 16 , 10 3 + 5 4 , C = -5 2 , 5 , D = (0, 5), E = (5, 0), F = (0, -5). All normals are chosen to be bisectors except w which is parallel to the line (DE). The vector v is orthogonal to the segment [BC]. The point C is obtained by considering the intersection between the line (Bw) (starting from B with direction w), and the segment [OC]. The points A , B , D , E , F are obtained by performing a scaling of A, B, D, E, F of a factor OC OC . The polygon A B C D E F is ABCDEF scaled by a factor OC +OC 2OC .

- 1 3 φ 1 6 . 11 (

 131611 )ds dr.For all r in [-3, 3], we haver (s)ds if -1 ≤ r ≤ 1 g(s)ds dr if -1 ≤ t ≤ 1 6 + 3(t -1) if 1 ≥ tand in particular φ 0 (3) = 12 and φ 0 (3) = 3. Set φ 1 (s) = φ 0 (6s -3)/12.φ 1 (0) = 0 φ 1 (t) = (6t -3) 2 2 -9/2 + 2(3t) /12 = 3t 2 /2 = if t ≤ 1/(1) = 1 φ 1 (1) = 3/2. φ 1 is stricly increasing, let φ : [0, 1] → [0, 1] denote the inverse of φ 1 , we have φ(1) = 1 φ (1) = 2/3 φ(t) = 2t/3 if t ≤ 1/Lemma Interpolation inside a sublevel set). Consider any strictly increasing C k function φ : (0, 2) → R such that φ(1) = 1 and φ (m) (1) = 0, m = 2, . . . k. Then the functionG : (0, 2) × R/2πZ → R 2 (s, θ) → φ(s)n(θ)is diffeomorphism which satisfies for any m = 1 . . . , k and l = 2, . . . , k,∂ m G ∂θ m (1, θ) = n (m) (θ) ∂ m+1 G ∂λ∂θ m (1, θ) = φ (1)n (m) (θ) ∂ l+m G ∂λ l ∂θ m (λ -, θ) = 0.Lemma 12. : Combinatorial Arbogast-Faà di Bruno Formula (from[START_REF] Ma | Higher chain formula proved by combinatorics[END_REF]). Let g : R → R and f : R p → [0, +∞) be C k functions. Then we have for any m ≤ k and any indices i 1 , . . . , i m ∈ {1, . . . , p}. ∂ m m l=1 ∂x i l g • f (x) = π∈P g (|π|) (f (x)) B∈π ∂ |B| f l∈B ∂x i l (x),

  Since argmin D f ⊂ int(D), we may consider any sequence of point (y j ) j∈N in D\argmin D f converging to ȳ. By Lemma 12, we have for any indices i 1 , . . . , i m+1 ∈ {1, . . . , p}, and any j in N,∂ (m+1) m+1 l=1 ∂x i l (φ • f )(y j ) = φ (f (y j )) f (y j )≤f (x)≤1 Q m+1 (x) ∞ + O(f (y j ))= O(f (y j )),

Lemma 15 .

 15 Let p : R + → R + be concave increasing and C 1 with p ≥ c for some c > 0. Assume that there exists A > 0 such that for all x in R + p(x) -xp (x) ≤ A.Then setting a = A/c, we have for all x ≥ a, p(x -a) -xp (x -a) ≤ 0 Proof : For all x ≥ a, we havef (x -a) -(x -a)f (x -a) ≤ A, hence f (x -a) -xf (x -a) ≤ A -af (x -a) ≤ A -ac = 0.

  • , the support function of the polar of P [35, Theorem 1.7.6]. Hence the the convex conjugate of ω is the indicator of the polytope P • [37, Theorem 13.2].

  and[START_REF] Torralba | Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation[END_REF], we may write for all t in [0, t], x(t) = y(t) + α(t)(C -B) + β(t)(-v) where α and β are positive functions. Since y(t) belongs to the line (BC ), this shows that x(t) has to be above this line for all t ≥ 0, t ≤ t and actually, x( t) in BCC . Hence at time t, we have x( t) in[CC ]. This holds true because x( t) is on the boundary of OCB and on the boundary of BCC . Hence either x( t) in [CC ], either x( t) in[BC]. Equation[START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF] ensures that if x( t) in [BC] then x( t) = C which concludes the proof.Corollary 8 (Secants of gradient curves may all fail to converge). There exists a C k strictly convex function on R 2 with a unique minimizer x, such that any nonconstant solution to the gradient flow equation

In the sense of sets inclusion the sequence being indexed on N or Z

See Theorem 2 for the full version.

By structural, we include homotopic deformations by mere summation

It is actually not a proper distance.

Acknowledgements. The authors acknowledge the support of AI Interdisciplinary Institute ANITI funding, through the French "Investing for the Future -PIA3" program under the Grant agreement n • ANR-19-PI3A-0004, Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19-1-7026, FA9550-18-1-0226, and ANR MasDol. J. Bolte acknowledges the support of ANR Chess, grant ANR-17-EURE-0010 and ANR OMS.

Let I = Z or I = N. Let (P N i ) i∈I be a sequence of interpolable polygon-normal pairs. Setting for i in I, P N i = (A j,i ) n i j=1 , (V j,i ) n i j=1

where n j is in N and denoting by T i the polygon A 1,i . . . A n i ,i , we say that the sequence (P N i ) i∈I is strictly increasing if for all i in I, T i ⊂ int(T i+1 ).

Let (P N i ) i∈I be a strictly increasing sequence of interpolable polygon-normal pairs. A sequence ( i ) i∈I in (0, 1) is said to be admissible if 0 ∈ int(T i ) for each i in I and

We have the following corollary of Theorem 2.

Corollary 1 (Smooth convex interpolation of polygon sequences). Let I = Z or I = N. Let (P N i ) i∈I be a strictly increasing sequence of interpolable polygon-normal pairs and ( i ) i∈I be admissible. Set T := int (∪ i∈I T i ) .

Then for any k in N, k ≥ 2 there exists a C k convex function f : T → R, and an increasing sequence

(iv) ∇ 2 f is positive definite outside argmin f . When there is a unique minimizer then ∇ 2 f is positive definite throughout T (this is the case when I = N or when I = Z and ∩ i∈I T i is a singleton).

We add two remarks which will be useful for directional convergence issues and the construction of Legendre functions:

(a) If two consecutive elements of the sequence of interpolable polygon-normal pairs are homothetic with center 0 in the interior of both polytopes, then the restriction of the resulting convex function to this convex ring can be constructed such that all the sublevel sets within this ring are homothetic with the same center.

(b) If further conditions are imposed on the elements of a strictly increasing interpolable polygon-normal pair, then the resulting function can be constructed to be Legendre and globally Lipschitz continuous (that is, its Legendre conjugate has bounded support). This is a consequence of Proposition 2 and will be detailled in the next section.

More on Legendre functions and a pathological function with polyhedral domain

Using intensively polygonal interpolation, we build below a finite continuous Legendre function h on an ∞ square with oscillating "mirror lines": t → ∇h * (∇h(x 0 ) + tc).

Setting s(t) = (1 + t)/(1 -t), we have, for all t ≤ 1/2

, we deduce from the previous remark and (30) above:

Finally using (29) again,

This proves the desired result.

Combining Lemma 7 and Proposition 2, we obtain the following result. Theorem 3. Let (P N i ) i∈N * be a strictly increasing sequence of interpolable polygon-normal pairs. Set for i in N * , P N i = (A j,i

where n i is in N * , denote by T i the polygon A 1,i . . . A n i ,i , and assume that for all i in N * , T i = 3iP where P is a fixed polygon which contains the unit disk in its interior. Then for any k in N, k ≥ 2 and all l ≥ 3, there exists a C k globally Lipschitz continuous Legendre function, h : R 2 → R, and an increasing sequence (λ i ) i∈N , such that for each i in N:

• For any x with h(x) = λ i and ∇h(x) is colinear to V i for each vertex x of T i ,

• h has positive definite Hessian and is globally Lipschitz continuous,

• h * has compact domain and is C k on the interior of its domain.

Corollary 2 (Continuity on the domain).

The function h * constructed in Theorem 3 has compact polygonal domain and is continuous on this domain.

to the equation ẋ(t) = -∇g(x(t)), t ≥ 0, x(0) = x 0 .

Set t = sup x(t)∈OBC t, we have t < +∞ and x( t) in [CC ].

Proof : The fact that g is differentiable comes from the fact that its subgradient is uniquely determined by the normal cone to S which has dimension one because of the smoothness of the boundary of S. Since S is interpolating the polygon, we have g(B) = g(C) = 1. Furthermore, we have for all t, d dt g(x(t)) = -∇g(x(t)) 2 = -1, thence t ≤ 1 -g(C ). By homogeneity, for any x = 0 and s > 0, ∇g(sx) = ∇g(x). For any x in [BC], by convexity

and therefore

By homogeneity of g, ( 33) is true for any x in the triangle OCB (different from 0) and thus in the triangle C CB . Denote by y the solution to the equation ẏ = -∇g(C) y(0) = B, which integrates to y(t) = B -tw for all t. Equation (33) ensures that for any 0 ≤ t ≤ t

Hence, we have for any 0

Furthermore, for all x in [BC], we have

The first term is maximal for x = C and thus the second term is minimal for x = C, we have thus for all x in [BC]

Equation ( 35) holds for all x in OCB different from O by homogeneity. We deduce that for all 0 ≤ t ≤ t, we have

Corollary 11 (A nonconverging central path). There exists a Legendre function h : D → R, defined on a closed square D, continuous on D, a vector c in R 2 , such that the h central path r → x(r) has two distinct accumulation points.

Proof :

The optimality condition which characterizes x(r) for any r > 0 writes,

and the construction is the same as in Corollary 10.

Hessian Riemannian gradient dynamics may not converge

The construction of this paragraph is similar to the two previous paragraphs. Consider a C k (k ≥ 2) Legendre function h : D → R and the continuous time dynamics

where H = ∇ 2 h is the Hessian of h and ∇ H f = H -1 ∇f is the gradient of some differentiable function f in the Riemannian metric induced by H on int D. Such dynamics were considered in [START_REF] Bolte | Barrier operators and associated gradientlike dynamical systems for constrained minimization problems[END_REF][START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF].

We have the following result: