Hessian Riemannian gradient flows in convex programming

Introduction

The aim of this paper is to study the existence, global convergence and geometric properties of gradient flows with respect to a specific class of Hessian Riemannian metrics on convex sets. Our work is indeed deeply related to the constrained minimization problem

where $(H\mbox{-}SD)$ stands for $H$-steepest descent. We focus on those metrics that are induced by the Hessian $H=\nabla^{2}h$ of a Legendre type convex function $h$ defined on $C$ (cf. Def. 3.1).

The use of Riemannian methods in optimization has increased recently: in relation with Karmarkar algorithm and linear programming see Karmarkar , Bayer-Lagarias ; for continuous-time models of proximal type algorithms and related topics see Iusem-Svaiter-Da Cruz , Bolte-Teboulle . For a systematic dynamical system approach to constrained optimization based on double bracket flows, see Brockett , the monograph of Helmke-Moore and the references therein. On the other hand, the structure of $(H\mbox{-}SD)$ is also at the heart of some important problems in applied mathematics. For connections with population dynamics and game theory see Hofbauer-Sygmund , Akin , Attouch-Teboulle . We will see that $(H\mbox{-}SD)$ can be reformulated as the differential inclusion $\frac{d}{dt}\nabla h(x(t))+\nabla f(x(t))\in{\rm Im}\>A^{T},\>x(t)\in{{\cal F}},$ which is formally similar to some evolution problems in infinite dimensional spaces arising in thermodynamical systems, see for instance Kenmochi-Pawlow and references therein.

Motivated by the previous result and with the aim of solving $(P)$, we are then naturally led to consider Hessian Riemannian metrics that cannot be smoothly extended out of ${{\cal F}}$. Such a requirement is fulfilled by the Hessian of a Legendre (convex) function $h$, whose definition is recalled in section 3. We give then a differential inclusion reformulation of $(H\mbox{-}SD)$, which permits to show that in the case of a linear objective function $f$, the flow of $-\nabla_{{}_{H}}f_{|_{{{\cal F}}}}$ stands at the crossroad of many optimization methods. In fact, following , we prove that viscosity methods and Bregman proximal algorithms produce their paths or iterates in the orbit of $(H\mbox{-}SD)$. The $D$-function of $h$ plays an essential role for this. In section 4.4 it is given a systematic method to construct Legendre functions based on barrier functions for convex inequality problems, which is illustrated with some examples; relations to other works are discussed.

Section 4 deals with global existence and convergence properties. After having given a non trivial well-posedness result (cf. Theorem 4.1), we prove in section 4.2 that $f(x(t))\rightarrow\inf_{\overline{{{\cal F}}}}f$ as $t\rightarrow+\infty$ whenever $f$ is convex. A natural problem that arises is the trajectory convergence to a critical point. Since one expects the limit to be a (local) solution to $(P)$, which may belong to the boundary of $C$, the notion of critical point must be understood in the sense of the optimality condition for a local minimizer $a$ of $f$ over $\overline{{{\cal F}}}$:

where $N_{\overline{{{\cal F}}}}(a)$ is the normal cone to $\overline{{{\cal F}}}$ at $a$, and $\nabla f$ is the Euclidean gradient of $f$. This involves an asymptotic singular behavior that is rather unusual in the classical theory of dynamical systems, where the critical points are typically supposed to be in the manifold. In section 4.3 we assume that the Legendre type function $h$ is a Bregman function with zone $C$ and prove that under a quasi-convexity assumption on $f$, the trajectory converges to some point $a$ satisfying $({\cal O})$. When $f$ is convex, the preceding result amounts to the convergence of $x(t)$ toward a global minimizer of $f$ over $\overline{{{\cal F}}}$. We also give a variational characterization of the limit and establish an abstract result on the rate of convergence under uniqueness of the solution. We consider in section 4.5 the case of linear programming, for which asymptotic convergence as well as a variational characterization are proved without the Bregman-type condition. Within this framework, we also give some estimates on the convergence rate that are valid for the specific Legendre functions commonly used in practice. In section 4.6, we consider the interesting case of positivity and equality constraints, introducing a dual trajectory $\lambda(t)$ that, under some appropriate conditions, converges to a solution to the dual problem of $(P)$ whenever $f$ is convex, even if primal convergence is not ensured.

Finally, inspired by the seminal work , we define in section 5 a change of coordinates called Legendre transform coordinates, which permits to show that the orbits of $(H\mbox{-}SD)$ may be seen as straight lines in a positive cone. This leads to additional geometric interpretations of the flow of $-\nabla_{{}_{H}}f_{|_{{{\cal F}}}}$. On the one hand, the orbits are geodesics with respect to an appropriate metric and, on the other hand, they may be seen as $\dot{q}$-trajectories of some Lagrangian, with consequences in terms of integrable Hamiltonians.

Preliminaries

If $f$ is convex then this condition is also sufficient for $a\in\overline{{{\cal F}}}$ to be in $S(P)$.

2 Riemannian gradient flows on the relative interior of the feasible set

endows $C$ with a ${\cal C}^{0}$ Riemannian structure. The corresponding Riemannian gradient vector field of the objective function $f$ restricted to $C$, which we denote by $\nabla_{{}_{H}}f_{|_{C}}$, is given by

Next, take $N={{\cal F}}=C\cap{\cal A}$, which is a smooth submanifold of $C$ with $T_{x}{{\cal F}}\simeq{\cal A}_{0}$ for each $x\in{{\cal F}}$. Definition (5) induces a metric on ${{\cal F}}$ for which the gradient of the restriction $f_{|_{{\cal F}}}$ is denoted by $\nabla_{{}_{H}}f_{|_{{\cal F}}}$. Conditions $(g_{1})$ and $(g_{2})$ imply that for all $x\in{{\cal F}}$

and we conclude that for all $x\in{{\cal F}}$

Given $x\in{{\cal F}}$, the vector $-\nabla_{{}_{H}}f_{|_{{\cal F}}}(x)$ can be interpreted as that direction in ${\cal A}_{0}$ such that $f$ decreases the most steeply at $x$ with respect to the metric $(\cdot,\cdot)_{x}^{H}$. The steepest descent method for the (local) minimization of $f$ on the Riemannian manifold ${{\cal F}},(\cdot,\cdot)^{H}_{x}$ consists in finding the solution trajectory $x(t)$ of the vector field $-\nabla_{{}_{H}}f_{|_{{\cal F}}}$ with initial condition $x^{0}\in{{\cal F}}$:

Legendre gradient flows in constrained optimization

This section is intended to motivate the particular class of Riemannian metrics that is studied in this paper in view of the asymptotic convergence of the solution to (10).

Suppose that the objective function $f$ is convex. For simplicity, we also assume that $A=0$ so that ${{\cal F}}=C$. In the framework of convex minimization, the set of minimizers of $f$ over $\overline{C}$, denoted by $\mbox{\rm Argmin}\>_{\overline{C}}\>f$, is characterized in variational terms as follows:

Setting $q_{a}(x)=\frac{1}{2}|x-a|^{2}$ for all $a\in\mbox{\rm Argmin}\>_{\overline{C}}$, one observes that $\nabla q_{a}(x)=x-a$ and thus, by (11), $q_{a}$ is a Liapounov functional for $-\nabla f$. This key property allows one to establish the asymptotic convergence as $t\to+\infty$ of the corresponding steepest descent trajectories; see for more details in a very general non-smooth setting. To use the same kind of arguments in a non Euclidean context, observe that by (6) together with the continuity of $\nabla f$, the following variational Riemannian characterization holds

we obtain $\nabla_{H}D_{h}(y,\cdot)(x)=x-y.$

To finish the proof, remark that taking $\varphi_{y}=D_{h}(y,\cdot)$ with $D_{h}$ being defined by (13), we obtain $\nabla\varphi_{y}(x)=\nabla^{2}h(x)(x-y)$, and therefore $\nabla_{H}\varphi_{y}(x)=x-y$ in virtue of (6). ∎

(a) In the theory of Bregman proximal methods for convex optimization, the distance-like function $D_{h}$ defined by (13) is called the $D$-function of $h$. Theorem 3.1 is a new and surprising motivation for the introduction of $D_{h}$ in relation with variational inequality problems. (b) For a geometrical approach to Hessian Riemannian structures the reader is referred to the recent work of Duistermaat .

2 Legendre type functions and the (H​-​S​D)𝐻-𝑆𝐷(H\mbox{-}SD) dynamical system

Here and subsequently, we take $H=\nabla^{2}h$ with $h$ satisfying $(H_{0})$. The Hessian mapping $C\ni x\mapsto H(x)$ endows $C$ with the (locally Lipschitz continuous) Riemannian metric

The corresponding steepest descent method in the manifold ${{\cal F}},(\cdot,\cdot)^{H}_{x}$, which we refer to as $(H\mbox{-}SD)$ for short, is then the following continuous dynamical system

with $H=\nabla^{2}h$ and where $-\infty\leq T_{m}<0<T_{M}\leq+\infty$ define the interval corresponding to the unique maximal solution of $(H\mbox{-}SD)$. Given an initial condition $x^{0}\in{{\cal F}}$, we shall say that $(H\hbox{-}SD)$ is well-posed when its maximal solution satisfies $T_{M}=+\infty$. In section 4.1 we will give some sufficient conditions ensuring the well-posedness of $(H\mbox{-}SD)$.

3 Differential inclusion formulation of (H​-​S​D)𝐻-𝑆𝐷(H\mbox{-}SD) and some consequences

It is easily seen that the solution $x(t)$ of $(H\hbox{-}SD)$ satisfies:

Assume that $x$ is a solution of (17), and let $I^{\prime}$ be the subset of $(T_{m},T_{M})$ on which $t\mapsto(x(t),\nabla h(x(t))$ is derivable. We may assume that $x(t)\in{{\cal F}}$ and $\frac{d}{dt}\nabla h(x(t))+\nabla f(x(t))\in{\cal A}_{0}^{\perp}$, $\forall t\in I^{\prime}$. Since $x$ is absolutely continuous, $\dot{x}(t)+H(x(t))^{-1}\nabla f((x(t))\in H(x(t))^{-1}{\cal A}_{0}^{\perp}$ and $\dot{x}(t)\in{\cal A}_{0}$, $\forall t\in I^{\prime}$. But the orthogonal complement of ${\cal A}_{0}$ with respect to the inner product $\langle H(x)\cdot,\cdot\rangle$ is exactly $H(x)^{-1}{\cal A}_{0}^{\perp}$ when $x\in{{\cal F}}$. It follows that $\dot{x}+P_{x}H(x)^{-1}\nabla f(x)=0$ on $I^{\prime}$. This implies that $x$ is the ${\cal C}^{1}$ solution of $(H\hbox{-}SD)$. ∎

Suppose that $f$ is convex. On account of Proposition 3.1, $(H\hbox{-}SD)$ can be interpreted as a continuous-time model for a well-known class of iterative minimization algorithms. In fact, an implicit discretization of (17) yields the following iterative scheme: $\nabla h(x^{k+1})-\nabla h(x^{k})+\mu_{k}\nabla f(x^{k+1})\in{\rm Im}\>A^{T},\;Ax^{k+1}=b,$ where $\mu_{k}>0$ is a step-size parameter and $x^{0}\in{{\cal F}}$. This is the optimality condition for

The above algorithm is accordingly called the Bregman proximal minimization method; for an insight of its importance in optimization see for instance .

which corresponds to the so-called viscosity method relative to $g(x)=D_{h}(x,x^{0})$; see and Corollary 4.1. Remark now that for a linear objective function, (18) and (20) are essentially the same: the sequence generated by the former belongs to the optimal path defined by the latter. Indeed, setting $t_{0}=0$ and $t_{k+1}=t_{k}+\mu_{k}$ for all $k\geq 0$ ($\mu_{0}=0$) and integrating (17) over $[t_{k},t_{k+1}]$, we obtain that $x(t_{k+1})$ satisfies the optimality condition for (18). The following result summarizes the previous discussion.

Assume that $f$ is linear and that the corresponding $(H\mbox{-}SD)$ dynamical system is well-posed. Then, the viscosity optimal path $\widetilde{x}(\varepsilon)$ relative to $g(x)=D_{h}(x,x^{0})$ and the sequence $(x^{k})$ generated by (18) exist and are unique, with in addition $\widetilde{x}(\varepsilon)=x(1/\varepsilon)$, $\forall\varepsilon>0$, and $x^{k}=x(\sum^{k-1}_{l=0}\mu_{l})$, $\forall\ k\geq 1$, where $x(t)$ is the solution of $(H\mbox{-}SD)$.

In order to ensure asymptotic convergence for proximal-type algorithms, it is usually required that the step-size parameters satisfy $\sum\mu_{k}=+\infty$ . By Proposition 3.2, this is necessary for the convergence of (18) in the sense that when $(H\mbox{-}SD)$ is well-posed, if $x^{k}$ converges to some $x^{*}\in S(P)$ then either $x^{0}=x^{*}$ or $\sum\mu_{k}=+\infty$.

Global existence, asymptotic analysis and examples

Notice that $(WP_{1})$ is weaker than the classical assumption imposing $f$ to have bounded lower level sets in the $H$ metric sense. Next, let $D_{h}$ be the $D$-function of $h$ that is defined by (19) and consider the following condition:

When $\overline{{{\cal F}}}$ is unbounded $(WP_{1})$ and $(WP_{2})$ involve some a priori properties on $f$. This is actually not necessary for the well-posedness of $(H\mbox{-}SD)$. Consider:

This property is satisfied by relevant Legendre type functions; take for instance (33).

Assume that (16) and $(H_{0})$ hold and additionally that either $(WP_{1})$, $(WP_{2})$ or $(WP_{3})$ is satisfied. If $\inf_{{}_{{{\cal F}}}}f>-\infty$ then the dynamical system $(H$-$SD)$ is well-posed. Consequently, the mapping $t\mapsto f(x(t))$ is nonincreasing and convergent as $t\rightarrow+\infty$.

When no confusion may occur, we drop the dependence on the time variable $t$. By definition,

We have that $T_{M}>0$. The definition (8) of $P_{x}$ implies that for all $y\in{\cal A}_{0}$, $(H(x)^{-1}\nabla f(x)+\dot{x},y+\dot{x})_{x}^{H}=0$ on $[0,T_{M})$ and therefore

By (3)(ii), $f(x(t))$ is convergent as $t\to T_{M}$. Moreover

Suppose that $T_{M}<+\infty$. To obtain a contradiction, we begin by proving that $x$ is bounded. If $(WP_{1})$ holds then $x$ is bounded because $f(x(t))$ is non-increasing so that $x(t)\in\{y\in\overline{{{\cal F}}}\>|f(y)\leq f(x^{0})\}$, $\forall t\in[0,T_{M})$. Assume now that $f$ and $h$ comply with $(WP_{2})$, and let $a\in\overline{{{\cal F}}}$. For each $t\in[0,T_{M})$ take $y=x(t)-a$ in (21) to obtain $\langle\nabla f(x)+\frac{d}{dt}\nabla h(x),x-a+\dot{x}\rangle=0.$ By (22), this gives $\langle\frac{d}{dt}\nabla h(x),x-a\rangle+\langle\nabla f(x),x-a\rangle=0$, which we rewrite as

Now, let $a\in\overline{F}$ be a minimizer of $f$ on $\overline{{{\cal F}}}$. From the quasi-convexity property of $f$, it follows that $\forall t\in[0,T_{M})$, $\langle\nabla f(x(t)),x(t)-a\rangle\geq 0$. Therefore, $D_{h}(a,x(t))$ is non-increasing and $(WP_{2})$(ii) implies that $x$ is bounded. Suppose that $(WP_{3})$ holds and fix $t\in[0,T_{M})$, we have $|x(t)-x^{0}|\leq\int_{0}^{t}|\dot{x}(s)|ds\leq\int_{0}^{t}||\sqrt{H(x(s))^{-1}}|||\sqrt{H(x(s))}\>\dot{x}(s)|ds\leq(\int_{0}^{t}||H(x(s))^{-1}||ds)^{1/2}(\int_{0}^{t}\langle H(x(s))\dot{x}(s),\dot{x}(s)\rangle ds)^{1/2}$. The latter follows from the Cauchy-Schwartz inequality together with the fact that $\|H(x)\|^{2}$ is the biggest eigenvalue of $H(x)$. Thus $|x(t)-x^{0}|\leq 1/2[\int_{0}^{t}||H(x(s))^{-1}||ds+\int_{0}^{t}\langle H(x(s))\dot{x}(s),\dot{x}(r)\rangle ds].$ Combining $(WP_{3})$ and (23), Gronwall’s lemma yields the boundedness of $x$.

. By convexity of $h$, $\langle\nabla h(x^{j})-\nabla h(y),x^{j}-y\rangle\geq 0$ for all $y\in C$. Dividing by $|\nabla h(x^{j})|$ and letting $j\rightarrow+\infty$, we get $\langle\nu,y-x^{*}\rangle\leq 0$ for all $y\in C$, which holds also for $y\in\overline{C}$. Hence, $\nu\in N_{\overline{C}}(x^{*})$. ∎

Therefore, $\nu\in N_{\overline{C}}(x^{*})$. Let $\nu_{0}=\Pi_{{\cal A}_{0}}\nu$ be the Euclidean orthogonal projection of $\nu$ onto ${\cal A}_{0}$, and take $y=\nu_{0}$ in (21). Using (22), integration gives

By $(H_{0})$ and the boundedness property of $x$, the right-hand side of (25) is bounded under the assumption $T_{M}<+\infty$. Hence, to draw a contradiction from (25) it suffices to prove $\langle\nabla h(x(t_{j})),\nu_{0}\rangle\rightarrow+\infty$. Since $\langle\nabla h(x(t_{j}))/|\nabla h(x(t_{j}))|,\nu_{0}\rangle\rightarrow|\nu_{0}|^{2}$, the proof of the result is complete if we check that $\nu_{0}\neq 0$. This is a direct consequence of the following

This completes the proof of the theorem. ∎

2 Value convergence for a convex objective function

As a first result concerning the asymptotic behavior of $(H\mbox{-}SD)$, we have the following:

If $(H\mbox{-}SD)$ is well-posed and $f$ is convex then $\forall a\in{{\cal F}},\;\forall t>0,\;f(x(t))\leq f(a)+\frac{1}{t}D_{h}(a,x^{0})$, where $D_{h}$ is defined by (19), hence $\lim\limits_{t\to+\infty}f(x(t))=\inf_{\overline{{{\cal F}}}}f.$

We begin by noticing that $f(x(t))$ converges as $t\to+\infty$ (see Theorem 4.1). Fix $a\in{{\cal F}}$. By (24), we have that the solution $x(t)$ of $(H$-$SD)$ satisfies $\frac{d}{dt}D_{h}(a,x(t))+\langle\nabla f(x(t)),x(t)-a\rangle=0,\>\forall t\geq 0.$ The convex inequality$f(x)+\langle\nabla f(x),x-a\rangle\leq f(a)$ yields $D_{h}(a,x(t))+\int_{0}^{t}[f(x(s))-f(a)]ds\leq D_{h}(a,x^{0}).$ Using that $D_{h}\geq 0$ and since $f(x(t))$ is non-increasing, we get the estimate. Letting $t\to+\infty$, it follows that $\lim_{t\to+\infty}f(x(t))\leq f(a).$ Since $a\in{{\cal F}}$ was arbitrary chosen, the proof is complete. ∎

3 Bregman metrics and trajectory convergence

In this section we establish the convergence of $x(t)$ under some additional properties on the $D$-function of $h$. Let us begin with a definition.

Observe that this notion slightly weakens the usual definition of Bregman function that was proposed by Censor and Lent in ; see also . Actually, a Bregman function in the sense of Definition 4.1 belongs to the class of $B$-functions introduced by Kiwiel (see [31, Definition 2.4]). Recall the following important asymptotic separation property:

[31, Lemma 2.16] If $h$ is a Bregman function with zone $C$ then $\forall y\in\overline{C}$, $\forall(y^{j})\subset C$ such that $D_{h}(y,y^{j})\to 0$, we have $y^{j}\to y$.

Suppose that $(H_{0})$ holds with $h$ being a Bregman function with zone $C$. If $f$ is quasi-convex satisfying (16) and $S(P)\neq\emptyset$ then $(H$-$SD)$ is well-posed and its solution $x(t)$ converges as $t\to+\infty$ to some $x^{*}\in\overline{{{\cal F}}}$ with $-\nabla f(x^{*})\in N_{\overline{C}}(x^{*})+{\cal A}_{0}^{\perp}.$ If in addition $f$ is convex then $x(t)$ converges to a solution of $(P)$.

Notice first that $(WP_{2})$ is satisfied. By Theorem 4.1, $(H$-$SD)$ is well-posed, $x(t)$ is bounded and for each $a\in S(P)$, $D_{h}(a,x(t))$ is non-increasing and hence convergent Set $f_{\infty}=\lim_{t\to+\infty}f(x(t))$ and define $L=\{y\in\overline{{{\cal F}}}\;|\;f(y)\leq f_{\infty}\}$. The set $L$ is nonempty and closed. Since $f$ is supposed to be quasi-convex, $L$ is convex, and similar arguments as in the proof of Theorem 4.1 under $(WP_{2})$ show that $D_{h}(a,x(t))$ is convergent for all $a\in L$. Let $x^{*}\in L$ denote a cluster point of $x(t)$ and take $t_{j}\to+\infty$ such that $x(t_{j})\to x^{*}$. Then, by (iii) in Definition 4.1, $\lim_{t}D_{h}(x^{*},x(t))=\lim_{j}D_{h}(x^{*},x(t_{j}))=0.$ Therefore, $x(t)\to x^{*}$ thanks to Lemma 4.3. Let us prove that $x^{*}$ satisfies the optimality condition $-\nabla f(x^{*})\in N_{\overline{C}}(x^{*})+{\cal A}_{0}^{\perp}$. Fix $z\in{\cal A}_{0}$, and for each $t\geq 0$ take $y=-\dot{x}(t)+z$ in (21) to obtain $\langle\frac{d}{dt}\nabla h(x(t))+\nabla f(x(t)),z\rangle=0.$ This gives

where $s(t)=[\nabla h(x^{0})-\nabla h(x(t))]/t.$ If $x^{*}\in{{\cal F}}$ then $\nabla h(x(t))\to\nabla h(x^{*})$, hence $\langle\nabla f(x^{*}),z\rangle=\lim_{t\to+\infty}\frac{1}{t}\int_{0}^{t}\langle\nabla f(x(s)),z\rangle ds=\lim_{t\to+\infty}\langle s(t),z\rangle=0.$ Therefore, $\Pi_{{\cal A}_{0}}\nabla f(x^{*})=0$. But $N_{\overline{{{\cal F}}}}(x^{*})={\cal A}_{0}^{\perp}$ when $x^{*}\in{{\cal F}}$, which proves our claim in this case. Assume now that $x^{*}\notin{{\cal F}}$, which implies that $x^{*}\in\partial C\cap{\cal A}$. By (26), we have that $\langle s(t),z\rangle$ converges to $\langle\nabla f(x^{*}),z\rangle$ as $t\to+\infty$ for all $z\in{\cal A}_{0}$, and therefore $\Pi_{{\cal A}_{0}}s(t)\to\Pi_{{\cal A}_{0}}\nabla f(x^{*})$ as $t\to+\infty$. On the other hand, by Lemma 4.1, we have that there exists $\nu\in-N_{\overline{C}}(x^{*})$ with $|\nu|=1$ such that $\nabla h(x(t_{j}))/|\nabla h(x(t_{j}))|\to\nu$ for some $t_{j}\to+\infty$. Since $N_{\overline{C}}(x^{*})$ is positively homogeneous, we deduce that $\exists$ $\bar{\nu}\in-N_{\overline{C}}(x^{*})$ such that $\Pi_{{\cal A}_{0}}\nabla f(x^{*})=\Pi_{{\cal A}_{0}}\bar{\nu}$. Thus, $-\nabla f(x^{*})\in-\Pi_{{\cal A}_{0}}\bar{\nu}+{\cal A}_{0}^{\perp}\subseteq N_{\overline{C}}(x^{*})+{\cal A}_{0}^{\perp}$, which proves the theorem. ∎

Following , we remark that when $f$ is linear, the limit point can be characterized as a sort of “$D_{h}$-projection” of the initial condition onto the optimal set $S(P)$. In fact, we have:

Under the assumptions of Theorem 4.2, if $f$ is linear then the solution $x(t)$ of $(H$-$SD)$ converges as $t\to+\infty$ to the unique optimal solution $x^{*}$ of

Let $x^{*}\in S(P)$ be such that $x(t)\to x^{*}$ as $t\to+\infty$. Let $\bar{x}\in S(P)$. Since $x(t)\in{{\cal F}}$, the optimality of $\bar{x}$ yields $f(x(t))\geq f(\bar{x})$, and it follows from (20) that $D_{h}(x(t),x^{0})\leq D_{h}(\bar{x},x^{0})$. Letting $t\to+\infty$ in the last inequality, we deduce that $x^{*}$ solves (27). Noticing that $D_{h}(\cdot,x^{0})$ is strictly convex due to Definition 4.1(i), we conclude the result. ∎

We finish this section with an abstract result concerning the rate of convergence under uniqueness of the optimal solution. We will apply this result in the next section. Suppose that $f$ is convex and satisfies (3) and (16), with in addition $S(P)=\{a\}$. Given a Bregman function $h$ complying with $(H_{0})$, consider the following growth condition:

where $U_{a}$ is a neighborhood of $a$ and with $\alpha>0$, $\beta\geq 1$. The next abstract result gives an estimation of the convergence rate with respect to the $D$-function of $h$.

Assume that $f$ and $h$ satisfy the above conditions an let $x:[0,+\infty)\to{{\cal F}}$ be the solution of $(H\mbox{-}SD)$. Then we have the following estimations: $\bullet$ If $\beta=1$ then there exists $K>0$ such that $D_{h}(a,x(t))\leq Ke^{-\alpha t}$, $\forall t>0.$ $\bullet$ If $\beta>1$ then there exists $K^{\prime}>0$ such that $D_{h}(a,x(t))\leq K^{\prime}/t^{\frac{1}{\beta-1}}$, $\forall t>0.$

The assumptions of Theorem 4.2 are satisfied, this yields the well-posedness of $(H$-$SD)$ and the convergence of $x(t)$ to $a$ as $t\to+\infty$. Besides, from (24) it follows that for all $t\geq 0$, $\frac{d}{dt}D_{h}(a,x(t))+\langle\nabla f(x(t)),x(t)-a\rangle=0.$ By convexity of $f$, we have $\frac{d}{dt}D_{h}(a,x(t))+f(x(t))-f(a)\leq 0.$ Since $x(t)\to a$, there exists $t_{0}$ such that $\forall t\geq t_{0}$, $x(t)\in U_{a}\cap{{\cal F}}$. Therefore by combining $(GC)$ and the last inequality it follows that

In order to integrate this differential inequality, let us first observe that we have the following equivalence: $D_{h}(a,x(t))>0,\>\forall t\geq 0$ iff $x^{0}\neq a$. Indeed, if $a\in\overline{{{\cal F}}}\setminus{{\cal F}}$ then the equivalence follows from $x(t)\in{{\cal F}}$ together with Lemma 4.3; if $a\in{{\cal F}}$ then the optimality condition that is satisfied by $a$ is $\Pi_{{\cal A}_{0}}\nabla f(a)=0$, and the equivalence is a consequence of the uniqueness of the solution $x(t)$ of $(H$-$SD)$. Hence, we can assume that $x^{0}\neq a$ and divide (28) by $D_{h}(a,x(t))^{\beta}$ for all $t\geq t_{0}$. A simple integration procedure then yields the result. ∎

4 Examples: interior point flows in convex programming

This section gives a systematic method to construct explicit Legendre metrics on a quite general class of convex sets. By so doing, we will also show that many systems studied earlier by various authors appears as particular cases of $(H\mbox{-}SD)$ systems.

Suppose that the open convex set $C$ is given by

is essentially smooth with ${\rm int}\>{\rm dom}\>h=C$ and $h\in{\cal C}^{3}(C)$, where $C$ is given by (30). If we assume in addition the following non-degeneracy condition:

then $H=\nabla^{2}h$ is positive definite on $C$, and consequently $h$ satisfies $(H_{0})$.

and the differential equation in $(H$-$SD)$ is given by

For suitable choices of $f$, this is a Lotka-Volterra type equation that naturally arises in population dynamics theory and, in that context, the structure $(\cdot,\cdot)^{H}$ with $h$ as in (33) is usually referred to as the Shahshahani metric; see and the references therein. The figure 1 gives a numerical illustration of system (35) for $n=3$ and with $f(x)=x_{3}-x_{2}$.

Karmarkar studied (35) in for a quadratic objective function as a continuous model of the interior point algorithm introduced by him in . Equation (34) is studied by Faybusovich in when $(P)$ is a linear program, establishing connections with completely integrable Hamiltonian systems and exponential convergence rate, and by Herzel et al. in , who prove quadratic convergence for an explicit discretization.

Take now the log barrier kernel $\theta_{1}$ and $h(x)=-\sum_{i=1}^{n}\ln x_{i}.$ Since $\nabla^{2}h(x)=X^{-2}$ with $X$ defined as above, the associated differential equation is

5 Convergence results for linear programming

Let us consider the specific case of a linear program

Let $h$ be given by (39) with $\theta$ satisfying $(H_{1})$. Under (38), $(H\mbox{-}SD)$ is well-posed and $x(t)$ converges as $t\to+\infty$ to the unique solution $x^{*}$ of

where $I_{0}=\{i\in I\mid g_{i}(x)=0\mbox{ for all }x\in S(LP)\}$.

But $\langle c,x(t)\rangle=\langle c,x^{*}(t)\rangle$ and $\forall i\in I_{0}$, $g_{i}(x^{*}(t))=g_{i}(x(t))>0$. Since $x^{*}\in{\rm ri}\>S(LP)$, for all $i\notin I_{0}$ and $j$ large enough, $g_{i}(x^{*}(t_{j}))>0$. Thus, the right-hand side of (41) is finite at $t_{j}$, and it follows that $\sum\limits_{i\notin I_{0}}D_{\theta}(g_{i}(\bar{x}),g_{i}(x^{0}))\leq\sum\limits_{i\notin I_{0}}D_{\theta}(g_{i}(x^{*}),g_{i}(x^{0})).$ Hence, $\bar{x}=x^{*}$. ∎

Rate of convergence. We turn now to the case where there is no equality constraint so that the linear program is

The following lemma is a sharper version of Proposition 4.2 in the linear context.

Then there exists positive constants $K,L,M$ such that for all $t>0$ the trajectory of $(H$-$SD)$ satisfies $D_{h}(a,x(t))\leq Ke^{-Lt}$ if $\beta=1$, and $D_{h}(a,x(t))\leq M/t^{\frac{1}{\beta-1}}$ if $\beta>1$.

By Lemma 4.4, there exists $k_{0}$ such that for all $t>0$,

Now, if we prove that $\exists\lambda>0$ such that

for all $i\in I$ and for $t$ large enough, then from (44) it follows that $f(\cdot)=\langle c,\cdot\rangle$ satisfies the assumptions of Proposition 4.2 and the conclusion follows easily. Since $x(t)\rightarrow a$, to prove (45) it suffices to show that $\forall r_{0}\geq 0$, $\exists\eta,\mu>0$ such that $\forall s$, $|s-r_{0}|<\eta$, $\mu D_{\theta}(r_{0},s)^{\beta}\leq|r_{0}-s|.$ The case where $r_{0}=0$ is a direct consequence of (43). Let $r_{0}>0$. An easy computation yields $\frac{d^{2}}{ds^{2}}D_{\theta}(r_{0},s)_{|s=r_{0}}=\theta^{\prime\prime}(r_{0}),$ and by Taylor’s expansion formula

with $\theta^{\prime\prime}(r_{0})>0$ due to $(H_{1})$(iii). Let $\eta$ be such that $\forall s$, $|s-r_{0}|<\eta$, $s>0$, $D_{\theta}(r_{0},s)\leq\theta^{\prime\prime}(r_{0})(s-r_{0})^{2}$ and $D_{\theta}(r_{0},s)\leq 1$; since $\beta\geq 1$, $D_{\theta}(r_{0},s)^{\beta}\leq D_{\theta}(r_{0},s)\leq\theta^{\prime\prime}(r_{0})|s-r_{0}|$. ∎

6 Dual convergence

In convex optimization theory, it is usual to associate with $(P)$ the dual problem given by

Suppose that $(H\mbox{-}SD)$ is well-posed. Integrating the differential inclusion (17), we obtain

where $c(t)=\frac{1}{t}\int_{0}^{t}\nabla f(x(\tau))d\tau$ and $\lambda(t)$ is the dual trajectory defined by

Assume that $x(t)$ is bounded. From (47), it follows that $\nabla f$ is constant on $S(P)$, and then it is easy to see that $\nabla f(x(t))\to\nabla f(x^{*})$ as $t\to+\infty$ for any $x^{*}\in S(P)$. Consequently, $c(t)\to\nabla f(x^{*})$. By (51) together with [36, Theorem 26.5], we have $x(t)=\nabla h^{*}(\nabla h(x^{0})-t\lambda(t)),$ where the Fenchel conjugate $h^{*}$ is given by $h^{*}(\lambda)=\sum_{i=1}^{n}\theta^{*}(\lambda_{i}).$ Take any solution $\widetilde{x}$ of $A\widetilde{x}=b$. Since $Ax(t)=b$, we have $\widetilde{x}-\nabla h^{*}(\nabla h(x^{0})-t\lambda(t))\in{\rm Ker}\>A$. On account of (50), $\lambda(t)$ is the unique optimal solution of

As a direct consequence of [26, Propositions 10 and 11], we obtain that under (47), (48), (53) and $(H_{1})$, $\{\lambda(t)\mid t\to+\infty\}$ is bounded and its cluster points belong to $S(D)$. The convergence of $\lambda(t)$ is more difficult to establish. In fact, under some additional conditions on $\theta^{*}$ (see [14, Conditions $(H_{0})$-$(H_{1})$] or [26, Conditions (A7) and (A8)]) it is possible to show that $\lambda(t)$ converges to a particular element of the dual optimal set (the “$\theta^{*}$-center” in the sense of [14, Definition 5.1] or the $D_{h}(\cdot,x^{0})$-center as defined in [26, pag. 616]), which is characterized as the unique solution of a nested hierarchy of optimization problems on the dual optimal set. We will not develop this point here. Let us only mention that for all the examples of section 4.4, $\theta_{i}^{*}$ satisfies such additional conditions and consequently:

Under (47), (48) and (53), for each of the explicit Legendre kernels given in section 4.4, $\lambda(t)$ given by (51) converges to a particular dual solution.

Legendre transform coordinates

The proof is elementary and is left to the reader. ∎

From now on, ${\cal A}$ is the affine subspace defined by (1), whose dimension is $r=n-m$.

By Lemma 5.1, the previous definition is consistent.

2 Legendre transform coordinates

If $g\in\Gamma_{0}({\cal A})$ is of Legendre type in the sense of Definition 5.1, then $\nabla g({\rm int}_{\cal A}{\rm dom}\>g)$ is a nonempty, open and convex subset of ${\cal A}_{0}$. In addition, $\nabla g$ is a one-to-one continuous mapping from ${\rm int}_{\cal A}{\rm dom}\>g$ onto its image.

In the sequel, we assume that $h$ satisfies the basic condition $(H_{0})$ and ${{\cal F}}=C\cap{\cal A}\neq\emptyset$. The Legendre transform coordinates mapping on ${{\cal F}}$ associated with $h$ is defined by

This definition retrieves the Legendre transform coordinates introduced by Bayer and Lagarias in for the particular case of the log-barrier on a polyhedral set.

Under the above definitions and assumptions, ${{\cal F}}^{*}$ is a convex, (relatively) open and nonempty subset of ${\cal A}_{0}$, $\phi_{h}$ is a ${\cal C}^{1}$ diffeomorphism from ${{\cal F}}$ to ${{\cal F}}^{*}$, and for all $x\in{{\cal F}}$, $d\phi_{h}(x)=\Pi_{{\cal A}_{0}}H(x)$ and $d\phi_{h}(x)^{-1}=\sqrt{H(x)^{-1}}\Pi_{\sqrt{H(x)}{\cal A}_{0}}\sqrt{H(x)^{-1}}$, where $H(x)=\nabla^{2}h(x)$.

By Propositions 5.1 and 5.2, ${{\cal F}}^{*}$ is a convex, open and nonempty subset of ${\cal A}_{0}$ and $\phi_{h}$ is a continuous bijection. By $(H_{0})$(ii), $\phi_{h}$ is of class ${\cal C}^{1}$ on ${{\cal F}}$ and we have for all $x\in{{\cal F}}$, $d\phi_{h}(x)=\Pi_{{\cal A}_{0}}\nabla^{2}h(x)=\Pi_{{\cal A}_{0}}H(x).$ Let $v\in{\cal A}_{0}$ be such that $d\phi_{h}(x)v=0$. It follows that $H(x)v\in{\cal A}_{0}^{\perp}$ and in particular $\langle H(x)v,v\rangle=0$. Hence, $v=0$ thanks to $(H_{0})$(iii). The implicit function theorem implies then that $\phi_{h}$ is a ${\cal C}^{1}$ diffeomorphism. The formula concerning $d\phi_{h}(x)^{-1}$ is a direct consequence of the next lemma.

This follows by the same method as in , pag. 545; we leave the proof to the reader. ∎

Similarly to the classical Legendre type functions theory, the inverse of $\phi_{h}$ can be expressed in terms of Fenchel conjugates. For that purpose, we notice that inverting $\phi_{h}$ is a minimization problem. Indeed, given $y\in{\cal A}_{0}$, the problem of finding $x\in{{\cal F}}$ such that $y=\Pi_{{\cal A}_{0}}\nabla h(x)$ is equivalent to $x=\mbox{\rm Argmin}\{h(z)-\langle y,z\rangle|z\in{\cal A}\}$, or equivalently

We have that $\phi_{h}^{-1}:{{\cal F}}^{*}\to{{\cal F}}$ is given by $\phi_{h}^{-1}(y)=\nabla[h^{*}\square(\delta_{{\cal A}_{0}^{\perp}}+\langle\cdot,\widetilde{x}\rangle)](y),$ for any $\widetilde{x}\in{\cal A}$, and moreover ${{\cal F}}^{*}=\Pi_{{\cal A}_{0}}{\rm int}\>{\rm dom}\>h^{*}$.

3 Linear problems in Legendre transform coordinates

One of the first interest of Legendre transform coordinates is to transform linear constraints into positive cones.

As a direct consequence of Propositions 5.3 and 5.4:

Under the assumptions of Proposition 5.4, if $\eta=0$ then ${{\cal F}}^{*}$ is a positive convex cone and if $\eta=+\infty$ then ${{\cal F}}^{*}={\cal A}_{0}$.

3.2 (H​-​S​D)𝐻-𝑆𝐷(H\mbox{-}SD)-trajectories in Legendre transform coordinates

For all $y\in{{\cal F}}^{*}$, $[(\phi_{h})_{*}\nabla_{{}_{H}}f_{|_{{\cal F}}}]\>(y)=\Pi_{{\cal A}_{0}}c.$