Search

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

One of the most famous single-valuedness results for set-valued maps is due to Kenderov [Fund. Math., LXXXVIII (1975), pp. 61--69] and states that a monotone set-valued operator is single-valued at any point where it is lower semicontinuous. This has been extended in Christensen and Kenderov [Math. Scand., 54 (1984), pp. 70--78] to monotone maps satisfying a so-called $*$-property. Our aim in this work is twofold: first, to prove that the $*$-property assumption can be weakened, and second, to emphasize that these classical single-valuedness results for monotone operators can be obtained, in very simple way, as direct consequences of counterpart results proved for quasi-monotone operators in terms of single-directionality.

We consider the primal problem of finding the zeros of the sum of a maximal monotone operator and the composition of another maximal monotone operator with a linear continuous operator. By formulat...

We give two self-dual regularizations of maximal monotone operators on Hilbert spaces. These regularizations and their set-valued inverses are strongly monotone, single-valued, and Lipschitz with full domain. Moreover, these regularizations graphically converge to the original monotone operator. If a maximal monotone operator has nonempty zeros, these self-dual regularizations can be used to find its least norm solution. When the maximal monotone operator is the subdifferential of a proper lower semicontinuous convex function with nonempty minimizers, this translates to finding the least norm minimizer.

Monotone operators are of basic importance in optimization as they generalize simultaneously subdifferential operators of convex functions and positive semidefinite (not necessarily symmetric) matrices. In 1970, Asplund [A monotone convergence theorem for sequences of nonlinear mapping, in Nonlinear Functional Analysis, American Math Society, Providence, RI, 1970, pp. 1-9] studied the additive decomposition of a maximal monotone operator as the sum of a subdifferential operator and an “irreducible” monotone operator. In 2007, Borwein and Wiersma [SIAM J. Optim., 18 (2007), pp. 946-960] introduced another additive decomposition, where the maximal monotone operator is written as the sum of a subdifferential operator and a “skew” monotone operator. Both decompositions are variants of the well-known additive decomposition of a matrix via its symmetric and skew part. This paper presents a detailed study of the Borwein-Wiersma decomposition of a maximal monotone linear relation. We give sufficient conditions and characterizations for a maximal monotone linear relation to be Borwein-Wiersma decomposable and show that Borwein-Wiersma decomposability implies Asplund decomposability. We exhibit irreducible linear maximal monotone operators without full domain, thus answering one of the questions raised by Borwein and Wiersma. The Borwein-Wiersma decomposition of any maximal monotone linear relation is made quite explicit in Hilbert space.

This paper deals with an iterative method, in a real Hilbert space, for approximating a common element of the set of fixed points of a demicontractive operator (possibly quasi-nonexpansive or strictly pseudocontractive) and the set of solutions of a variational inequality problem for a monotone, Lipschitz continuous mapping. The considered algorithm can be regarded as a combination of a variation of the hybrid steepest descent method and the so-called extragradient method. Under classical conditions, we prove the strong convergence of the sequences of iterates given by the considered scheme.

We establish representations of a monotone mapping as the sum of a maximal subdifferential mapping and a “remainder” monotone mapping, where the remainder is “acyclic” in the sense that it contains no nontrivial subdifferential component. This is the nonlinear analogue of a skew linear operator. Examples of indecomposable and acyclic operators are given. In particular, we present an explicit nonlinear acyclic operator.

We consider the size of monotone circuits for quadratic Boolean functions, that is, disjunctions of length-2 monomials. Our motivation is that a good (linear in the number of variables) lower bound on the monotone circuit size for a certain type of quadratic function would imply a good (even exponential) lower bound on the general nonmonotone circuit size. To get more insight into the structure of monotone circuits for quadratic functions, we consider the so-called single level conjecture posed explicitly in the early 1990s. The conjecture claims that monotone single level circuits, that is, circuits which have only one level of AND gates, for quadratic functions are not much larger than arbitrary monotone circuits. In this paper we disprove the conjecture as follows: there exist quadratic functions whose monotone circuits have linear size but whose monotone single level circuits require almost quadratic size.

We consider the forward-backward splitting method for finding a zero of the sum of two maximal monotone mappings. This method is known to converge when the inverse of the forward mapping is strongly monotone. We propose a modification to this method, in the spirit of the extragradient method for monotone variational inequalities, under which the method converges assuming only the forward mapping is (Lipschitz) continuous on some closed convex subset of its domain. The modification entails an additional forward step and a projection step at each iteration. Applications of the modified method to decomposition in convex programming and monotone variational inequalities are discussed.

Convergence of an algorithm for strongly monotone variational inequality problems (VIPs) is investigated. At each iteration, the algorithm adds a quadratic cut through the analytic center of the consequently shrinking convex set. It is shown that the sequence of analytic centers converges to the unique solution in ${\cal O}(1/\sqrt{k})$, where k is the number of iterations.

We consider a mixed problem composed in part of finding a zero of a maximal monotone operator and in part of solving a monotone variational inequality problem. We propose a solution method for this problem that alternates between a proximal step (for the maximal monotone operator part) and a projection-type step (for the monotone variational inequality part) and analyze its convergence and rate of convergence. This method extends a decomposition method of Chen and Teboulle [Math. Programming, 64 (1994), pp. 81--101] for convex programming and yields, as a by-product, new decomposition methods.

We propose new methods for solving the variational inequality problem where the underlying function $F$ is monotone. These methods may be viewed as projection-type methods in which the projection direction is modified by a strongly monotone mapping of the form $I - \alpha F$ or, if $F$ is affine with underlying matrix $M$, of the form $I+ \alpha M^T$, with $\alpha \in (0,\infty)$. We show that these methods are globally convergent, and if in addition a certain error bound based on the natural residual holds locally, the convergence is linear. Computational experience with the new methods is also reported.

The present paper shows that one cannot expect the Jackson type estimates to hold for higher degree moduli of smoothness in monotone (or comonotone) spline approximation. This result gives a complete negative answer to a question raised by DeVore for $m \geq 2$ in monotone spline approximation. It also indicates that an equivalence between monotone polynomial approximation and monotone spline approximation claimed by Wang is wrong in one direction. There are corresponding results in $L^p $ spaces.

A few simple notes are made in relation to the so-called fundamental theorem of mathematical finance; in particular, a simple counterexample to the martingale measure existence is given via the corresponding monotone linear continuous functional which has no monotone extensions.

A kind of structural stability with respect to a parameter $\theta \in \Theta $ for a generic strongly monotone discrete-time dynamical system $\{ {T_\theta ^n :X \to X;n \in \mathbb{Z}_ + } \}$ is studied. Here, X and $\Theta $ are strongly ordered spaces, and the mapping $(x,\theta ) \mapsto T_\theta x$ from $\mathcal{X}$ into X is assumed to be continuous, strongly monotone and satisfying a compactness hypothesis. A classification of structurally stable points in $\chi $ is introduced; the set of all such points is denoted by $\mathcal{S}$. No hyperbolicity hypothesis is assumed. If $\mathcal{X}$ is an open subset of a strongly ordered separable Banach space $\mathcal{V}$, it is proved that (1) $\mu (\mathcal{X} \backslash \mathcal{S}) = 0$ for every Gaussian measure $\mu $ on $\mathcal{V}$; (2) $(x,\theta ) \in \mathcal{S}$ implies $\omega _\theta (x) \times \{ \theta \} \subset \mathcal{S}$, where $\omega _\theta (x)$ denotes the $\omega $-limit set of $x \in X$ under the semigroup $\{ {T_\theta ^n :...

Hirsch’s results concerning quasi convergence of almost all trajectories of strongly monotone semiflows are derived under weaker assumptions adopted from Matano. The proofs are based on a sequential limit set trichotomy, which follows from the nonordering principle and the limit set dichotomy. The assumption excluding totally ordered arcs of equilibria, which is required for the set of asymptotically stable points to be dense, is verified for dynamical systems that are analytic on the state space.

We correct an error in the statement of Theorem 2.4 in “Convergence in strongly monotone systems with an increasing first integral” (M. Banaji and D. Angeli, SIAM J. Math. Anal., 42 (2010), pp. 334...

By using the penalty method and Ekeland’s variational principle, this paper proves the optimality condition for a solution to a nonconvex optimal control problem, in which the system is governed by a strongly monotone variational inequality.

In this paper we consider a linearization of a nonlinear monotone Hilbert network in a neighborhood of some operating point. Three theorems are established which give estimates for the difference between the exact and approximate current distribution. Two examples of specific networks are considered.

In this paper feedback systems described by nonlinear (possibly multivalued) monotone operators are considered. We establish conditions for the existence and uniqueness of outputs corresponding to a given pair of inputs, conditions for causality, Lipschitz continuity and stability. Also, feedback systems over an extended Hilbert space are discussed. Finally, linear approximations to a nonlinear feedback system are studied.

The initial-value problem is studied for evolution equations in Hilbert space of the general form d se(u)+N(u) l:, dt where and are maximal monotone operators. Existence of a solution is proved when1 is a subgradient and either is strongly monotone or 9 is coercive; existence is established also in the case where 1 is strongly monotone and is subgradient. Uniqueness is provedwhen one of or is continuous self-adjoint and thesum is strictlymonotone; examples of nonuniqueness are given. Applications are indicated for various classes of degenerate nonlinear partial differential equations or systems of mixed elliptic-parabolic-pseudo- parabolic types and problems with nonlocal nonlinearity.

Conditions characterizing optimal arcs for certain problems of Bolza in Hilbert spaces are obtained by using methods of convex analysis and of maximal monotone operators.

We prove Jackson type estimates for the approximation of monotone functions by monotone polynomials. The results are given in terms of the modulus of continuity of $f^{(k)} $ , for any $k \geqq 0$. The estimates are of the same order as for the unconstrained approximation by polynomials.

This article introduces new concepts called the moduli of monotonicity of a real function defined on an interval. They are a one-sided analogue of the well-known modulus of continuity, and are a measure of the extent by which a given function fails to be monotone. It is shown that they naturally arise in the process of approximating a real function by nondecreasing polynomials. Upper and lower bounds on the “degree of approximation” by monotone polynomials are derived in terms of these moduli.

Applied to strongly monotone variational inequalities, Newton’s algorithm achieves local quadratic convergence. In this paper it is shown how the basic Newton method can be modified to yield an algorithm whose global convergence can be guaranteed by monitoring the monotone decrease of the “gap function” associated with the variational inequality. Each iteration consists in the solution of a linear program in the space of primal-dual variables and of a linesearch. Convergence does not depend on strong monotonicity. However, under strong monotonicity and geometric stability assumptions, the set of active constraints at the solution is implicitly identified, and quadratic convergence is achieved.

We consider the nonlinear singular integral magnetic field equation $R{\bf{M}} = h{\bf{M}} + A{\bf{M}} = {\bf{H}}_a $, in the Hilbert space of vector-functions ${\bf{L}}^2 ( \Omega )$, where ${\bf{M}}$ is the magnetization vector, $( {h{\bf{M}}} )(x) = g [ {{\bf{M}}( x ),x]}$ is the total field, and $({\bf {AM}})(x) = ( - 1/(4\pi )){\operatorname{grad}}\,{\operatorname{div}}\smallint _\Omega ({\bf M}(y)/r)dy$. We prove that: (i) A is bounded, with $\parallel A\parallel = 1$; (ii) A is self-adjoint; (iii) A is positively semidefinite, with $( {A{\bf{M}},{\bf{M}}} )\geqq 0$.Uniqueness is proved in case h is strictly monotone; existence of $R^{ - 1} $ and its continuity are proved in case h is strongly monotone, continuous and bounded. In this case the Galerkin method (and, if magnetic-material is also isotropic, the Ritz method) is shown to yield a numerical solution of the equation.

For the numerical treatment of the nonlinear singular integral magnetic field equation $R{\bf M} = h{\bf M} + A{\bf M} = {\bf H}_a$, which has been considered by the author in Part I [SIAM J. Appl. Math., 39 (1980), pp. 14-20]. Tucker stability is established in the case where $(h{\bf M})(x) = {\bf g}({\bf M}(x),x)$ is a bounded, continuous, and strongly monotone operator in ${\bf L}^2 $. In the special cases ${\bf g}({\bf M},x) = c{\bf M}$ and ${\bf g}({\bf M},x) = g(M,x){{\bf M}/M}$, which are important for engineering applications, explicit perturbation estimates are obtained.

For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence $\{ z^k \} $ by taking $z^{k + 1} $ to be the minimizes of $f(z) + ({1 / {2c_k }})\| {z - z^k } \|^2 $, where $c_k > 0$. This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential $\partial f$ is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if $c_k $ stays large enough, in fact superlinear if $c_k \to \infty $. The case of $T = \partial f$ is treated in extra detail. Applicati...

Many $0 - 1$ programming problems can be reduced, at least in theory, to monotone problems in the same variables, i.e., ones whose set of feasible solutions is monotone. A class of special monotone sets, called master sets, is introduced. To each monotone set S one can associate a family F of master sets $S^ * $, so that all the facets of (the convex hull of) S can be obtained (by means of a straightforward transformation) from those of any $S^ * \in F$.