Optimal Boundary Control of Diffusion on Graphs via Linear Programming

• URL: http://arxiv.org/abs/2511.03129v1
• Date: Wed, 05 Nov 2025 02:41:07 GMT
• Title: Optimal Boundary Control of Diffusion on Graphs via Linear Programming
• Authors: Harbir Antil, Rainald Löhner, Felipe Pérez,
• Abstract summary: We propose a framework for steady-state diffusion and flux optimization on geometric networks.<n> Boundary potentials act as controls that drive interior flux according to a linear network Laplacian.<n>The analysis connects classical results such as the Minkowski--Weyl decomposition, Hoffman's bound, and the fundamental theorem of linear programming with modern network-based diffusion modeling.
• Score: 2.064612766965483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a linear programming (LP) framework for steady-state diffusion and flux optimization on geometric networks. The state variable satisfies a discrete diffusion law on a weighted, oriented graph, where conductances are scaled by edge lengths to preserve geometric fidelity. Boundary potentials act as controls that drive interior fluxes according to a linear network Laplacian. The optimization problem enforces physically meaningful sign and flux-cap constraints at all boundary edges, derived directly from a gradient bound. This yields a finite-dimensional LP whose feasible set is polyhedral, and whose boundedness and solvability follow from simple geometric or algebraic conditions on the network data. We prove that under the absence of negative recession directions--automatically satisfied in the presence of finite box bounds, flux caps, or sign restrictions--the LP admits a global minimizer. Several sufficient conditions guaranteeing boundedness of the feasible region are identified, covering both full-rank and rank-deficient flux maps. The analysis connects classical results such as the Minkowski--Weyl decomposition, Hoffman's bound, and the fundamental theorem of linear programming with modern network-based diffusion modeling. Two large-scale examples illustrate the framework: (i) A typical large stadium in a major modern city, which forms a single connected component with relatively uniform corridor widths, and a (ii) A complex street network emanating from a large, historical city center, which forms a multi-component system.

Related papers

• The Inductive Bias of Convolutional Neural Networks: Locality and Weight Sharing Reshape Implicit Regularization [57.37943479039033]
  We study how architectural inductive bias reshapes the implicit regularization induced by the edge-of-stability phenomenon in gradient descent.<n>We show that locality and weight sharing fundamentally change this picture.
  arXiv  Detail & Related papers  (2026-03-05T04:50:51Z)
• Variational Bayesian Flow Network for Graph Generation [54.94088904387278]
  We propose Variational Bayesian Flow Network (VBFN) for graph generation.<n>VBFN performs variational lifting to a tractable joint Gaussian variational belief family governed by structured precisions.<n>On synthetic and molecular graph datasets, VBFN improves fidelity and diversity, and surpasses baseline methods.
  arXiv  Detail & Related papers  (2026-01-30T03:59:38Z)
• Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions [5.081469534056712]
  Mean-field control (MFC) offers a scalable solution to the curse of dimensionality in multi-agent systems.<n>We bridge the gap to real-world network structures by proposing a rigorous framework for MFC on large sparse graphs.
  arXiv  Detail & Related papers  (2026-01-29T09:57:48Z)
• Solving nonlinear subsonic compressible flow in infinite domain via multi-stage neural networks [1.1317872970491056]
  In aerodynamics, accurately modeling subsonic compressible flow over airfoils is critical for aircraft design.<n>Traditional approaches often rely on linearized equations or finite, truncated domains, which introduce non-negligible errors and limit applicability in real-world scenarios.<n>We propose a novel framework utilizing Physics-Informed Networks (PINNs) to solve the full nonlinear compressible potential equation in an unbounded domain.
  arXiv  Detail & Related papers  (2026-01-01T13:46:01Z)
• Gated X-TFC: Soft Domain Decomposition for Forward and Inverse Problems in Sharp-Gradient PDEs [0.0]
  Gated X-TFC is a novel framework for both forward and inverse problems.<n>It overcomes limitations through a soft, learned domain decomposition.<n>Gated X-TFC achieves superior accuracy and dramatic improvements in computational efficiency.
  arXiv  Detail & Related papers  (2025-10-01T15:43:02Z)
• Understanding the training of infinitely deep and wide ResNets with Conditional Optimal Transport [26.47265060394168]
  We show that the gradient flow for deep neural networks converges arbitrarily at a distance ofr.<n>This is done by relying on the theory of gradient distance of finite width in spaces.
  arXiv  Detail & Related papers  (2024-03-19T16:34:31Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widths [25.237054775800164]
  This paper studies the convergence of gradient flow and gradient descent for nonlinear ReLU activated implicit networks. We prove that both GF and GD converge to a global minimum at a linear rate if the width $m$ of the implicit network is textitlinear in the sample size.
  arXiv  Detail & Related papers  (2022-05-16T06:07:56Z)
• Deep Learning Approximation of Diffeomorphisms via Linear-Control Systems [91.3755431537592]
  We consider a control system of the form $dot x = sum_i=1lF_i(x)u_i$, with linear dependence in the controls. We use the corresponding flow to approximate the action of a diffeomorphism on a compact ensemble of points.
  arXiv  Detail & Related papers  (2021-10-24T08:57:46Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Exact imposition of boundary conditions with distance functions in physics-informed deep neural networks [0.5804039129951741]
  We introduce geometry-aware trial functions in artifical neural networks to improve the training in deep learning for partial differential equations. To exactly impose homogeneous Dirichlet boundary conditions, the trial function is taken as $phi$ multiplied by the PINN approximation. We present numerical solutions for linear and nonlinear boundary-value problems over domains with affine and curved boundaries.
  arXiv  Detail & Related papers  (2021-04-17T03:02:52Z)
• Directional convergence and alignment in deep learning [38.73942298289583]
  We show that although the minimizers of cross-entropy and related classification losses at infinity, network weights learn by gradient flow converge in direction. This proof holds for deep homogeneous networks allowing for ReLU, max-pooling, linear, and convolutional layers.
  arXiv  Detail & Related papers  (2020-06-11T17:50:11Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.