PaperlayerView exact revision on arXiv

Source-linked AI summary

Hessian Riemannian gradient flows in convex programming

Felipe Alvarez, Jérôme Bolte, Olivier Brahic

arXiv:1811.10331v1math.OC

TL;DR

The paper asks how Hessian Riemannian gradient flows can be used to solve constrained minimization problems. It characterizes these metrics through a variational-inequality integration property and studies the resulting flows. It establishes existence and convergence results, including convergence to global minimizers under convexity, and gives dual and geometric interpretations.

  • Problem

    The paper studies existence, global convergence, and geometric properties of Hessian Riemannian gradient flows for constrained minimization.

    Source: §1 · p. 2

  • Method

    It uses Hessian metrics induced by Legendre-type convex functions, characterizes them through a variational-inequality integration property, and reformulates the flow as a differential inclusion.

    Source: §1 · pp. 2–3

  • Results

    Under quasi-convexity and the stated Bregman-function condition, trajectories converge to a point satisfying the local-minimizer optimality condition; for convex f, the limit is a global minimizer.

    Source: §1 · p. 3

  • Takeaways & Limitations

    For linear objectives, flow orbits also represent paths or iterates of viscosity methods and Bregman proximal algorithms, as well as geodesics and certain Lagrangian trajectories.

    Source: §1 · p. 3

    The paper does not develop the characterization of the dual limit as the unique solution of a nested hierarchy of optimization problems on the dual optimal set.

    Source: §4.6 · p. 21

Abstract

from arXiv · show

Motivated by a constrained minimization problem, it is studied the gradient flows with respect to Hessian Riemannian metrics induced by convex functions of Legendre type. The first result characterizes Hessian Riemannian structures on convex sets as those metrics that have a specific integration property with respect to variational inequalities, giving a new motivation for the introduction of Bregman-type distances. Then, the general evolution problem is introduced and a differential inclusion reformulation is given. A general existence result is proved and global convergence is established under quasi-convexity conditions, with interesting refinements in the case of convex minimization. Some explicit examples of these gradient flows are discussed. Dual trajectories are identified and sufficient conditions for dual convergence are examined for a convex program with positivity and equality constraints. Some convergence rate results are established. In the case of a linear objective function, several optimality characterizations of the orbits are given: optimal path of viscosity methods, continuous-time model of Bregman-type proximal algorithms, geodesics for some adequate metrics and projections of $\dot q$-trajectories of some Lagrange equations and completely integrable Hamiltonian systems.

1 Introduction

The paper studies existence, convergence, and geometry of steepest-descent flows for constrained minimization using Hessian metrics induced by Legendre-type convex functions. It characterizes these metrics through variational inequalities and develops convergence and geometric results for the resulting flows.

1 Introduction

  • The flow is formulated by placing a Riemannian metric on the convex set, restricting it to the relative interior of the feasible set, and following the metric steepest-descent field.The metrics of interest are Hessians of Legendre-type convex functions.Source: §1 · p. 2
  • The flow also admits a differential-inclusion reformulation formally resembling evolution problems in infinite-dimensional thermodynamic systems.The inclusion is given as d/dt ∇h(x(t)) + ∇f(x(t)) ∈ Im A^T, with x(t) in the feasible set.Source: §1 · p. 2
  • For convex objectives, the variational-inequality integration property characterizes Hessian metrics and yields D-functions whose gradients recover the vector fields x − a.For a Hessian induced by h, the D-function is Dh(a, x) = h(a) − h(x) − dh(x)(x − a).Source: §1 · p. 2
  • For linear objectives, viscosity methods and Bregman proximal algorithms produce paths or iterates in the flow’s orbit, with the D-function playing an essential role.The paper also describes a systematic construction of Legendre functions from barrier functions for convex inequality problems.Source: §1 · p. 3
  • Under quasi-convexity and the stated Bregman-function condition, trajectories converge to a point satisfying the local-minimizer optimality condition; for convex f, the limit is a global minimizer.The introduction also reports a general well-posedness result and convergence of f(x(t)) to inf f.Source: §1 · p. 3
  • For positivity and equality constraints, a dual trajectory converges to a dual solution under appropriate conditions when f is convex, even if primal convergence is not ensured.The paper also gives a variational characterization of limits and an abstract convergence-rate result under uniqueness.Source: §1 · p. 3
  • Legendre transform coordinates make the orbits straight lines in a positive cone and identify them as geodesics and as trajectories of certain Lagrangian systems.The latter interpretation has consequences for integrable Hamiltonians.Source: §1 · p. 3

2 Preliminaries

The preliminaries set up the constrained minimization problem and define the Riemannian gradient flow on the relative interior of its feasible set. The metric gradient is characterized by tangency and the differential pairing, and steepest descent follows its negative direction.

2.1 The minimization problem and optimality conditions

  • The problem minimizes f over the feasible set F, defined by membership in C and the equality constraint Ax = b; when f is convex, the stated local optimality condition is also sufficient for global optimality.The set of optimal solutions is denoted S(P).Source: §2.1 · p. 4

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

  • A Riemannian gradient is tangent to the manifold and pairs with every tangent vector through the differential of the function.On the feasible manifold F, tangent spaces are identified with the null space of A, and the induced metric defines the gradient of f restricted to F.Source: §2.2 · p. 5
  • The negative Riemannian gradient is the feasible direction of steepest decrease, and its trajectory from an initial point defines the steepest-descent method.The metric on F is induced by restricting the metric defined on C.Source: §2.2 · p. 5

3 Legendre gradient flows in constrained optimization

The section characterizes Hessian metrics through variational inequalities and introduces constrained steepest-descent flows on Legendre-type domains. It relates these flows to differential inclusions, Bregman proximal methods, and viscosity paths for linear objectives.

3.1 Liapounov functionals, variational inequalities and Hessian metrics

  • Although f decreases along steepest-descent trajectories, its Lyapunov property alone does not ensure that the trajectory converges.The variational characterization of minimizers motivates seeking a corresponding Lyapunov function in the non-Euclidean setting.Source: §3.1 · p. 6
  • The fields x ↦ x − y are Riemannian gradients exactly for metrics induced by Hessians of strictly convex functions, with D_h generating those fields.Specifically, the gradient of D_h(y, ·) at x is x − y.Source: §3.1 · p. 6

3.2 Legendre type functions and the (H-SD) dynamical system

  • The Legendre metric is induced by h on C and restricted to the feasible set F; the section imposes Legendre-type, smoothness, positive-Hessian, and local-Lipschitz conditions on h.These are the stated conditions for defining the Riemannian structure used by (H-SD).Source: §3.2 · p. 8
  • The (H-SD) system is the steepest-descent flow on the feasible manifold, with well-posedness requiring its maximal solution to extend for all positive time.The metric on F is obtained by restricting the metric on C.Source: §3.2 · p. 8

3.3 Differential inclusion formulation of (H-SD) and some consequences

  • The differential inclusion formulation describes the same trajectories as (H-SD), and its solutions are unique and of class C1.The trajectories remain in F and start from the given feasible initial point.Source: §3.3 · pp. 8–9
  • For convex objectives, an implicit discretization of the flow yields the Bregman proximal minimization method.Its optimality condition uses the gradient difference ∇h(x_k+1) − ∇h(x_k) and a positive step size.Source: §3.3 · p. 9
  • For linear objectives, the flow is a central optimal path and coincides at reciprocal parameter values with the viscosity optimal path; sampled trajectories match the proximal iterates.The correspondence is stated for a well-posed flow.Source: §3.3 · p. 9
  • Unless initialized at an optimal solution, convergence of the proximal iterates to an optimizer requires the cumulative step sizes to diverge.The stated necessary condition is Σ μ_k = +∞.Source: §3.3 · p. 10

4 Global existence, asymptotic analysis and examples

This section establishes well-posedness and asymptotic convergence for (H-SD), then develops explicit Legendre metrics and examples connecting Hessian flows with interior-point dynamics. It also examines linear-programming trajectories, including convergence and rates for primal trajectories and conditional convergence for dual trajectories.

4.1 Well-posedness of (H-SD)

  • Under any of three alternative conditions and a finite lower bound on f, (H-SD) is well-posed, and f(x(t)) is nonincreasing and convergent.The alternatives are (WP1), (WP2), or (WP3).Source: §4.1 · p. 10

4.2 Value convergence for a convex objective function

  • For convex f and well-posed (H-SD), f(x(t)) ≤ f(a) + Dh(a, x0)/t for every a ∈ F, so its limit is at most the minimum value.The estimate uses the D-function Dh defined in (19).Source: §4.2 · p. 12

4.3 Bregman metrics and trajectory convergence

  • With a Bregman function h, quasi-convex f, and a nonempty solution set, (H-SD) is well-posed and x(t) converges; if f is convex, the limit solves (P).The Bregman-function assumptions include bounded D-function sublevel sets and an asymptotic separation property.Source: §4.3 · p. 13
  • For linear f under Theorem 4.2’s assumptions, x(t) converges to the unique optimal solution that minimizes Dh(·, x0) over the optimal set.The paper characterizes this limit as a Dh-projection of the initial condition onto S(P).Source: §4.3 · p. 13
  • With a unique minimizer and the stated growth condition, Dh(a, x(t)) decays exponentially when β = 1 and at a power rate when β > 1.The proposition assumes convex f and a Bregman function h satisfying (H0).Source: §4.3 · pp. 13–14

4.4 Examples: interior point flows in convex programming

  • The section constructs Legendre metrics on sets defined by concave inequalities: h = Σθ(g_i) is essentially smooth, and a non-degeneracy condition makes its Hessian positive definite.The kernels include log and inverse barriers as well as entropy examples; the latter yield Bregman functions with zone C.Source: §4.4 · pp. 14–15
  • For positivity and equality constraints, the Boltzmann-Shannon entropy kernel gives an explicit (H-SD) differential equation and a representative trajectory.The section also notes that systems studied in earlier works arise as particular cases of (H-SD).Source: §4.4 · pp. 14–16, Figure 1 · p. 16
  • On the simplex, the entropy-kernel flow uses the Shahshahani metric and can yield Lotka–Volterra dynamics, with prior work connecting related flows to interior-point methods and integrable Hamiltonian systems.The cited studies also establish exponential convergence rates and quadratic convergence for an explicit discretization.Source: §4.4 · p. 16

4.5 Convergence results for linear programming

  • Under the stated optimal-set and Slater assumptions, the linear-programming flow is well-posed and converges to a unique point in the optimal set characterized by Proposition 4.4.The result applies to the specified Legendre kernel with θ satisfying (H1).Source: §4.5 · p. 17
  • For the Boltzmann–Shannon kernels θ3 and θ6, the Euclidean error decays exponentially; for θ4 and θ5, it is bounded by K/t.These examples assume a unique solution and the stated Bregman-function setting.Source: §4.5 · pp. 18–19

4.6 Dual convergence

  • Under (47), (48), (53), and (H1), dual-trajectory cluster points are optimal, and for the explicit kernels of section 4.4 the dual trajectory converges to a particular dual solution.The dual trajectory can be interpreted as a penalty approximation in which positivity constraints are penalized by a separable strictly convex function.Source: §4.6 · pp. 20–21

5.1 Legendre functions on affine subspaces

The section extends Legendre-type functions to affine subspaces and shows that the extension is consistent with affine coordinates. It also establishes that restricting a Legendre-type function to a suitable affine subspace preserves that property.

5.1 Legendre functions on affine subspaces

  • The section's central extension generalizes the Legendre-type notion to functions whose domains lie in an affine subspace of R^n.The stated motivation is that the Legendre-type property does not depend on canonical coordinates.Source: §5.1 · p. 21
  • Legendre type is invariant under affine invertible changes of coordinates, supporting a consistent definition on affine subspaces.The section defines a function on an affine subspace as Legendre type when its representation under such a mapping is Legendre type in R^r.Source: §5.1 · p. 21
  • If F = C ∩ A is nonempty, restricting a Legendre-type function h to A remains Legendre type and has relative interior domain F.The proof reduces the restriction to coordinates on R^r and verifies essential smoothness and strict convexity.Source: §5.1 · pp. 21–22

5.2 Legendre transform coordinates

The section defines Legendre transform coordinates on the feasible affine slice and establishes their regularity. It relates the coordinate map and its inverse to gradients and a minimization problem.

5.2 Legendre transform coordinates

  • The affine-subspace mapping generalizes the classical Legendre correspondence, whose full-space form maps int dom h onto int dom h* with inverse ∇h*.The section invokes this full-space property as background for its affine-subspace generalization.Source: §5.2 · p. 22
  • For a Legendre-type function on A, its gradient maps the relative interior of its domain one-to-one and continuously onto a nonempty, open, convex subset of A0.This extends the familiar mapping property of Legendre functions to affine subspaces.Source: §5.2 · p. 22
  • The map φ_h(x) = Π_A0∇h(x) sends F bijectively and C1-diffeomorphically onto a convex, relatively open, nonempty subset F* of A0.Its derivative is Π_A0H(x), and the theorem also gives a formula for the inverse derivative.Source: §5.2 · pp. 22–23
  • Inverting φ_h amounts to minimizing h(z) − ⟨y,z⟩ over A, with the minimizer characterized through the Fenchel conjugate of h + δ_A.The image F* is identified with Π_A0 int dom h*.Source: §5.2 · p. 23

5.3 Linear problems in Legendre transform coordinates

For polyhedral feasible sets, Legendre transform coordinates describe conjugate domains and linear-objective flows. The section then characterizes those flows as geodesics, projected Lagrange trajectories, and projections associated with a completely integrable Hamiltonian system.

5.3.1 Polyhedral sets in Legendre transform coordinates

  • For polyhedral C and the specified separable h, dom h* is described by y + B^Tλ = 0 with λ_i ≥ −η when η is finite; η = 0 gives a positive cone F*, while η = +∞ gives F* = A0.When η = +∞, dom h* = R^n.Source: §5.3.1 · pp. 23–24

5.3.2 (H-SD)-trajectories in Legendre transform coordinates

  • For a linear objective, the pushforward of the H-steepest-descent vector field is the constant vector Π_A0c, so its trajectories are straight lines in F*.The section also gives two optimality characterizations of these trajectories, extending results for the log-metric.Source: §5.3.2 · p. 24

5.3.3 Geodesic curves

  • With the metric induced by φ_h, the H-steepest-descent solution is the unique geodesic through x0 with its specified initial velocity.The metric on F is obtained by transporting the Euclidean metric on F*; the manifold is not complete when Π_A0c ≠ 0 and F* is not an affine subspace.Source: §5.3.3 · pp. 24–25

5.3.4 Lagrange equations

  • For the Lagrangian system in (59), projecting each qdot trajectory onto A yields an H-steepest-descent solution with initial condition given by the projected initial velocity.The stated projection is x(t) = Π_A qdot(t).Source: §5.3.4 · p. 25

5.3.5 Completely integrable Hamiltonian systems

  • When Π_A0c ≠ 0, the restricted Lagrangian system gives, via the Legendre transform, a completely integrable Hamiltonian system on A0 × F*.The restricted system's trajectories project to the H-steepest-descent trajectories.Source: §5.3.5 · pp. 26–27
Loading 1811.10331v1…