Factorization in molecular modeling and belief propagation algorithms

1.   Introduction

In the last few decades, there has been a lot of interest in the study of higher-order variational problems on Riemannian manifolds. One of the most prominent second-order variational problems has the Lagrangian function given by the squared norm of the covariant acceleration. Stationary curves for this problem are the so-called Riemannian cubics or bi-harmonic curves ^[1,2]. These curves have played an important role in the study of interpolation problems ^[4,5,6]. Approaches to this second order problem are not restricted to its variational character, it has also been studied as an optimal control problem in which the control system is an affine connection system ^{[7,8,9,10,11,12]}. From the point of view of applications, this problem can be seen as an optimal navigation problem with regard to fuel consumption, and may involve several agents, have obstacles to avoid or be conditioned by constraints ^{[13,14,15,16,17]}.

The theory of Riemannian cubics can be interpreted as a higher-order extension of the theory of geodesics. An extension of this theory to odd-degree Riemannian polynomials has been developed in ^[18,19,20] (for a more general setting, see also ^[21] and references therein). Although the concept of odd-degree Riemannian polynomials given in ^[18] can be seen as a higher-order generalization of the concept of geodesics, it cannot be said to be a generalization of lower-degree polynomials, starting with the cubic ones. Indeed, geodesics are particular cases of higher-degree Riemannian polynomials, but Riemannian cubics cannot in general be seen as higher-degree Riemannian polynomials.

The notion of Riemannian polynomials given in ^[18] was motivated by the optimization properties of the Euclidean polynomials and, thus, can be seen as a generalization of polynomials from Euclidean spaces to Riemannian manifolds. These polynomials play an important role in the study of interpolation and data fitting problems in curved spaces. Applications range from the control theory of mechanical systems to image processing or statistical analysis of shape data. The polynomials are used to construct interpolation curves (Riemannian splines) that give trajectories of physical systems along some prescribed positions ^[6,20,22], or they can be combined with least squares fitting to better represent image (or shape) data ^[23,24]. The degree of the polynomials provides a certain smoothness of the splines and accuracy of the represented data.

In this paper, we propose studying a variational problem of order $4$ which gives rise to a definition of higher-degree polynomials that is different from the one presented in ^[18]. The stationary curves of the proposed problem can be interpreted as the best approximations of Riemannian cubics when their existence is conditioned by boundary or interpolation conditions, and reduce naturally to Riemannian cubics when such curves exist.

The study of this variational problem in the rotation group SO(3) was presented in ^[25]. In this paper, we consider the problem in a general Riemannian manifold and derive the Euler-Lagrange equation (Section 3). Then, in Section 4, we analyse what happens on Lie groups. Since the Lagrangian function is invariant, we use the higher-order Euler-Poincaré reduction presented in ^[26] to obtain the corresponding equation on the Lie algebra.

2.   Riemannian geometry

In what follows $(M, \langle \; .\; , \; . \; \rangle)$ is an n-dimensional Riemannian manifold. The Levi-Civita connection is the mapping $\nabla$, which assigns to each two smooth vector fields $X$ and $Y$ in $M$, a new vector field, $\nabla_XY$, satisfying the following properties:

$({\rm{i}})$ $\nabla$ is ${{{\rm{I\kern-.17em R}}}}$-bilinear in $X$ and $Y$,

$({\rm{ii}})$ $\nabla_{fX}Y = f\nabla_XY$,

$({\rm{iii}})$ $\nabla_X(fY) = (Xf)Y+f\nabla_XY$,

$({\rm{iv}})$ $\nabla_XY$ is smooth in $M$,

$({\rm{v}})$ $\nabla_XY-\nabla_YX = [X, Y]$ $\;$ (Symmetry),

$({\rm{vi}})$ $X\langle Y, Z\rangle = \langle \nabla_XY, Z \rangle +\langle Y, \nabla_XZ\rangle$ (Compatibility),

where $X$, $Y$ and $Z$ are smooth vector fields on $M$, $f$ a smooth real valued function on $M$ and $[X, Y]$ denotes the Lie bracket of the vector fields $X$ and $Y$ defined by

The covariant derivative of a vector field $X$ along a curve $x$ in $M$ is given by $(DX/dt)(t) = \nabla _{(dx/dt)(t)}X(t)$, where $dx/dt$ is the velocity vector field along $x$. The $j$th-order covariant derivative $D^jX/dt^j$ is the covariant derivative of the vector field $D^{j-1}X/dt^{j-1}$, where $j\geq 1$. The $j$th-order covariant derivative $D^jx/dt^j$ of a curve $x$ is the $(j-1)$th-order covariant derivative of the velocity vector field along $x$, for $j\geq 2$.

For any vector field $X$ along a 2-parameter curve $x: (r, t) \to x(r, t)$, the covariant derivatives $DX/\partial r$ and $DX/\partial t$ are vector fields along $x$ defined as follows: We fix $t$ (resp., $r$) and consider $X$ restricted to the curve $x_t :r\mapsto x(r, t)$ (resp., $x_r :t\mapsto x(r, t)$), which leads to a vector field along $x_t$ (resp., $x_r$). The covariant derivative of the vector field $X$ along the curve $x_t$ (resp., $x_r$) gives rises to the vector field $DX/\partial r$ (resp., $DX/\partial t$) along $x$. As examples, we can set $X$ equal to $\partial x/\partial r$ or $\partial x/\partial t$ and obtain the following higher-order covariant derivatives,

or even higher-order ones. Note that, from the symmetry of the Levi-Civita connection (condition (5)), we get immediately that

To deal with higher-order partial covariant derivatives, we shall need to define the curvature tensor.

The curvature tensor $R$ is given by the identity

where $X$, $Y$, $Z$ are vector fields in $M$. Therefore, $R$ measures how much covariant derivatives fail to commute. For any vector field $X$ along a 2-parameter curve $x: (r, t) \to x(r, t)$, we have

From Eq (2.3) we see that $R$ is an essential tool to interchange the order of partial covariant derivatives. For this reason, the following symmetries of $R$ play such an important role in this paper.

For all vector fields $X$, $Y$, $Z$ and $W$ in $M$, the curvature tensor $R$ satisfies the skew-symmetry identities

and

and, as a consequence of (2.4) and (2.5), the symmetry by pairs identity

The cyclic permutation property

is called the first Bianchi identity.

The covariant differential of the curvature tensor $R$ is defined by

and the symmetry properties of $R$ lead to the following equalities.

and the second Bianchi identity

for every vector field $X$, $Y$, $Z$, $W$ and $V$ on $M$.

More details about Riemannian geometry can be found in Milnor ^[27], Lee ^[28] and O'Neill ^[29].

3.   Riemannian heptics

3.1.   Riemannian cubic problem

Let $x$ be a $\mathcal{C}^3$-piecewise smooth curve on $M$ and $\Gamma(x)$ the vector field along $x$ defined by

It is well-known that the curves $x$ satisfying

are the so-called Riemannian cubics. They arose as a natural generalization of geodesics. In fact, the Riemannian cubics are the extremal curves of the bienergy functional

and this functional is seen as a second order extension of the energy functional

Geodesics are the curves $x$ satisfying

and are critical points of the energy functional (3.3).

The variational problem that consists in finding the curves minimizing the bienergy functional (3.3) is called the Riemannian cubic problem and appears as a natural extension of the geodesic problem. It can be formulated as a optimal control problem in the following way.

subject to the control system

and the boundary conditions

Studying this problem from the point of view of Hamiltonian systems and optimal control proved to be very interesting and led to fruitful research ^[7,8,10,12].

Remark 1. Riemannian cubics and geodesics can also be seen as generalizations of Euclidean polynomials (of degree $1$ and $3$, respectively). This simple interpretation is based on optimization properties of these Euclidean curves. In fact, these properties are not restricted to polynomials of degree $1$ and $3$, but are valid for arbitrary odd-degree Euclidean polynomials. It is well-know that Euclidean polynomials $x$ of degree $2m-1$ satisfy the inequality

among all ${\cal C}^m$ functions $y$ satisfying the boundary conditions

and

moreover, the equality occurs iff $y$ coincides with $x$. The differential equation

is the Euler-Lagrange equation of the $m$-energy functional

Seen as a solution of Eq (3.12), each Euclidean polynomial is contained in the class of Euclidean polynomial of higher-order (Property A).

Remark 2. In ^[18], the Euclidean variational problem of order $m$ is extended to Riemannian manifolds by considering the following generalization of the $m$-energy functional

This variational problem gives rise to a notion of odd-degree Riemannian polynomials, for which, in general, property A fails, even when the curvature is constant.

3.2.   Riemannian heptic problem

To extend the Riemannian cubic problem we formulate the following fourth-order variational problem.

Consider the functional $J$ defined by

The Riemannian heptic problem $({\cal P})$ consists in finding the curves minimizing the functional $J$ among the set $\Omega$ of all $\mathcal{C}^3$-piecewise smooth curves $x$ satisfying the boundary conditions

and

where $v_{ij}\in T_{x_i}M$, with $i = 0, 1$ and $1\leq j\leq 3$.

The variational problem $({\cal P})$ can be formulated as an optimal control problem as follows:

subject to the control system

and the boundary conditions

When studying optimal control problems for these higher-order dynamic systems, we encounter even higher-order bundles than in the Riemannian cubic problem.

3.3.   The first variation formula

An admissible variation of the curve $x\in \Omega$ is a ${\cal C}^{3}$-piecewise smooth one-parameter variation

such that $\alpha_r \in \Omega$, for all $r \in (-\epsilon, \epsilon)$, $\epsilon > 0$. The variational vector field $X$ associated with an admissible variation $\alpha$ of $x$ is given by

Admissible variations of $x$ give rise to the real vector space $T_{x}\Omega$ of all the ${\cal C}^{3}$ piecewise smooth vector field $X$ along $x$ verifying the boundary conditions

and

The first variation $\delta J(x)$ of $J$ at the curve $x$ is the linear form on $T_x\Omega$ defined by

where $\alpha$ is an admissible variation of $x$ with associated variational vector field $X$.

Necessary conditions for $x \in \Omega$ to be a local minimizer of $J$ follow from the Hamilton variational principle through the first variation of $J$ at $x$,

which gives rise to the Euler-Lagrange equations for the problem $({\cal P})$.

To obtain the first variation formula of $J$ at $x$ let us consider an admissible variation $\alpha$ of $x \in \Omega$.

First of all, we have to compute $(D/\partial r)\Gamma(\alpha).$ To begin, note that, although we know from (2.1) that

we need to use the curvature tensor $R$ to measure how much the second covariant derivative $(D/\partial r)(D/\partial t)Y$ is symmetric in $r$ and $t$, for $Y$ an arbitrary vector field along $\alpha$. From (2.3), we know that

Making use of these tools to interchange the order of partial covariant derivatives, we obtain

and, consequently,

The previous identity allows to write $(d/dr)J(\alpha _{r})$ as follows:

If we apply the properties of the curvature tensor, we see that

Now, integrating by parts, one has

When we take $r = 0$, most of the terms above vanish due to the conditions (2.1) and the fact that both $x$ and $X$ are ${\cal C}^3$-piecewise smooth on $[0, T]$. Hence, the expression of $\delta J(x) (X)$ can be simplified as follows:

Lemma 3. If $\alpha$ is an admissible variation of $x \in \Omega$ and $X$ the variational vector field associated with $\alpha$, then

where

Proposition 4. A necessary condition for the curve $x \in \Omega$ to be a local minimizer for the functional $J$ over $\Omega$ is that $x$ is smooth and satisfies

where $\Pi(x)$ is given by (3.25).

Proof. Suppose that $x$ is a local minimizer of $J$ over $\Omega$. Then, by applying the Hamilton variational principle to $J$ at $x$, we have $\delta J(x)(X) = 0$, $\forall X\in T_x\Omega$ (see (3.21)), and then the right-hand side of (3.24) is zero, for arbitrary $X \in T_x\Omega$.

Let us first consider $X \in T_x\Omega$ defined by

where $\Pi(x)$ is the vector field along $x$ given by (3.25) and $f$ is a smooth real-valued function on $[0, T]$ verifying $f^{(k)}(t_i) = 0$, $k = 0, 1, 2, 3$, and $f(t) > 0$, for $t\in (t_{i-1}, t_i)$, $i = 1, \ldots, l-1$. It follows from (3.24) and (3.21) that $\Pi(x(t)) = 0$ for $t\in [0, T]$.

To show that $x$ is smooth, let us take the vector field $X \in T_x\Omega$ so that

for $i = 1, \ldots, l-1$. Thus, since $x$ satisfies the Eq (3.26), it follows from (3.24) and (3.21) that

which implies that

for $i = 1, \ldots, l-1$. Hence, $\Gamma(x)$ is ${\cal C}^3$ on $[0, T]$ and, consequently $x$ is ${\cal C}^7$. Since $x$ is a solution of the differential equation of eighth-order (3.26), it follows that the eighth-order covariant derivative of $x$ can be written in terms of the covariant derivatives of order less than $8$, so, in turn, the same argument can be used for covariant derivatives of any order. This leads us to conclude that $x$ is smooth on $[0, T]$.

Definition 5. A curve $x$ in $M$ is said to be a Riemannian heptic if $x$ is a smooth solution of the differential Eq (3.26).

4.   Riemannian heptics on connected and compact Lie groups

4.1.   Bi-invariant metrics on connected and compact Lie groups

Let $G$ be a connected and compact Lie group endowed with a bi-invariant Riemannian metric $\langle \cdot, \cdot \rangle$ and let $\mathfrak{g}$ be its Lie algebra. We denote by $L_x:G\to G$ the left-translation map by an element $x$ of $G$. The left-invariant vector field associated with an element $u$ of $\mathfrak{g}$ is $u_L:x\mapsto T_eL_xu$, where $T_eL_x$ is the differential of $L_x$ at $e$ and $e$ the identity of $G$. The Levi-Civita connection $\nabla$ induced by $\langle \cdot, \cdot \rangle$ is completely determined by its restriction $\stackrel{\mathfrak{g}}{\nabla}$ to $\mathfrak{g}$ via left-translations. The bilinear map $\stackrel{\mathfrak{g}}{\nabla}:\mathfrak{g}^2\to\mathfrak{g}$ is given by

for each $u$ and $z \in \mathfrak{g}$, and we have

When we restrict the curvature tensor $R$ of $G$ to the Lie algebra $\mathfrak{g}$ of $G$, we obtain the map $\mathfrak{R}:\mathfrak{g}^2\to\mathfrak{g}$ defined by

The differential of the curvature tensor $\nabla R$ is constant and equal to zero.

In addition, the inner product on $\mathfrak{g}$ corresponding to the Riemannian metric verifies

The property (4.4) can be described by means of the adjoint representation ad of $\mathfrak{g}$, that is, by saying that the map $\hbox{ad}_z$ is skew-adjoint, for $z\in {\mathfrak{g}}$.

We denote by $^{\flat}$ and $^{\sharp}$ the musical isomorphisms between $\mathfrak{g}$ and its dual $\mathfrak{g}^*$ defined by the inner product on $\mathfrak{g}$. Thus, we know that

More details about bi-invariant metrics on Lie groups can be found in Milnor ^[27] and Kobayashi and Nomizu ^[30].

4.2.   Lie hexics

Let $x$ be a curve in $G$ and $V$ the velocity vector field of $x$. The lift $x_1$ of the curve $x$ to $TG$ can be reduced to the Lie algebra $\mathfrak{g}$ by considering the curve $v$ given by $V = T_eL_xv$. The reduced curve $v$ is described, with respect to a given basis $\mathfrak{B} = \{e_1, \ldots, e_n\}$ of $\mathfrak{g}$, by $v = \sum_{i = 1}^n v_ie_i$, where $v_1, \ldots, v_n$ can be seen as pseudo-velocities of $x$ with respect to the basis $\mathfrak{B}$. The $j$-order derivative of the curve $v$ is given by $v^{(j)} = \sum_{i = 1}^n v_i^{(j)} e_i$, $j\geq 1$ (and is independent of the chosen basis).

If $x$ is a Riemannian heptic on $G$ then we call Lie hexic to the corresponding reduced curve $v$ in $\mathfrak{g}$. To give a characterization of Lie hexics on a Lie algebra we need to compute the expression of $T_xL_{x^{-1}}\Pi(x)$.

Higher-order covariant derivatives of the curve $x$ can be written in terms of the curve $v$ and its derivatives, as we can see for the first two covariant derivatives of the velocity vector field $V$ below.

Similar formulas can be obtained for the higher-order covariant derivatives of a vector field $Y$ along $x$. When we consider the reduced curve $y$ of $Y$ in $\mathfrak{g}$, it follows that

By taking $Y = (D/dt)V$, we obtain an expression for $\Gamma(x)$,

This gives rise to the reduced equation of Riemannian cubics,

and leads to the definition of Lie quadratics proposed by Noakes in ^[31].

We can also derive

in terms of the curve $v$ and its derivatives and, after many technical entedious computations, it is possible to obtain the reduction of the Eq (3.26) to the Lie algebra $\mathfrak{g}$.

Since the Lagrangian function $L$ of the variational problem $(\cal{P})$ is left-invariant, this reduction gives rise to the Euler-Poincaré equation for the reduced Lagrangian function $l$. Therefore, we chose to obtain the reduced equations by applying a variational principle to the Lagrangian function $l$ as we are showing in the next subsection.

4.3.   Euler-Poincaré reduction for the Riemannian heptic problem

The Lagrangian function $L$ associated with the Riemannian heptic problem $(\mathcal{P})$ on the Lie group $G$ is invariant with respect to the lift of the left translation. Under these conditions, we can define the reduced Lagrangian $l : \mathfrak{g}^4 \to {{{\rm{I\kern-.17em R}}}}$ given by the restriction of $L$ to the Lie algebra $\mathfrak{g}^4$. If we apply a variational principle to the Lagrangian function $l$ we obtain the Euler-Poincaré equations for the problem $(\mathcal{P})$.

Let $x$ be a curve in $G$. The corresponding reduced curve $v$ in the Lie algebra $\mathfrak{g}$ can be lifted to $\mathfrak{g}^4$ by considering $\left(v; v^{(1)}; v^{(2)}; v^{(3)}\right)$. If we denote the partial functional derivative of $l$ with respect to $z \in \mathfrak{g}$ by $(\delta l)/(\delta z)$, then we have that the curve $x$ in $G$ is a solution of the Euler-Lagrange equations (3.26) iff the reduced curve $v$ in $\mathfrak{g}$ is a solution of the Euler-Poincaré equations

The restriction of $L$ to $\mathfrak{g}^4$ is defined as follows:

To obtain the Euler-Poincaré equations, we begin by deriving the partial functional derivatives

Then, it follows that

If we apply the dual of the adjoint representation at $v$ to the expression given in (4.6), we conclude that

On the other hand, deriving (4.6) with respect to time, we obtain

Finally, combining Eqs (4.7) and (4.8) and applying the isomorphism $^\sharp$, we get the Euler-Poincaré equation for $l$ as follows:

Therefore, Lie hexics are the smooth curves on the Lie algebra $\mathfrak{g}$ that are solutions of the Euler-Poincaré equation (4.9). Consequently, solving Eq (4.9) together with equation $dx/dt = T_eL_{x}v$ leads to Riemannian heptics on $G$.

5.   Final remarks

In this paper, we study a fourth-order extension of the geodesic problem that appears as the most natural extension of the Riemannian cubic problem. We derive the Euler-Lagrange equation for this variational problem and obtain the concept of Riemannin heptics as a seventh-degree generalization of Riemannian cubics. These curves may, in fact, be seen as the best approximations to Riemannian cubics when the existence of cubics is conditioned by boundary or interpolation conditions, and reduce naturally to Riemannian cubics when such curves exist. From this point of view, Riemannian heptics are a more conceptual generalization of Euclidean heptic polynomials to Riemannian manifolds than the geometrical polynomials defined in ^[18,19,20].

When we specialized the problem to Lie groups, we obtained an invariant variational problem, which allowed us to derive the corresponding Euler-Poincaré equation (4.9). Hence, this equation characterizes the Lie hexics and, consequently, the Riemannian heptics on Lie groups.

Furthermore, this study shows the advantages of the Euler-Poincaré reduction. This method allows us to significantly simplify the calculations that we would have to do to reduce the Euler-Lagrange equation to the Lie algebra. In fact, it was possible to avoid deriving all the terms with four Lie brackets that would appear if we applied the reduction directly to the Euler-Lagrange equation (3.26) (see Subsection 4.2).

Use of AI tools declaration

The authors declare that they have not used artificial intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was partially supported by the Centre for Mathematics of the University of Coimbra (funded by the Portuguese Government through FCT/MCTES, DOI 10.54499/UIDB/00324/2020).

Conflict of interest

The authors declare that there are no conflicts of interest.