Search

(see paper for full abstract) We show that the Edge-Disjoint Paths problem is W[1]-hard parameterized by the number $k$ of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no $f(k)\cdot n^{o(k)}$ algorithm for Edge-Disjoint Paths on planar DAGs, where $k$ is the number of terminal pairs, $n$ is the number of vertices and $f$ is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most $2$. Our result shows that the $n^{O(k)}$ algorithm of Fortune et al. (TCS '80) for Edge-Disjoint Paths on DAGs is asymptotically tight, even if we add an extra restriction of planarity. As a special case of our result, we obtain that Edge-Disjoint Paths on planar directed graphs is W[1]-hard parameterized by the number $k$ of terminal pairs. This answers a question of Cygan et al. (FOCS '13) and Schrijver (pp. 417-444, Building Bridges II, '19), and completes the landscape of the parameterized complexity status of edge and vertex versions of the Disjoint Paths problem on planar directed and planar undirected graphs., Comment: A preliminary version of the paper to appear in CIAC 2021

In this paper we get error bounds for fully discrete approximations of infinite horizon problems via the dynamic programming approach. It is well known that considering a time discretization with a positive step size $h$ an error bound of size $h$ can be proved for the difference between the value function (viscosity solution of the Hamilton-Jacobi-Bellman equation corresponding to the infinite horizon) and the value function of the discrete time problem. However, including also a spatial discretization based on elements of size $k$ an error bound of size $O(k/h)$ can be found in the literature for the error between the value functions of the continuous problem and the fully discrete problem. In this paper we revise the error bound of the fully discrete method and prove, under similar assumptions to those of the time discrete case, that the error of the fully discrete case is in fact $O(h+k)$ which gives first order in time and space for the method. This error bound matches the numerical experiments of many papers in the literature in which the behaviour $1/h$ from the bound $O(k/h)$ have not been observed., 14 pages

Given a nonnegative matrix factorization, $R$, and a factorization rank, $r$, Exact nonnegative matrix factorization (Exact NMF) decomposes $R$ as the product of two nonnegative matrices, $C$ and $S$ with $r$ columns, such as $R = CS^\top$. A central research topic in the literature is the conditions under which such a decomposition is unique/identifiable, up to trivial ambiguities. In this paper, we focus on partial identifiability, that is, the uniqueness of a subset of columns of $C$ and $S$. We start our investigations with the data-based uniqueness (DBU) theorem from the chemometrics literature. The DBU theorem analyzes all feasible solutions of Exact NMF, and relies on sparsity conditions on $C$ and $S$. We provide a mathematically rigorous theorem of a recently published restricted version of the DBU theorem, relying only on simple sparsity and algebraic conditions: it applies to a particular solution of Exact NMF (as opposed to all feasible solutions) and allows us to guarantee the partial uniqueness of a single column of $C$ or $S$. Second, based on a geometric interpretation of the restricted DBU theorem, we obtain a new partial identifiability result. This geometric interpretation also leads us to another partial identifiability result in the case $r=3$. Third, we show how partial identifiability results can be used sequentially to guarantee the identifiability of more columns of $C$ and $S$. We illustrate these results on several examples, including one from the chemometrics literature., 27 pages, 8 figures, 7 examples. This third version makes minor modifications. Paper accepted in SIAM J. on Matrix Analysis and Applications

In this paper we study two different ways of coupling a local operator with a nonlocal one in such a way that the resulting equation is related to an energy functional. In the first strategy the coupling is given via source terms in the equation and in the second one a flux condition in the local part appears. For both models we prove existence and uniqueness of a solution that is obtained via direct minimization of the related energy functional. In the second part of this paper we extend these ideas to deal with local/nonlocal elasticity models in which we couple classical local elasticity with nonlocal peridynamics.

In this paper, we analyze and discuss the well-posedness of a new variant of the so-called sweeping process, introduced by J.J. Moreau in the early 70's \cite{More71} with motivation in plasticity theory. In this variant, the normal cone to the (mildly non-convex) prox-regular moving set $C(t)$, supposed to have an absolutely continuous variation, is perturbed by a sum of a Carath\'{e}odory mapping and an integral forcing term. The integrand of the forcing term depends on two time-variables, that is, we study a general integro-differential sweeping process of Volterra type. By setting up an appropriate semi-discretization method combined with a new Gronwall-like inequality (differential inequality), we show that the integro-differential sweeping process has one and only one absolutely continuous solution. We also establish the continuity of the solution with respect to the initial value. The results of the paper are applied to the study of nonlinear integro-differential complementarity systems which are combination of Volterra integro-differential equations with nonlinear complementarity constraints. Another application is concerned with non-regular electrical circuits containing time-varying capacitors and nonsmooth electronic device like diodes. Both applications represent an additional novelty of our paper., Comment: 36 pages, 1 figures

Given a simple graph $G$, denote by $\Delta(G)$, $\delta(G)$, and $\chi'(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is \emph{$\Delta$-critical} if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)\le \Delta(G)$ for every proper subgraph $H$ of $G$; and $G$ is \emph{overfull} if $|E(G)|>\Delta \lfloor |V(G)|/2 \rfloor$. Since a maximum matching in $G$ can have size at most $\lfloor |V(G)|/2 \rfloor$, it follows that $\chi'(G) = \Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $\Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $\Delta(G) > |V(G)|/3$. In this paper, we show that any $\Delta$-critical graph $G$ is overfull if $\Delta(G) - 7\delta(G)/4\ge(3|V(G)|-17)/4$., Comment: One portion of arXiv:2005.12909 is incorporated into this paper. arXiv admin note: text overlap with arXiv:2004.00734, arXiv:2103.05171

This paper studies an infinite horizon optimal control problem for discrete-time linear systems and quadratic criteria, both with random parameters which are independent and identically distributed with respect to time. A classical approach is to solve an algebraic Riccati equation that involves mathematical expectations and requires certain statistical information of the parameters. In this paper, we propose an online iterative algorithm in the spirit of Q-learning for the situation where only one random sample of parameters emerges at each time step. The first theorem proves the equivalence of three properties: the convergence of the learning sequence, the well-posedness of the control problem, and the solvability of the algebraic Riccati equation. The second theorem shows that the adaptive feedback control in terms of the learning sequence stabilizes the system as long as the control problem is well-posed. Numerical examples are presented to illustrate our results., Comment: 24 pages, 3 figures

In this paper we propose a tool for high-dimensional approximation based on trigonometric polynomials where we allow only low-dimensional interactions of variables. In a general high-dimensional setting, it is already possible to deal with special sampling sets such as sparse grids or rank-1 lattices. This requires black-box access to the function, i.e., the ability to evaluate it at any point. Here, we focus on scattered data points and grouped frequency index sets along the dimensions. From there we propose a fast matrix-vector multiplication, the grouped Fourier transform, for high-dimensional grouped index sets. Those transformations can be used in the application of the previously introduced method of approximating functions with low superposition dimension based on the analysis of variance (ANOVA) decomposition where there is a one-to-one correspondence from the ANOVA terms to our proposed groups. The method is able to dynamically detected important sets of ANOVA terms in the approximation. In this paper, we consider the involved least-squares problem and add different forms of regularization: Classical Tikhonov-regularization, namely, regularized least squares and the technique of group lasso, which promotes sparsity in the groups. As for the latter, there are no explicit solution formulas which is why we applied the fast iterative shrinking-thresholding algorithm to obtain the minimizer. Moreover, we discuss the possibility of incorporating smoothness information into the least-squares problem. Numerical experiments in under-, overdetermined, and noisy settings indicate the applicability of our algorithms. While we consider periodic functions, the idea can be directly generalized to non-periodic functions as well.

Transient dynamics often differ drastically from the asymptotic dynamics of systems. In this paper we analyze transient dynamics in birth-jump metapopulations where dispersal occurs immediately after birth (e.g., via larval dispersal). We address the choice of appropriate norms as well as the effect of stage structure on transient dynamics. We advocate the use of the \ell 1 norm, because of its biological interpretation, and extend the transient metrics of reactivity and attenuation to birth-jump metapopulations in this norm. By way of examples we compare this norm to the more commonly used \ell 2 norm. Our focus is the case where transient dynamics are very different than asymptotic dynamics. We provide simple examples of metapopulations where this is the case and also show how increasing the number of habitat patches can increase this difference. We then connect the reactivity and attenuation of metapopulations to the source-sink classification of habitat patches and demonstrate how to meaningfully measure reactivity when metapopulations are stage-structured, with a focus on marine metapopulations. Our paper makes three primary contributions. First, itprovides guidance to readers as to the appropriate norm and scalings for studying transients in birthjump metapopulations. Second, it provides three examples of transient behavior in metapopulations involving slow-fast systems, crawl-bys, and high dimensionality. Third, it connects the concepts of reactivity and attenuation to the source-sink classification of habitat patches more commonly found in marine metapopulations.

The focus of this paper is on stochastic variational inequalities (VI) under Markovian noise. A prominent application of our algorithmic developments is the stochastic policy evaluation problem in reinforcement learning. Prior investigations in the literature focused on temporal difference (TD) learning by employing nonsmooth finite time analysis motivated by stochastic subgradient descent leading to certain limitations. These encompass the requirement of analyzing a modified TD algorithm that involves projection to an a-priori defined Euclidean ball, achieving a non-optimal convergence rate and no clear way of deriving the beneficial effects of parallel implementation. Our approach remedies these shortcomings in the broader context of stochastic VIs and in particular when it comes to stochastic policy evaluation. We developed a variety of simple TD learning type algorithms motivated by its original version that maintain its simplicity, while offering distinct advantages from a non-asymptotic analysis point of view. We first provide an improved analysis of the standard TD algorithm that can benefit from parallel implementation. Then we present versions of a conditional TD algorithm (CTD), that involves periodic updates of the stochastic iterates, which reduce the bias and therefore exhibit improved iteration complexity. This brings us to the fast TD (FTD) algorithm which combines elements of CTD and the stochastic operator extrapolation method of the companion paper. For a novel index resetting policy FTD exhibits the best known convergence rate. We also devised a robust version of the algorithm that is particularly suitable for discounting factors close to 1., Comment: arXiv admin note: text overlap with arXiv:2011.02987

$\renewcommand{\Re}{\mathbb{R}}$ We develop a general randomized technique for solving "implic it" linear programming problems, where the collection of constraints are defined implicitly by an underlying ground set of elements. In many cases, the structure of the implicitly defined constraints can be exploited in order to obtain efficient linear program solvers. We apply this technique to obtain near-optimal algorithms for a variety of fundamental problems in geometry. For a given point set $P$ of size $n$ in $\Re^d$, we develop algorithms for computing geometric centers of a point set, including the centerpoint and the Tukey median, and several other more involved measures of centrality. For $d=2$, the new algorithms run in $O(n\log n)$ expected time, which is optimal, and for higher constant $d>2$, the expected time bound is within one logarithmic factor of $O(n^{d-1})$, which is also likely near optimal for some of the problems., This paper is a merge of two conference papers that were published sixteen years apart. The first paper appeared in SODA 2004, and the second paper (which can be viewed as an applications paper of the first paper) appeared in SoCG 2020

Random projection techniques based on Johnson-Lindenstrauss lemma are used for randomly aggregating the constraints or variables of optimization problems while approximately preserving their optimal values, that leads to smaller-scale optimization problems. D'Ambrosio et al. have applied random projection to a quadratic optimization problem so as to decrease the number of decision variables. Although the problem size becomes smaller, the projected problem will also almost surely be non-convex if the original problem is non-convex, and hence will be hard to solve. In this paper, by focusing on the fact that the level of the non-convexity of a non-convex quadratic optimization problem can be alleviated by random projection, we find an approximate global optimal value of the problem by attributing it to a convex problem with smaller size. To the best of our knowledge, our paper is the first to use random projection for convexification of non-convex optimization problems. We evaluate the approximation error between optimum values of a non-convex optimization problem and its convexified randomly projected problem., 25 pages, 4 figures

Satisfiability of Boolean circuits is among the most known and important problems in theoretical computer science. This problem is NP-complete in general but becomes polynomial time when restricted either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is strictly connected with the problems of solving equations (or systems of equations) over finite algebras. The research reported in this work was motivated by a desire to know for which finite algebras $\mathbf A$ there is a polynomial time algorithm that decides if an equation over $\mathbf A$ has a solution. We are also looking for polynomial time algorithms that decide if two circuits over a finite algebra compute the same function. Although we have not managed to solve these problems in the most general setting we have obtained such a characterization for a very broad class of algebras from congruence modular varieties. This class includes most known and well-studied algebras such as groups, rings, modules (and their generalizations like quasigroups, loops, near-rings, nonassociative rings, Lie algebras), lattices (and their extensions like Boolean algebras, Heyting algebras or other algebras connected with multi-valued logics including MV-algebras). This paper seems to be the first systematic study of the computational complexity of satisfiability of non-Boolean circuits and solving equations over finite algebras. The characterization results provided by the paper is given in terms of nice structural properties of algebras for which the problems are solvable in polynomial time., 50 pages

The aim of this paper is to present a new proof of an explicit version of the Berry-Ess\'{e}en type inequality of Bolthausen (Zeitschrift f\"ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 66, 379--386, 1984). The literature already provides several proofs of it using variants of Stein's method. The characteristic function method has also been applied but led only to weaker results. In this paper, we show how to overcome the difficulties of this method by using a new identity for permanents of complex matrices in combination with a recently proved inequality for the characteristic function of the approximated distribution., Comment: 21 pages

The main task in this paper is to prove that the perfectly matched layers (PML) method converges exponentially with respect to the PML parameter, for scattering problems with periodic surfaces. In [5], a linear convergence is proved for the PML method for scattering problems with rough surfaces. At the end of that paper, three important questions are asked, and the third question is if exponential convergence holds locally. In our paper, we answer this question for a special case, which is scattering problems with periodic surfaces. The result can also be easily extended to locally perturbed periodic surfaces or periodic layers. Due to technical reasons, we have to exclude all the half integer valued wavenumbers. The main idea of the proof is to apply the Floquet-Bloch transform to write the problem into an equivalent family of quasi-periodic problems, and then study the analytic extension of the quasi-periodic problems with respect to the Floquet-Bloch parameters. Then the Cauchy integral formula is applied for piecewise analytic functions to avoid linear convergent points. Finally the exponential convergence is proved from the inverse Floquet-Bloch transform. Numerical results are also presented at the end of this paper.

This paper concerns the modeling and numerical simulation of the process of speciation. In particular, given conditions for which one or more speciation events within an ecosystem occur, our aim is to develop the necessary modeling and simulation tools. Care is also taken to establish a solid mathematical foundation on which our modeling framework is built. This is the subject of the first half of the paper. The second half is devoted to developing a multiscale framework for eco-evolutionary modeling, where the relevant scales are that of species and individual/population, respectively. The species level model we employ can be considered as an extension of the classical Lotka--Volterra model, where in addition to the species abundance, the model also governs the evolution of the species mean traits and species trait covariances and in this sense generalizes the purely ecological Lotka--Volterra model to an eco-evolutionary model. Although the model thus allows for evolving species, it does not (by construction) allow for the branching of species, i.e., speciation events. The reason for this is related to that of separate scales; the unit of species is too coarse to capture the fine-scale dynamics of a speciation event. Instead, the branching species should be regarded as a population of individuals moving along a selection of trait axes (i.e., trait-space). For this, we employ a trait-specific population density model governing the dynamics of the population density as a function of evolutionary traits. At this scale there is no a priori definition of species, but both species and speciation may be defined a posteriori as, e.g., local maxima and saddle points of the population density, respectively. Hence, a system of interacting species can be described at the species level, while for branching species a population level description is necessary. Our multiscale framework thus consists of coupling the species and population level models where speciation events are detected in advance and then resolved at the population scale until the branching is complete. Moreover, since the population level model is formulated as a PDE, we first establish the well-posedness in the time-discrete setting and then derive the a posteriori error estimates, which provides a fully computable upper bound on an energy-type error, including also for the case of general smooth distributions (which will be useful for the detection of speciation events). Several numerical tests validate our framework in practice. publishedVersion

This paper considers the equilibrium positions of $n$ particles in one dimension. Two forces act on the particles; a nonlocal repulsive particle-interaction force and an external force which pushes them to an impenetrable barrier. While the continuum limit as $n \to \infty$ is known for a certain class of potentials, numerical simulations show that a discrete boundary layer appears at the impenetrable barrier, i.e. the positions of $o(n)$ particles do not fit to the particle density predicted by the continuum limit. In this paper we establish a first-order $\Gamma$-convergence result which guarantees that these $o(n)$ particles converge to a specific continuum boundary-layer profile., Comment: 34 pages

Efficient sampling from a high-dimensional Gaussian distribution is an old but high-stake issue. Vanilla Cholesky samplers imply a computational cost and memory requirements which can rapidly become prohibitive in high dimension. To tackle these issues, multiple methods have been proposed from different communities ranging from iterative numerical linear algebra to Markov chain Monte Carlo (MCMC) approaches. Surprisingly, no complete review and comparison of these methods have been conducted. This paper aims at reviewing all these approaches by pointing out their differences, close relations, benefits and limitations. In addition to this state of the art, this paper proposes a unifying Gaussian simulation framework by deriving a stochastic counterpart of the celebrated proximal point algorithm in optimization. This framework offers a novel and unifying revisit of most of the existing MCMC approaches while extending them. Guidelines to choose the appropriate Gaussian simulation method for a given sampling problem in high dimension are proposed and illustrated with numerical examples., 53 pages, 11 figures

This paper presents the analysis of the stability properties of PID controllers for dynamical systems with multiple state delays, focusing on the mathematical characterization of the potential sensitivity of stability with respect to infinitesimal parametric perturbations. These perturbations originate for instance from neglecting feedback delay, a finite difference approximation of the derivative action, or neglecting fast dynamics. The analysis of these potential sensitivity problems leads us to the introduction of a `robustified' notion of stability called \emph{strong stability}, inspired by the corresponding notion for neutral functional differential equations. We prove that strong stability can be achieved by adding a low-pass filter with a sufficiently large cut-off frequency to the control loop, on the condition that the filter itself does not destabilize the nominal closed-loop system. Throughout the paper, the theoretical results are illustrated by examples that can be analyzed analytically, including, among others, a third-order unstable system where both proportional and derivative control action are necessary for achieving stability, while the regions in the gain parameter-space for stability and strong stability are not identical. Besides the analysis of strong stability, a computational procedure is provided for designing strongly stabilizing PID controllers. Computational case-studies illustrating this design procedure complete the presentation.

We prove that solution operators of elliptic obstacle-type variational inequalities (or, more generally, locally Lipschitz continuous functions possessing certain pointwise-a.e. convexity properties) are Newton differentiable when considered as maps between suitable Lebesgue spaces and equipped with the strong-weak Bouligand differential as a generalized set-valued derivative. It is shown that this Newton differentiability allows to solve optimal control problems with H1-cost terms and one-sided pointwise control constraints by means of a semismooth Newton method. The superlinear convergence of the resulting algorithm is proved in the infinite-dimensional setting and its mesh independence is demonstrated in numerical experiments. We expect that the findings of this paper are also helpful for the design of numerical solution procedures for quasi-variational inequalities and the optimal control of obstacle-type variational problems., Comment: Minor revisions. Published in SIAM Journal on Control and Optimization, Vol. 61, Iss. 3 (2023)

Hip-Hop solutions of the $2N$-body problem are solutions that satisfy at every instance of time, that the $2N$ bodies with the same mass $m$, are at the vertices of two regular $N$-gons, each one of these $N$-gons are at planes that are equidistant from a fixed plane $��_0$ forming an antiprism. In this paper, we first prove that for every $N$ and every $m$ there exists a family of periodic hip-hop solutions. For every solution in these families the oriented distance to the plane $��_0$, which we call $d(t)$, is an odd function that is also even with respect to $t=T$ for some $T>0.$ For this reason we call solutions in these families, double symmetric solutions. By exploring more carefully our initial set of periodic solutions, we numerically show that some of the branches stablished in our existence theorem have bifurcations that produce branches of solutions with the property that the oriented distance function $d(t)$ is not even with respect to any $T>0$, we call these solutions single symmetry solutions. We prove that no single symmetry solution is a choreography. We also display explicit double symmetric solutions that are choreographies., 20 pages, 15 Figures

In this paper, we consider a class of highly oscillatory Hamiltonian systems which involve a scaling parameter $\varepsilon\in(0,1]$. The problem arises from many physical models in some limit parameter regime or from some time-compressed perturbation problems. The solution of the model exhibits rapid temporal oscillations with $\mathcal{O}(1)$-amplitude and $\mathcal{O}(1/\varepsilon)$-frequency, which makes classical numerical methods inefficient. We apply the two-scale formulation approach to the problem and propose two new time-symmetric numerical integrators. The methods are proved to have the uniform second order accuracy for all $\varepsilon$ at finite times and some near-conservation laws in long times. Numerical experiments on a H\'{e}non-Heiles model, a nonlinear Schr\"{o}dinger equation and a charged-particle system illustrate the performance of the proposed methods over the existing ones., Comment: 21 pages

In this paper we generalize some results in \cite{Yu2021} concerning stacked central configurations. We can deal with the general homogeneous potential $U_{\alpha}$ (containing the vortex case) in $\mathbb{R}^3$. We give the admissible set of $\alpha$ for a convex central configuration (with respect to the Newtonian potential i.e. $\alpha=3$). We discuss some properties of the regular $n$-gon co-circular central configurations. We also find that the stacked property is particular for central configurations by studying the S-balanced configuration case., Comment: misoperation

This paper studies the learning of linear operators between infinite-dimensional Hilbert spaces. The training data comprises pairs of random input vectors in a Hilbert space and their noisy images under an unknown self-adjoint linear operator. Assuming that the operator is diagonalizable in a known basis, this work solves the equivalent inverse problem of estimating the operator's eigenvalues given the data. Adopting a Bayesian approach, the theoretical analysis establishes posterior contraction rates in the infinite data limit with Gaussian priors that are not directly linked to the forward map of the inverse problem. The main results also include learning-theoretic generalization error guarantees for a wide range of distribution shifts. These convergence rates quantify the effects of data smoothness and true eigenvalue decay or growth, for compact or unbounded operators, respectively, on sample complexity. Numerical evidence supports the theory in diagonal and non-diagonal settings., Comment: To appear in SIAM/ASA Journal on Uncertainty Quantification (JUQ); 34 pages, 5 figures, 2 tables

In this paper, we study optimal control problems of semilinear elliptic and parabolic equations. A tracking cost functional, quadratic in the control and state variables, is considered. No control constraints are imposed. We prove that the corresponding state equations are well posed for controls in L2. However, it is well known that in the L2 framework the mappings involved in the control problem are not Frechet differentiable in general, which makes any analysis of the optimality conditions challenging. Nevertheless, we prove that every L2 optimal control belongs to L∞, and consequently standard optimality conditions are available. The first author was supported by MCIN/AEI/10.13039/501100011033 under research project PID2020-114837GB-I00. The second author was partially supported by the German Research Foundation (DFG) under project grant Wa 3626/3-2.