Search

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

We consider a second order dynamical system for solving variational inequalities in Hilbert spaces. Under standard conditions, we prove the existence and uniqueness of strong global solution of the proposed dynamical system. The exponential convergence of trajectories is established under strong pseudo-monotonicity and Lipschitz continuity assumptions. A discrete version of the proposed dynamical system leads to a relaxed inertial projection algorithm whose linear convergence is proved under suitable conditions on parameters. We discuss the possibility of extension to general monotone inclusion problems. Finally some numerical experiments are reported demonstrating the theoretical results.

This paper studies the graph-theoretic conditions for stability of positive monotone systems. Using concepts from input-to-state stability and network small-gain theory, we first establish necessary and sufficient conditions for the stability of linear positive systems described by Metzler matrices. Specifically, we derive two sets of stability conditions based on two forms of input-to-state stability gains for Metzler systems, namely max-interconnection gains and sum-interconnection gains. Based on the max-interconnection gains, we show that the cyclic small-gain theorem becomes necessary and sufficient for the stability of Metzler systems; based on the sum-interconnection gains, we obtain novel graph-theoretic conditions for the stability of Metzler systems. All these conditions highlight the role of cycles in the interconnection graph and unveil how the structural properties of the graph affect stability. Finally, we extend our results to the nonlinear monotone system and obtain similar sufficient conditions for global asymptotic stability.

This work is concerned with a Freidlin--Wentzell type large deviation principle for a family of multiscale quasilinear and semilinear stochastic partial differential equations. Employing the weak c...

Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed by the Simplex method inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. We begin by showing that combinatorial cubes have monotone and Bland pivot height bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size pivot height, for all pivot rules. In contrast, we show that many well-known combinatorial polytopes have exponentially-long monotone paths. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths., Comment: 24 pages, 8 figures

Nonlinear multiscale problems are ubiquitous in materials science and biology. Complicated interactions between nonlinearities and (nonseparable) multiple scales pose a major challenge for analysis...

In the first part of the paper we provide a new classification of incompressible fluids characterized by a continuous monotone relation between the velocity gradient and the Cauchy stress. The considered class includes Euler fluids, Navier-Stokes fluids, classical power-law fluids as well as stress power-law fluids, and their various generalizations including the fluids that we refer to as activated fluids, namely fluids that behave as an Euler fluid prior activation and behave as a viscous fluid once activation takes place. We also present a classification concerning boundary conditions that are viewed as the constitutive relations on the boundary. In the second part of the paper, we develop a robust mathematical theory for activated Euler fluids associated with different types of the boundary conditions ranging from no-slip to freeslip and include Navier's slip as well as stick-slip. Both steady and unsteady flows of such fluids in three-dimensional domains are analyzed.

The introduction of the Hessian damping in the continuous version of Nesterov's accelerated gradient method provides, by temporal discretization, fast proximal gradient algorithms where the oscilla...

Finite difference schemes are the method of choice for solving nonlinear, degenerate elliptic PDEs, because the Barles--Souganidis convergence framework [G. Barles and P. E. Souganidis, Asymptotic ...

International audience; Quasi-variational inequalities are variational inequalities in which the constraint map depends on the current point. Due to this characteristic, specific proofs have been built to prove adapted existence results. Semicontinuity and generalized monotonicity are assumed and many efforts have been made in the last decades to use the weakest concepts. In the case of quasi-variational inequalities defined on a product of spaces, the existence statements in the literature require pseudomonotonicity of the operator, a hypothesis that is too strong for many applications, in particular in economics. On the other hand, the current minimal hypotheses for existence results for general quasi-variational inequalities are quasi-monotonicity and local upper sign-continuity. But since the product of quasi-monotone (respectively, locally upper sign-continuous) operators is not in general quasi-monotone (respectively, locally upper sign-continuous), it is thus quite difficult to use these general-type existence result in the quasi-variational inequalities defined on a product of spaces. In this work we prove, in an infinite-dimensional setting, several existence results for product-type quasi-variational inequalities by only assuming the quasi-monotonicity and local upper sign-continuity of the component operators. Our technique of proof is strongly based on an innovative stability result and on the new concept of net-lower sign-continuity.

Projective splitting is a family of methods for solving inclusions involving sums of maximal monotone operators. First introduced by Eckstein and Svaiter in 2008, these methods have enjoyed significant innovation in recent years, becoming one of the most flexible operator splitting frameworks available. While weak convergence of the iterates to a solution has been established, there have been few attempts to study convergence rates of projective splitting. The purpose of this paper is to do so under various assumptions. To this end, there are three main contributions. First, in the context of convex optimization, we establish an $O(1/k)$ ergodic function convergence rate. Second, for strongly monotone inclusions, strong convergence is established as well as an ergodic $O(1/\sqrt{k})$ convergence rate for the distance of the iterates to the solution. Finally, for inclusions featuring strong monotonicity and cocoercivity, linear convergence is established., Comment: This version adds references to the extragradient method

Here, we consider stationary monotone mean-field games (MFGs) and study the existence of weak solutions induced by monotonicity. First, we introduce a regularized problem that preserves the monoton...

The FitzHugh--Nagumo equations are known to admit fast traveling pulse solutions with monotone tails. It is also known that this system admits traveling pulses with exponentially decaying oscillato...

In this paper, we present a new monotone approximation of a given real-valued Caratheodory function on the product ${X}\times{A}$ of Borel spaces, where $A$ is also compact. We demonstrate its appl...

Property testers form an important class of sublinear algorithms. In the standard property testing model, an algorithm accesses the input function f:D -> R via an oracle. With very few exceptions, all property testers studied in this model rely on the oracle to provide function values at all queried domain points. However, in many realistic situations, the oracle may be unable to reveal the function values at some domain points due to privacy concerns, or when some of the values get erased by mistake or by an adversary. The testers do not learn anything useful about the property by querying those erased points. Moreover, the knowledge of a tester may enable an adversary to erase some of the values so as to increase the query complexity of the tester arbitrarily or, in some cases, make the tester entirely useless. In this work, we initiate a study of property testers that are resilient to the presence of adversarially erased function values. An alpha-erasure-resilient epsilon-tester is given parameters alpha, epsilon in (0,1), along with oracle access to a function f such that at most an alpha fraction of function values have been erased. The tester does not know whether a value is erased until it queries the corresponding domain point. The tester has to accept with high probability if there is a way to assign values to the erased points such that the resulting function satisfies the desired property P. It has to reject with high probability if, for every assignment of values to the erased points, the resulting function has to be changed in at least an epsilon-fraction of the non-erased domain points to satisfy P. We design erasure-resilient property testers for a large class of properties. For some properties, it is possible to obtain erasure-resilient testers by simply using standard testers as a black box. However, there are more challenging properties for which all known testers rely on querying a specific point. If this point is erased, all these testers break. We give efficient erasure-resilient testers for several important classes of such properties of functions including monotonicity, the Lipschitz property, and convexity. Finally, we show a separation between the standard testing and erasure-resilient testing. Specifically, we describe a property that can be epsilon-tested with O(1/epsilon) queries in the standard model, whereas testing it in the erasure-resilient model requires number of queries polynomial in the input size.

When approximating a function that depends on a parameter, one encounters many practical examples where linear interpolation or linear approximation with respect to the parameters prove ineffective. This is particularly true for responses from hyperbolic partial differential equations (PDEs) where linear, low-dimensional bases are difficult to construct. We propose the use of displacement interpolation where the interpolation is done on the optimal transport map between the functions at nearby parameters, to achieve an effective dimensionality reduction of hyperbolic phenomena. We further propose a multi-dimensional extension by using the intertwining property of the Radon transform. This extension is a generalization of the classical translational representation of Lax-Philips [Lax and Philips, Bull. Amer. Math. Soc. 70 (1964), pp.130--142].

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1=), where > 0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.) We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and well studied stochastic processes, including multi-type branching processes and stochastic context-free grammars.

The nonlinear systems obtained by discretizing degenerate parabolic equations may be hard to solve, especially with Newton's method. In this paper, we apply to the Richards equation, a strategy that consists of defining a new primary unknown for the continuous equation in order to stabilize Newton's method by parametrizing the graph linking the pressure and the saturation. The resulting form of the Richards equation is then discretized thanks to a monotone finite volume scheme. We prove the well-posedness of the numerical scheme. Then we show under appropriate nondegeneracy conditions on the parametrization that Newton's method converges locally and quadratically. Finally, we provide numerical evidences of the efficiency of our approach.

We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and it exploits new insight on the combinatorial structure of Robinsonian matrices. For an $n\times n$ nonnegative matrix with $m$ nonzero entries, it terminates in $n-1$ SFS sweeps, with overall running time $O(n^2 +nm\log n)$., Comment: 35 pages, 5 figures

We prove that a class of monotone, \emph{$W_1$-contractive} schemes for scalar conservation laws converge at a rate of $\Delta x^2$ in the Wasserstein distance ($W_1$-distance), whenever the initial data is decreasing and consists of a finite number of piecewise constants. It is shown that the Lax--Friedrichs, Enquist--Osher and Godunov schemes are $W_1$-contractive. Numerical experiments are presented to illustrate the main result. To the best of our knowledge, this is the first proof of second-order convergence of any numerical method for discontinuous solutions of nonlinear conservation laws.

A popular approach for addressing uncertainty in variational inequality problems is by solving the expected residual minimization (ERM) problem. This avenue necessitates distributional information associated with the uncertainty and requires minimizing nonconvex expectation-valued functions. We consider a distinctly different approach in the context of uncertain linear complementarity problems with a view towards obtaining robust solutions. Specifically, we define a robust solution to a complementarity problem as one that minimizes the worst-case of the gap function. In what we believe is amongst the first efforts to comprehensively address such problems in a distribution-free environment, we show that under specified assumptions on the uncertainty sets, the robust solutions to uncertain monotone linear complementarity problem can be tractably obtained through the solution of a single convex program. We also define uncertainty sets that ensure that robust solutions to non-monotone generalizations can also be obtained by solving convex programs. More generally, robust counterparts of uncertain non-monotone LCPs are proven to be low-dimensional nonconvex quadratically constrained quadratic programs. We show that these problems may be globally resolved by customizing an existing branching scheme. We further extend the tractability results to include uncertain affine variational inequality problems defined over uncertain polyhedral sets as well as to hierarchical regimes captured by mathematical programs with uncertain complementarity constraints. Preliminary numerics on uncertain linear complementarity and traffic equilibrium problems suggest that the presented avenues hold promise., Comment: 37 pages, 3 figures, 8 tables

We study a Dirichlet optimal control problem for a quasi-linear monotone elliptic equation, the so-called weighted p-Laplace problem. The coefficient of the p-Laplacian, the weight u, we take as a control in BV (Ω) ∩ L∞(Ω). In this article, we use box-type constraints for the control such that there is a strictly positive lower and some upper bound. In order to handle the inherent degeneracy of the p-Laplacian, we use a regularization, sometimes referred to as the ε-p-Laplacian. We derive existence and uniqueness of solutions to the underlying boundary value problem and the optimal control problem. In fact, we introduce a two-parameter model for the weighted ε-p- Laplacian, where we approximate the nonlinearity by a bounded monotone function, parametrized by k. Further, we discuss the asymptotic behavior of the solutions to the regularized problem on each (ε, k)-level as the parameters tend to zero and infinity, respectively. This author’s research was supported by the DFG-EC315 “Engineering of Advanced Materials” and by the Spanish Ministerio de Economía y Competitividad under projects MTM2011-22711 and MTM2014-57531-P.

We begin by considering second order dynamical systems of the from $\ddot x(t) + \gamma(t)\dot x(t) + \lambda(t)B(x(t))=0$, where $B: {\cal H}\rightarrow{\cal H}$ is a cocoercive operator defined on a real Hilbert space ${\cal H}$, $\lambda:[0,+\infty)\rightarrow [0,+\infty)$ is a relaxation function and $\gamma:[0,+\infty)\rightarrow [0,+\infty)$ a damping function, both depending on time. For the generated trajectories, we show existence and uniqueness of the generated trajectories as well as their weak asymptotic convergence to a zero of the operator $B$. The framework allows to address from similar perspectives second order dynamical systems associated with the problem of finding zeros of the sum of a maximally monotone operator and a cocoercive one. This captures as particular case the minimization of the sum of a nonsmooth convex function with a smooth convex one. Furthermore, we prove that when $B$ is the gradient of a smooth convex function the value of the latter converges along the ergodic trajectory to its minimal value with a rate of ${\cal O}(1/t)$.

A Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$ is said to be $\varepsilon$-far from monotone if $f$ needs to be modified in at least $\varepsilon$-fraction of the points to make it monotone. We design a randomized tester that is given oracle access to $f$ and an input parameter $\varepsilon>0$ and has the following guarantee: It outputs \sf Yes if the function is monotonically nondecreasing and outputs \sf No with probability $>2/3$, if the function is $\varepsilon$-far from monotone. This nonadaptive, one-sided tester makes $O(n^{7/8}\varepsilon^{-3/2}\ln(1/\varepsilon))$ queries to the oracle.

International audience; Results on stability of both local and global metric regularity under set-valued perturbations are presented. As an application, we study (super)linear convergence of a Newton- type iterative process for solving generalized equations. We investigate several iterative schemes such as the inexact Newton’s method, the nonsmooth Newton’s method for semismooth functions, the inexact proximal point algorithm, etc. Moreover, we also cover a forward-backward splitting algorithm for finding a zero of the sum of two multivalued (not necessarily monotone) operators. Finally, a globalization of the Newton’s method is discussed.

Operator splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which all simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze the convergence rate of the forward-Douglas-Rachford splitting (FDRS) algorithm, which is a generalization of the forward-backward splitting (FBS) and Douglas-Rachford splitting (DRS) algorithms. Under general convexity assumptions, we derive the ergodic and nonergodic convergence rates of the FDRS algorithm, and show that these rates are the best possible. Under Lipschitz differentiability assumptions, we show that the best iterate of FDRS converges as quickly as the last iterate of the FBS algorithm. Under strong convexity assumptions, we derive convergence rates for a sequence that strongly converges to a minimizer. Under strong convexity and Lipschitz differentiability assumptions, we show that FDRS converges linearly. We also provide examples where the objective is strongly convex, yet FDRS converges arbitrarily slowly. Finally, we relate the FDRS algorithm to a primal-dual forward-backward splitting scheme and clarify its place among existing splitting methods. Our results show that the FDRS algorithm automatically adapts to the regularity of the objective functions and achieves rates that improve upon the sharp worst case rates that hold in the absence of smoothness and strong convexity., Comment: 26 pages, 2 figures. Accepted for publication in SIAM Journal on Optimization

This paper is concerned with some new projection methods for solving variational inequality problems with monotone and Lipschitz-continuous mapping in Hilbert space. First, we propose the projected reflected gradient algorithm with a constant stepsize. It is similar to the projected gradient method, namely, the method requires only one projection onto the feasible set and only one value of the mapping per iteration. This distinguishes our method from most other projection-type methods for variational inequalities with monotone mapping. Also we prove that it has R-linear rate of convergence under the strong monotonicity assumption. The usual drawback of algorithms with constant stepsize is the requirement to know the Lipschitz constant of the mapping. To avoid this, we modify our first algorithm so that the algorithm needs at most two projections per iteration. In fact, our computational experience shows that such cases with two projections are very rare. This scheme, at least theoretically, seems to be very effective. All methods are shown to be globally convergent to a solution of the variational inequality. Preliminary results from numerical experiments are quite promising.

Primal-dual splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They decompose problems that are built from sums, linear compositions, and infimal convolutions of simple functions so that each simple term is processed individually via proximal mappings, gradient mappings, and multiplications by the linear maps. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze a monotone inclusion problem that captures a large class of primal-dual splittings as a special case. We introduce a unifying scheme and use some abstract analysis of the algorithm to prove convergence rates of the proximal point algorithm, forward-backward splitting, Peaceman-Rachford splitting, and forward-backward-forward splitting applied to the model problem. Our ergodic convergence rates are deduced under variable metrics, stepsizes, and relaxation. Our nonergodic convergence rates are the first shown in the literature. Finally, we apply our results to a large class of primal-dual algorithms that are a special case of our scheme and deduce their convergence rates., 31 pages, 1 table

$L^p$ optimal control with $p\in [0,1)$ is investigated. The difficulty of natural lack of convexity and thus of weak lower semicontinuity is addressed by introducing appropriately chosen regularization terms. Existence results and necessary optimality conditions are obtained, and convergence of a monotone scheme is proved. Special attention is given to the particular case of optimal control problems with quadratic tracking and regularized $L^0$ control costs are given. A maximum principle is derived and existence of controls, in some cases relaxed controls, is proved, and an estimate on the consequences of relaxation are estimated.

We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was ...

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182--196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659--668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1-e^{-c})/c approximation. This matches results of Vondrák [STOC, ACM, New York, 2008, pp. 67--74], who has shown that the continuous greedy algorithm produces a (1-e^{-c})/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.

This paper is concerned with Nicholson's blowflies equation, a kind of time-delayed reaction-diffusion equation. It is known that when the ratio of birth rate coefficient and death rate coefficient satisfies $1 e$, the equation losses its monotonicity, and its traveling waves are oscillatory when the time-delay $r$ or the wave speed $c$ is large, which causes the study of stability of these nonmonotone traveling waves to be challenging. In this paper, we use the technical weighted energy method to prove that when $e c_*>0$ are exponentially stable, where $c_*>0$ is the minimum wave speed. Here, we allow the traveling wave to be either monotone or nonmonotone with any speed $c>c_*$ and any size of the time-delay $r>0$; however, when $\frac{p}{d}> e^2$ with a smal...

We study the question of existence of positive steady states of nonlinear evolution equations. We recast the steady state equation in the form of eigenvalue problems for a parametrised family of unbounded linear operators, which are generators of strongly continuous semigroups; and a fixed point problem. In case of irreducible governing semigroups we consider evolution equations with non-monotone nonlinearities of dimension two, and we establish a new fixed point theorem for set-valued maps. In case of reducible governing semigroups we establish results for monotone nonlinearities of any finite dimension $n$. In addition, we establish a non-quasinilpotency result for a class of strictly positive operators, which are neither irreducible nor compact, in general. We illustrate our theoretical results with examples of partial differential equations arising in structured population dynamics. In particular, we establish existence of positive steady states of a size-structured juvenile-adult and a structured consumer-resource population model, as well as for a selection-mutation model with distributed recruitment process., Comment: to appear in SIAM Journal on Mathematical Analysis

A topological graph drawn on a cylinder whose base is horizontal is \emph{angularly monotone} if every vertical line intersects every edge at most once. Let $c(n)$ denote the maximum number $c$ such that every simple angularly monotone drawing of a complete graph on $n$ vertices contains at least $c$ pairwise disjoint edges. We show that for every simple complete topological graph $G$ there exists $\Delta$, $0

We consider the homogenization of monotone systems of viscous Hamilton-Jacobi equations with convex nonlinearities set in the stationary, ergodic setting. The primary focus of this paper is on collapsing systems which, as the microscopic scale tends to zero, average to a deterministic scalar Hamilton-Jacobi equation. However, our methods also apply to systems which do not collapse and, as the microscopic scale tends to zero, average to a deterministic system of Hamilton-Jacobi equations., Comment: 30 pages

International audience; A general primal-dual splitting algorithm for solving systems of structured coupled monotone inclusions in Hilbert spaces is introduced and its asymptotic behavior is analyzed. Each inclusion in the primal system features compositions with linear operators, parallel sums, and Lip-schitzian operators. All the operators involved in this structured model are used separately in the proposed algorithm, most steps of which can be executed in parallel. This provides a flexible solu-tion method applicable to a variety of problems beyond the reach of the state-of-the-art. Several applications are discussed to illustrate this point.

We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the optimization problem by repeated optimization over a randomly chosen one-dimensional subspace. This randomized method only uses zeroth-order information about the objective function and does not need any problem-specific parametrization. We prove convergence and give convergence rates for smooth objectives assuming that the one-dimensional optimization can be solved exactly or approximately by an oracle. A convenient property of Random Pursuit is its invariance under strictly monotone transformations of the objective function. It thus enjoys identical convergence behavior on a wider function class. To support the theoretical results we present extensive numerical performance results of Random Pursuit, two gradient-free algorithms recently proposed by Nesterov, and a classical adaptive step-size random search scheme. We also present an accelerated heuristic version of the Random Pursuit algorithm which significantly improves standard Random Pursuit on all numerical benchmark problems. A general comparison of the experimental results reveals that (i) standard Random Pursuit is effective on strongly convex functions with moderate condition number, and (ii) the accelerated scheme is comparable to Nesterov's fast gradient method and outperforms adaptive step-size strategies. The appendix contains additional supporting online material., Comment: 35 pages, 5 figures, 8 algorithms, 21 tables, submitted to journal The appendix contains additional supporting online material, not contained in the journal version

A curve $\gamma$ in the plane is $t$-monotone if its interior has at most $t-1$ vertical tangent points. A family of $t$-monotone curves $F$ is simple if any two members intersect at most once. It is shown that if $F$ is a simple family of $n$ $t$-monotone curves with at least $\epsilon n^2$ intersecting pairs (disjoint pairs), then there exists two subfamilies $F_1,F_2\subset F$ of size $\delta n$ each, such that every curve in $F_1$ intersects (is disjoint to) every curve in $F_2$, where $\delta$ depends only on $\epsilon$. We apply these results to find pairwise disjoint edges in simple topological graphs with $t$-monotone edges.

We present a quasi-monotone semi-Lagrangian particle level set (QMSL-PLS) method for moving interfaces. The QMSL method is a blend of first order monotone and second order semi-Lagrangian methods. The QMSL-PLS method is easy to implement, efficient, and well adapted for unstructured, either simplicial or hexahedral, meshes. We prove that it is unconditionally stable in the maximum discrete norm, $\parallel\cdot\parallel_{h,\infty}$, and the error analysis shows that when the level set solution $u(t)$ is in the Sobolev space $W^{r+1,\infty}(D), r\geq 0$, the convergence in the maximum norm is of the form $(KT/\Delta t)min(1,\Delta t\parallel v \parallel_{h,\infty}/h)((1-\alpha)h^{p}+h^{q})$, $p=min(2,r+1)$, and $q=min(3,r+1)$, where $v$ is a velocity. This means that at high CFL numbers, that is, when $\Delta t>h$, the error is $O(\frac{(1-\alpha)h^{p}+h^{q})}{\Delta t})$, whereas at CFL numbers less than 1, the error is $O((1-\alpha)h^{p-1}+h^{q-1}))$. We have tested our method with satisfactory results i...

The theory of viscosity solutions has been effective for representing and approximating weak solutions to fully nonlinear partial differential equations such as the elliptic Monge--Ampere equation. The approximation theory of Barles and Souganidis [Asymptotic Anal., 4 (1991), pp. 271--283] requires that numerical schemes be monotone (or elliptic in the sense of [A. M. Oberman, SIAM J. Numer. Anal., 44 (2006), pp. 879--895]). But such schemes have limited accuracy. In this article, we establish a convergence result for filtered schemes, which are nearly monotone. This allows us to construct finite difference discretizations of arbitrarily high-order. We demonstrate that the higher accuracy is achieved when solutions are sufficiently smooth. In addition, the filtered scheme provides a natural detection principle for singularities. We employ this framework to construct a formally second-order scheme for the Monge--Ampere equation and present computational results on smooth and singular solutions.

In a recent paper by Monteiro and Svaiter, a hybrid proximal extragradient (HPE) framework was used to study the iteration-complexity of a first-order (or, in the context of optimization, second-order) method for solving monotone nonlinear equations. The purpose of this paper is to extend this analysis to study a prox-type first-order method for monotone smooth variational inequalities and inclusion problems consisting of the sum of a smooth monotone map and a maximal monotone point-to-set operator. Each iteration of the method computes an approximate solution of a proximal subproblem obtained by linearizing the smooth part of the operator in the corresponding proximal equation for the original problem, which is then used to perform an extragradient step as prescribed by the HPE framework. Both pointwise and ergodic iteration-complexity results are derived for the aforementioned first-order method using corresponding results obtained here for a subfamily of the HPE framework.

This paper is mainly devoted to the study and applications of Holder metric subregularity (or metric $q$-subregularity of order $q\in(0,1]$) for general set-valued mappings between infinite-dimensional spaces. Employing advanced techniques of variational analysis and generalized differentiation, we derive neighborhood and point-based sufficient conditions as well as necessary conditions for $q$-metric subregularity with evaluating the exact subregularity bound, which are new even for the conventional (first-order) metric subregularity in both finite and infinite dimensions. In this way we also obtain new fractional error bound results for composite polynomial systems with explicit calculating fractional exponents. Finally, metric $q$-subregularity is applied to conduct a quantitative convergence analysis of the classical proximal point method (PPM) for finding zeros of maximal monotone operators on Hilbert spaces.

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are used in access control, property testing and data structures. We show a connection between 2-TC-spanners and local monotonicity filters. A local monotonicity filter, introduced by Saks and Seshadhri [SIAM J. Comput., pp. 2897–2926], is a randomized algorithm that, given access to an oracle for an almost monotone function $f : \{1,2,\dots,m\}^d \to \mathbb{R}$, can quickly evaluate a related function $g : \{1,2,\dots,m\}^d \to \mathbb{R}$ which is guaranteed to be monotone. Furthermore, the filter can be implemented in a distributed manner. We show that an efficient local monotonicity filter implies a sparse 2-TC-spanner of the directed hypergrid, providing a new technique for proving lower bounds for local monotonicity filters. Our connection is, in fact, ...

We consider a bistable differential-difference equation with inhomogeneous diffusion. Employing a piecewise linear nonlinearity, often referred to as McKean's caricature of the cubic, we construct front solutions which correspond, in the case of homogeneous diffusion, to monotone traveling front solutions or, in the case of propagation failure, to stationary front solutions. A general form for these fronts is given for essentially arbitrary inhomogeneous discrete diffusion, and conditions are given for the existence of solutions to the original discrete Nagumo equation. The specific case of one defect is considered in depth, giving a complete understanding of propagation failure and a grasp on changes in wave speed. Insight into the dynamic behavior of these front solutions as a function of the magnitude and relative position of the defects is obtained with the assistance of numerical results.

This paper develops a method of upper and lower solutions for a general system of second-order ordinary differential equations with two-point boundary conditions. Our motivation of study stems from a class of financial mathematics problems under regime-switching diffusion models. Two examples are double barrier option valuation and optimal selling rules in asset trading. We establish the existence of a unique $C^2$ solution of the two-point boundary value problem. We construct monotone sequences of upper and lower solutions that are shown to converge to the unique solution of the boundary value problem. This construction provides a feasible numerical method to compute approximate solutions. An important feature of the proposed numerical method is that the unique solution is bracketed by the upper and lower approximate solutions, which provide an interval estimate of the unique solution function. We apply the general results to a regime-switching mean-reverting model and improve related results already rep...

The elliptic Monge-Ampere equation is a fully nonlinear partial differential equation that originated in geometric surface theory and has been applied in dynamic meteorology, elasticity, geometric optics, image processing, and image registration. Solutions can be singular, in which case standard numerical approaches fail. Novel solution methods are required for stability and convergence to the weak (viscosity) solution. In this article we build a wide stencil finite difference discretization for the Monge-Ampere equation. The scheme is monotone, so the Barles-Souganidis theory allows us to prove that the solution of the scheme converges to the unique viscosity solution of the equation. Solutions of the scheme are found using a damped Newton's method. We prove convergence of Newton's method and provide a systematic method to determine a starting point for the Newton iteration. Computational results are presented in two and three dimensions, which demonstrates the speed and accuracy of the method on a number of exact solutions, which range in regularity from smooth to nondifferentiable.

We prove that the sequences generated by the Douglas-Rachford method converge weakly to zero of the sum of two maximal monotone operators using new tools introduced in recent works of Eckstein and the author. The assumption of maximal monotonicity of the sum is also removed, using a recent result of Bauschke.

The stability and monotonicity of nonlinear difference schemes are studied. The basic approach is to investigate a nonlinear scheme in terms of its corresponding scheme in variations. The advantage of such an approach is that the scheme in variations will always be linear and, hence, enables the investigation of the stability and monotonicity for nonlinear operators using linear patterns. In part I of our two-part paper, we focus on the theoretical background. We establish the notion that the stability (and monotonicity) of a scheme in variations implies the stability (and, respectively, monotonicity) of its original scheme, and that a nonlinear explicit scheme is stable iff (if and only if) the corresponding scheme in variations is stable. Criteria are developed for monotonicity and stability of difference schemes associated with the numerical analysis of systems of partial differential equations (PDEs). The theorem of Friedrichs (1954) is generalized to be applicable to variational schemes with nonsymmetric matrices. High-order interpolation and employment of monotone piecewise cubics in construction of monotone central schemes are considered. As applied to hyperbolic conservation laws with, in general, stiff source terms, we construct a second-order staggered central scheme based on operator-splitting techniques.

In [Z. Cai and S. Zhang, SIAM J. Numer. Anal., 47 (2009), pp. 2132-2156], we introduced and analyzed a recovery-based a posteriori error estimator for conforming linear finite element approximation to interface problems. It was shown theoretically that the estimator is robust with respect to the size of jumps provided that the distribution of coefficients is locally monotone. Numerical examples showed that this condition is unnecessary. This paper extends the idea in [Z. Cai and S. Zhang, SIAM J. Numer. Anal., 47 (2009), pp. 2132-2156] to mixed and nonconforming finite element methods for developing and analyzing robust estimators. Numerical results on test problems are also presented. Moreover, an a priori error estimate is obtained when the underlying problem has low regularity.

Two block monotone iterative schemes, called Jacobi and Gauss-Seidel monotone iterations, are presented for numerical solutions of a class of semilinear parabolic equations under nonlinear boundary conditions by the finite difference method. These iteration schemes extend the method for semilinear elliptic boundary value problems to parabolic equations, including a comparison result between them. It is shown that by using an upper solution and a lower solution as initial iterations each of the iterative schemes yields two sequences which converge monotonically from above and below, respectively, to a unique solution of the finite difference system. Some error estimates and a convergence theorem are given, and various sufficient conditions for the construction of upper and lower solutions are obtained. Numerical results are presented for some physical model problems, including some problems with known continuous solutions and two problems with L-shaped and trapezoidal domains.