Search

Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Science has been revealing their computational complexity for classical problems. This paper presents an initial study on reconfiguration problems derived from a submodular function, which has more of a flavor of Data Mining. Our submodular reconfiguration problems request to find a solution sequence connecting two input solutions such that each solution has an objective value above a threshold in a submodular function $f: 2^{[n]} \to \mathbb{R}_+$ and is obtained from the previous one by applying a simple transformation rule. We formulate three reconfiguration problems: Monotone Submodular Reconfiguration (MSReco), which applies to influence maximization, and two versions of Unconstrained Submodular Reconfiguration (USReco), which apply to determinantal point processes. Our contributions are summarized as follows: 1. We prove that MSReco and USReco are both $\mathsf{PSPACE}$-complete. 2. We design a $\frac{1}{2}$-approximation algorithm for MSReco and a $\frac{1}{n}$-approximation algorithm for (one version of) USReco. 3. We devise inapproximability results that approximating the optimum value of MSReco within a $(1-\frac{1+\epsilon}{n^2})$-factor is $\mathsf{PSPACE}$-hard, and we cannot find a $(\frac{5}{6}+\epsilon)$-approximation for USReco. 4. We conduct numerical study on the reconfiguration version of influence maximization and determinantal point processes using real-world social network and movie rating data., Comment: 11 pages. Accepted to the 15th ACM International Conference on Web Search and Data Mining (WSDM 2022)

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: (1) reduce the enumeration in the tight ( 1 − e − 1 ) -approximation of [Sviridenko 04] from subsets of size three to two; (2) present an improved upper bound of 0.42945 for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.

We construct an exact completion for regular categories enriched in the cartesian closed category $\mathsf{Pos}$ of partially ordered sets and monotone functions by employing a suitable calculus of relations. We then characterize the embedding of any regular category into its completion and use this to obtain examples of concrete categories which arise as such completions. In particular, we prove that the exact completion in this enriched sense of both the categories of Stone and Priestley spaces is the category of compact ordered spaces of L. Nachbin. Finally, we consider the relationship between the enriched exact completion and categories of internal posets in ordinary categories., Comment: 42 pages. To appear in Journal of Pure and Applied Algebra

Discrete-time replicator map is a prototype of evolutionary selection game dynamical models that have been very successful across disciplines in rendering insights into the attainment of the equilibrium outcomes, like the Nash equilibrium and the evolutionarily stable strategy. By construction, only the fixed point solutions of the dynamics can possibly be interpreted as the aforementioned game-theoretic solution concepts. Although more complex outcomes like chaos are omnipresent in the nature, it is not known to which game-theoretic solutions they correspond. Here we construct a game-theoretic solution that is realized as the chaotic outcomes in the selection monotone game dynamic. To this end, we invoke the idea that in a population game having two-player--two-strategy one-shot interactions, it is the product of the fitness and the heterogeneity (the probability of finding two individuals playing different strategies in the infinitely large population) that is optimized over the generations of the evolutionary process.

In this paper we provide a generalization of the Douglas-Rachford splitting (DRS) and the primal-dual algorithm (Vu 2013, Condat 2013) for solving monotone inclusions in a real Hilbert space involving a general linear operator. The proposed method allows for primal and dual non-standard metrics and activates the linear operator separately from the monotone operators appearing in the inclusion. In the simplest case when the linear operator has full range, it reduces to classical DRS. Moreover, the weak convergence of primal-dual sequences to a Kuhn-Tucker point is guaranteed, generalizing the main result in Svaiter (2011). Inspired by Gabay (1983), we also derive a new Split-ADMM (SADMM) by applying our method to the dual of a convex optimization problem involving a linear operator which can be expressed as the composition of two linear operators. The proposed SADMM activates one linear operator implicitly and the other one explicitly, and we recover ADMM when the latter is set as the identity. Connections and comparisons of our theoretical results with respect to the literature are provided for the main algorithm and SADMM. The flexibility and efficiency of both methods is illustrated via a numerical simulations in total variation image restoration and a sparse minimization problem., Comment: 26 pages

The distribution of entanglement of typical multiparty quantum states is not uniform over the range of the measure utilized for quantifying the entanglement. We intend to find the response to disorder in the state parameters on this non-uniformity for typical states. We find that the typical entanglement, averaged over the disorder, is taken farther away from uniformity, as quantified by decreased standard deviation, in comparison to the clean case. The feature is seemingly generic, as we see it for Gaussian and non-Gaussian disorder distributions, for varying strengths of the disorder, and for disorder insertions in one and several state parameters. The non-Gaussian distributions considered are uniform and Cauchy-Lorentz. Two- and three-qubit pure state Haar-uniform generations are considered for the typical state productions. We also consider noisy versions of the initial states produced in the Haar-uniform generations. A genuine multiparty entanglement monotone is considered for the three-qubit case, while concurrence is used to measure two-qubit entanglement., Comment: 13 pages, 11 figures. This version is close to the published version, except that here, the disorder in the "second step" is inserted in the relevant state parameter/s after normalization of the state in the "first step". Primary results unchanged

We provide an existence and uniqueness result for mild solutions to semilinear stochastic partial differential equations in the framework of the semigroup approach with locally monotone coefficients. An important component of the proof is an application of the dilation theorem of Nagy, which allows us to reduce the problem to infinite dimensional stochastic differential equations on a larger Hilbert space. Properties of the solutions like the Markov property are discussed as well., Comment: 9 pages

We revisit Machina's local utility as a tool to analyze attitudes to multivariate risks. We show that for non-expected utility maximizers choosing between multivariate prospects, aversion to multivariate mean preserving increases in risk is equivalent to the concavity of the local utility functions, thereby generalizing Machina's result in Machina (1982). To analyze comparative risk attitudes within the multivariate extension of rank dependent expected utility of Galichon and Henry (2011), we extend Quiggin's monotone mean and utility preserving increases in risk and show that the useful characterization given in Landsberger and Meilijson (1994) still holds in the multivariate case., Comment: 18 pages

We consider pairwise interaction energies and we investigate their minimizers among lattices with prescribed minimal vectors (length and coordination number), i.e. the one corresponding to the crystal's bonds. In particular, we show the universal minimality -- i.e. the optimality for all completely monotone interaction potentials -- of strongly eutactic lattices among these structures. This gives new optimality results for the square, triangular, simple cubic (SC), face-centred-cubic (FCC) and body-centred-cubic (BCC) lattices in dimensions 2 and 3 when points are interacting through completely monotone potentials. We also show the universal maximality of the triangular and FCC lattices among all lattices with prescribed bonds. Furthermore, we apply our results to Lennard-Jones type potentials, showing the minimality of any universal minimizer (resp. maximizer) for small (resp. large) bond lengths, where the ranges of optimality are easily computable. Finally, a numerical investigation is presented where a phase transition of type "square-rhombic-triangular" (resp. "SC-rhombic-BCC-rhombic-FCC") in dimension $d=2$ (resp. $d=3$) among lattices with more than 4 (resp. 6) bonds is observed., Comment: 16 pages. 2 Figures. Version accepted in Journal of Physics A

We consider the problem of estimating the mean vector θ of a d -dimensional spherically symmetric distributed X based on balanced loss functions of the forms: (i) ω ρ ( ‖ δ − δ 0 ‖ 2 ) + ( 1 − ω ) ρ ( ‖ δ − θ ‖ 2 ) and (ii) l ω ‖ δ − δ 0 ‖ 2 + ( 1 − ω ) ‖ δ − θ ‖ 2 , where δ 0 is a target estimator, and where ρ and l are increasing and concave functions. For d ≥ 4 and the target estimator δ 0 ( X ) = X , we provide Baranchik-type estimators that dominate δ 0 ( X ) = X and are minimax. The findings represent extensions of those of Marchand & Strawderman (2020) in two directions: (a) from scale mixture of normals to the spherical class of distributions with Lebesgue densities, and (b) from completely monotone to concave ρ ′ and l ′ .

The cup game on $n$ cups is a multi-step game with two players, a filler and an emptier. At each step, the filler distributes $1$ unit of water among the cups, and then the emptier selects a single cup to remove (up to) $1$ unit of water from. There are several objective functions that the emptier might wish to minimize. One of the strongest guarantees would be to minimize tail size, which is defined to be the number of cups with fill $2$ or greater. A simple lower-bound construction shows that the optimal tail size for deterministic emptying algorithms is $\Theta(n)$, however. We present a simple randomized emptying algorithm that achieves tail size $\tilde{O}(\log n)$ with high probability in $n$ for $\operatorname{poly} n$ steps. Moreover, we show that this is tight up to doubly logarithmic factors. We also extend our results to the multi-processor cup game, achieving tail size $\tilde{O}(\log n + p)$ on $p$ processors with high probability in $n$. We show that the dependence on $p$ is near optimal for any emptying algorithm that achieves polynomial-bounded backlog. A natural question is whether our results can be extended to give unending guarantees, which apply to arbitrarily long games. We give a lower bound construction showing that no monotone memoryless emptying algorithm can achieve an unending guarantee on either tail size or the related objective function of backlog. On the other hand, we show that even a very small (i.e., $1 / \operatorname{poly} n$) amount of resource augmentation is sufficient to overcome this barrier.

In \cite{PSMA}, Pal et al. introduced some weighted means and gave some related inequalities by using an approach for operator monotone functions. This paper discusses the construction of these weighted means in a simple and nice setting that immediately leads to the inequalities established there. The related operator version is here immediately deduced as well. According to our constructions of the means, we study all cases of the weighted means from three weighted arithmetic/geometric/harmonic means, by the use of the concept such as stable and stabilizable means. Finally, the power symmetric means are studied and new weighted power means are given., Comment: 14 pages

A non-Markovianity measure for quantum channels is introduced based on causality measure - a monotone of causal (temporal) correlations - arising out of the pseudo-density matrix (PDM) formalism which treats quantum correlations in space and time on an equal footing. Using the well known damped Jaynes-Cummings model of a two-level system interacting with a bosonic reservoir at zero temperature as an example, it is shown that breakdown of monotonicity of the causality measure is associated with the revival of temporal (causal) correlations hence with the negativity of the decay rate. Also, a note on the comparison with other well known non-Markovianity measures is given., Comment: 9 pages, 3 figures; Revised and corrections made

In this paper, we show that all totally nonnegative GCD matrices are always divisors of the corresponding LCM matrices in the ring M n ( Z ) . We also introduce “column monotone matrices” used to construct all totally nonnegative GCD matrices.

We consider a class of optimization problems with Cartesian variational inequality (CVI) constraints, where the objective function is convex and the CVI is associated with a monotone mapping and a convex Cartesian product set. This mathematical formulation captures a wide range of optimization problems including those complicated by the presence of equilibrium constraints, complementarity constraints, or an inner-level large scale optimization problem. In particular, an important motivating application arises from the notion of efficiency estimation of equilibria in multi-agent networks, e.g., communication networks and power systems. In the literature, the iteration complexity of the existing solution methods for optimization problems with CVI constraints appears to be unknown. To address this shortcoming, we develop a first-order method called averaging randomized block iteratively regularized gradient (aRB-IRG). The main contributions include: (i) In the case where the associated set of the CVI is bounded and the objective function is nondifferentiable and convex, we derive new non-asymptotic suboptimality and infeasibility convergence rate statements in a mean sense. We also obtain deterministic variants of the convergence rates when we suppress the randomized block-coordinate scheme. Importantly, this paper appears to be the first work to provide these rate guarantees for this class of problems. (ii) In the case where the CVI set is unbounded and the objective function is smooth and strongly convex, utilizing the properties of the Tikhonov trajectory, we establish the global convergence of aRB-IRG in an almost sure and a mean sense. We provide the numerical experiments for computing the best Nash equilibrium in a networked Cournot competition model.

Given two random variables $X$ and $Y$, stochastic monotonicity describes a monotone influence of $X$ on $Y$. We prove two different characterizations of stochastically monotone $2$-copulas using the isomorphism between $2$-copulas and Markov operators. The first approach establishes a one-to-one correspondence between stochastically monotone copulas and monotonicity-preserving Markov operators. The second approach characterizes stochastically monotone copulas by their monotonicity property with respect to the Markov product. Applying the latter result, we identify all idempotent stochastically monotone copulas as ordinal sums of the independence copula $\Pi$.

In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a widely-used measure of an algorithm's "sequentiality". Algorithms in the adaptive model proceed in rounds, and can issue polynomially many queries to a function $f$ in each round. The queries in each round must be independent, produced by a computation that depends only on query results obtained in previous rounds. In this work, we examine two fundamental variants of submodular maximization in the adaptive complexity model: cardinality-constrained monotone maximization, and unconstrained non-mono-tone maximization. Our main result is that an $r$-round algorithm for cardinality-constrained monotone maximization cannot achieve an approximation factor better than $1 - 1/e - \Omega(\min \{ \frac{1}{r}, \frac{\log^2 n}{r^3} \})$, for any $r < n^c$ (where $c>0$ is some constant). This is the first result showing that the number of rounds must blow up polynomially large as we approach the optimal factor of $1-1/e$. For the unconstrained non-monotone maximization problem, we show a positive result: For every instance, and every $\delta>0$, either we obtain a $(1/2-\delta)$-approximation in $1$ round, or a $(1/2+\Omega(\delta^2))$-approximation in $O(1/\delta^2)$ rounds. In particular (and in contrast to the cardinality-constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than $1/2$ regardless of the number of rounds, and (ii) it takes $r$ rounds to achieve a factor of $1/2-O(1/r)$., Comment: To appear in STOC 2020

Inspired by classical sensitivity results for nonlinear optimization, we derive and discuss new quantitative bounds to characterize the solution map and dual variables of a parametrized nonlinear program. In particular, we derive explicit expressions for the local and global Lipschitz constants of the solution map of non-convex or convex optimization problems, respectively. Our results are geared towards the study of time-varying optimization problems which are commonplace in various applications of online optimization, including power systems, robotics, signal processing and more. In this context, our results can be used to bound the rate of change of the optimizer. To illustrate the use of our sensitivity bounds we generalize existing arguments to quantify the tracking performance of continuous-time, monotone running algorithms. Further, we introduce a new continuous-time running algorithm for time-varying constrained optimization which we model as a so-called perturbed sweeping process. For this discontinuous scheme, we establish an explicit bound on the asymptotic solution tracking for a class of convex problems.

In the classical selection problem, the input consists of a collection of elements and the goal is to pick a subset of elements from the collection such that some objective function $f$ is maximized. This problem has been studied extensively in the data-mining community and it has multiple applications including influence maximization in social networks, team formation and recommender systems. A particularly popular formulation that captures the needs of many such applications is one where the objective function $f$ is a monotone and non-negative submodular function. In these cases, the corresponding computational problem can be solved using a simple greedy $(1-\frac{1}{e})$-approximation algorithm. In this paper, we consider a generalization of the above formulation where the goal is to optimize a function that maximizes the submodular function $f$ minus a linear cost function $c$. This formulation appears as a more natural one, particularly when one needs to strike a balance between the value of the objective function and the cost being paid in order to pick the selected elements. We address variants of this problem both in an offline setting, where the collection is known a priori, as well as in online settings, where the elements of the collection arrive in an online fashion. We demonstrate that by using simple variants of the standard greedy algorithm (used for submodular optimization) we can design algorithms that have provable approximation guarantees, are extremely efficient and work very well in practice., Comment: Extended version of KDD 2021 paper

This note considers the problem of minimizing interacting free energy. Motivated by the mirror descent algorithm, for a given interacting free energy, we propose a descent dynamics with a novel metric that takes into consideration the reference measure and the interacting term. This metric naturally suggests a monotone reparameterization of the probability measure. By discretizing the reparameterized descent dynamics with the explicit Euler method, we arrive at a new mirror-descent-type algorithm for minimizing interacting free energy. Numerical results are included to demonstrate the efficiency of the proposed algorithms.

We prove the Hamiltonian unknottedness of real Lagrangian tori in the monotone $S^2\times S^2$, namely any real Lagrangian torus in $S^2\times S^2$ is Hamiltonian isotopic to the Clifford torus $\mathbb{T}_{\text{Clif}}$. The proof is based on a neck-stretching argument, Gromov's foliation theorem, and the Cieliebak-Schwingenheuer criterion., Comment: 16 pages, various improvements, to appear in Math. Ann

In order to understand how the combination of domain evolution and impulsive harvesting affect the dynamics of a population, we propose a diffusive logistic population model with impulsive harvesting on a periodically evolving domain. Initially the ecological reproduction index of the impulsive problem is introduced and given by an explicit formula, which depends on the domain evolution rate and the impulsive function. Then the threshold dynamics of the population under monotone or nonmonotone impulsive harvesting is established based on this index. Finally numerical simulations are carried out to illustrate our theoretical results, and reveal that a large domain evolution rate can improve the population survival, no matter which impulsive harvesting takes place. Contrary, impulsive harvesting has a negative effect on the population survival, and can even lead to the extinction of the population., Comment: 26 pages, 8 figures

The warping degree of an oriented knot diagram is the minimal number of crossing changes which are required to obtain a monotone knot diagram from the diagram. The minimal warping degree of a knot is the minimal value of the warping degree for all oriented minimal diagrams of the knot. In this paper, all prime alternating knots with minimal warping degree two are determined., Comment: 25 pages, 35 figures

International audience; We present a new notion of solution for mean field games master equations. This notion allows us to work with solutions which are merely continuous. We prove first results of uniqueness and stability for such solutions. It turns out that this notion is helpful to characterize the value function of mean field games of optimal stopping or impulse control and this is the topic of the second half of this paper. The notion of solution we introduce is only useful in the monotone case. We focus in this paper in the finite state space case.

Quantum monotone metric was introduced by Petz [Linear Algebra Appl. 244, 81–96 (1996)], and it was proved that quantum monotone metrics on the set of quantum states with trace one were characterized by operator monotone functions. Later, these were extended to monotone metrics on the set of positive operators whose traces are not always the one based on completely positive, trace preserving maps. It was shown that these extended monotone metrics were characterized by operator monotone functions continuously parameterized by traces of positive operators and did not have some ideal properties such as monotonicity and convexity with respect to the positive operators. In this paper, we introduce another extension of quantum monotone metrics that have monotonicity under completely positive, trace non-increasing maps and additive noise. We prove that our extended monotone metrics can be characterized only by static operator monotone functions from few assumptions without assuming continuities of metrics. We show that our monotone metrics have some natural properties such as additivity of direct sum, convexity, and monotonicity with respect to positive operators.

We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting. Our main result shows that while VC dimension by itself does not always provide tight bounds on the number of samples required to test a class of functions in this model, it can be combined with a closely-related variant that we call "lower VC" (or LVC) dimension to obtain strong lower bounds on this sample complexity. We use this result to obtain strong and in many cases nearly optimal lower bounds on the sample complexity for testing unions of intervals, halfspaces, intersections of halfspaces, polynomial threshold functions, and decision trees. Conversely, we show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that is polynomially smaller than the number of samples required for PAC learning. Finally, we also use the connection between VC dimension and property testing to establish new lower bounds for testing radius clusterability and testing feasibility of linear constraint systems., Comment: 44 pages

We prove homogenization for a class of viscous Hamilton-Jacobi equations in the stationary and ergodic setting in one space dimension. Our assumptions include most notably the following: the Hamiltonian is of the form $G(p) + \beta V(x,\omega)$, the function $G$ is coercive and strictly quasiconvex, $\min G = 0$, $\beta>0$, the random potential $V$ takes values in $[0,1]$ with full support and it satisfies a hill condition that involves the diffusion coefficient. Our approach is based on showing that, for every direction outside of a bounded interval $(\theta_1(\beta),\theta_2(\beta))$, there is a unique sublinear corrector with certain properties. We obtain a formula for the effective Hamiltonian and deduce that it is coercive, identically equal to $\beta$ on $(\theta_1(\beta),\theta_2(\beta))$, and strictly monotone elsewhere., Comment: 21 pages, 1 figure

The paper introduces and solves a structural controllability problem for continuum ensembles of linear time-invariant systems. All the individual linear systems of an ensemble are sparse, governed by the same sparsity pattern. Controllability of an ensemble system is, by convention, the capability of using a common control input to simultaneously steer every individual systems in it. A sparsity pattern is structurally controllable if it admits a controllable linear ensemble system. A main contribution of the paper is to provide a graphical condition that is necessary and sufficient for a sparsity pattern to be structurally controllable. Like other structural problems, the property of being structural controllable is monotone. We provide a complete characterization of minimal sparsity patterns as well.

We extend the methods from [39, 37] to a class of non-potential mean-field game (MFG) systems with mixed couplings. Up to now, splitting methods have been applied to potential MFG systems that can be cast as convex-concave saddle-point problems. Here, we show that a class of non-potential MFG can be cast as primal-dual pairs of monotone inclusions and solved via extensions of convex optimization algorithms such as the primal-dual hybrid gradient (PDHG) algorithm. A critical feature of our approach is in considering dual variables of nonlocal couplings in Fourier or feature spaces.

In this announcement, we report results on the existence of families of large-amplitude internal hydrodynamic bores. These are traveling front solutions of the full two-phase incompressible Euler equation in two dimensions. The fluids are bounded above and below by flat horizontal walls and acted upon by gravity. We obtain continuous curves of solutions to this system that bifurcate from the trivial solution where the interface is flat. Following these families to the their extreme, the internal interface either overturns, comes into contact with the upper wall, or develops a highly degenerate "double stagnation" point. Our construction is made possible by a new abstract machinery for global continuation of monotone front-type solutions to elliptic equations posed on infinite cylinders. This theory is quite robust and, in particular, can treat fully nonlinear equations as well as quasilinear problems with transmission boundary conditions., Comment: This is a shorter description of results first appearing in arXiv:2005.00651 with additional motivation and connections to modeling

In this paper, we study the strong convergence of two Mann-type inertial extragradient algorithms, which are devised with a new step size, for solving a variational inequality problem with a monotone and Lipschitz continuous operator in real Hilbert spaces. Strong convergence theorems for our algorithms are proved without the prior knowledge of the Lipschitz constant of the operator. Finally, we provide some numerical experiments to illustrate the performances of the proposed algorithms and provide a comparison with related ones., Comment: 19 pages, 6 figures

We show that the dynamic resource theory of quantum entanglement can be formulated using the superchannel theory. In this formulation, we identify the separable channels and the class of free superchannels that preserve channel separability as free resources, and choose the swap channels as dynamic entanglement golden units. Our first result is that the one-shot dynamic entanglement cost of a bipartite quantum channel under the free superchannels is bounded by the standard log-robustness of channels. The one-shot distillable dynamic entanglement of a bipartite quantum channel under the free superchannels is found to be bounded by a resource monotone that we construct from the hypothesis-testing relative entropy of channels with minimization over separable channels. We also address the one-shot catalytic dynamic entanglement cost of a bipartite quantum channel under a larger class of free superchannels that could generate the dynamic entanglement which is asymptotically negligible; it is bounded by the generalized log-robustness of channels., Comment: 19 pages, 5 figures. See two independent related works by B. Regula and R. Takagi, and by X. Yuan et al

In this work we investigate how to quantify the coherence of quantum measurements. First, we establish a resource theoretical framework to address the coherence of measurement and show that any statistical distance can be adopted to define a coherence monotone of measurement. For instance, the relative entropy fulfills all the required properties as a proper monotone. We specifically introduce a coherence monotone of measurement in terms of off-diagonal elements of positive-operator-valued measure components. This quantification provides a lower bound on the robustness of measurement-coherence that has an operational meaning as the maximal advantage over all incoherent measurements in state discrimination tasks. Finally, we propose an experimental scheme to assess our quantification of measurement-coherence and demonstrate it by performing an experiment using a single qubit on IBM Q processor.

We introduce the concept of non-uniform input-to-state stability for networks. It combines the uniform global stability with the uniform attractivity of any subnetwork, while it allows for non-uniform convergence of all components. For an infinite network consisting of input-to-state stable subsystems, that do not necessarily have a uniform KL-bound on the transient behaviour, we show: If the gain operator satisfies the uniform small-gain condition, then the whole network is non-uniformly input-to-state stable and all its finite subnetworks are input-to-state stable., Comment: Accepted to IMA Journal of Mathematical Control and Information

A networked dynamical system is composed of subsystems interconnected through prescribed interactions. In many engineering applications, however, one subsystem can also affect others through "unintended" interactions that can significantly hamper the intended network's behavior. Although unintended interactions can be modeled as disturbance inputs to the subsystems, these disturbances depend on the network's states. As a consequence, a disturbance attenuation property of each isolated subsystem is, alone, insufficient to ensure that the network behavior is robust to unintended interactions. In this paper, we provide sufficient conditions on subsystem dynamics and interaction maps, such that the network's behavior is robust to unintended interactions. These conditions require that each subsystem attenuates constant external disturbances, is monotone or "near-monotone", the unintended interaction map is monotone, and the prescribed interaction map does not contain feedback loops. We employ this result to guide the design of resource-limited genetic circuits. More generally, our result provide conditions under which robustness of constituent subsystems is sufficient to guarantee robustness of the network to unintended interactions.

Let f be a smooth real function with strictly monotone first k derivatives. We show that for a finite set A, with ∣A + A∣ ≤K∣A∣, $$\left| {{2^k}f(A) - ({2^k} - 1)f(A)} \right|{ \gg _k}\,{\left| A \right|^{k + 1 - o(1)}}/{K^{{O_k}(1)}}.$$ We deduce several new sum-product type implications, e.g. that A+A being small implies unbounded growth for a many enough times iterated product set A ⋯ A.

We look at how one can construct from the data of a dimer model a Lagrangian submanifold in $(\mathbb{C}^*)^n$ whose valuation projection approximates a tropical hypersurface. Each face of the dimer corresponds to a Lagrangian disk with boundary on our tropical Lagrangian submanifold, forming a Lagrangian mutation seed. Using this we find tropical Lagrangian tori $L_{T^2}$ in the complement of a smooth anticanonical divisor of a toric del-Pezzo whose wall-crossing transformations match those of monotone SYZ fibers. An example is worked out for the mirror pair $(\mathbb{CP}^2\setminus E, W), \check X_{9111}$. We find a symplectomorphism of $\mathbb{CP}^2\setminus E$ interchanging $L_{T^2}$ and a SYZ fiber. Evidence is provided that this symplectomorphism is mirror to fiberwise Fourier-Mukai transform on $\check X_{9111}$., Comment: 55 pages, 24 figures. This is the final version of the paper accepted in Selecta Mathematica. arXiv admin note: substantial text overlap with arXiv:1904.06005

We consider a nonlinear optimal control problem with dynamics described by a differential inclusion involving a maximal monotone map ▫$A colon mathbb{R}^N to 2^{mathbb{R}^N}$▫. We do not assume that ▫$D(A) = mathbb{R}^N$▫, incorporating in this way systems with unilateral constraints in our framework. We present two relaxation methods. The first one is an outgrowth of the reduction method from the existence theory, while the second method uses Young measures. We show that the two relaxation methods are equivalent and admissible.

This article is devoted to a description of the dynamics of the phase flow of monotone contact Hamiltonian systems. Particular attention is paid to locating the maximal attractor (or repeller), which could be seen as the union of compact invariant sets, and investigating its topological and dynamical properties. This is based on an analysis from the viewpoint of gradient-like systems., Comment: 25 pages

International audience; We introduce a new paradigm for solving regularized variational problems. These are typically formulated to address ill-posed inverse problems encountered in signal and image processing. The objective function is traditionally defined by adding a regularization function to a data fit term, which is subsequently minimized by using iterative optimization algorithms. Recently, several works have proposed to replace the operator related to the regularization by a more sophisticated denoiser. These approaches, known as plug-and-play (PnP) methods, have shown excellent performance. Although it has been noticed that, under nonexpansiveness assumptions on the denoisers, the convergence of the resulting algorithm is guaranteed, little is known about characterizing the asymptotically delivered solution. In the current article, we propose to address this limitation. More specifically, instead of employing a functional regularization, we perform an operator regularization, where a maximally monotone operator (MMO) is learned in a supervised manner. This formulation is flexible as it allows the solution to be characterized through a broad range of variational inequalities, and it includes convex regularizations as special cases. From an algorithmic standpoint, the proposed approach consists in replacing the resolvent of the MMO by a neural network (NN). We provide a universal approximation theorem proving that nonexpansive NNs provide suitable models for the resolvent of a wide class of MMOs. The proposed approach thus provides a sound theoretical framework for analyzing the asymptotic behavior of first-order PnP algorithms. In addition, we propose a numerical strategy to train NNs corresponding to resolvents of MMOs. We apply our approach to image restoration problems and demonstrate its validity in terms of both convergence and quality.

This paper studies an epidemic model with nonlocal dispersals. We focus on the influences of initial data and nonlocal dispersals on its spatial propagation. Here, initial data stand for the spatial concentrations of the infectious agent and the infectious human population when the epidemic breaks out and the nonlocal dispersals mean their diffusion strategies. Two types of initial data decaying to zero exponentially or faster are considered. For the first type, we show that spreading speeds are two constants whose signs change with the number of elements in some set. Moreover, we find an interesting phenomenon: the asymmetry of nonlocal dispersals can influence the propagating directions of the solutions and the stability of steady states. For the second type, we show that the spreading speed is decreasing with respect to the exponentially decaying rate of initial data, and further, its minimum value coincides with the spreading speed for the first type. In addition, we give some results about the nonexistence of traveling wave solutions and the monotone property of the solutions. Finally, some applications are presented to illustrate the theoretical results.

This paper proposes an accelerated proximal point method for maximally monotone operators. The proof is computer-assisted via the performance estimation problem approach. The proximal point method includes various well-known convex optimization methods, such as the proximal method of multipliers and the alternating direction method of multipliers, and thus the proposed acceleration has wide applications. Numerical experiments are presented to demonstrate the accelerating behaviors.

We conduct a pair of quasirandom estimations of the separability probabilities with respect to ten measures on the 15-dimensional convex set of two-qubit states, using its Euler-angle parameterization. The measures include the (non-monotone) Hilbert-Schmidt one, plus nine others based on operator monotone functions. Our results are supportive of previous assertions that the Hilbert-Schmidt and Bures (minimal monotone) separability probabilities are $\frac{8}{33} \approx 0.242424$ and $\frac{25}{341} \approx 0.0733138$, respectively, as well as suggestive of the Wigner-Yanase counterpart being $\frac{1}{20}$. However, one result appears inconsistent (much too small) with an earlier claim of ours that the separability probability associated with the operator monotone (geometric-mean) function $\sqrt{x}$ is $1-\frac{256}{27 \pi ^2} \approx 0.0393251$. But a seeming explanation for this disparity is that the volume of states for the $\sqrt{x}$-based measure is infinite. So, the validity of the earlier conjecture--as well as an alternative one, $\frac{1}{9} \left(593-60 \pi ^2\right) \approx 0.0915262$, we now introduce--can not be examined through the numerical approach adopted, at least perhaps not without some truncation procedure for extreme values., Comment: 19 pages, 16 figures--text moderately expanded, but sample size in main analyses doubled in size. To appear in International Journal of Quantum Information

In this paper, we discuss about monotone vector fields, which is a typical extension to the theory of convex functions, by exploiting the tangent space structure. This new approach to monotonicity in CAT(0) spaces stands in opposed to the monotonicity defined earlier in CAT(0) spaces by Khatibzadeh and Ranjbar [14] and Chaipunya and Kumam [8]. In particular, this new concept extends the theory from both Hilbert spaces and Hadamard manifolds, while the known concept barely has any obvious relationship to the theory in Hadamard manifolds. We also study the corresponding resolvents and Yosida approximations of a given monotone vector field and derive many of their important properties. Finally, we prove a generation theorem by showing convergence of an exponential formula applied to resolvents of a monotone vector field. Our findings improve several known results in the literature including generation theorems of Jost [13, Theorem 1.3.13], Mayer [19, Theorem 1.13], Stojkovic [22, Theorem 2.18], and Bac\'ak [4, Theorem 1.5] for proper, convex, lower semicontinuous functions in the context of complete CAT(0) spaces, and also by Iwamiya and Okochi [11, Theorem 4.1] for monotone vector fields in the context of Hadamard manifolds.

We study dynamic optimal portfolio allocation for monotone mean--variance preferences in a general semimartingale model. Armed with new results in this area we revisit the work of Cui, Li, Wang and Zhu (2012, MAFI) and fully characterize the circumstances under which one can set aside a non-negative cash flow while simultaneously improving the mean--variance efficiency of the left-over wealth. The paper analyzes, for the first time, the monotone hull of the Sharpe ratio and highlights its relevance to the problem at hand., Comment: (v4) updated bibliography

The problem of monotone smoothing splines with bounds is formulated as a constrained minimization problem of the calculus of variations. Existence and uniqueness of solutions of this problem is proved, as well as the equivalence of it to a finite dimensional but nonlinear optimization problem. A new algorithm for computing the solution which is a spline curve, using a branch and bound technique, is presented. The method is applied to examples in neuroscience and for fitting cumulative distribution functions from data.

We study a conical extension of averaged nonexpansive operators and the role it plays in convergence analysis of fixed point algorithms. Various properties of conically averaged operators are systematically investigated, in particular, the stability under relaxations, convex combinations and compositions. We derive conical averagedness properties of resolvents of generalized monotone operators. These properties are then utilized in order to analyze the convergence of the proximal point algorithm, the forward-backward algorithm, and the adaptive Douglas-Rachford algorithm. Our study unifies, improves and casts new light on recent studies of these topics.

In this paper, we introduce for the first time a class of state-dependent maximal monotone differential inclusions. Then the existence and uniqueness of solutions are obtained by using an implicit discretization scheme and a kind of hypo-monotonicity assumption respectively. In addition, a characterization for nonsmooth Lyapunov pairs associated with such systems is provided. Our result can be applied to study state-dependent sweeping processes and Lur'e dynamical systems. It is new even the involved maximal monotone operators depend only on the time.

We study deterministic continuous-time lossy dynamical flow networks with constant exogenous demands, fixed routing, and finite flow and buffer capacities. In the considered model, when the total net flow in a cell ---consisting of the difference between the total flow directed towards it minus the outflow from it--- exceeds a certain capacity constraint, then the exceeding part of it leaks out of the system. The ensuing network flow dynamics is a linear saturated system with compact state space that we analyze using tools from monotone systems and contraction theory. Specifically, we prove that there exists a set of equilibria that is globally asymptotically stable. Such equilibrium set reduces to a single globally asymptotically stable equilibrium for generic exogenous demand vectors. Moreover, we show that the critical exogenous demand vectors giving rise to non-unique equilibria correspond to phase transitions in the asymptotic behavior of the dynamical flow network., Comment: 7 pages, 4 figures, submitted at IFAC 2020

We study permutations $p$ such that both $p$ and $p^2$ avoid a given pattern $q$. We obtain a generating function for the case of $q=312$ (equivalently, $q=231$), we prove that if $q$ is monotone increasing, then above a certain length, there are no such permutations, and we prove an upper bound for $q=321$. We also present some intriguing questions in the case of $q=132$., Comment: 10 pages