Showing 1–50 of 525 results for author: Liu, S

Locally measure preserving property of bi-Lipschitz maps between Moran sets

Authors: Liang-yi Huang, Shishuang Liu

Abstract: In literature it is shown that bi-Lipschitz maps between self-similar sets or self-affine sets enjoy a locally measure preserving property, namely, if $f:(E,μ)\to (F,ν)$ is a bi-Lipschitz map, then the Radon-Nykodym derivative $df^*ν/dμ$ is a constant function on a subset $E'\subset E$ with $μ(E')>0$, where $f^*ν(\cdot)=ν(f(\cdot))$. Indeed, this measure preserving property plays an important role… ▽ More In literature it is shown that bi-Lipschitz maps between self-similar sets or self-affine sets enjoy a locally measure preserving property, namely, if $f:(E,μ)\to (F,ν)$ is a bi-Lipschitz map, then the Radon-Nykodym derivative $df^*ν/dμ$ is a constant function on a subset $E'\subset E$ with $μ(E')>0$, where $f^*ν(\cdot)=ν(f(\cdot))$. Indeed, this measure preserving property plays an important role in Lipschitz classification of fractal sets. In this paper, we show that such measure preserving property also holds for bi-Lipschitz maps between two Moran sets in a certain class. △ Less

Submitted 14 July, 2024; originally announced July 2024.

Convergence and Error Estimates of A Semi-Lagrangian scheme for the Minimum Time Problem

Authors: Marianne Akian, Shanqing Liu

Abstract: We consider a semi-Lagrangian scheme for solving the minimum time problem, with a given target, and the associated eikonal type equation. We first use a discrete time deterministic optimal control problem interpretation of the time discretization scheme, and show that the discrete time value function is semiconcave under regularity assumptions on the dynamics and the boundary of target set. We est… ▽ More We consider a semi-Lagrangian scheme for solving the minimum time problem, with a given target, and the associated eikonal type equation. We first use a discrete time deterministic optimal control problem interpretation of the time discretization scheme, and show that the discrete time value function is semiconcave under regularity assumptions on the dynamics and the boundary of target set. We establish a convergence rate of order $1$ in terms of time step based on this semiconcavity property. Then, we use a discrete time stochastic optimal control interpretation of the full discretization scheme, and we establish a convergence rate of order $1$ in terms of both time and spatial steps using certain interpolation operators, under further regularity assumptions. We extend our convergence results to problems with particular state constraints. We apply our results to analyze the convergence rate and computational complexity of the fast-marching method. We also consider the multi-level fast-marching method recently introduced by the authors. △ Less

Submitted 9 July, 2024; originally announced July 2024.

Ricci-DeTurck Flow from Initial Metric with Morrey-type Integrability Condition

Authors: Man-Chun Lee, Stephen Shang Yi Liu

Abstract: In this work, we study the short-time existence theory of Ricci-DeTurck flow starting from rough metrics which satisfy a Morrey-type integrability condition. Using the rough existence theory, we show the preservation and improvement of distributional scalar curvature lower bounds provided the singular set for such metrics is not too large. As an application, we use the Ricci flow smoothing to stud… ▽ More In this work, we study the short-time existence theory of Ricci-DeTurck flow starting from rough metrics which satisfy a Morrey-type integrability condition. Using the rough existence theory, we show the preservation and improvement of distributional scalar curvature lower bounds provided the singular set for such metrics is not too large. As an application, we use the Ricci flow smoothing to study the removable singularity for scalar curvature rigidity in the compact case under Morrey regularity conditions. Our result supplements those of Jiang-Sheng-Zhang. △ Less

Submitted 14 July, 2024; v1 submitted 9 July, 2024; originally announced July 2024.

Comments: 23 pages; abstract updated

MSC Class: 53E20

Mechanism design for coordinating vehicle-based mobile sensing tasks within the ride-hailing platform

Authors: Shenglin Liu, Qian Ge, Ke Han, Daisuke Fukuda, Takao Dantsuji

Abstract: This paper evaluates the benefit of integrating vehicle-based mobile crowd-sensing tasks into the ride-hailing system through the collaboration between the data user and the ride-hailing platform. In such a system, the ride-hailing platform commissions high-valued sensing tasks to idle drivers who can undertake either ride-hailing or sensing requests. Considering the different service requirements… ▽ More This paper evaluates the benefit of integrating vehicle-based mobile crowd-sensing tasks into the ride-hailing system through the collaboration between the data user and the ride-hailing platform. In such a system, the ride-hailing platform commissions high-valued sensing tasks to idle drivers who can undertake either ride-hailing or sensing requests. Considering the different service requirements and time windows between sensing and ride-hailing requests, we design a staggered operation strategy for ride-hailing order matching and the sensing task assignment. The auction-based mechanisms are employed to minimize costs while incentivizing driver participation in mobile sensing. To address the budget deficit problem of the primal VCG-based task assignment mechanism, we refine the driver selection approach and tailor the payment rule by imposing additional budget constraints. We demonstrate the benefits of our proposed mechanism through a series of numerical experiments using the NYC Taxi data. Experimental results reveal the potential of the mechanism for achieving high completion rates of sensing tasks at low social costs without degrading ride-hailing services. Furthermore, drivers who participate in both mobile sensing tasks and ride-hailing requests may gain higher income, but this advantage may diminish with an increasing number of such drivers and higher demand for ride-hailing services. △ Less

Submitted 1 July, 2024; originally announced July 2024.

Comments: 30 pages, 9 figures

Can independent Metropolis beat crude Monte Carlo?

Authors: Siran Liu, Petros Dellaportas, Michalis K. Titsias

Abstract: Assume that we would like to estimate the expected value of a function $F$ with respect to a density $π$. We prove that if $π$ is close enough under KL divergence to another density $q$, an independent Metropolis sampler estimator that obtains samples from $π$ with proposal density $q$, enriched with a variance reduction computational strategy based on control variates, achieves smaller asymptotic… ▽ More Assume that we would like to estimate the expected value of a function $F$ with respect to a density $π$. We prove that if $π$ is close enough under KL divergence to another density $q$, an independent Metropolis sampler estimator that obtains samples from $π$ with proposal density $q$, enriched with a variance reduction computational strategy based on control variates, achieves smaller asymptotic variance than that of the crude Monte Carlo estimator. The control variates construction requires no extra computational effort but assumes that the expected value of $F$ under $q$ is analytically available. We illustrate this result by calculating the marginal likelihood in a linear regression model with prior-likelihood conflict and a non-conjugate prior. Furthermore, we propose an adaptive independent Metropolis algorithm that adapts the proposal density such that its KL divergence with the target is being reduced. We demonstrate its applicability in a Bayesian logistic and Gaussian process regression problems and we rigorously justify our asymptotic arguments under easily verifiable and essentially minimal conditions. △ Less

Submitted 25 June, 2024; originally announced June 2024.

Comments: 37 pages, 3 figures

Chebyshev Moment Method for Regular Graphs II: Discrete Trace Formula

Authors: Yulin Gong, Wenbo Li, Shiping Liu

Abstract: We establish discrete trace formulas on a regular graph to relate its spectrum and non-backtracking walks. Our approach is based on the Chebyshev-type polynomials and we refer to this treatment as Chebyshev moment method. A key fact is that Chebyshev-type polynomials form a complete orthogonal basis with respect to the Kesten-McKay distribution. Based on this method, we further apply Cauchy's inte… ▽ More We establish discrete trace formulas on a regular graph to relate its spectrum and non-backtracking walks. Our approach is based on the Chebyshev-type polynomials and we refer to this treatment as Chebyshev moment method. A key fact is that Chebyshev-type polynomials form a complete orthogonal basis with respect to the Kesten-McKay distribution. Based on this method, we further apply Cauchy's integral formula for holomorphic functions to prove the pre-trace formula for all regular graphs and the trace formula for finite regular graphs. We further apply our results to study the resolvent, heat and Schrödinger equations, Ihara zeta functions, and combinatorial enumeration problems on regular graphs. △ Less

Submitted 25 June, 2024; originally announced June 2024.

MSC Class: 05C30; 05C31; 05C50; 05C62

The general Kastler-Kalau-Walze type theorem for the J-twist DJ of the Dirac operator

Authors: Siyao Liu, Yong Wang

Abstract: In [21] and [22], we proved the Kastler-Kalau-Walze type theorem for the J-twist DJ of the Dirac operator on 3-dimensional, 4-dimensional and 6-dimensional almost product Riemannian spin manifold with boundary. In this paper, we generalize our previous conclusions and establish the proof of the general Kastler-Kalau-Walze type theorem for the J-twist DJ of the Dirac operator on even-dimensional… ▽ More In [21] and [22], we proved the Kastler-Kalau-Walze type theorem for the J-twist DJ of the Dirac operator on 3-dimensional, 4-dimensional and 6-dimensional almost product Riemannian spin manifold with boundary. In this paper, we generalize our previous conclusions and establish the proof of the general Kastler-Kalau-Walze type theorem for the J-twist DJ of the Dirac operator on even-dimensional almost product Riemannian spin manifold with boundary. △ Less

Submitted 25 June, 2024; v1 submitted 24 June, 2024; originally announced June 2024.

Comments: 32 pages. arXiv admin note: text overlap with arXiv:2211.06602, arXiv:2203.10467, arXiv:2312.00154, arXiv:2401.10909

Energetic Spectral-Element Time Marching Methods for Phase-Field Nonlinear Gradient Systems

Authors: Shiqin Liu, Haijun Yu

Abstract: We propose two efficient energetic spectral-element methods in time for marching nonlinear gradient systems with the phase-field Allen--Cahn equation as an example: one fully implicit nonlinear method and one semi-implicit linear method. Different from other spectral methods in time using spectral Petrov-Galerkin or weighted Galerkin approximations, the presented implicit method employs an energet… ▽ More We propose two efficient energetic spectral-element methods in time for marching nonlinear gradient systems with the phase-field Allen--Cahn equation as an example: one fully implicit nonlinear method and one semi-implicit linear method. Different from other spectral methods in time using spectral Petrov-Galerkin or weighted Galerkin approximations, the presented implicit method employs an energetic variational Galerkin form that can maintain the mass conservation and energy dissipation property of the continuous dynamical system. Another advantage of this method is its superconvergence. A high-order extrapolation is adopted for the nonlinear term to get the semi-implicit method. The semi-implicit method does not have superconvergence, but can be improved by a few Picard-like iterations to recover the superconvergence of the implicit method. Numerical experiments verify that the method using Legendre elements of degree three outperforms the 4th-order implicit-explicit backward differentiation formula and the 4th-order exponential time difference Runge-Kutta method, which were known to have best performances in solving phase-field equations. In addition to the standard Allen--Cahn equation, we also apply the method to a conservative Allen--Cahn equation, in which the conservation of discrete total mass is verified. The applications of the proposed methods are not limited to phase-field Allen--Cahn equations. They are suitable for solving general, large-scale nonlinear dynamical systems. △ Less

Submitted 23 June, 2024; originally announced June 2024.

Comments: 28 pages, 10 figures

A novel dual-stage algorithm for capacitated arc routing problems with time-dependent service costs

Authors: Qingya Li, Shengcai Liu, Juan Zou, Ke Tang

Abstract: This paper focuses on solving the capacitated arc routing problem with time-dependent service costs (CARPTDSC), which is motivated by winter gritting applications. In the current literature, exact algorithms designed for CARPTDSC can only handle small-scale instances, while heuristic algorithms fail to obtain high-quality solutions. To overcome these limitations, we propose a novel dual-stage algo… ▽ More This paper focuses on solving the capacitated arc routing problem with time-dependent service costs (CARPTDSC), which is motivated by winter gritting applications. In the current literature, exact algorithms designed for CARPTDSC can only handle small-scale instances, while heuristic algorithms fail to obtain high-quality solutions. To overcome these limitations, we propose a novel dual-stage algorithm, called MAENS-GN, that consists of a routing stage and a vehicle departure time optimization stage. The former obtains the routing plan, while the the latter determines the vehicle departure time. Importantly, existing literature often ignores the characteristic information contained in the relationship between the route cost and the vehicle departure time. The most significant innovation in this paper lies in the exploitation of this characteristic information during the vehicle departure time optimization stage. Specifically, we conduct a detailed analysis of this relationship under various scenarios and employ tailored methods to obtain the (approximately) optimal vehicle departure time. Furthermore, we propose an improved initialization strategy that considers time-dependent characteristics to achieve better solution quality. In addition to the modified benchmark test sets, we also experiment on a real-world test set. Experimental results demonstrate that MAENS-GN can obtain high-quality solutions on both small-scale and larger-scale instances of CARPTDSC. △ Less

Submitted 16 May, 2024; originally announced June 2024.

Generalized multiple Borel-Cantelli Lemma in dynamics and its applications

Authors: Sixu Liu

Abstract: Multiple Borel-Cantelli Lemma is a criterion that characterizes the occurrence of multiple rare events on the same time scale. We generalize the multiple Borel-Cantelli Lemma in dynamics established by Dolgopyat, Fayad and Liu [J. Mod. Dyn. 18 (2022) 209--289], broadening its applications to encompass several non-smooth systems with absolute continuous measures. Utilizing this generalization, we d… ▽ More Multiple Borel-Cantelli Lemma is a criterion that characterizes the occurrence of multiple rare events on the same time scale. We generalize the multiple Borel-Cantelli Lemma in dynamics established by Dolgopyat, Fayad and Liu [J. Mod. Dyn. 18 (2022) 209--289], broadening its applications to encompass several non-smooth systems with absolute continuous measures. Utilizing this generalization, we derive multiple Logarithm Law for hitting time and recurrence of dispersing billiard maps and piecewise expanding maps under some regular conditions, including tent map, Lorentz-like map and Gauss map. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Asymptotics of two-dimensional hydroelastic waves: The zero mass, zero bending limit

Authors: Shunlian Liu, David M. Ambrose

Abstract: We consider two-dimensional hydroelastic waves, in which a free fluid surface separates two fluids of infinite vertical extent. Elastic effects are accounted for at the interface, with a parameter measuring the elastic bending force and another parameter measuring the mass of the elastic sheet. In prior work, the authors have demonstrated well-posedness of this initial value problem in Sobolev spa… ▽ More We consider two-dimensional hydroelastic waves, in which a free fluid surface separates two fluids of infinite vertical extent. Elastic effects are accounted for at the interface, with a parameter measuring the elastic bending force and another parameter measuring the mass of the elastic sheet. In prior work, the authors have demonstrated well-posedness of this initial value problem in Sobolev spaces. We now take the limit as these two parameters vanish. Since the size of the time interval of existence given by this prior theory vanishes as the mass and bending parameters go to zero, we now establish estimates which are uniform with respect to these parameters. We may then make an additional estimate which demonstrates that the solutions form a Cauchy sequence as the parameters go to zero, so that the limit may be taken. This demonstrates that the vortex sheet with surface tension is the zero mass, zero bending limit of hydroelastic waves in two spatial dimensions. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Comments: 40 pages

MSC Class: 35Q35; 35B40; 35Q31; 76B07; 76B45

Multigrid preconditioning for discontinuous Galerkin discretizations of an elliptic optimal control problem with a convection-dominated state equation

Authors: Sijing Liu, Valeria Simoncini

Abstract: We consider discontinuous Galerkin methods for an elliptic distributed optimal control problem constrained by a convection-dominated problem. We prove global optimal convergence rates using an inf-sup condition, with the diffusion parameter $\varepsilon$ and regularization parameter $β$ explicitly tracked. We then propose a multilevel preconditioner based on downwind ordering to solve the discreti… ▽ More We consider discontinuous Galerkin methods for an elliptic distributed optimal control problem constrained by a convection-dominated problem. We prove global optimal convergence rates using an inf-sup condition, with the diffusion parameter $\varepsilon$ and regularization parameter $β$ explicitly tracked. We then propose a multilevel preconditioner based on downwind ordering to solve the discretized system. The preconditioner only requires two approximate solves of single convection-dominated equations using multigrid methods. Moreover, for the strongly convection-dominated case, only two sweeps of block Gauss-Seidel iterations are needed. We also derive a simple bound indicating the role played by the multigrid preconditioner. Numerical results are shown to support our findings. △ Less

Submitted 13 June, 2024; originally announced June 2024.

MSC Class: 49J20; 49M41; 65N30; 65N55

Chebyshev Moment Method for Regular Graphs I: Kesten-McKay and Semicircle distributions

Authors: Yulin Gong, Wenbo Li, Shiping Liu

Abstract: We develop the Chebyshev moment method to study the spectrum of regular graphs, motivated by the work of Serré. By this method, we give an elementary proof of the weak convergence to the Kesten-McKay distribution for the normalized spectral measures of random $N$-lifts in probability as $N$ tends to infinity. For a sequence of random $(q_n+1)$-regular graphs $G_n$ with $n$ vertices, we show that i… ▽ More We develop the Chebyshev moment method to study the spectrum of regular graphs, motivated by the work of Serré. By this method, we give an elementary proof of the weak convergence to the Kesten-McKay distribution for the normalized spectral measures of random $N$-lifts in probability as $N$ tends to infinity. For a sequence of random $(q_n+1)$-regular graphs $G_n$ with $n$ vertices, we show that if $q_n=n^{o(1)}$ and $q_n$ tends to infinity, then the normalized spectral measure converges in Wasserstein $p$-distance $W_{p}$ to the semicircle distribution for any $p \in [1,\infty)$ almost surely. This strengthens the result of Dumitriu and Pal. △ Less

Submitted 9 June, 2024; originally announced June 2024.

MSC Class: 05C31; 05C50; 05C80; 60B20

Generalization Bound and New Algorithm for Clean-Label Backdoor Attack

Authors: Lijia Yu, Shuang Liu, Yibo Miao, Xiao-Shan Gao, Lijun Zhang

Abstract: The generalization bound is a crucial theoretical tool for assessing the generalizability of learning methods and there exist vast literatures on generalizability of normal learning, adversarial learning, and data poisoning. Unlike other data poison attacks, the backdoor attack has the special property that the poisoned triggers are contained in both the training set and the test set and the purpo… ▽ More The generalization bound is a crucial theoretical tool for assessing the generalizability of learning methods and there exist vast literatures on generalizability of normal learning, adversarial learning, and data poisoning. Unlike other data poison attacks, the backdoor attack has the special property that the poisoned triggers are contained in both the training set and the test set and the purpose of the attack is two-fold. To our knowledge, the generalization bound for the backdoor attack has not been established. In this paper, we fill this gap by deriving algorithm-independent generalization bounds in the clean-label backdoor attack scenario. Precisely, based on the goals of backdoor attack, we give upper bounds for the clean sample population errors and the poison population errors in terms of the empirical error on the poisoned training dataset. Furthermore, based on the theoretical result, a new clean-label backdoor attack is proposed that computes the poisoning trigger by combining adversarial noise and indiscriminate poison. We show its effectiveness in a variety of settings. △ Less

Submitted 1 June, 2024; originally announced June 2024.

Normed modules and The Stieltjes integrations of functions defined on finite-dimensional algebras

Authors: Hanpeng Gao, Shengda Liu, Yu-Zhe Liu, Yucheng Wang

Abstract: We define integrals for functions on finite-dimensional algebras, adapting methods from Leinster's research. This paper discusses the relationships between the integrals of functions defined on subsets $\mathbb{I}_1 \subseteq {\mathitΛ}_1$ and $\mathbb{I}_2 \subseteq {\mathitΛ}_2$ of two finite-dimensional algebras, under the influence of a mapping $ω$, which can be an injection or a bijection. We… ▽ More We define integrals for functions on finite-dimensional algebras, adapting methods from Leinster's research. This paper discusses the relationships between the integrals of functions defined on subsets $\mathbb{I}_1 \subseteq {\mathitΛ}_1$ and $\mathbb{I}_2 \subseteq {\mathitΛ}_2$ of two finite-dimensional algebras, under the influence of a mapping $ω$, which can be an injection or a bijection. We explore four specific cases: $\bullet$ $ω$ as a monotone non-decreasing and right-continuous function; $\bullet$ $ω$ as an injective, absolutely continuous function; $\bullet$ $ω$ as a bijection; $\bullet$ and $ω$ as the identity on $\mathbb{R}$. These scenarios correspond to the frameworks of Lebesgue-Stieltjes integration, Riemann-Stieltjes integration, substitution rules for Lebesgue integrals, and traditional Lebesgue or Riemann integration, respectively. △ Less

Submitted 31 May, 2024; originally announced June 2024.

Comments: 23 pages

MSC Class: 16G10; 46B99; 46M40

Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise

Authors: Rishabh Dudeja, Songbin Liu, Junjie Ma

Abstract: We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise. We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit. At each iteration, these algorithms exploit prior knowle… ▽ More We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise. We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit. At each iteration, these algorithms exploit prior knowledge about the noise structure by applying a non-linear matrix denoiser to the eigenvalues of the observed matrix and prior information regarding the signal structure by applying a non-linear iterate denoiser to the previous iterates generated by the algorithm. We exploit our result on the dynamics of these algorithms to derive the optimal choices for the matrix and iterate denoisers. We show that the resulting algorithm achieves the smallest possible asymptotic estimation error among a broad class of iterative algorithms under a fixed iteration budget. △ Less

Submitted 28 May, 2024; originally announced May 2024.

Convergence analysis of a weak Galerkin finite element method on a Bakhvalov-type mesh for a singularly perturbed convection-diffusion equation in 2D

Authors: Shicheng Liu, Xiangyun Meng, Qilong Zhai

Abstract: In this paper, we propose a weak Galerkin finite element method (WG) for solving singularly perturbed convection-diffusion problems on a Bakhvalov-type mesh in 2D. Our method is flexible and allows the use of discontinuous approximation functions on the meshe. An error estimate is devised in a suitable norm and the optimal convergence order is obtained. Finally, numerical experiments are given to… ▽ More In this paper, we propose a weak Galerkin finite element method (WG) for solving singularly perturbed convection-diffusion problems on a Bakhvalov-type mesh in 2D. Our method is flexible and allows the use of discontinuous approximation functions on the meshe. An error estimate is devised in a suitable norm and the optimal convergence order is obtained. Finally, numerical experiments are given to support the theory and to show the efficiency of the proposed method. △ Less

Submitted 23 May, 2024; originally announced May 2024.

Optimal asymptotic volume ratio for noncompact 3-manifolds with asymptotically nonnegative Ricci curvature and a uniformly positive scalar curvature lower bound

Authors: Xian-Tao Huang, Shuai Liu

Abstract: In this paper, we study 3-dimensional complete non-compact Riemannian manifolds with asymptotically nonnegative Ricci curvature and a uniformly positive scalar curvature lower bound. Our main result is that, if this manifold has $k$ ends and finite first Betti number, then it has at most linear volume growth, and furthermore, if the negative part of Ricci curvature decays sufficiently fast at infi… ▽ More In this paper, we study 3-dimensional complete non-compact Riemannian manifolds with asymptotically nonnegative Ricci curvature and a uniformly positive scalar curvature lower bound. Our main result is that, if this manifold has $k$ ends and finite first Betti number, then it has at most linear volume growth, and furthermore, if the negative part of Ricci curvature decays sufficiently fast at infinity, then we have an optimal asymptotic volume ratio $\limsup_{r\rightarrow\infty}\frac{\mathrm{Vol}(B(p, r))}{r}\leq4kπ$. In particular, our results apply to 3-dimensional complete non-compact Riemannian manifolds with nonnegative Ricci curvature and a uniformly positive scalar curvature lower bound. △ Less

Submitted 5 June, 2024; v1 submitted 15 May, 2024; originally announced May 2024.

Comments: 21 pages. Some improvements on the main theorem: In (2) of Theorem 1.6, the assumption on the positive function f is weaken to $\int_{0}^{\infty}rf(r)dr<\infty$. Other minor changes in the exposition

Principal eigenvalue for some elliptic operators with large drift: Neumann boundary conditions

Authors: Shuang Liu, Yuan Lou, Maolin Zhou

Abstract: The paper is concerned with the principal eigenvalue of some linear elliptic operators with drift in two dimensional space. We provide a refined description of the asymptotic behavior for the principal eigenvalue as the drift rate approaches infinity. Under some non-degeneracy assumptions, our results illustrate that these asymptotic behaviors are completely determined by some connected components… ▽ More The paper is concerned with the principal eigenvalue of some linear elliptic operators with drift in two dimensional space. We provide a refined description of the asymptotic behavior for the principal eigenvalue as the drift rate approaches infinity. Under some non-degeneracy assumptions, our results illustrate that these asymptotic behaviors are completely determined by some connected components in the omega-limit set of the system of ordinary differential equations associated with the drift term, which includes stable fixed points, stable limit cycles, hyperbolic saddles connecting homoclinic orbits, and families of closed orbits. Some discussions on degenerate cases are also included. △ Less

Submitted 15 May, 2024; v1 submitted 14 May, 2024; originally announced May 2024.

Comments: 53 pages, 9 figures

MSC Class: 35P15; 35P20; 34C25

Fukaya categories of hyperplane arrangements

Authors: Sukjoo Lee, Yin Li, Si-Yang Liu, Cheuk Yu Mak

Abstract: To a simple polarized hyperplane arrangement (not necessarily cyclic) $\mathbb{V}$, one can associate a stopped Liouville manifold (equivalently, a Liouville sector) $\left(M(\mathbb{V}),ξ\right)$, where $M(\mathbb{V})$ is the complement of finitely many hyperplanes in $\mathbb{C}^d$, obtained as the complexifications of the real hyperplanes in $\mathbb{V}$. The Liouville structure on… ▽ More To a simple polarized hyperplane arrangement (not necessarily cyclic) $\mathbb{V}$, one can associate a stopped Liouville manifold (equivalently, a Liouville sector) $\left(M(\mathbb{V}),ξ\right)$, where $M(\mathbb{V})$ is the complement of finitely many hyperplanes in $\mathbb{C}^d$, obtained as the complexifications of the real hyperplanes in $\mathbb{V}$. The Liouville structure on $M(\mathbb{V})$ comes from a very affine embedding, and the stop $ξ$ is determined by the polarization. In this article, we study the symplectic topology of $\left(M(\mathbb{V}),ξ\right)$. In particular, we prove that their partially wrapped Fukaya categories are generated by Lagrangian submanifolds associated to the bounded and feasible chambers of $\mathbb{V}$. A computation of the Fukaya $A_\infty$-algebra of these Lagrangians then enables us to identity these wrapped Fukaya categories with the $\mathbb{G}_m^d$-equivariant hypertoric convolution algebras $\widetilde{B}(\mathbb{V})$ associated to $\mathbb{V}$. This confirms a conjecture of Lauda-Licata-Manion (arXiv:2009.03981) and provides evidence for the general conjecture of Lekili-Segal (arXiv:2304.10969) on the equivariant Fukaya categories of symplectic manifolds with Hamiltonian torus actions. △ Less

Submitted 3 June, 2024; v1 submitted 9 May, 2024; originally announced May 2024.

Comments: Fix graphical issues, add some references and expand some of the expositions in section 3. Comments welcome!

MSC Class: 53D40(Primary); 14M25(Secondary)

Normed modules and the categorization of Lebesgue integration

Authors: Yu-Zhe Liu, Shengda Liu, Zhaoyong Huang, Panyue Zhou

Abstract: We explore the assignment of norms to $Λ$-modules over a finite-dimensional algebra $Λ$, resulting in the establishment of normed $Λ$-modules. Our primary contribution lies in constructing a new category $\mathscr{N}\!\!or^p$ related to normed modules along with its full subcategory $\mathscr{A}^p$. By examining the objects and morphisms in these categories, we establish a framework for understand… ▽ More We explore the assignment of norms to $Λ$-modules over a finite-dimensional algebra $Λ$, resulting in the establishment of normed $Λ$-modules. Our primary contribution lies in constructing a new category $\mathscr{N}\!\!or^p$ related to normed modules along with its full subcategory $\mathscr{A}^p$. By examining the objects and morphisms in these categories, we establish a framework for understanding the categorization of Lebesgue integration. △ Less

Submitted 4 May, 2024; originally announced May 2024.

Comments: 36 pages, 1 figures

MSC Class: 16G10; 46B99; 46M40

Parameterized Wasserstein Gradient Flow

Authors: Yijie Jin, Shu Liu, Hao Wu, Xiaojing Ye, Haomin Zhou

Abstract: We develop a fast and scalable numerical approach to solve Wasserstein gradient flows (WGFs), particularly suitable for high-dimensional cases. Our approach is to use general reduced-order models, like deep neural networks, to parameterize the push-forward maps such that they can push a simple reference density to the one solving the given WGF. The new dynamical system is called parameterized WGF… ▽ More We develop a fast and scalable numerical approach to solve Wasserstein gradient flows (WGFs), particularly suitable for high-dimensional cases. Our approach is to use general reduced-order models, like deep neural networks, to parameterize the push-forward maps such that they can push a simple reference density to the one solving the given WGF. The new dynamical system is called parameterized WGF (PWGF), and it is defined on the finite-dimensional parameter space equipped with a pullback Wasserstein metric. Our numerical scheme can approximate the solutions of WGFs for general energy functionals effectively, without requiring spatial discretization or nonconvex optimization procedures, thus avoiding some limitations of classical numerical methods and more recent deep-learning-based approaches. A comprehensive analysis of the approximation errors measured by Wasserstein distance is also provided in this work. Numerical experiments show promising computational efficiency and verified accuracy on various WGF examples using our approach. △ Less

Submitted 22 May, 2024; v1 submitted 29 April, 2024; originally announced April 2024.

A note on Steinerberger's curvature for graphs

Authors: David Cushing, Supanat Kamtue, Erin Law, Shiping Liu, Florentin Münch, Norbert Peyerimhoff

Abstract: In this note, we provide Steinerberger curvature formulas for block graphs, discuss curvature relations between two graphs and the graph obtained by connecting them via a bridge, and show that self-centered Bonnet-Myers sharp graphs are precisely those which are antipodal. We also discuss similarities and differences between Steinerberger and Ollivier Ricci curvature results. In this note, we provide Steinerberger curvature formulas for block graphs, discuss curvature relations between two graphs and the graph obtained by connecting them via a bridge, and show that self-centered Bonnet-Myers sharp graphs are precisely those which are antipodal. We also discuss similarities and differences between Steinerberger and Ollivier Ricci curvature results. △ Less

Submitted 27 April, 2024; originally announced April 2024.

Curvature, diameter and signs of graphs

Authors: Wei Chen, Shiping Liu

Abstract: We prove a Li-Yau type eigenvalue-diameter estimate for signed graphs. That is, the nonzero eigenvalues of the Laplacian of a non-negatively curved signed graph are lower bounded by $1/D^2$ up to a constant, where $D$ stands for the diameter. This leads to several interesting applications, including a volume estimate for non-negatively curved signed graphs in terms of frustration index and diamete… ▽ More We prove a Li-Yau type eigenvalue-diameter estimate for signed graphs. That is, the nonzero eigenvalues of the Laplacian of a non-negatively curved signed graph are lower bounded by $1/D^2$ up to a constant, where $D$ stands for the diameter. This leads to several interesting applications, including a volume estimate for non-negatively curved signed graphs in terms of frustration index and diameter, and a two-sided Li-Yau estimate for triangle-free graphs. Our proof is built upon a combination of Chung-Lin-Yau type gradient estimate and a new trick involving strong nodal domain walks of signed graphs. We further discuss extensions of part of our results to nonlinear Laplacians on signed graphs. △ Less

Submitted 23 April, 2024; originally announced April 2024.

Comments: 28 pages, 2 figures. All comments are welcome

Control Theoretic Approach to Fine-Tuning and Transfer Learning

Authors: Erkan Bayram, Shenyu Liu, Mohamed-Ali Belabbas, Tamer Başar

Abstract: Given a training set in the form of a paired $(\mathcal{X},\mathcal{Y})$, we say that the control system $\dot x = f(x,u)$ has learned the paired set via the control $u^*$ if the system steers each point of $\mathcal{X}$ to its corresponding target in $\mathcal{Y}$. If the training set is expanded, most existing methods for finding a new control $u^*$ require starting from scratch, resulting in a… ▽ More Given a training set in the form of a paired $(\mathcal{X},\mathcal{Y})$, we say that the control system $\dot x = f(x,u)$ has learned the paired set via the control $u^*$ if the system steers each point of $\mathcal{X}$ to its corresponding target in $\mathcal{Y}$. If the training set is expanded, most existing methods for finding a new control $u^*$ require starting from scratch, resulting in a quadratic increase in complexity with the number of points. To overcome this limitation, we introduce the concept of $\textit{ tuning without forgetting}$. We develop $\textit{an iterative algorithm}$ to tune the control $u^*$ when the training set expands, whereby points already in the paired set are still matched, and new training samples are learned. At each update of our method, the control $u^*$ is projected onto the kernel of the end-point mapping generated by the controlled dynamics at the learned samples. It ensures keeping the end-points for the previously learned samples constant while iteratively learning additional samples. △ Less

Submitted 19 May, 2024; v1 submitted 16 April, 2024; originally announced April 2024.

Convergence analysis of novel discontinuous Galerkin methods for a convection dominated problem

Authors: Satyajith Bommana Boyana, Thomas Lewis, Sijing Liu, Yi Zhang

Abstract: In this paper, we propose and analyze a numerically stable and convergent scheme for a convection-diffusion-reaction equation in the convection-dominated regime. Discontinuous Galerkin (DG) methods are considered since standard finite element methods for the convection-dominated equation cause spurious oscillations. We choose to follow a novel DG finite element differential calculus framework intr… ▽ More In this paper, we propose and analyze a numerically stable and convergent scheme for a convection-diffusion-reaction equation in the convection-dominated regime. Discontinuous Galerkin (DG) methods are considered since standard finite element methods for the convection-dominated equation cause spurious oscillations. We choose to follow a novel DG finite element differential calculus framework introduced in Feng et al. (2016) and approximate the infinite-dimensional operators in the equation with the finite-dimensional DG differential operators. Specifically, we construct the numerical method by using the dual-wind discontinuous Galerkin (DWDG) formulation for the diffusive term and the average discrete gradient operator for the convective term along with standard DG stabilization. We prove that the method converges optimally in the convection-dominated regime. Numerical results are provided to support the theoretical findings. △ Less

Submitted 9 April, 2024; originally announced April 2024.

MSC Class: 65N30

Entropic curvature not comparable to other curvatures -- or is it?

Authors: Supanat Kamtue, Shiping Liu, Florentin Münch, Norbert Peyerimhoff

Abstract: In this paper we consider global $θ$-curvatures of finite Markov chains with associated means $θ$ in the spirit of the entropic curvature (based on the logarithmic mean) by Erbar-Maas and Mielke. As in the case of Bakry-Émery curvature, we also allow for a finite dimension parameter by making use of an adapted $Γ$ calculus for $θ$-curvatures. We prove explicit positive lower curvature bounds (both… ▽ More In this paper we consider global $θ$-curvatures of finite Markov chains with associated means $θ$ in the spirit of the entropic curvature (based on the logarithmic mean) by Erbar-Maas and Mielke. As in the case of Bakry-Émery curvature, we also allow for a finite dimension parameter by making use of an adapted $Γ$ calculus for $θ$-curvatures. We prove explicit positive lower curvature bounds (both finite- and infinite-dimensional) for finite abelian Cayley graphs. In the case of cycles, we provide also an upper curvature bound which shows that our lower bounds are asymptotically sharp (up to a logarithmic factor). Moreover, we prove new universal lower curvature bounds for finite Markov chains as well as curvature perturbation results (allowing, in particular, to compare entropic and Bakry-Émery curvatures). Finally, we present examples where entropic curvature differs significantly from other curvature notions like Bakry-Émery curvature or Ollivier Ricci and sectional curvatures. △ Less

Submitted 6 April, 2024; originally announced April 2024.

MSC Class: 53C21; 60J10; 05C81

Improved model-free bounds for multi-asset options using option-implied information and deep learning

Authors: Evangelia Dragazi, Shuaiqiang Liu, Antonis Papapantoleon

Abstract: We consider the computation of model-free bounds for multi-asset options in a setting that combines dependence uncertainty with additional information on the dependence structure. More specifically, we consider the setting where the marginal distributions are known and partial information, in the form of known prices for multi-asset options, is also available in the market. We provide a fundamenta… ▽ More We consider the computation of model-free bounds for multi-asset options in a setting that combines dependence uncertainty with additional information on the dependence structure. More specifically, we consider the setting where the marginal distributions are known and partial information, in the form of known prices for multi-asset options, is also available in the market. We provide a fundamental theorem of asset pricing in this setting, as well as a superhedging duality that allows to transform the maximization problem over probability measures in a more tractable minimization problem over trading strategies. The latter is solved using a penalization approach combined with a deep learning approximation using artificial neural networks. The numerical method is fast and the computational time scales linearly with respect to the number of traded assets. We finally examine the significance of various pieces of additional information. Empirical evidence suggests that "relevant" information, i.e. prices of derivatives with the same payoff structure as the target payoff, are more useful that other information, and should be prioritized in view of the trade-off between accuracy and computational efficiency. △ Less

Submitted 2 April, 2024; originally announced April 2024.

MSC Class: 91G20; 91G60; 68T07

Normal approximation for exponential random graphs

Authors: Xiao Fang, Song-Hao Liu, Qi-Man Shao

Abstract: The question of whether the central limit theorem (CLT) holds for the total number of edges in exponential random graph models (ERGMs) in the subcritical region of parameters has remained an open problem. In this paper, we establish the CLT in a subset of the subcritical region known as Dobrushin's uniqueness region. As a result of our proof, we also derive a convergence rate for the CLT and an ex… ▽ More The question of whether the central limit theorem (CLT) holds for the total number of edges in exponential random graph models (ERGMs) in the subcritical region of parameters has remained an open problem. In this paper, we establish the CLT in a subset of the subcritical region known as Dobrushin's uniqueness region. As a result of our proof, we also derive a convergence rate for the CLT and an explicit formula for the asymptotic variance. To establish our main result, we develop Stein's method for the normal approximation for general functionals of nonlinear exponential families of random variables, which is of independent interest. In addition to ERGM, our general theorem can also be applied to other models. △ Less

Submitted 2 April, 2024; originally announced April 2024.

Comments: 27 pages

MSC Class: 60F05; 05C80

A second-order correction method for loosely coupled discretizations applied to parabolic-parabolic interface problems

Authors: Erik Burman, Rebecca Durst, Miguel A. Fernández, Johnny Guzmán, Sijing Liu

Abstract: We consider a parabolic-parabolic interface problem and construct a loosely coupled prediction-correction scheme based on the Robin-Robin splitting method analyzed in [J. Numer. Math., 31(1):59--77, 2023]. We show that the errors of the correction step converge at $\mathcal O((Δt)^2)$, under suitable convergence rate assumptions on the discrete time derivative of the prediction step, where $Δt$ st… ▽ More We consider a parabolic-parabolic interface problem and construct a loosely coupled prediction-correction scheme based on the Robin-Robin splitting method analyzed in [J. Numer. Math., 31(1):59--77, 2023]. We show that the errors of the correction step converge at $\mathcal O((Δt)^2)$, under suitable convergence rate assumptions on the discrete time derivative of the prediction step, where $Δt$ stands for the time-step length. Numerical results are shown to support our analysis and the assumptions. △ Less

Submitted 1 April, 2024; originally announced April 2024.

Estimates of discrete time derivatives for the parabolic-parabolic Robin-Robin coupling method

Authors: Erik Burman, Rebecca Durst, Miguel A. Fernández, Johnny Guzmán, Sijing Liu

Abstract: We consider a loosely coupled, non-iterative Robin-Robin coupling method proposed and analyzed in [J. Numer. Math., 31(1):59--77, 2023] for a parabolic-parabolic interface problem and prove estimates for the discrete time derivatives of the scalar field in different norms. When the interface is flat and perpendicular to two of the edges of the domain we prove error estimates in the $H^2$-norm. Suc… ▽ More We consider a loosely coupled, non-iterative Robin-Robin coupling method proposed and analyzed in [J. Numer. Math., 31(1):59--77, 2023] for a parabolic-parabolic interface problem and prove estimates for the discrete time derivatives of the scalar field in different norms. When the interface is flat and perpendicular to two of the edges of the domain we prove error estimates in the $H^2$-norm. Such estimates are key ingredients to analyze a defect correction method for the parabolic-parabolic interface problem. Numerical results are shown to support our findings. △ Less

Submitted 1 April, 2024; originally announced April 2024.

Auxiliary-Variable Adaptive Control Lyapunov Barrier Functions for Spatio-Temporally Constrained Safety-Critical Applications

Authors: Shuo Liu, Wei Xiao, Calin A. Belta

Abstract: Recent work has shown that stabilizing an affine control system while optimizing a quadratic cost subject to state and control constraints can be mapped to a sequence of Quadratic Programs (QPs) using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). One of the main challenges in this method is that the QPs could easily become infeasible under safety and spatio-temporal const… ▽ More Recent work has shown that stabilizing an affine control system while optimizing a quadratic cost subject to state and control constraints can be mapped to a sequence of Quadratic Programs (QPs) using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). One of the main challenges in this method is that the QPs could easily become infeasible under safety and spatio-temporal constraints with tight control bounds. In our own recent work, we defined Auxiliary-Variable Adaptive CBFs (AVCBFs) to improve the feasibility of the CBF-based QP, while avoiding extensive parameter tuning. In this paper, we consider spatio-temporal constraints as finite-time reachability requirements. In order to satisfy these requirements, we generalize AVCBFs to Auxiliary-Variable Adaptive Control Lyapunov Barrier Functions (AVCLBFs) that work for systems and constraints with arbitrary relative degrees. We show that our method has fewer conflicts with safety and input constraints, and outperforms the state of the art in term of adaptivity and feasibility in solving the QP. We illustrate our approach on an optimal control problem for a unicycle. △ Less

Submitted 31 March, 2024; originally announced April 2024.

Comments: 8 pages, 4 figures. arXiv admin note: text overlap with arXiv:2310.00238

Monotone inclusion methods for a class of second-order non-potential mean-field games

Authors: Levon Nurbekyan, Siting Liu, Yat Tin Chow

Abstract: We propose a monotone splitting algorithm for solving a class of second-order non-potential mean-field games. Following [Achdou, Capuzzo-Dolcetta, "Mean Field Games: Numerical Methods," SINUM (2010)], we introduce a finite-difference scheme and observe that the scheme represents first-order optimality conditions for a primal-dual pair of monotone inclusions. Based on this observation, we prove tha… ▽ More We propose a monotone splitting algorithm for solving a class of second-order non-potential mean-field games. Following [Achdou, Capuzzo-Dolcetta, "Mean Field Games: Numerical Methods," SINUM (2010)], we introduce a finite-difference scheme and observe that the scheme represents first-order optimality conditions for a primal-dual pair of monotone inclusions. Based on this observation, we prove that the finite-difference system obtains a solution that can be provably recovered by an extension of the celebrated primal-dual hybrid gradient (PDHG) algorithm. △ Less

Submitted 29 March, 2024; originally announced March 2024.

MSC Class: Primary; 35Q89; 65M06; 35A15; 49N80; Secondary; 35Q91; 35Q93; 91A16; 93A15; 93A16

Safety-Critical Planning and Control for Dynamic Obstacle Avoidance Using Control Barrier Functions

Authors: Shuo Liu, Yihui Mao

Abstract: Dynamic obstacle avoidance is a challenging topic for optimal control and optimization-based trajectory planning problems, especially when in a tight environment. Many existing works use control barrier functions (CBFs) to enforce safety constraints within control systems. Inside these works, CBFs are usually formulated under model predictive control (MPC) framework to anticipate future states and… ▽ More Dynamic obstacle avoidance is a challenging topic for optimal control and optimization-based trajectory planning problems, especially when in a tight environment. Many existing works use control barrier functions (CBFs) to enforce safety constraints within control systems. Inside these works, CBFs are usually formulated under model predictive control (MPC) framework to anticipate future states and make informed decisions, or integrated with path planning algorithms as a safety enhancement tool. However, these approaches usually require knowledge of the obstacle boundary equations or have very slow computational efficiency. In this paper, we propose a novel framework to the iterative MPC with discrete-time CBFs (DCBFs) to generate a collision-free trajectory. The DCBFs are obtained from convex polyhedra generated in sequential grid maps, without the need to know the boundary equations of obstacles. Additionally, a path planning algorithm is incorporated into this framework to ensure the global optimality of the generated trajectory. We demonstrate through numerical examples that our framework enables a unicycle robot to safely and efficiently navigate through tight and dynamically changing environments, tackling both convex and nonconvex obstacles with remarkable computing efficiency and reliability in control and trajectory generation. △ Less

Submitted 27 March, 2024; originally announced March 2024.

Comments: 9 pages, 4 figures. arXiv admin note: text overlap with arXiv:2210.04361

The Share-a-Ride Problem with mixed ride-hailing and logistic vehicles

Authors: Wen Ji, Shenglin Liu, Ke Han, Tao Liu

Abstract: This study explores the potential of using ride-hailing vehicles (RVs) for integrated passenger and freight transport based on shared mobility. In this crowd-sourced mode, ride-hailing platforms can profit from parcel delivery services, and logistics companies can reduce operational costs by utilizing the capacities of RVs. The Share-a-Ride problem with ride-hailing and logistic vehicles (SARP-RL)… ▽ More This study explores the potential of using ride-hailing vehicles (RVs) for integrated passenger and freight transport based on shared mobility. In this crowd-sourced mode, ride-hailing platforms can profit from parcel delivery services, and logistics companies can reduce operational costs by utilizing the capacities of RVs. The Share-a-Ride problem with ride-hailing and logistic vehicles (SARP-RL) determines the number of logistic vehicles (LVs) and the assignment of passenger/parcel requests to RVs and LVs, aiming at maximizing the total RV profits and minimizing logistic costs. An exact solution framework is proposed by (1) generating a feasible trip that serves a given set of requests at maximal profits; (2) generating all feasible trips for the entire set of passenger and parcel requests via an efficient enumeration method; and (3) finding all Pareto-optimal solutions of the bi-objective problem via an $\varepsilon$-constraint method. Not only is the proposed method exact, it also converts the NP-hard problem to a simple vehicle-trip matching problem. More importantly, the total computational time can be compressed to an arbitrary degree via straightforward parallelization. A case study of the Manhattan network demonstrates the solution characteristics of SARP-RL. The results indicate that: (i) Coordinating RV and LV operations to serve passenger and parcel requests (SARP-RL) can simultaneously reduce logistic costs and increase RV profits. (ii) Key factors influencing the performance of SARP-RL include the RV fleet size, spatial distribution of parcel requests, passenger/parcel request ratio, and unit price of transport service, which are quantitatively analyzed to offer managerial insights for real-world implementation. △ Less

Submitted 18 March, 2024; originally announced March 2024.

Comments: 27 pages, 11 figures

Anomaly cancellation formulas and E_8 bundles for almost complex manifolds

Authors: Siyao Liu, Yong Wang

Abstract: In this paper, we extend the elliptic genus in [10] by the gauge group E_8 and the gauge group E_8*E_8. Then we prove that the generalized elliptic genus are the weak Jacobi forms. Using these elliptic genus, we obtain some SL_2(Z) modular forms and get some new anomaly cancellation formulas of characteristic forms for almost complex manifolds. In this paper, we extend the elliptic genus in [10] by the gauge group E_8 and the gauge group E_8*E_8. Then we prove that the generalized elliptic genus are the weak Jacobi forms. Using these elliptic genus, we obtain some SL_2(Z) modular forms and get some new anomaly cancellation formulas of characteristic forms for almost complex manifolds. △ Less

Submitted 15 March, 2024; originally announced March 2024.

Comments: 26 pages

Managing Distributional Ambiguity in Stochastic Optimization through a Statistical Upper Bound Framework

Authors: Shixin Liu, Jian Hu

Abstract: Stochastic optimization is often hampered by distributional ambiguity, where critical probability distributions are poorly characterized or unknown. Addressing this challenge, we introduce a new framework that targets the minimization of a statistical upper bound for the expected value of uncertain objectives, facilitating more statistically robust decision-making. Central to our approach is the A… ▽ More Stochastic optimization is often hampered by distributional ambiguity, where critical probability distributions are poorly characterized or unknown. Addressing this challenge, we introduce a new framework that targets the minimization of a statistical upper bound for the expected value of uncertain objectives, facilitating more statistically robust decision-making. Central to our approach is the Average Percentile Upper Bound (APUB), a novel construct that simultaneously delivers a statistically rigorous upper bound for the population mean and a meaningful risk metric for the sample mean. The integration of APUB into stochastic optimization not only fortifies the process against distributional ambiguity but also reinforces key data-driven decision-making attributes, such as reliability, consistency, and comprehensibility. Notably, APUB-enriched optimization problems feature tractability, with particular advantages in two-stage stochastic optimization with random recourse. Empirical demonstrations on two-stage product mix and multi-product newsvendor benchmark problems reveal the benefit of the APUB optimization framework, in comparison with conventional techniques such as sample average approximation and distributionally robust optimization. △ Less

Submitted 18 April, 2024; v1 submitted 13 March, 2024; originally announced March 2024.

DPOT: Auto-Regressive Denoising Operator Transformer for Large-Scale PDE Pre-Training

Authors: Zhongkai Hao, Chang Su, Songming Liu, Julius Berner, Chengyang Ying, Hang Su, Anima Anandkumar, Jian Song, Jun Zhu

Abstract: Pre-training has been investigated to improve the efficiency and performance of training neural operators in data-scarce settings. However, it is largely in its infancy due to the inherent complexity and diversity, such as long trajectories, multiple scales and varying dimensions of partial differential equations (PDEs) data. In this paper, we present a new auto-regressive denoising pre-training s… ▽ More Pre-training has been investigated to improve the efficiency and performance of training neural operators in data-scarce settings. However, it is largely in its infancy due to the inherent complexity and diversity, such as long trajectories, multiple scales and varying dimensions of partial differential equations (PDEs) data. In this paper, we present a new auto-regressive denoising pre-training strategy, which allows for more stable and efficient pre-training on PDE data and generalizes to various downstream tasks. Moreover, by designing a flexible and scalable model architecture based on Fourier attention, we can easily scale up the model for large-scale pre-training. We train our PDE foundation model with up to 0.5B parameters on 10+ PDE datasets with more than 100k trajectories. Extensive experiments show that we achieve SOTA on these benchmarks and validate the strong generalizability of our model to significantly enhance performance on diverse downstream PDE tasks like 3D data. Code is available at \url{https://github.com/thu-ml/DPOT}. △ Less

Submitted 6 May, 2024; v1 submitted 6 March, 2024; originally announced March 2024.

A Primal-dual hybrid gradient method for solving optimal control problems and the corresponding Hamilton-Jacobi PDEs

Authors: Tingwei Meng, Siting Liu, Wuchen Li, Stanley Osher

Abstract: Optimal control problems are crucial in various domains, including path planning, robotics, and humanoid control, demonstrating their broad applicability. The connection between optimal control and Hamilton-Jacobi (HJ) partial differential equations (PDEs) underscores the need for solving HJ PDEs to address these control problems effectively. While numerous numerical methods exist for tackling HJ… ▽ More Optimal control problems are crucial in various domains, including path planning, robotics, and humanoid control, demonstrating their broad applicability. The connection between optimal control and Hamilton-Jacobi (HJ) partial differential equations (PDEs) underscores the need for solving HJ PDEs to address these control problems effectively. While numerous numerical methods exist for tackling HJ PDEs across different dimensions, this paper introduces an innovative optimization-based approach that reformulates optimal control problems and HJ PDEs into a saddle point problem using a Lagrange multiplier. Our method, based on the preconditioned primal-dual hybrid gradient (PDHG) method, offers a solution to HJ PDEs with first-order accuracy and numerical unconditional stability, enabling larger time steps and avoiding the limitations of explicit time discretization methods. Our approach has ability to handle a wide variety of Hamiltonian functions, including those that are non-smooth and dependent on time and space, through a simplified saddle point formulation that facilitates easy and parallelizable updates. Furthermore, our framework extends to viscous HJ PDEs and stochastic optimal control problems, showcasing its versatility. Through a series of numerical examples, we demonstrate the method's effectiveness in managing diverse Hamiltonians and achieving efficient parallel computation, highlighting its potential for wide-ranging applications in optimal control and beyond. △ Less

Submitted 4 March, 2024; originally announced March 2024.

Numerical Analysis on Neural Network Projected Schemes for Approximating One Dimensional Wasserstein Gradient Flows

Authors: Xinzhe Zuo, Jiaxi Zhao, Shu Liu, Stanley Osher, Wuchen Li

Abstract: We provide a numerical analysis and computation of neural network projected schemes for approximating one dimensional Wasserstein gradient flows. We approximate the Lagrangian mapping functions of gradient flows by the class of two-layer neural network functions with ReLU (rectified linear unit) activation functions. The numerical scheme is based on a projected gradient method, namely the Wasserst… ▽ More We provide a numerical analysis and computation of neural network projected schemes for approximating one dimensional Wasserstein gradient flows. We approximate the Lagrangian mapping functions of gradient flows by the class of two-layer neural network functions with ReLU (rectified linear unit) activation functions. The numerical scheme is based on a projected gradient method, namely the Wasserstein natural gradient, where the projection is constructed from the $L^2$ mapping spaces onto the neural network parameterized mapping space. We establish theoretical guarantees for the performance of the neural projected dynamics. We derive a closed-form update for the scheme with well-posedness and explicit consistency guarantee for a particular choice of network structure. General truncation error analysis is also established on the basis of the projective nature of the dynamics. Numerical examples, including gradient drift Fokker-Planck equations, porous medium equations, and Keller-Segel models, verify the accuracy and effectiveness of the proposed neural projected algorithm. △ Less

Submitted 26 February, 2024; originally announced February 2024.

Anomaly cancellation and modularity: E8*E8*E8 case

Authors: Siyao Liu, Yong Wang, Yuchen Yang

Abstract: In [5] and [19], the authors gave anomaly cancellation formulas for the gauge groups E8,E8*E8. In this paper, we mainly deal with the case of gauge group E8*E8*E8. Using the E8*E8*E8 bundle, we construct some modular forms over SL2(Z). By these modular forms, we get some new anomaly cancellation formulas of characteristic forms. In [5] and [19], the authors gave anomaly cancellation formulas for the gauge groups E8,E8*E8. In this paper, we mainly deal with the case of gauge group E8*E8*E8. Using the E8*E8*E8 bundle, we construct some modular forms over SL2(Z). By these modular forms, we get some new anomaly cancellation formulas of characteristic forms. △ Less

Submitted 23 February, 2024; originally announced February 2024.

Comments: 18 pages

A new type of simplified inverse Lax-Wendroff boundary treatment I: hyperbolic conservation laws

Authors: Shihao Liu, Tingting Li, Ziqiang Cheng, Yan Jiang, Chi-Wang Shu, Mengping Zhang

Abstract: In this paper, we design a new kind of high order inverse Lax-Wendroff (ILW) boundary treatment for solving hyperbolic conservation laws with finite difference method on a Cartesian mesh. This new ILW method decomposes the construction of ghost point values near inflow boundary into two steps: interpolation and extrapolation. At first, we impose values of some artificial auxiliary points through a… ▽ More In this paper, we design a new kind of high order inverse Lax-Wendroff (ILW) boundary treatment for solving hyperbolic conservation laws with finite difference method on a Cartesian mesh. This new ILW method decomposes the construction of ghost point values near inflow boundary into two steps: interpolation and extrapolation. At first, we impose values of some artificial auxiliary points through a polynomial interpolating the interior points near the boundary. Then, we will construct a Hermite extrapolation based on those auxiliary point values and the spatial derivatives at boundary obtained via the ILW procedure. This polynomial will give us the approximation to the ghost point value. By an appropriate selection of those artificial auxiliary points, high-order accuracy and stable results can be achieved. Moreover, theoretical analysis indicates that comparing with the original ILW method, especially for higher order accuracy, the new proposed one would require fewer terms using the relatively complicated ILW procedure and thus improve computational efficiency on the premise of maintaining accuracy and stability. We perform numerical experiments on several benchmarks, including one- and two-dimensional scalar equations and systems. The robustness and efficiency of the proposed scheme is numerically verified. △ Less

Submitted 15 February, 2024; originally announced February 2024.

Distributed Observer Design over Directed Switching Topologies

Authors: Haotian Xu, Shuai Liu, Bohui Wang, Jingcheng Wang

Abstract: The distributed observer design problem holds significant importance in cases in which the output information of a system is decentralized across different subsystems. Each subsystem has a local observer and access to one part of the measurement outputs and information exchanged through communication networks. This paper focuses on the design of distributed observer with jointly connected directed… ▽ More The distributed observer design problem holds significant importance in cases in which the output information of a system is decentralized across different subsystems. Each subsystem has a local observer and access to one part of the measurement outputs and information exchanged through communication networks. This paper focuses on the design of distributed observer with jointly connected directed switching networks. The problem presents challenges due to passive switching modes and the open-loop unboundedness that results from local observability. To overcome these challenges, we develop a network transformation mapping method whereby each local observer can classify itself into an independent subgraph based on independent judgment. Next, an observable decomposition and reorganization method is developed for the digraph case to ensure that each subgraph possesses independent dynamic properties. Asymptotic omniscience is then proven using a developed recursive proof method. This paper includes many previous results as special cases, because most are only suitable for undirected switching topologies or fast-switching cases. An adaptive coupling gain design is proposed to simplify the calculation and verification of conditions that guarantee asymptotic omniscience. Finally, simulation results with the power system show the validity of the developed theory. △ Less

Submitted 12 February, 2024; originally announced February 2024.

Random Geometric Graph Alignment with Graph Neural Networks

Authors: Suqi Liu, Morgane Austern

Abstract: We characterize the performance of graph neural networks for graph alignment problems in the presence of vertex feature information. More specifically, given two graphs that are independent perturbations of a single random geometric graph with noisy sparse features, the task is to recover an unknown one-to-one mapping between the vertices of the two graphs. We show under certain conditions on the… ▽ More We characterize the performance of graph neural networks for graph alignment problems in the presence of vertex feature information. More specifically, given two graphs that are independent perturbations of a single random geometric graph with noisy sparse features, the task is to recover an unknown one-to-one mapping between the vertices of the two graphs. We show under certain conditions on the sparsity and noise level of the feature vectors, a carefully designed one-layer graph neural network can with high probability recover the correct alignment between the vertices with the help of the graph structure. We also prove that our conditions on the noise level are tight up to logarithmic factors. Finally we compare the performance of the graph neural network to directly solving an assignment problem on the noisy vertex features. We demonstrate that when the noise level is at least constant this direct matching fails to have perfect recovery while the graph neural network can tolerate noise level growing as fast as a power of the size of the graph. △ Less

Submitted 11 February, 2024; originally announced February 2024.

Comments: 29 pages, 2 figure, 1 table

High-Performance Distributed Control for Large-Scale Linear Systems: A Partitioned Distributed Observer Approach

Authors: Haotian Xu, Shuai Liu, Ling Shi

Abstract: In recent years, the distributed-observer-based distributed control law has shown powerful ability to arbitrarily approximate the centralized control performance. However, the traditional distributed observer requires each local observer to reconstruct the state information of the whole system, which is unrealistic for large-scale scenarios. To fill this gap, this paper develops a greedy-idea-base… ▽ More In recent years, the distributed-observer-based distributed control law has shown powerful ability to arbitrarily approximate the centralized control performance. However, the traditional distributed observer requires each local observer to reconstruct the state information of the whole system, which is unrealistic for large-scale scenarios. To fill this gap, this paper develops a greedy-idea-based large-scale system partition algorithm, which can significantly reduce the dimension of local observers. Then, the partitioned distributed observer for large-scale systems is proposed to overcome the problem that the system dynamics are difficult to estimate due to the coupling between partitions. Furthermore, the two-layer Lyapunov analysis method is adopted and the dynamic transformation lemma of compact errors is proven, which solves the problem of analyzing stability of the error dynamic of the partitioned distributed observer. Finally, it is proved that the distributed control law based on the partitioned distributed observer can also arbitrarily approximate the control performance of the centralized control law, and the dimension of the local observer is greatly reduced compared with the traditional method. The simulation results show that when the similarity between the physical network and the communication network is about 80%, the local observer dimension is greatly reduced by 90% and the relative error between the performance of the distributed control law and that of the centralized control law is less than 1%. △ Less

Submitted 10 February, 2024; originally announced February 2024.

Preconditioning for Physics-Informed Neural Networks

Authors: Songming Liu, Chang Su, Jiachen Yao, Zhongkai Hao, Hang Su, Youjia Wu, Jun Zhu

Abstract: Physics-informed neural networks (PINNs) have shown promise in solving various partial differential equations (PDEs). However, training pathologies have negatively affected the convergence and prediction accuracy of PINNs, which further limits their practical applications. In this paper, we propose to use condition number as a metric to diagnose and mitigate the pathologies in PINNs. Inspired by c… ▽ More Physics-informed neural networks (PINNs) have shown promise in solving various partial differential equations (PDEs). However, training pathologies have negatively affected the convergence and prediction accuracy of PINNs, which further limits their practical applications. In this paper, we propose to use condition number as a metric to diagnose and mitigate the pathologies in PINNs. Inspired by classical numerical analysis, where the condition number measures sensitivity and stability, we highlight its pivotal role in the training dynamics of PINNs. We prove theorems to reveal how condition number is related to both the error control and convergence of PINNs. Subsequently, we present an algorithm that leverages preconditioning to improve the condition number. Evaluations of 18 PDE problems showcase the superior performance of our method. Significantly, in 7 of these problems, our method reduces errors by an order of magnitude. These empirical findings verify the critical role of the condition number in PINNs' training. △ Less

Submitted 1 February, 2024; originally announced February 2024.

Solutions of the loop equations of a class of generalized Frobenius manifolds

Authors: Si-Qi Liu, Haonan Qu, Yuewei Wang, Youjin Zhang

Abstract: We prove the existence and uniqueness of solution of the loop equation associated with a semisimple generalized Frobenius manifold with non-flat unity, and show, for a particular example of one dimensional generalized Frobenius manifold, that the deformation of the Principal Hierarchy induced by the solution of the loop equation is the extended q-deformed KdV hierarchy. We prove the existence and uniqueness of solution of the loop equation associated with a semisimple generalized Frobenius manifold with non-flat unity, and show, for a particular example of one dimensional generalized Frobenius manifold, that the deformation of the Principal Hierarchy induced by the solution of the loop equation is the extended q-deformed KdV hierarchy. △ Less

Submitted 1 February, 2024; originally announced February 2024.

A supervised learning scheme for computing Hamilton-Jacobi equation via density coupling

Authors: Jianbo Cui, Shu Liu, Haomin Zhou

Abstract: We propose a supervised learning scheme for the first order Hamilton-Jacobi PDEs in high dimensions. The scheme is designed by using the geometric structure of Wasserstein Hamiltonian flows via a density coupling strategy. It is equivalently posed as a regression problem using the Bregman divergence, which provides the loss function in learning while the data is generated through the particle form… ▽ More We propose a supervised learning scheme for the first order Hamilton-Jacobi PDEs in high dimensions. The scheme is designed by using the geometric structure of Wasserstein Hamiltonian flows via a density coupling strategy. It is equivalently posed as a regression problem using the Bregman divergence, which provides the loss function in learning while the data is generated through the particle formulation of Wasserstein Hamiltonian flow. We prove a posterior estimate on $L^1$ residual of the proposed scheme based on the coupling density. Furthermore, the proposed scheme can be used to describe the behaviors of Hamilton-Jacobi PDEs beyond the singularity formations on the support of coupling density.Several numerical examples with different Hamiltonians are provided to support our findings. △ Less

Submitted 29 January, 2024; originally announced January 2024.

Comments: 29 pages

MSC Class: 65M75; 65P10; 49Q22; 68T07

Continuous-time structural failure time model for intermittent treatment

Authors: Guanbo Wang, Siyi Liu, Shu Yang

Abstract: The intermittent intake of treatment is commonly seen in patients with chronic disease. For example, patients with atrial fibrillation may need to discontinue the oral anticoagulants when they experience a certain surgery and re-initiate the treatment after the surgery. As another example, patients may skip a few days before they refill a treatment as planned. This treatment dispensation informati… ▽ More The intermittent intake of treatment is commonly seen in patients with chronic disease. For example, patients with atrial fibrillation may need to discontinue the oral anticoagulants when they experience a certain surgery and re-initiate the treatment after the surgery. As another example, patients may skip a few days before they refill a treatment as planned. This treatment dispensation information (i.e., the time at which a patient initiates and refills a treatment) is recorded in the electronic healthcare records or claims database, and each patient has a different treatment dispensation. Current methods to estimate the effects of such treatments censor the patients who re-initiate the treatment, which results in information loss or biased estimation. In this work, we present methods to estimate the effect of treatments on failure time outcomes by taking all the treatment dispensation information. The developed methods are based on the continuous-time structural failure time model, where the dependent censoring is tackled by inverse probability of censoring weighting. The estimators are doubly robust and locally efficient. △ Less

Submitted 28 January, 2024; originally announced January 2024.

Numerical analysis of a first-order computational algorithm for reaction-diffusion equations via the primal-dual hybrid gradient method

Authors: Shu Liu, Xinzhe Zuo, Stanley Osher, Wuchen Li

Abstract: In arXiv:2305.03945 [math.NA], a first-order optimization algorithm has been introduced to solve time-implicit schemes of reaction-diffusion equations. In this research, we conduct theoretical studies on this first-order algorithm equipped with a quadratic regularization term. We provide sufficient conditions under which the proposed algorithm and its time-continuous limit converge exponentially f… ▽ More In arXiv:2305.03945 [math.NA], a first-order optimization algorithm has been introduced to solve time-implicit schemes of reaction-diffusion equations. In this research, we conduct theoretical studies on this first-order algorithm equipped with a quadratic regularization term. We provide sufficient conditions under which the proposed algorithm and its time-continuous limit converge exponentially fast to a desired time-implicit numerical solution. We show both theoretically and numerically that the convergence rate is independent of the grid size, which makes our method suitable for large-scale problems. The efficiency of our algorithm has been verified via a series of numerical examples conducted on various types of reaction-diffusion equations. The choice of optimal hyperparameters as well as comparisons with some classical root-finding algorithms are also discussed in the numerical section. △ Less

Submitted 25 January, 2024; originally announced January 2024.

Comments: Any feedback or comments are welcome