# On the nature of Bregman functions

Edouard Pauwels

► To cite this version:

Edouard Pauwels. On the nature of Bregman functions. 2023. hal-03974132

HAL Id: hal-03974132

https://hal.science/hal-03974132

Preprint submitted on 5 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# On the nature of Bregman functions

Edouard Pauwels

► To cite this version:

Edouard Pauwels. On the nature of Bregman functions. Operations Research Letters, 2024, 57, pp.107183. 10.1016/j.orl.2024.107183. hal-03974132v2

HAL Id: hal-03974132

https://hal.science/hal-03974132v2

Submitted on 4 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the nature of Bregman functions

Edouard Pauwels*

Draft of February 5, 2023

## Abstract

Let $C \subset \mathbb{R}^n$ be convex, compact, with nonempty interior and $h$ be Legendre with domain $C$, continuous on $C$. We prove that $h$ is Bregman if and only if it is strictly convex on $C$ and $C$ is a polytope. This provides insights on sequential convergence of many Bregman divergence based algorithm: abstract compatibility conditions between Bregman and Euclidean topology may equivalently be replaced by explicit conditions on $h$ and $C$. This also emphasizes that a general convergence theory for these methods (beyond polyhedral domains) would require more refinements than Bregman's conditions.

# 1 Introduction

Let $C \subset \mathbb{R}^n$ be convex compact with nonempty interior, $h: C \to \mathbb{R}$ be convex. We assume throughout the article that $h$ is Legendre:

* $h$ is essentially smooth: continuously differentiable on $\text{int}C$, such that $\|\nabla h\|$ goes to $+\infty$ when approaching the boundary of $C$.

* $h$ is strictly convex on $\text{int}C$.

We will also assume throughout the text that $h$ is continuous on $C$. The Bregman divergence associated to $h$ is then for all $y \in C$ and $x \in \text{int}C$,

$$D_h(y, x) = h(y) - h(x) - \langle \nabla h(x), y - x \rangle.$$

## 1.1 Fejérian sequences:

Let $f: C \to \mathbb{R}$ be convex proper lower semi-continuous. Consider the problem

$$\min_{x \in C} f(x) \tag{1}$$

<footnote>*IRIT, CNRS, Université de Toulouse, Toulouse, France. Institut universitaire de France (IUF).</footnote>
# On the nature of Bregman functions

Edouard Pauwels*

Draft of September 3, 2024

## Abstract

Let $C \subset \mathbb{R}^n$ be convex, compact, with nonempty interior and $h$ be Legendre with domain $C$, continuous on $C$. We prove that $h$ is Bregman if and only if it is strictly convex on $C$ and $C$ is a polytope. This provides insights on sequential convergence of many Bregman divergence based algorithm: abstract compatibility conditions between Bregman and Euclidean topology may equivalently be replaced by explicit conditions on $h$ and $C$. This also emphasizes that a general convergence theory for these methods (beyond polyhedral domains) would require more refinements than Bregman's conditions.

## 1 Introduction

Let $C \subset \mathbb{R}^n$ be convex compact with nonempty interior, $h: C \to \mathbb{R}$ be convex. We assume throughout the article that $h$ is Legendre, has domain $C$, and is continuous on $C$:

* $h$ is continuous on $C^1$.

* $h$ is essentially smooth: continuously differentiable on the interior of its domain, $\text{int}C$, such that for all $x \in \text{bd}C$ and $y \in \text{int}C$,

$$ \lim_{t \to 0, t>0} \langle \nabla h(x+t(y-x)), y-x \rangle = -\infty $$

* $h$ is strictly convex on the interior of its domain, $\text{int}C$.

Note that this corresponds to the classical definition in [20, Section 26] for the pair $(\text{int}C, h)$, and contrary to [20], $C$ is closed. This convention is used throughout the text, the notation $C$ denotes a closed set which is the focus of our interest. The Bregman divergence associated to $h$ is then for all $y \in C$ and $x \in \text{int}C$,

$$ D_h(y, x) = h(y) - h(x) - \langle \nabla h(x), y - x \rangle. $$

<footnote>*Toulouse School of Economics, France. Institut universitaire de France (IUF).</footnote>

<footnote n="1">¹The domain of $h$ is $C$ and $h$ is not defined outside $C$. $h$ is assumed to be continuous on $C$ equipped with the subspace topology. Equivalently we could consider $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$, with value $+\infty$ outside $C$, in this case $h_C$, the restriction of $h$ to $C$, is assumed to be continuous. Our arguments are limited to sequences in $C$ so that both points of view are equivalent in this work.</footnote>
and denote by $S \subset C$, the solution set of (1). The following definition is adapted from the Euclidean setting [11].

**Definition 1.** Let $(x_k)_{k \in \mathbb{N}}$ be a sequence in intC, it is called Fejérian, or Fejér, for problem (1) if

* All accumulation points are in S.

* For all $y \in S$, $D_h(y, x_k)$ has a finite limit as $k \to \infty$.

Actually, Definition 1 may be given for a general closed convex set $S \subset C$ (see e.g. [11] which may be directly adapted). We stick to the optimization problem (1) for simplicity since it already covers a wide range of algorithms.

## 1.2 Algorithmic examples

We list below some of the most common algorithms generating Fejérian sequences in convex optimization.

**Mirror descent:** the algorithm is due to Nemirovsky [13]. Assume that $f$ is Lipschitz. Initialize $x_0 \in \text{int}C$ and, given sequence of positive step sizes $(\alpha_k)_{k \in \mathbb{N}}$, iterate

$$x_{k+1} = \nabla h^*(\nabla h(x_k) - \alpha_k v_k), \quad (2)$$

$$v_k \in \partial f(x_k). \quad (3)$$

Assuming $\sum_{k=0}^{+\infty} \alpha_k = +\infty$ and $\sum_{k=0}^{+\infty} \alpha_k^2 < +\infty$ the resulting algorithmic sequence is Fejér. In this case equation (4.22) in [6] ensures that accumulation points are in S and equation (4.21) combined with [Lemma 2, Section 2.2][14] ensures that $D(y, x_k)$ has a limit for all $y \in S$.

**Bregman gradient and NoLips algorithm:** Assume that $f$ is $C^1$ on an open set containing $C$ and $h - \alpha f$ is convex for some $\alpha > 0$. Initialize $x_0 \in \text{int}C$ and iterate

$$x_{k+1} = \nabla h^*(\nabla h(x_k) - \alpha \nabla f(x_k)). \quad (4)$$

In this case, for all $y \in S$, $D_h(y, x_k)$ is non increasing as $k$ grows [4, Lemma 5]. This extends to the NoLips algorithm proposed for composite objectives in [4]. Similarly, the work presented in [1] presents a continuous time variant of Fejér property in the context of Hessian-Riemannian gradient flows.

**Proximal minimization with D-functions:** Assume that $f$ is proper lower-semicontinuous. Initialize $x_0 \in \text{int}C$ and, given sequence of positive step sizes $(\alpha_k)_{k \in \mathbb{N}}$, iterate

$$x_{k+1} = \arg \min_{x \in C} \alpha_k f(x) + D_h(x, x_k). \quad (5)$$

In this case, for all $y \in S$, $D_h(y, x_k)$ is non increasing as $k$ grows [10, Lemma 3.3] and if $\sum_{k=0}^{+\infty} \alpha_k = +\infty$, then the resulting sequence has all its accumulation point in S [10, Theorem 3.4].
## 1.1 Fejérian sequences:

Let $f: C \to \mathbb{R}$ be convex proper lower semi-continuous. Consider the problem

$$ \min_{x \in C} f(x) \qquad (1) $$

and denote by $S \subset C$, the solution set of (1). The following definition is adapted from the Euclidean setting [14], see also the extension to Bregman monotone sequences [5], note that we do not put emphasis on monotonicity, but rather on convergence which is sufficient for our purpose.

**Definition 1.** Let $(x_k)_{k \in \mathbb{N}}$ be a sequence in intC, it is called weak D-Fejér for problem (1) if

* All accumulation points are in S.

* For all $y \in S$, $D_h(y, x_k)$ has a finite limit as $k \to \infty$.

Actually, Definition 1 may be given for a general closed convex set $S \subset C$ (see e.g. [14] which may be directly adapted and [5]). We stick to the optimization problem (1) for simplicity since it already cover a wide range of algorithms.

## 1.2 Algorithmic examples

We list below some of the most common algorithms exhibiting Bregman Fejérian behaviors in convex optimization.

**Mirror descent:** the algorithm is due to Nemirovsky [18]. Assume that $f$ is Lipschitz. Initialize $x_0 \in \text{int}C$ and, given sequence of positive step sizes $(\alpha_k)_{k \in \mathbb{N}}$, iterate

$$ x_{k+1} = \nabla h^*(\nabla h(x_k) - \alpha_k v_k), \qquad (2) $$

$$ v_k \in \partial f(x_k). \qquad (3) $$

Assuming $\sum_{k=0}^{+\infty} \alpha_k = +\infty$ and $\sum_{k=0}^{+\infty} \alpha_k^2 < +\infty$ the resulting algorithmic sequence is weak D-Fejér. In this case equation (4.22) in [7] ensures that accumulation points are in S and equation (4.21) combined with [Lemma 2, Section 2.2][19] ensures that $D(y, x_k)$ has a limit for all $y \in S$.

**Bregman gradient and NoLips algorithm:** Assume that $f$ is $C^1$ on an open set containing $C$ and $h - \alpha f$ is convex for some $\alpha > 0$. Initialize $x_0 \in \text{int}C$ and iterate

$$ x_{k+1} = \nabla h^*(\nabla h(x_k) - \alpha \nabla f(x_k)). \qquad (4) $$

In this case, for all $y \in S$, $D_h(y, x_k)$ is non increasing as $k$ grows [6, Lemma 5]. This extends to the NoLips algorithm proposed for composite objectives in [6]. Similarly, the work presented in [1] describes a continuous time variant of Bregman Fejérian properties in the context of Hessian-Riemannian gradient flows.
**Alternating projection:** Beyond optimization problem (1), in his foundational paper [7], Bregman considers an alternating projection algorithm generating a Fejér sequence to find an element in the intersection of convex sets.

## 1.3 Sequential convergence analysis

The Fejérian property can be used to prove convergence of the sequence similarly as in the Euclidean case, in relation to Opial’s Lemma (see [11] for an overview). This argument is valid provided that the topology encoded by $D_h$ is equivalent to the Euclidean topology. This is always true in the interior of $C$ by strict convexity, but further assumptions need to be made to ensure that this also holds at the boundary. The first condition is

$$ (x_k)_{k \in \mathbb{N}} \subset \text{int} C, y \in C \quad D_h(y, x_k) \underset{k \to \infty}{\to} 0 \quad \Rightarrow \quad x_k \underset{k \to \infty}{\to} y \quad (A) $$

We know from continuity of $h$ on its domain that strict convexity of $h$ on the whole domain $C$ (not only the interior) is sufficient for (A) [12, Lemma 2.16]. If we assume the opposite implication

$$ (x_k)_{k \in \mathbb{N}} \subset \text{int} C, y \in C, \quad x_k \underset{k \to \infty}{\to} y \quad \Rightarrow \quad D_h(y, x_k) \underset{k \to \infty}{\to} 0 \quad (B) $$

then we have the following Féjer argument: assume that (A) and (B) hold true, then any Fejérian sequence $(x_k)_{k \in \mathbb{N}}$ (Definition 1) converges. Indeed, an accumulation point $\bar{x}$ exists by compacity, it must be in $S$ by Definition 1, from property (A), up to a subsequence, $D_h(\bar{x}, x_k) \to 0$, but Definition 1 ensures that $D_h(\bar{x}, x_k)$ converges so its limit must be 0 and property (B) ensures that $x_k \to \bar{x}$.

Note that by continuity of $h$ on its domain, condition (B) is equivalent to $\langle \nabla h(x_k), y - x_k \rangle \to 0$ as $x_k \to y$. Conditions (A) and (B) date back to Bregman [7] and have been extensively considered in the literature [8, 9, 10, 5, 12, 1, 2, 4] in the same abstract form or with adaptation to broader settings that considered here. Given $h$, a Legendre function, continuous on its compact domain $C$, if conditions (A) and (B) are satisfied, then $h$ is called a Bregman function.

## 1.4 Main results

We are interested in the following question: How restrictive are conditions (A) and (B)? In other words, how much does it take for a continuous Legendre function to be Bregman? We provide the following answer.

**Theorem 1.** Let $C \subset \mathbb{R}^n$ be convex, compact, with nonempty interior and $h$ be Legendre with domain $C$, continuous on $C$. Then:

* (A) holds if and only if $h$ is strictly convex on $C$.

* (B) holds if and only if $C$ is a polytope.
**Proximal minimization with D-functions:** Assume that $f$ is proper lower-semicontinuous. Initialize $x_0 \in \text{int}C$ and, given sequence of positive step sizes $(\alpha_k)_{k \in \mathbb{N}}$, iterate

$$x_{k+1} = \arg \min_{x \in C} \alpha_k f(x) + D_h(x, x_k). \qquad (5)$$

In this case, for all $y \in S$, $D_h(y, x_k)$ is non increasing as $k$ grows [13, Lemma 3.3] and if $\sum_{k=0}^{+\infty} \alpha_k = +\infty$, then the resulting sequence has all its accumulation point in $S$ [13, Theorem 3.4] so that the resulting sequence is weak D-Fejér.

**Alternating projection:** Beyond optimization problem (1), in his foundational paper [8], Bregman considers an alternating projection algorithm generating a weak D-Fejér sequence to find an element in the intersection of convex sets.

## 1.3 Sequential convergence analysis

The weak D-Fejér property can be used to prove convergence of the sequence similarly as in the Euclidean case, in relation to Opial’s Lemma (see [14] for an overview). This argument is valid provided that the topology encoded by $D_h$ is equivalent to the Euclidean topology. This is always true in the interior of $C$ by strict convexity, but further assumptions need to be made to ensure that this also holds at the boundary. The first condition is

$$(x_k)_{k \in \mathbb{N}} \subset \text{int}C, y \in C, \quad D_h(y, x_k) \underset{k \to \infty}{\to} 0 \quad \Rightarrow \quad x_k \underset{k \to \infty}{\to} y \qquad (A)$$

We know from continuity of $h$ on its domain that strict convexity of $h$ on the whole domain $C$ (not only the interior) is sufficient for (A) [17, Lemma 2.16]. If we assume the opposite implication

$$(x_k)_{k \in \mathbb{N}} \subset \text{int}C, y \in C, \quad x_k \underset{k \to \infty}{\to} y \quad \Rightarrow \quad D_h(y, x_k) \underset{k \to \infty}{\to} 0 \qquad (B)$$

then we have the following Féjer argument: assume that (A) and (B) hold true, then any weak D-Fejér sequence $(x_k)_{k \in \mathbb{N}}$ (Definition 1) converges. Indeed, an accumulation point $\bar{x}$ exists by compacity, it must be in $S$ by Definition 1, from property (A), up to a subsequence, $D_h(\bar{x}, x_k) \to 0$, but Definition 1 ensures that $D_h(\bar{x}, x_k)$ converges so its limit must be 0 and property (B) ensures that $x_k \to \bar{x}$.

Note that by continuity of $h$ on its domain, condition (B) is equivalent to $\langle \nabla h(x_k), y - x_k \rangle \to 0$ as $x_k \to y$. Conditions (A) and (B) date back to Bregman [8] and have been extensively considered in the literature [11, 12, 15, 13, 4, 17, 5, 1, 2, 6, 21] in the same abstract form or with adaptation to broader settings than considered here. Given $h$, a Legendre function, continuous on its compact domain $C$, if conditions (A) and (B) are satisfied, then $h$ is called a Bregman function.

## 1.4 Main results

We are interested in the following question: How restrictive are conditions (A) and (B)? In other words, how much does it take for a continuous Legendre function to be Bregman? We provide the following answer.
Theorem 1, provides an explicit sufficient condition on h ensuring convergence of all algorithms described in Section 1.2. Indeed if C is a polytope and h is strictly convex on C, then any Fej´erian sequence converges. Furthermore, Theorem 1 illustrates the fact that existing Fej´er arguments for sequential convergence are only valid for polytopic domains, and convergence analysis for more general domains will require different arguments.

Theorem 1 can be obtained by combining Proposition 1, Proposition 2, Lemma 5 and Lemma 6. We make crucial use of [15, Lemma 1]. Let us mention that Theorem 1 and all our presentation is limited to compact C, but most proof arguments relate to possibly unbounded closed C so that the intermediate results convey information of independent interest for this more general case. The link between strict convexity and (A) is natural and one implication is due to Kiwiel [12]. The connection between (B) and the polytopic nature of C is the most interesting part of our results and we will start with it.

2 Condition (B)

Let us first illustrate failure of (B) and its relation with curvature with a simple example, which was described independently in [3, Remark 2].

2.1 Intuition: incompatibility with curvature

Set h: x ↦→ − √ 1 − ‖ x ‖ 2 on C ⊂ R $^{2}$, the unit Euclidean ball in the plane. We have ∇ h : x ↦→ x 1 √ 1 − ‖ x ‖ 2 . Considering polar coordinates in the plane, x = ( r cos( θ ) , r sin( θ )), with e$_{1}$ the first basis vector (1 , 0), we have

$$
h(e_1) - h(x) - \langle \nabla h(x), e_1 - x \rangle = -\sqrt{1-r^2} + \frac{r(r - \cos(\theta))}{\sqrt{1-r^2}}
$$

Choosing θ ( r ) = arccos ( r − √ 1 − r $^{2}$) for r ≥ 0, as r → 1, x ( r ) = ( r cos( θ ( r )), r sin( θ ( r ))) goes to e$_{1}$ and D$_{h}$ ( e$_{1}$, x ) → 1.

Actually, the curve r → x ( r ) converges to e$_{1}$ with a vertical tangent as shown in Figure 1. This illustrates the main mechanism of failure of condition B. Because of curvature, chords all meet the interior of C so that the directional derivative of h along chords explodes at their endpoints. Here the curve remains on a chord segment in a region of negative directional derivative along the chord.

From this illustration, one intuition is that the boundary of the compact domain C of a Bregman function should not have too much curvature. More precisely it should not have curvature accumulating anywhere. This intuition is actually correct, the key mechanism is that around extreme points, there is a lot of curvature which allows to generate behavior similar to the circle example above, see Figure 1. This cannot happen too densely other- wise this contradicts (B), and as a result, the extreme points of C have to be isolated, this is expressed in Proposition 1. On the other hand, polyhedra have a very strong structure which will enforce (B) this is Proposition 2.
**Theorem 1.** Let $C \subset \mathbb{R}^n$ be convex, compact, with nonempty interior and $h$ be Legendre with domain $C$, continuous on $C$. Then:

* (A) holds if and only if $h$ is strictly convex on $C$.

* (B) holds if and only if $C$ is a polytope.

Theorem 1, provides an explicit sufficient condition on $h$ ensuring convergence of all algorithms described in Section 1.2. Indeed if $C$ is a polytope and $h$ is strictly convex on $C$, then any weak $D$-Fejér sequence converges. Furthermore, Theorem 1 illustrates the fact that existing Fejérian arguments for sequential convergence are only valid for polytopic domains, and convergence analysis for more general domains will require different arguments.

Theorem 1 can be obtained by combining Proposition 1, Proposition 2, Lemma 5 and Lemma 6. We make crucial use of [22, Lemma 1]. Let us mention that Theorem 1 and all our presentation is limited to compact $C$, but most proof arguments relate to possibly unbounded closed $C$ so that the intermediate results convey information of independent interest for this more general case. The link between strict convexity and (A) is essentially known, one implication is due to Kiwiel [17] and the reverse implication is connected to total convexity, see [9, Proposition 1.2.6]. We provide a self contained proof based on a result of [22] for completeness. The connection between (B) and the polytopic nature of $C$ is the most interesting part of our results and we will start with it. We discuss extensions of our main result in Section 4.

# 2 Condition (B)

Let us first illustrate failure of (B) and its relation with curvature with a simple example, which was described independently in [3, Example 4.2].

## 2.1 Intuition: incompatibility with curvature

Set $h: x \mapsto -\sqrt{1 - \|x\|^2}$ on $C \subset \mathbb{R}^2$, the unit Euclidean ball in the plane. We have $\nabla h: x \mapsto x \frac{1}{\sqrt{1 - \|x\|^2}}$. Considering polar coordinates in the plane, $x = (r \cos(\theta), r \sin(\theta))$, with $e_1$ the first basis vector $(1, 0)$, we have

$$h(e_1) - h(x) - \langle \nabla h(x), e_1 - x \rangle = -\sqrt{1 - r^2} + \frac{r(r - \cos(\theta))}{\sqrt{1 - r^2}}$$

Choosing $\theta(r) = \arccos(r - \sqrt{1 - r^2})$ for $r \ge 0$, as $r \to 1$, $x(r) = (r \cos(\theta(r)), r \sin(\theta(r)))$ goes to $e_1$ and $D_h(e_1, x) \to 1$.

Actually, the curve $r \to x(r)$ converges to $e_1$ with a vertical tangent as shown in Figure 1. This illustrates the main mechanism of failure of condition B. Because of curvature, chords all meet the interior of $C$ so that the directional derivative of $h$ along chords explodes
<figure><img src="image_1.png" /><figcaption>Figure 1: Left: Illustration of the tangential phenomenon, closedness to the boundary and to the opposite extremity of the chord. Right: in general extreme points constitute a region of high curvature and it is possible to find neighboring points in a similar configuration. This cannot happen too much under condition (B) and in particular extreme points should not accumulate anywhere.</figcaption></figure>

## 2.2 First implication

In this section we prove the following

**Proposition 1.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior and $h$ be Legendre on $C$, continuous on $C$ and satisfy (B). Then the extreme points of $C$ are locally finite. In particular if $C$ is bounded it is a polytope.

We start with two lemmas

**Lemma 1.** Under the assumptions of Proposition 1, let $x \in \text{bd}C$ and $y \in C$ be such that $\frac{x+y}{2} \in \text{int}C$. Then $D_h(y, (1-\lambda)x + \lambda y) \to +\infty$ as $\lambda \to 0$.

**Proof:** Note that in this case the open segment $(x, y)$ is contained in the interior of $C$. For any $\lambda \in (0, 1)$, setting $z_\lambda = (1-\lambda)x + \lambda y$, we have

$$D_h(y, (1-\lambda)x + \lambda y) = h(y) - h(z_\lambda) - (1-\lambda) \langle \nabla h(z_\lambda), y-x \rangle.$$

Letting $\lambda \to 0$, consider any accumulation point, $d \in \mathbb{R}^n$ of $\frac{\nabla h(z_\lambda)}{\|\nabla h(z_\lambda)\|}$. We have $d \in N_C(x)$ by [1, Lemma 4.2] and $y-x \in \text{int}T_C(x)$ (since $\frac{x+y}{2} \in \text{int}C$), so that $\langle d, y-x \rangle < 0$. Therefore, up to a subsequence as $\lambda \to 0$,

$$D_h(y, (1-\lambda)x + \lambda y) = h(y) - h(z_\lambda) - (1-\lambda) \|\nabla h(z_\lambda)\| \left\langle \frac{\nabla h(z_\lambda)}{\|\nabla h(z_\lambda)\|}, y-x \right\rangle, \\ \to +\infty$$

since $h(z_\lambda) \to h(x)$, $\|\nabla h(z_\lambda)\| \to \infty$ and $\langle d, y-x \rangle < 0$. The result follows because $d$ was arbitrary. This concludes the proof. $\square$
<figure><img src="image_2.png" /><figcaption>Figure 1: Left: Illustration of the tangential phenomenon, closedness to the boundary and to the opposite extremity of the chord. Right: in general extreme points constitute a region of high curvature and it is possible to find neighboring points in a similar configuration. This cannot happen too much under condition (B) and in particular extreme points should not accumulate anywhere.</figcaption></figure>

at their endpoints. Here the curve remains on a chord segment in a region of negative directional derivative along the chord.

From this illustration, one intuition is that the boundary of the compact domain $C$ of a Bregman function should not have too much curvature. More precisely it should not have curvature accumulating anywhere. This intuition is actually correct, the key mechanism is that around extreme points, there is a lot of curvature which allows to generate behavior similar to the circle example above, see Figure 1. This cannot happen too densely otherwise this contradicts (B), and as a result, the extreme points of $C$ have to be isolated, this is expressed in Proposition 1. On the other hand, polyhedra have a very strong structure which will enforce (B) this is Proposition 2.

## 2.2 First implication

In this section we prove the following

**Proposition 1.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior and $h$ be Legendre, with domain $C$, continuous on $C$ and satisfy (B). Then the extreme points of $C$ are locally finite. In particular if $C$ is bounded it is a polytope.

We start with two lemmas

**Lemma 1.** Under the assumptions of Proposition 1, let $x \in \text{bd}C$ and $y \in C$ be such that $\frac{x+y}{2} \in \text{int}C$. Then $D_h(y, (1-\lambda)x + \lambda y) \to +\infty$ as $\lambda \to 0$.

**Proof:** Note that in this case the open segment $(x, y)$ is contained in the interior of $C$.
**Lemma 2.** Under the hypotheses of Proposition 1, let $a \in \text{bdC}$ be an extreme points and $y \in C$, different from $a$. Then for any $\epsilon, K > 0$, there exists $c \in \text{intC}$ such that

$$ \begin{gathered} \|c - a\| \le \epsilon \\ D_h(y, c) \ge K. \end{gathered} $$

**Proof:** First if $[a, y] \cap \text{intC} \ne \emptyset$, then we are in the conditions of Lemma 1, which provides the desired result (with $x = a$). We may therefore assume that $[a, y] \subset \text{bdC}$.

**Claim 1.** There exists $\epsilon_1 > 0$ such that for any $b \in \text{intC} \cap B_{\epsilon_1}(a)$, the line from $y$ to $b$ crosses the boundary of $C$ at $x$ such that $\|x - a\| \le \epsilon$.

**Proof of the claim.** We may assume that $\epsilon_1 < \|y - a\|$, so that, since $a \ne y$, the points $y$ and $b$ define a unique line for any $b \in B_{\epsilon_1}(a)$. We also impose that $\epsilon_1 < \epsilon$. Assume toward a contradiction that for all such $\epsilon_1 > 0$, there is $b \in \text{intC} \cap B_{\epsilon_1}(a)$, such that the line from $y$ to $b$ either does not cross the boundary of $C$ or it crosses it at a point at distance greater than $\epsilon$. In both cases, since $b \in B_{\epsilon}(a)$ (as we assumed $\epsilon_1 < \epsilon$), the line from $y$ to $b$ exits $B_{\epsilon}(a)$ at a point $x \in C$. In this case, using a vanishing sequence of values for $\epsilon_1$, we can produce a sequence $(b_k)_{k \in \mathbb{N}}$ converging to $a$ such that each segment $[y, b_k]$ can be extended up to $x_k \in C$ where $b_k \in [x_k, y]$ and $\|x_k - a\| = \epsilon$. Passing to the limit, up to subsequences $b_k \to a$ and $x_k \to x \in C$, we have $a \in [x, y]$ where $a \ne y$ and $a \ne x$ which contradicts the fact that $a$ is an extreme point of $C$. This proves the claim.

We may choose $\epsilon_1 \le \epsilon$, now consider any point $b \in \text{intC} \cap B_{\epsilon_1}(a)$, $b$ belongs to a segment of the form $[x, y]$ for some $x \in \text{bdC} \cap B_{\epsilon}(a)$. Note that $[b, x] \subset B_{\epsilon}(a)$ so that we can apply Lemma 1 and obtain $c \in [b, x]$ with $D_h(y, c)$ arbitrarily large. This proves the desired result.

□

**Proof of Proposition 1:** Assume that the set of extreme points of $C$ it is not locally finite. This means that we can find a bounded sequence $(z_k)_{k \in \mathbb{N}}$ of pairwise distinct extreme points. This sequence has a converging subsequence, let $y$ be its limit. Since the sequence has pairwise distinct elements, there is at most one $k \in \mathbb{N}$ such that $y = z_k$ and we may remove it from the sequence. In other words $z_k \to y \in C$ as $k \to \infty$ and $z_k \ne y$ for all $k \in \mathbb{N}$. We will show that in this case, condition B is violated.

Fix $k \in \mathbb{N}$, using Lemma 2 with $a = z_k$, we may find $x_k \in \text{intC}$ such that $\|x_k - z_k\| \le \|z_k - y\|$ and $D_h(y, x_k) \ge k$. Now as $k \to \infty$, we have $x_k \to y$ and $D_h(y, x_k) \to +\infty$ which contradicts condition B. This concludes the proof. □

## 2.3 Reverse implication

**Proposition 2.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior and locally polyhedral (represented locally by finitely many affine inequalities, for example a polytope), let $h$ be Legendre on $C$, continuous on $C$, then (B) holds.
For any $\lambda \in (0, 1)$, we have

$$ 
\begin{aligned}
D_h(y, (1-\lambda)x + \lambda y) - h(y) + h((1-\lambda)x + \lambda y) \\
&= -(1-\lambda) \langle \nabla h(x + \lambda(y-x)), y-x \rangle \\
&= -(1-\lambda) \left\langle \nabla h \left( x + 2\lambda \left( \frac{y+x}{2} - x \right) \right), 2 \left( \frac{y+x}{2} - x \right) \right\rangle.
\end{aligned}
$$

Letting $\lambda \to 0$, the right hand side goes to $+\infty$ by essential smoothness and the result follows because $h((1-\lambda)x+\lambda y)$ remains bounded by continuity of $h$ on $C$. This concludes the proof. $\square$

**Remark 1.** Lemma 1 holds true if one relaxes continuity of $h$ by boundedness on $C$. This is discussed in Section 4

**Lemma 2.** Under the hypotheses of Proposition 1, let $a \in \text{bd}C$ be an extreme points and $y \in C$, different from $a$. Then for any $\epsilon, K > 0$, there exists $c \in \text{int}C$ such that

$$ 
\begin{gathered}
\|c - a\| \le \epsilon \\
D_h(y, c) \ge K.
\end{gathered}
$$

**Proof:** First if $[a, y] \cap \text{int}C \ne \emptyset$, then we are in the conditions of Lemma 1, which provides the desired result (with $x = a$). We may therefore assume that $[a, y] \subset \text{bd}C$.

**Claim 1.** There exists $\epsilon_1 > 0$ such that for any $b \in \text{int}C \cap B_{\epsilon_1}(a)$, the line from $y$ to $b$ crosses the boundary of $C$ at $x$ such that $\|x - a\| \le \epsilon$.

**Proof of the claim.** We may assume that $\epsilon_1 < \|y - a\|$, so that, since $a \ne y$, the points $y$ and $b$ define a unique line for any $b \in B_{\epsilon_1}(a)$. We also impose that $\epsilon_1 < \epsilon$. Assume toward a contradiction that for all such $\epsilon_1 > 0$, there is $b \in \text{int}C \cap B_{\epsilon_1}(a)$, such that the line from $y$ to $b$ either does not cross the boundary of $C$ or it crosses it at a point at distance greater than $\epsilon$. In both cases, since $b \in B_{\epsilon}(a)$ (as we assumed $\epsilon_1 < \epsilon$), the line from $y$ to $b$ exits $B_{\epsilon}(a)$ at a point $x \in C$. In this case, using a vanishing sequence of values for $\epsilon_1$, we can produce a sequence $(b_k)_{k \in \mathbb{N}}$ converging to $a$ such that each segment $[y, b_k]$ can be extended up to $x_k \in C$ where $b_k \in [x_k, y]$ and $\|x_k - a\| = \epsilon$. Passing to the limit, up to subsequences $b_k \to a$ and $x_k \to x \in C$, we have $a \in [x, y]$ where $a \ne y$ and $a \ne x$ which contradicts the fact that $a$ is an extreme point of $C$. This proves the claim.

We may choose $\epsilon_1 \le \epsilon$, now consider any point $b \in \text{int}C \cap B_{\epsilon_1}(a)$, $b$ belongs to a segment of the form $[x, y]$ for some $x \in \text{bd}C \cap B_{\epsilon}(a)$. Note that $[b, x] \subset B_{\epsilon}(a)$ so that we can apply Lemma 1 and obtain $c \in [b, x]$ with $D_h(y, c)$ arbitrarily large. This proves the desired result. $\square$

**Proof of Proposition 1:** Assume that the set of extreme points of $C$ is not locally finite. This means that we can find a bounded sequence $(z_k)_{k \in \mathbb{N}}$ of pairwise distinct extreme points. This sequence has a converging subsequence, let $y$ be its limit. Since the
The result follows from the following ([15, Lemma 1]).

**Lemma 3** (Tseng and Bertsekas). Let $h: \mathbb{R}^p \to \mathbb{R} \cup +\infty$, be lower semicontinuous and continuous on its domain $C$. Then

* For any $y \in C$, there exists a nondegenerate closed ball centered at $y$ such that $C \cap B$ is closed.

* For any $y \in C$, and $d$ such that $y+d \in C$ and sequences $x_k \to y$ and $d_k \to d$ such that $x_k + d_k \in C$ for all $k$, we have

$$ \limsup_{k \to \infty} h'(x_k, d_k) \le h'(y, d). $$

**Lemma 4.** Let $C$ be a polyhedra and $y \in C$. Then there exists $\epsilon > 0$ such that for any $x \in C \cap B_{\epsilon}(y)$, $2x - y \in C$.

**Proof:** Let $a_1, \dots, a_m \in \mathbb{R}^n$ and $b_1, \dots, b_m \in \mathbb{R}$ such that $C = \{x | \langle a_i, x \rangle \le b_i, i = 1, \dots, m\}$. Fix $y \in C$, and $I \subset \{1, \dots, m\}$ the set of active indices, such that $\langle a_i, y \rangle = b_i$ if and only if $i \in I$. By continuity of linear functions, there exists $\epsilon > 0$ such that for all $d$ with $\|d\| \le 2\epsilon$, and all $i \notin I$, $\langle a_i, y+d \rangle < b_i$. Now for any $x \in C$ such that $\|x - y\| \le \epsilon$, we have

$$ \langle a_i, 2x - y \rangle = \langle a_i, y + 2(x - y) \rangle < b_i \qquad \forall i \notin I, $$

$$ \langle a_i, 2x - y \rangle = 2 \langle a_i, x \rangle - \langle a_i, y \rangle \le 2b_i - \langle a_i, y \rangle = 2b_i - b_i = b_i \qquad \forall i \in I, $$

which shows that $2x - y \in C$ and concludes the proof. $\square$

**Proof of Proposition 2:** By continuity of $h$ on $C$, it suffices to show that

$$ \lim_{x \to y, x \in \text{int} C} \langle \nabla h(x), y - x \rangle = 0 $$

for all $y \in C$.

Fix $y \in C$ and consider $(x_k)_{k \in \mathbb{N}}$, converging to $y$. $C$ can be locally represented by a polyhedra and therefore Lemma 4 can be applied to $y$ and $C$. Let $\epsilon > 0$ be given by Lemma 4 and assume without loss of generality that $\|y - x_k\| \le \epsilon$ for all $k \in \mathbb{N}$. We have for all $k \in \mathbb{N}$, $x_k + (y - x_k) = y \in C$ so that applying Lemma 4 with $d_k = y - x_k$, which converges to 0

$$ \limsup_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \le h'(y, 0) = 0. $$

Furthermore, by Lemma 4, for all $k \in \mathbb{N}$, we have $2x_k - y = x_k + (x_k - y) \in C$. Therefore, one may apply Lemma 4 with $d_k = x_k - y$, which also converges to 0 to obtain

$$ \limsup_{k \to \infty} \langle \nabla h(x_k), x_k - y \rangle \le h'(y, 0) = 0. $$

which is equivalent to

$$ \liminf_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \ge 0. $$

We have shown that

$$ 0 \le \liminf_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \le \limsup_{k \to \infty} \langle \nabla h(x_k), x_k - y \rangle \le 0, $$

so that the limit is 0. This concludes the proof. $\square$
sequence has pairwise distinct elements, there is at most one $k \in \mathbb{N}$ such that $y = z_k$ and we may remove it from the sequence. In other words $z_k \to y \in C$ as $k \to \infty$ and $z_k \neq y$ for all $k \in \mathbb{N}$. We will show that in this case, condition B is violated.

Fix $k \in \mathbb{N}$, using Lemma 2 with $a = z_k$, we may find $x_k \in \text{int}C$ such that $\|x_k - z_k\| \le \|z_k - y\|$ and $D_h(y, x_k) \ge k$. Now as $k \to \infty$, we have $x_k \to y$ and $D_h(y, x_k) \to +\infty$ which contradicts condition B. This concludes the proof. $\square$

## 2.3 Reverse implication

**Proposition 2.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior and locally polyhedral (represented locally by finitely many affine inequalities, for example a polytope), let $h$ be Legendre, with domain $C$, continuous on $C$, then (B) holds.

The result follows from the following ([22, Lemma 1]).

**Lemma 3** (Tseng and Bertsekas). Let $h: \mathbb{R}^p \to \mathbb{R} \cup +\infty$, be lower semicontinuous and continuous on its domain $\text{dom } h$. Then

* For any $y \in \text{dom } h$, there exists a nondegenerate closed ball centered at $y$ such that $\text{dom } h \cap B$ is closed.

* For any $y \in \text{dom } h$, and $d$ such that $y + d \in \text{dom } h$ and sequences $x_k \to y$ and $d_k \to d$ such that $x_k + d_k \in \text{dom } h$ for all $k$, we have

$$ \limsup_{k \to \infty} h'(x_k, d_k) \le h'(y, d). $$

where $h'(y, d) = \lim_{t \to 0, t>0} \frac{h(y+td)-h(y)}{t}$ for any $y \in \text{dom } h$ and $d \in \mathbb{R}^p$.

**Lemma 4.** Let $C$ be a polyhedron and $y \in C$. Then there exists $\epsilon > 0$ such that for any $x \in C \cap B_\epsilon(y)$, $2x - y \in C$.

**Proof:** Let $a_1, \dots, a_m \in \mathbb{R}^n$ and $b_1, \dots, b_m \in \mathbb{R}$ such that $C = \{x | \langle a_i, x \rangle \le b_i, \forall i = 1, \dots, m\}$. Fix $y \in C$, and $I \subset \{1, \dots, m\}$ the set of active indices, such that $\langle a_i, y \rangle = b_i$ if and only if $i \in I$. By continuity of linear functions, there exists $\epsilon > 0$ such that for all $d$ with $\|d\| \le 2\epsilon$, and all $i \notin I$, $\langle a_i, y + d \rangle < b_i$. Now for any $x \in C$ such that $\|x - y\| \le \epsilon$, we have

$$ \langle a_i, 2x - y \rangle = \langle a_i, y + 2(x - y) \rangle < b_i \qquad \forall i \notin I, $$

$$ \langle a_i, 2x - y \rangle = 2 \langle a_i, x \rangle - \langle a_i, y \rangle \le 2b_i - \langle a_i, y \rangle = 2b_i - b_i = b_i \qquad \forall i \in I, $$

which shows that $2x - y \in C$ and concludes the proof. $\square$

**Proof of Proposition 2:** By continuity of $h$ on $C$, it suffices to show that

$$ \lim_{x \to y, x \in \text{int}C} \langle \nabla h(x), y - x \rangle = 0 $$
### 3 Condition (A)

One implication was given by [12, Lemma 2.16].

**Lemma 5 (Kiwiel).** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior, let $h$ be Legendre on $C$, continuous on $C$ and strictly convex on $C$, then (A) holds.

The reverse implication follows from Lemma 3 again.

**Lemma 6.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior, let $h$ be Legendre on $C$, continuous on $C$ such that (A) holds, then $h$ is strictly convex on $C$.

**Proof:** Toward a contradiction, assume that $h$ is not strictly convex. This means that there exists $x, y \in C$ such that

$$h\left(\frac{x+y}{2}\right) = \frac{h(x)+h(y)}{2}, \qquad (6)$$

which implies that $h$ is affine along the segment $[x, y]$, that is

$$h\left(\frac{x+y}{2} + t(x-y)\right) = h\left(x\left(t+\frac{1}{2}\right) + y\left(\frac{1}{2}-t\right)\right) = \frac{h(x)+h(y)}{2} + t(h(x)-h(y))$$

for all $t \in [-1/2, 1/2]$. In particular, setting $z = \frac{x+y}{2}$, we have

$$h'(z, x-z) = -h'(z, y-z) = \frac{h(x) - h(y)}{2}. \qquad (7)$$

Now consider $z_0 \in \text{int}C$ and the sequence $(z_k)_{k \in \mathbb{N}}$ in intC, such that for all $k \in \mathbb{N}$, $k \ge 1$, $z_k = \frac{1}{k}z_0 + \frac{k-1}{k}z \in C$.

We set for all $k \in \mathbb{N}$, $k \ge 1$, $y_k = \frac{2}{k+1}z_0 + \frac{k-1}{k+1}y \in C$. We have for all $k \ge 1$,

$$z_k - x = \frac{1}{k}z_0 + \frac{k-1}{2k}y + \left(\frac{k-1}{2k} - \frac{2k}{2k}\right)x = \frac{2}{2k}z_0 + \frac{k-1}{2k}y - \frac{k+1}{2k}x$$

$$y_k - x = \frac{2}{k+1}z_0 + \frac{k-1}{k+1}y - \frac{k+1}{k+1}x = (z_k - x) \frac{2k}{k+1}$$

$$y_k - z_k = y_k - x + x - z_k = (z_k - x) \left( \frac{2k}{k+1} - 1 \right) = \frac{k-1}{k+1}(z_k - x).$$

Using Lemma 3, we have

$$\begin{aligned} \limsup_{k \to \infty} \langle \nabla h(z_k), y_k - z_k \rangle &= \limsup_{k \to \infty} \frac{k-1}{k+1} \langle \nabla h(z_k), z_k - x \rangle \\ &= -\liminf_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle \\ &\le h'(z, y - z) = -h'(z, x - z), \end{aligned}$$
for all $y \in C$.

Fix $y \in C$ and consider $(x_k)_{k \in \mathbb{N}}$, converging to $y$. $C$ can be locally represented by a polyhedron and therefore Lemma 4 can be applied to $y$ and $C$. Let $\epsilon > 0$ be given by Lemma 4 and assume without loss of generality that $\|y - x_k\| \le \epsilon$ for all $k \in \mathbb{N}$. We have for all $k \in \mathbb{N}$, $x_k + (y - x_k) = y \in C$ so that applying Lemma 4 with $d_k = y - x_k$, which converges to 0

$$ \limsup_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \le h'(y, 0) = 0. $$

Furthermore, by Lemma 4, for all $k \in \mathbb{N}$, we have $2x_k - y = x_k + (x_k - y) \in C$. Therefore, one may apply Lemma 4 with $d_k = x_k - y$, which also converges to 0 to obtain

$$ \limsup_{k \to \infty} \langle \nabla h(x_k), x_k - y \rangle \le h'(y, 0) = 0. $$

which is equivalent to

$$ \liminf_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \ge 0. $$

We have shown that

$$ 0 \le \liminf_{k \to \infty} \langle \nabla h(x_k), y - x_k \rangle \le \limsup_{k \to \infty} \langle \nabla h(x_k), x_k - y \rangle \le 0, $$

so that the limit is 0. This concludes the proof. $\square$

### 3 Condition (A)

One implication follows from [17, Lemma 2.16].

**Lemma 5 (Kiwiel).** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior, let $h$ be Legendre, with domain $C$, continuous on $C$ and strictly convex on $C$, then (A) holds.

The reverse implication follows from the study of total convexity in [9, Proposition 1.2.6]. We provide a self contained proof based on Lemma 3 for completeness.

**Lemma 6.** Let $C \subset \mathbb{R}^n$ be convex closed with non-empty interior, let $h$ be Legendre, with domain $C$, continuous on $C$ such that (A) holds, then $h$ is strictly convex on $C$.

**Proof:** Toward a contradiction, assume that $h$ is not strictly convex. This means that there exists $x, y \in C$ such that $x \ne y$ and

$$ h\left(\frac{x+y}{2}\right) = \frac{h(x)+h(y)}{2}, \qquad (6) $$

which implies that $h$ is affine along the segment $[x, y]$, that is

$$ h\left(\frac{x+y}{2} + t(x-y)\right) = h\left(x\left(t+\frac{1}{2}\right) + y\left(\frac{1}{2}-t\right)\right) = \frac{h(x)+h(y)}{2} + t(h(x)-h(y)) $$
so that

$$ \limsup_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle \le h'(z, x - z) \le \liminf_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle $$

and $\langle \nabla h(z_k), x - z_k \rangle \to h'(z, x - z)$ as $k \to \infty$. We deduce by continuity of $h$ using (6) and (7)

$$ \lim_{k \to \infty} h(x) - h(z_k) - \langle \nabla h(z_k), x - z_k \rangle = h(x) - \frac{h(x) + h(y)}{2} - \frac{h(x) - h(y)}{2} = 0 $$

So we have that $z_k \to z \neq x$ but $D_h(x, z_k) \to 0$ which shows that condition (A) does not hold. This proves the result by contraposition. □

## Acknowledgements

The author would like to thank Jérôme Bolte for his continuous support and fruitful interactions. This work supported by the AI Interdisciplinary Institute ANITI, ANR-19-PI3A-0004, Air Force Office of Scientific Research, Air Force Material Command, USAF, FA9550-19-1-7026 FA8655-22-1-7012, and ANR MaSDOL 19-CE23-0017-01.

## References

[1] Alvarez, F., Bolte, J. and Brahic, O. (2004). Hessian Riemannian gradient flows in convex programming. SIAM journal on control and optimization, 43(2), 477–501.

[2] Auslender, A., Teboulle, M. (2006). Interior gradient and proximal methods for convex and conic optimization. SIAM Journal on Optimization, 16(3), 697-725.

[3] Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P. (2022). On the rate of convergence of Bregman proximal methods in constrained variational inequalities. arXiv preprint arXiv:2211.08043.

[4] Bauschke, H. H., Bolte, J. and Teboulle, M. (2016). A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2), 330–348.

[5] Bauschke, H. H., and Borwein, J. M. (1997). Legendre functions and the method of random Bregman projections. Journal of convex analysis, 4(1), 27-67.

[6] Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected sub-gradient methods for convex optimization. Operations Research Letters, 31(3), 167–175.

[7] Bregman, L. M. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3), 200-217.
for all $t \in [-1/2, 1/2]$. In particular, setting $z = \frac{x+y}{2}$, we have

$$h'(z, x - z) = -h'(z, y - z) = \frac{h(x) - h(y)}{2}. \qquad (7)$$

Now consider $z_0 \in \text{int}C$ and the sequence $(z_k)_{k \in \mathbb{N}}$ in $\text{int}C$, such that for all $k \in \mathbb{N}$, $k \ge 1$, $z_k = \frac{1}{k}z_0 + \frac{k-1}{k}z \in C$.

We set for all $k \in \mathbb{N}$, $k \ge 1$, $y_k = \frac{2}{k+1}z_0 + \frac{k-1}{k+1}y \in C$. We have for all $k \ge 1$,

$$z_k - x = \frac{1}{k}z_0 + \frac{k-1}{2k}y + \left(\frac{k-1}{2k} - \frac{2k}{2k}\right)x = \frac{2}{2k}z_0 + \frac{k-1}{2k}y - \frac{k+1}{2k}x$$

$$y_k - x = \frac{2}{k+1}z_0 + \frac{k-1}{k+1}y - \frac{k+1}{k+1}x = (z_k - x)\frac{2k}{k+1}$$

$$y_k - z_k = y_k - x + x - z_k = (z_k - x) \left( \frac{2k}{k+1} - 1 \right) = \frac{k-1}{k+1}(z_k - x).$$

Using Lemma 3, we have

$$\begin{aligned} \limsup_{k \to \infty} \langle \nabla h(z_k), y_k - z_k \rangle &= \limsup_{k \to \infty} \frac{k-1}{k+1} \langle \nabla h(z_k), z_k - x \rangle \\ &= -\liminf_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle \\ &\le h'(z, y - z) = -h'(z, x - z), \end{aligned}$$

so that

$$\limsup_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle \le h'(z, x - z) \le \liminf_{k \to \infty} \langle \nabla h(z_k), x - z_k \rangle$$

and $\langle \nabla h(z_k), x - z_k \rangle \to h'(z, x - z)$ as $k \to \infty$. We deduce by continuity of $h$ using (6) and (7)

$$\lim_{k \to \infty} h(x) - h(z_k) - \langle \nabla h(z_k), x - z_k \rangle = h(x) - \frac{h(x) + h(y)}{2} - \frac{h(x) - h(y)}{2} = 0$$

So we have that $z_k \to z \ne x$ but $D_h(x, z_k) \to 0$ which shows that condition (A) does not hold. This proves the result by contraposition. $\square$

# 4 Extensions

The proposed analysis is centered on a compact domain $C$ with $h$ continuous on its domain and dom $h = C$. This allows to convey the main message in a simple form. Theorem 1 has several direct extensions and calls for a broader discussion.

## 4.1 Unbounded domain

We notice that the arguments of Proposition 1 and Proposition 2 do not require boundedness of $C$. Let us also point out that Theorem 1 has the following consequence.
[8] Censor, Y., Lent, A. (1981). An iterative row-action method for interval convex programming. Journal of Optimization theory and Applications, 34(3), 321-353.

[9] Censor, Y., Zenios, S. A. (1992). Proximal minimization algorithm withd- functions. Journal of Optimization Theory and Applications, 73(3), 451-464.

[10] Chen, G., Teboulle, M. (1993). Convergence analysis of a proximal-like mini- mization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3), 538-543.

[11] Combettes, P. L. (2001). Fejér-monotonicity in convex optimization. Encyclo- pedia of optimization, 2, 106-114.

[12] Kiwiel, K. C. (1997). Free-steering relaxation methods for problems with strictly convex costs and linear constraints. Mathematics of Operations Research, 22(2), 326-349.

[13] A. S. Nemirovsky and D. B. Yudin (1983). Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York.

[14] Polyak, B. T. (1987). Introduction to optimization. Optimization software Inc., Publications Division, New York, 1, 32.

[15] Tseng, P., Bertsekas, D. P. (1991). Relaxation methods for problems with strictly convex costs and linear constraints. Mathematics of operations research, 16(3), 462-481.
**Corollary 1.** Let $C \subset \mathbb{R}^n$ be convex, closed, with nonempty interior and $h$ be Legendre, with domain $C$, continuous on $C$. Then:

• (B) holds if and only if $C$ is locally polyhedral: for any polytope $P$, $P \cap C$ is a polytope.

**Proof:** If $P$ is contained in a strict affine subspace $A$ of $\mathbb{R}^n$, then the restriction of $h$ to $A$ satisfy our hypothesis on $C \cap A$. Therefore it suffices to consider the full dimensional setting. Any polytope $P$ with non-empty interior admits a Legendre function $h_P$, with domain $P$, continuous on $P^2$. Then $h+h_P$ is Legendre with domain $C \cap P$, continuous on $C \cap P$. According to Theorem 1, Condition (B) holds true for $h+h_P$ if and only if $C \cap P$ is a polytope. Using the fact that $D_{h+h_P} = D_h + D_{h_P}$ we also notice that Condition (B) holds true for $h$ and $C$ if and only if Condition (B) holds true for $h+h_P$ and $C \cap P$, for all possible polytopes $P$ (with the construction of $h_P$ as above). This concludes the proof. $\square$

## 4.2 Bounded lower-semicontinuous $h$

A careful inspection of the proof of Proposition 1 allows to conclude that the same result holds if $h$ is bounded on $C$, not necessarily continuous. Indeed, the conclusion of Lemma 1 holds in this case (see Remark 1) and continuity of $h$ is not used further in the proof. This has the following consequence which shows that continuity of $h$ is essentially a requirement for condition (B).

**Corollary 2.** Let $C \subset \mathbb{R}^n$ be convex compact with non-empty interior and $h$ be convex, lower-semicontinuous, Legendre, with domain $C$, bounded on $C$ and satisfy (B). Then $h$ is continuous on $C$.

**Proof:** We deduce from Proposition 1, Remark 1 and the preceding discussion that $C$ is a polytope. Using the main result of [16], $h$ is therefore upper semi-continuous on $C$ and hence continuous since it was also assumed to be lower-semicontinuous. $\square$

The connection between Condition (A) and strict convexity of $h$ could also be discussed in light of potential relaxation of the continuity of $h$, we conjecture that continuity of $h$ is not necessary for the equivalence.

## 4.3 Unbounded $h$

If dom $h \neq C$, then $D_h(y, x)$ is only defined for $x \in \text{int}C$ and $y \in \text{dom} h$. Conditions (A) and (B) have no meaning if $y \notin \text{dom} h$ and it is unclear how to generalize them. It is also difficult to describe the behavior of the function $h$ outside of its domain, for example what would be the correct strict convexity notion on the boundary of dom $h$. These represent

<footnote n="2">²For example using the well known Boltzman-Shannon entropy applied to the polyhedral representation of $P$. Set $\phi(t) = t \log(t)$ for $t > 0$ and $\phi(0) = 0$, then if $P = \{x | \langle a_i, x \rangle \le b_i, \forall i = 1, \dots, m\}$, then $h_P: x \mapsto \sum_{i=1}^m \phi(b_i - \langle a_i, x \rangle)$ satisfies the desired property</footnote>
important issues since it could be the case that the target solution set $\mathcal{S}$ in (1) is not contained in dom $h$. Typical results in this setting relate to complexity estimates [6], but in general, the sequential convergence of Bregman type algorithms probably represents a hard problem. One would expect positive results under specific structural assumptions such as barier functions constructed based on polyhedral representation (e.g. the well known logarithmic barrier), in the spirit of the convergence of the central path for interior point methods.

## Acknowledgements

The author would like to thank Jérôme Bolte for his continuous support and fruitful interactions and Jalal Fadili for pointing out the connection between sequential consistency and total convexity. The author also thank the anonymous referee for very relevant comments and suggestions on the first version of this work. The author thanks TSE-P. This work supported by the AI Interdisciplinary Institute ANITI, ANR-19-PI3A-0004, Air Force Office of Scientific Research, Air Force Material Command, USAF, FA8655-22-1-7012, ANR Regulia, and ANR Chess.

## References

[1] Alvarez, F., Bolte, J. and Brahic, O. (2004). Hessian Riemannian gradient flows in convex programming. SIAM Journal on Control and Optimization, 43(2), 477–501.

[2] Auslender, A., Teboulle, M. (2006). Interior gradient and proximal methods for convex and conic optimization. SIAM Journal on Optimization, 16(3), 697-725.

[3] Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P. (2024). The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness. SIAM Journal on Optimization, 34(3), 2440-2471.

[4] Bauschke, H. H., and Borwein, J. M. (1997). Legendre functions and the method of random Bregman projections. Journal of Convex Analysis, 4(1), 27-67.

[5] Bauschke, H. H., Borwein, J. M., Combettes, P. L. (2003). Bregman monotone optimization algorithms. SIAM Journal on Control and Optimization, 42(2), 596-636.

[6] Bauschke, H. H., Bolte, J. and Teboulle, M. (2016). A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2), 330–348.

[7] Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected sub-gradient methods for convex optimization. Operations Research Letters, 31(3), 167–175.
[8] Bregman, L. M. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3), 200-217.

[9] Butnariu, D., Iusem, A. N. (2000). Totally convex functions for fixed points computation and infinite dimensional optimization (Vol. 40). Springer Science & Business Media.

[10] Butnariu, D., Iusem, A. N., Zalinescu, C. (2003). On uniform convexity, total convexity and convergence of the proximal point and outer bregman projection algorithm in banach spaces. Journal of Convex Analysis, 10(1), 35-62.

[11] Censor, Y., Lent, A. (1981). An iterative row-action method for interval convex programming. Journal of Optimization Theory and Applications, 34(3), 321-353.

[12] Censor, Y., Zenios, S. A. (1992). Proximal minimization algorithm withd-functions. Journal of Optimization Theory and Applications, 73(3), 451-464.

[13] Chen, G., Teboulle, M. (1993). Convergence analysis of a proximal-like mini-mization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3), 538-543.

[14] Combettes, P. L. (2001). Fejér-monotonicity in convex optimization. Encyclopedia of optimization, 2, 106-114.

[15] Eckstein, J. (1993). Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Mathematics of Operations Research, 18(1), 202-226.

[16] Gale, D., Klee, V. and Rockafellar, R. (1968). Convex functions on convex polytopes. Proceedings of the American Mathematical Society, 19(4), 867-873.

[17] Kiwiel, K. C. (1997). Free-steering relaxation methods for problems with strictly convex costs and linear constraints. Mathematics of Operations Research, 22(2), 326-349.

[18] A. S. Nemirovsky and D. B. Yudin (1983). Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York.

[19] Polyak, B. T. (1987). Introduction to optimization. Optimization Software Inc., Publications Division, New York, 1, 32.

[20] Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.

[21] Sorin, S. (2023). Continuous time learning algorithms in optimization and game theory. Dynamic Games and Applications, 13(1), 3-24.

[22] Tseng, P., Bertsekas, D. P. (1991). Relaxation methods for problems with strictly convex costs and linear constraints. Mathematics of Operations Research, 16(3), 462-481.