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

In this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a ...

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 tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems is established based on the squared fixed point residual. By using the performance estim...

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 ...

In this paper, we study the selection mechanism of the minimal wave speed for traveling waves to an abstract monotone semiflow. A necessary and sufficient condition for the nonlinear selection of t...

We propose an extension to our monotone and convergent method for the Monge--Ampere equation in dimension $d \geq2$ that incorporates the idea of filtered schemes. The method combines our original ...

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...

Fitzpatrick's variational representation of maximal monotone operators is here extended to a class of pseudo-monotone operators in Banach spaces. On this basis, the associated first-order flow is here reformulated as a minimization principle, extending a method that was pioneered by Brezis, Ekeland, and Nayroles for gradient flows. This formulation is used to prove that this family of problems is compact and stable with respect to arbitrary perturbations not only of data but also of operators. This is achieved via evolutionary $\Gamma$-convergence with respect to a nonlinear topology of weak type. These results are applied to the Cauchy problem for quasilinear parabolic PDEs. This provides the structural compactness and stability of models of several physical phenomena: nonlinear diffusion, incompressible viscous flow, phase transitions, and so on.

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 derive optimal error estimates in the max norm for the two-scale method for the Monge--Ampere equation introduced in [R. H. Nochetto, D. Ntogkas, and W. Zhang, “Two-scale method for the Monge-Am...

We introduce a new class of nonlocal nonlinear conservation laws in one space dimension that allow for nonlocal interactions over a finite horizon. The proposed model, which we refer to as the nonlocal pair-interaction model, inherits at the continuum level the unwinding feature of finite difference schemes for local hyperbolic conservation laws, so that the maximum principle and certain monotonicity properties hold and, consequently, the entropy inequalities are naturally satisfied. We establish a global-in-time well-posedness theory for these models which covers a broad class of initial data. Moreover, in the limit when the horizon parameter approaches zero, we are able to prove that our nonlocal model reduces to the conventional class of local hyperbolic conservation laws. Furthermore, we propose a numerical discretization method adapted to our nonlocal model, which relies on a monotone numerical flux and a uniform mesh, and we establish that these numerical solutions converge to a solution, providing ...

In this paper, we give a rigorous proof of the damping of the velocity and magnetic field for the linearized MHD equations around strictly monotone positive magnetic field $\mathbf{B}_{s}=(b(y), 0)...

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.

We consider semiflows in general Banach spaces motivated by monotone cyclic feedback systems or differential equations with integer-valued Lyapunov functionals. These semiflows enjoy strong monotonicity properties with respect to “cones” of high ranks, which imply order-related structures on the $\omega$-limit sets of precompact semiorbits. We show that for a pseudoordered precompact semiorbit the $\omega$-limit set $\omega(x)$ either is ordered, or is contained in the set of equilibria, or possesses a certain ordered homoclinic property. In particular, we show that if $\omega(x)$ contains no equilibrium, then $\omega(x)$ is ordered, and hence the dynamics of the semiflow on $\omega(x)$ is topologically conjugate to a compact flow on $\mathbb{R}^k$ with $k$ being the rank. We also establish a Poincare--Bendixson-type theorem in the case where $k=2$. All our results are established without the smoothness condition on the semiflow, allowing applications to many cellular or physiological feedback systems wit...

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.

This paper addresses a control system governed by two ODEs with a hysteresis nonlinearity of generalized play type. The characteristic curves describing the hysteresis region are allowed to be unbounded and are not necessarily monotone. The existence of solutions and some of their properties are established for our control system.

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of ones. Jerrum and Snir [J ACM 29 (1982), pp. 874--897] proved that tropical circuit complexity of homogeneous problems coincides with the monotone arithmetic circuit complexity of the corresponding polynomials. So, lower bounds on the monotone arithmetic circuit complexity of these polynomials yield lower bounds on the tropical complexity of the corresponding optimization problems. But the situation with nonhomogeneous problems is entirely different: here the gap between their tropical and arithmetic complexities can be even exponential. In this paper, we improve two classical lower bounds for monotone arithmetic circuits---Schnorr's bound and Hyafil--Valiant's bound---and use these improvements to derive general lower bounds for the tropical circuit complexity of nonhomogene...

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)$.

In large random graphs with fixed edge density and triangle density, it has been observed numerically [C. Radin, K. Ren, and L. Sadun, J. Phys. A, 47 (2014)] that a typical graph is finite-podal, meaning that it has only finitely many distinct “types” of vertices. In particular, it seems to be a fundamental property of such graphs to have large groups of vertices that are all of the same type. In this paper we describe a mechanism that produces such behavior. By known results on graph limits, the problem reduces to the study of a constrained maximization problem for symmetric measurable functions (graphons) on the unit square. As a first step we prove that, under an assumption that holds for a wide range of parameter values, the constrained maximizers are in some sense monotone.

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.

This paper is concerned with numerical methods for a class of two-dimensional quasi-linear elliptic boundary value problems. A compact finite difference method with a nonisotropic mesh is proposed for the problems. The existence of a maximal and a minimal compact difference solution is proved by the method of upper and lower solutions, and two sufficient conditions for the uniqueness of the solution are also given. The optimal error estimate in the discrete $L^{\infty}$ norm is obtained under certain conditions. The error estimate shows the fourth-order accuracy of the proposed method when two spatial mesh sizes are proportional. By using an upper solution or a lower solution as the initial iteration, an “almost optimal” Picard type of monotone iterative algorithm is presented for solving the resulting nonlinear discrete system efficiently. Applications using two model problems give numerical results that confirm our theoretical analysis.

We consider network models for isentropic flow and evaluate the application of three different momentum-related coupling constants: pressure, momentum flux, and the Bernoulli invariant. Subsonic solutions to generalized Riemann problems with subsonic initial conditions are proved to be unique, and the region where such initial conditions yield subsonic solutions is identified. The proof is restricted to monotone coupling constants. We also prove that the three momentum-related coupling constants fulfill the monotonicity constraint. Further, we analyze the existence of entropic solutions using a commonly applied entropy condition. The condition states that nonphysical solutions are characterized by production of mechanical energy at a junction. Both pressure and momentum flux are seen to yield nonphysical solutions in a constructed test case consisting of three pipe sections of equal cross-sectional area that are connected at a junction. The Bernoulli invariant is proved to yield entropic solutions for all...

A classical problem in ergodic control consists of studying the limit behavior of the optimal value $V_\lambda$ of a discounted cost functional with infinite horizon as the discount factor $\lambda$ tends to zero. In the literature, this problem has been addressed under various conditions ensuring that the rescaled value function $\lambda V_\lambda$ converges uniformly to a constant limit. The main goal of this paper is to study this problem without such conditions, so that the aforementioned limit need not be constant. So, under a nonexpansivity assumption, we derive Lipschitz bounds which yield compactness of $\{\lambda V_\lambda\}$ for both control systems and differential games. Then, we study the convergence of solutions to Hamilton--Jacobi equations under the hypothesis that the Hamiltonian is radially nondecreasing, hence allowing for the existence noncoercivity directions. Using PDE methods, we show that the convergence is monotone and we characterize the limit as the maximal subsolution of a cert...

In the present paper, we discuss the behavior of a boundary layer, called a sheath, arising in the plasma physics. We define the sheath by a monotone stationary solution to the Euler--Poisson equat...

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.

This article considers the (two-player) composite Nash equilibrium (CNE) problem with a separable nonsmooth part, which is known to include the composite saddle-point (CSP) problem as a special case. Due to its two-block structure, this problem can be solved by any algorithm belonging to the block-decomposition hybrid proximal-extragradient (BD-HPE) framework proposed in [R. D. C. Monteiro and B. F. Svaiter, SIAM J. Optim., 23 (2013), pp. 475--507]. The framework consists of a family of inexact proximal point methods for solving a more general two-block structured monotone inclusion problem which, at every iteration, solves two prox subinclusions according to a certain relative error criterion. By exploiting the fact that the two prox subinclusions in the context of the CNE problem are equivalent to two composite convex programs, this article proposes a new instance of the BD-HPE framework that approximately solves them using an accelerated gradient method. It is shown that the new instance is able to tak...

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.

This paper presents a hybrid proximal extragradient (HPE) self-concordant primal barrier method for solving a monotone variational inequality over a closed convex set endowed with a self-concordant barrier and with an underlying map that has Lipschitz continuous derivative. In contrast to the iteration of a previous method developed by the first and third authors that has to compute an approximate solution of a linearized variational inequality, the one of the present method solves a simpler Newton system of linear equations. The method performs two types of iterations, namely, those that follow ever changing interior paths and those that correspond to large-step HPE iterations. Due to its first-order nature, the present method is shown to have a better iteration-complexity than its zeroth order counterparts such as Korpelevich's algorithm and Tseng's modified forward-backward splitting method, although its work per iteration is larger than the one for the latter methods.

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 propose a generalized proximal point algorithm (PPA) in the generic setting of finding a root of a maximal monotone operator. In addition to the classical PPA, a number of benchmark operator splitting methods in the PDE and optimization literatures can be retrieved by this generalized PPA scheme. We establish the convergence rate of this generalized PPA scheme under different conditions, including estimating its worst-case convergence rate measured by the iteration complexity under mild assumptions and deriving its linear convergence rate under certain stronger conditions. Throughout our discussion, we pay particular attention to the special case where the operator is the sum of two maximal monotone operators and specify our theoretical results in the generic setting to this special case. Our result turns out to be a general and unified study on the convergence rate of a number of existing methods and subsumes some existing results in the literature.

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.