Source-linked AI summary
Optimal transport over a linear dynamical system
Yongxin Chen, Tryphon Georgiou, Michele Pavon
TL;DR
The paper studies minimum-energy steering of state distributions for linear systems, with and without white-noise disturbance. It reduces deterministic steering to OMT with prior dynamics, relates the stochastic problem to Schrödinger bridges, and establishes uniqueness and convergence as noise vanishes.
Problem
The problem is to steer an initial probability distribution of a linear-system state to a final distribution in finite time with minimum energy, including cases with and without stochastic disturbance.
Method
The paper transforms deterministic linear-dynamics steering into an OMT problem and studies the corresponding stochastic control problem as a Schrödinger bridge.
Results
The deterministic problem has a unique solution, while the stochastic solution converges weakly to the deterministic transport and its density flow as noise intensity tends to zero.
Takeaways & Limitations
OMT with prior dynamics extends classical OMT to constrained linear transport, and the zero-noise Schrödinger bridge provides a route to the deterministic solution.
Abstract
from arXiv · showhide
We consider the problem of steering an initial probability density for the state vector of a linear system to a final one, in finite time, using minimum energy control. In the case where the dynamics correspond to an integrator ($\dot x(t) = u(t)$) this amounts to a Monge-Kantorovich Optimal Mass Transport (OMT) problem. In general, we show that the problem can again be reduced to solving an OMT problem and that it has a unique solution. In parallel, we study the optimal steering of the state-density of a linear stochastic system with white noise disturbance; this is known to correspond to a Schrödinger bridge. As the white noise intensity tends to zero, the flow of densities converges to that of the deterministic dynamics and can serve as a way to compute the solution of its deterministic counterpart. The solution can be expressed in closed-form for Gaussian initial and final state densities in both cases.
I. INTRODUCTION
The paper formulates minimum-energy steering of linear-system state distributions, with and without stochastic disturbance, and relates these problems to OMT and Schrödinger bridges. It motivates OMT with prior dynamics as a generalization of classical OMT and establishes the paper’s main theoretical connections.
- Problem formulation: The task is to steer an initial state distribution to a final distribution over [0,1] using minimum-energy control.The system may include stochastic disturbance, and the state dynamics are linear with a controllable pair (A, B).
- Connection to OMT: For integrator dynamics, the steering problem reduces to classical OMT with quadratic cost.This corresponds to A(t) ≡ 0, B(t) ≡ I, and ϵ = 0.
- Connection to OMT: OMT with prior dynamics generalizes classical OMT by requiring transport paths to obey known nontrivial linear dynamics.The dynamics may facilitate or hinder transport, motivating applications involving particle beams, swarms, collective motion, and distribution interpolation.
- Schrödinger bridges: With stochastic disturbance, the corresponding density-steering problem is equivalent to a Schrödinger bridge.The diffusive term gives this formulation a stochastic OMT interpretation and a smoothing effect.
- Paper contributions: The paper develops OMT with prior dynamics, establishes its unique solution, and proves its connection to Schrödinger bridges and their zero-noise limit.It also treats arbitrary endpoint marginals and gives closed-form solutions for Gaussian marginals.
A. Solutions to OMT
Classical OMT admits a unique optimal transport map for absolutely continuous marginals, represented as the gradient of a convex function. Its dynamic formulation uses density and velocity fields satisfying transport optimality conditions.
- Static OMT solution: For absolutely continuous marginals, classical OMT has a unique solution and an optimal map given by the gradient of a convex function.The potential satisfies a Monge–Ampère equation involving the Hessian and endpoint densities.
- Dynamic formulation: The transport map induces displacement trajectories and intermediate densities through push-forward operations.These interpolating densities provide the time evolution between the endpoint distributions.
- Optimality conditions: A velocity field of the form v*(t,x) = ∇ψ(t,x) satisfies the sufficient optimality conditions for the dynamic OMT problem.The potential ψ may be obtained as a viscosity solution with a Hopf–Lax representation.
III. OPTIMAL MASS TRANSPORT WITH PRIOR DYNAMICS
The paper extends OMT by constraining transport paths to follow linear dynamics and by minimizing control energy. It establishes a unique solution while identifying the obstacle created by noninvertible input matrices.
- Problem formulation: The proposed generalization requires transport paths to satisfy linear dynamical constraints rather than unconstrained particle motion.The associated cost is derived from the control effort needed to steer the dynamics.
- Relation to classical OMT: The formulation reduces to classical OMT when A(t) ≡ 0 and B(t) ≡ I.In that case, the density path is the usual displacement interpolation between the two marginals.
- Reduction to OMT: When B(t) is invertible, the generalized formulation reduces to the standard OMT form through a change of variables.The reduction is not directly available when B(t) is noninvertible.
- Existence and uniqueness: When B(t) is noninvertible, the transformed Lagrangian may fail strict convexity and superlinearity, so existence and uniqueness require an independent argument.The paper establishes these properties for the quadratic control cost ˜L(t,x,u) = ∥u∥2/2.
- Problem formulation: For controllable linear dynamics, the problem seeks a minimum-energy continuous feedback law that steers ρ0 to ρ1.The problem can be recast in terms of one-time state-density functions.
- Existence and uniqueness: The paper shows directly that the OMT-with-prior-dynamics problem has a unique solution.This extends the classical OMT solution concept to transport constrained by linear dynamics.
A. Solutions to OMT-wpd
The OMT-with-prior-dynamics problem is transformed into a standard quadratic-cost OMT problem using linear-system quantities. The resulting optimal map determines the optimal trajectories and intermediate density flow.
- Endpoint reduction: The state-transition matrix and controllability Gramian provide closed-form least-energy trajectories between fixed endpoints.These quantities convert the dynamical steering cost into an endpoint transport cost.
- Endpoint reduction: The dynamical transport problem is converted to a Kantorovich OMT problem by a linear coordinate transformation.The transformed problem has a standard quadratic cost.
- Optimal map: The transformed optimal transport map exists and is the gradient of a convex function.This imports the standard quadratic-cost OMT solution structure into the prior-dynamics problem.
- Density interpolation: The original optimal map determines the system trajectories and the associated velocity field.The one-time marginals are obtained as push-forwards along the trajectory family and form the displacement interpolation with prior dynamics.
B. Variational analysis
The variational analysis derives sufficient optimality conditions for OMT with prior dynamics and constructs a solution using a Hamilton–Jacobi equation coupled to a transport equation.
- Variational formulation: The analysis minimizes a Lagrangian over admissible density flows and continuous feedback controls.Pointwise minimization over the control produces the optimality conditions.
- Optimality conditions: The optimal density satisfies a continuity equation with velocity A(t)x + B(t)B(t)′∇ψ, where ψ solves a Hamilton–Jacobi equation.The associated control is u*(t,x) = B(t)′∇ψ(t,x).
- Existence construction: A solution always exists for the coupled Hamilton–Jacobi and transport system.The construction uses the Bellman principle of optimality and verifies both equations, including the terminal condition.
- Displacement interpolation: The constructed density is the pushforward of the initial density along the displacement interpolation induced by the optimal transport map.The proof identifies the velocity field with the trajectories generated by the interpolation.
IV. SCHR ¨ODINGER BRIDGES AND THEIR ZERO-NOISE LIMIT
The section formulates Schrödinger bridges for linear stochastic dynamics and establishes their connection to optimal mass transport. As diffusion vanishes, the entropic interpolation and endpoint coupling converge to their deterministic OMT-with-prior-dynamics counterparts.
- Schrödinger bridge formulation: A Schrödinger bridge selects a path-space law matching prescribed endpoint marginals while remaining closest to a Markovian prior in relative entropy.For Brownian particles, the resulting flow is called an entropic interpolation.
- Schrödinger bridge formulation: The bridge can be computed from a unique pair of scaling measures associated with a positive Markov kernel.Those measures determine the endpoint joint law and the full distribution flow.
- Zero-noise limit: The stochastic-control formulation differs from OMT by an additional Laplacian in the Fokker–Planck constraint.After rescaling the cost, this diffusion term is the formal difference that disappears as ϵ goes to 0.
- Zero-noise limit: As ϵ goes to 0, the Schrödinger minimizers converge to the unique OMT solution.This is stated first for standard OMT and then extended to linear dynamics with prior dynamics.
- Zero-noise limit: For linear dynamics, Pϵ_01 converges weakly to the OMT-wpd coupling π and Pϵ_t converges weakly to the displacement interpolation µ_t.The result applies to endpoint measures with finite second moment.
- Computational implication: The zero-noise limit provides a way to compute OMT with prior dynamics using numerical Schrödinger-bridge algorithms.The paper notes that this algorithm differs from standard OMT numerical methods.
V. GAUSSIAN MARGINALS
For Gaussian marginals, the paper develops explicit Schrödinger-bridge expressions and takes their zero-noise limit. The limiting linear process yields a Gaussian density flow and an optimal solution to OMT with prior dynamics.
- Gaussian specialization: The Gaussian case provides closed-form expressions for the correspondence between Schrödinger bridges and OMT with prior dynamics.This specializes the general zero-noise theorem to normal endpoint marginals.
- Finite-noise bridge: The Schrödinger bridge is represented by a linear stochastic differential equation with feedback matrix Πϵ(t), affine term m(t), and noise √ϵB(t)dw(t).The matrix Πϵ(t) satisfies a Riccati differential equation with a boundary condition determined by the endpoint covariances.
- Zero-noise limit: As ϵ goes to 0, the stochastic equation becomes a deterministic linear process with drift modified by Π0(t) and m(t).The limiting process is specified by the zero-noise versions of the bridge parameters.
- Gaussian flow: The limiting process has Gaussian marginals because it is linear with Gaussian initial condition.Its mean and covariance evolve according to the corresponding linear dynamics and Lyapunov equation.
- Optimality: The density flow and associated control from the limiting process solve the OMT-wpd problem with the prescribed Gaussian marginals.The paper verifies the boundary condition and Hamilton–Jacobi optimality conditions.
VI. NUMERICAL EXAMPLES
Two examples illustrate the theory: Gaussian steering of inertial particles in a two-dimensional phase space and steering with prior dynamics for more general one-dimensional marginals.
- Gaussian example: The first example steers inertial particles in a two-dimensional phase space between Gaussian endpoint distributions using the closed-form control.It applies the Gaussian solution developed earlier.
- General-marginal example: The second example steers one-dimensional distributions with specified prior dynamics and more general endpoint marginals.In both examples, the entropic interpolations converge to the displacement interpolation.
A. Gaussian marginals
The Gaussian example steers inertial particles between joint normal endpoint distributions and compares Schrödinger-bridge interpolations with deterministic OMT-wpd and classical OMT. As diffusion decreases, the stochastic trajectories approach the deterministic OMT-wpd paths.
- The example considers inertial particles whose position and velocity are jointly normally distributed in a two-dimensional phase space.
- The task is to steer the initial joint normal distribution to a new joint normal distribution while interpolating the endpoint marginals over t ∈ [0, 1].
- Schrödinger-bridge flows are examined under stochastic forcing, with particular interest in the regime where random forcing is negligible relative to deterministic drift.
- For ϵ = 9, ϵ = 4, and ϵ = 0.01, the figures show one-time marginal flows of the Schrödinger bridge at progressively smaller diffusion levels.
- As ϵ decreases to zero, stochastic sample paths converge to the smooth OMT-wpd paths; classical OMT provides a constant-speed translation for comparison.
B. General marginals
The general-marginal example uses non-Gaussian one-dimensional endpoint distributions and compares OMT-wpd, classical OMT, and Schrödinger-bridge flows. The stochastic solution converges to OMT-wpd as diffusion vanishes.
- The second example studies particles with specified prior dynamics in a one-dimensional state space and non-Gaussian marginal distributions.
- The objective is minimum-energy steering from the initial distribution ρ0 to the final distribution ρ1, which requires solving OMT-wpd.
- In one dimension, the optimal transport map between endpoint distributions can be determined using the monotone transport construction.
- The OMT-wpd interpolation is compared with classical OMT, where particles move along straight lines.
- For diffusion levels √ϵ = 0.5, 0.3, 0.15, 0.05, and 0.01, Schrödinger-bridge flows converge to the OMT-wpd solution as ϵ → 0.
VII. RECAP
The recap presents linear-density steering as both particle herding and potential identification, generalizes classical OMT to nontrivial linear dynamics, and establishes the zero-diffusion connection between Schrödinger bridges and OMT.
- Steering a random dynamical-system state between distributions can be viewed as herding particles or identifying a potential producing the transition.
- With trivial dynamics, the problem reduces to classical OMT; the paper generalizes this setting to nontrivial linear dynamics.
- The paper develops a transformation relating the linear-dynamics Schrödinger bridge to a Brownian reference problem with transformed endpoint marginals.
- The associated path-space laws satisfy a weak-convergence relationship: Pϵ01 converges to π as ϵ goes to zero.
- The entropic interpolation Pϵt weakly converges to the displacement interpolation μt as ϵ goes to zero.
- The pinned bridge dynamics include the deterministic drift, an endpoint-dependent steering term, and the stochastic forcing term √ϵB(t)dw(t).