Newton-Like Dynamics and Forward-Backward Methods for Structured Monotone Inclusions in Hilbert Spaces

In a Hilbert space setting we introduce dynamical systems, which are linked to Newton and Levenberg–Marquardt methods. They are intended to solve, by splitting methods, inclusions governed by structured monotone operators M=A+B, where A is a general maximal monotone operator, and B is monotone and locally Lipschitz continuous. Based on the Minty representation of A as a Lipschitz manifold, we show that these dynamics can be formulated as differential systems, which are relevant to the Cauchy–Lipschitz theorem, and involve separately B and the resolvents of A. In the convex subdifferential case, by using Lyapunov asymptotic analysis, we prove a descent minimizing property and weak convergence to equilibria of the trajectories. Time discretization of these dynamics gives algorithms combining Newton’s method and forward-backward methods for solving structured monotone inclusions.     

A Class of Fejér Convergent Algorithms,Approximate Resolvents and the Hybrid Proximal-Extragradient Method

A new framework for analyzing Fejér convergent algorithms is presented. Using this framework, we define a very general class of Fejér convergent algorithms and establish its convergence properties. We also introduce a new definition of approximations of resolvents, which preserves some useful features of the exact resolvent and use this concept to present an unifying view of the Forward-Backward splitting method, Tseng’s Modified Forward-Backward splitting method, and Korpelevich’s method. We show that methods, based on families of approximate resolvents, fall within the aforementioned class of Fejér convergent methods. We prove that such approximate resolvents are the iteration maps of the Hybrid Proximal-Extragradient method, which is a generalization of the classical Proximal Point Algorithm.     

On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators

Nemirovski’s analysis (SIAM J. Optim. 15:229–251, 2005) indicates that the extragradient method has the O(1/t) convergence rate for variational inequalities with Lipschitz continuous monotone operators. For the same problems, in the last decades, a class of Fejér monotone projection and contraction methods is developed. Until now, only convergence results are available to these projection and contraction methods, though the numerical experiments indicate that they always outperform the extragradient method. The reason is that the former benefits from the ‘optimal’ step size in the contraction sense. In this paper, we prove the convergence rate under a unified conceptual framework, which includes the projection and contraction methods as special cases and thus perfects the theory of the existing projection and contraction methods. Preliminary numerical results demonstrate that the projection and contraction methods converge twice faster than the extragradient method.     

A family of operator splitting methods revisited

A family of operator splitting methods for maximal monotone operators is investigated. It generalizes the Douglas-Peaceman-Rachford-Varga class of methods in the way that it allows the scaling parameters to vary from iteration to iteration non-monotonically. Conditions for convergence of methods within this family and for obtaining a linear rate of convergence are given. These conditions cover more general cases than the existing ones.     

Lyusternik-Schnirelman theory and eigenvalue problems for monotone potential operators

We treat the eigenvalue problem Ax = λBx, where A and B are odd potential operators, A is strictly monotone, bounded, coercive, and continuously invertible, and B is monotone and compact. A naturally defined iteration operator is employed, together with the Lyusternik-Schnirelman theory, to prove the existence of infinitely many nontrivial eigenfunctions. With the possible exception of the multiplicity assertion the results which we obtain are not new. The method which we use, however, has not been applied before to problems of this type. It exploits both the potential character and the monotonicity of the operators and makes the treatment of the infinite dimensional problem essentially as simple as that of its finite dimensional analog. This simplification results primarily from the compactness properties of the iteration operator.     

Positive semigroups and algebraic Riccati equations in Banach spaces

We generalize Wonham’s theorem on solvability of algebraic operator Riccati equations to Banach spaces, namely there is a unique stabilizing solution to \(A^*P+PA-PBB^*P+C^*C=0\) when (A, B) is exponentially stabilizable and (C, A) is exponentially detectable. The proof is based on a new approach that treats the linear part of the equation as the generator of a positive semigroup on the space of symmetric operators from a Banach space to its dual, and the quadratic part as an order concave map. A direct analog of global Newton’s iteration for concave functions is then used to approximate the solution, the approximations converge in the strong operator topology, and the convergence is monotone. The linearized equations are the well-known Lyapunov equations of the form \(A^*P+PA=-Q\), and semigroup stability criterion in terms of them is also generalized.     

Approximating Solutions of Maximal Monotone Operators in Hilbert Spaces

Let H be a real Hilbert space and let T: H→2^H be a maximal monotone operator. In this paper, we first introduce two algorithms of approximating solutions of maximal monotone operators. One of them is to generate a strongly convergent sequence with limit vT⁻¹0. The other is to discuss the weak convergence of the proximal point algorithm. Next, using these results, we consider the problem of finding a minimizer of a convex function. Our methods are motivated by Halpern's iteration and Mann's iteration.     

一类求解单调变分不等式的隐式方法

1．引言变分不等式是一个非常有趣。非常困难的数学问题［"］．它具有广泛的应用（例如，数学规划中的许多基本问题都可以归结为一个变分不等式问题），因而得到深入的研究并有了不少算法［1，2，5－8，17－21］．对线性单调变分不等式，我们最近提出了一系列投影收缩算法Ig－13］．本文考虑求解单调变分不等式其中0CW是一闭凸集，F是从正p到自身的一个单调算子，一即有我们用比（·）表示到0上的投影．求解单调变分不等式的一个简单方法是基本投影法［1，6］，它的迭代式为然而，如果F不是仿射函数，只有当F一致强单调且LIPSChitZ连续…     

Average error bounds of trigonometric approximation on periodic Wiener spaces

In this paper, we study the approximation of identity operator and the convolution integral operator Bm by Fourier partial sum operators, Fejr operators, Valle-Poussin operators, Cesárooperators and Abel mean operators, respectively, on the periodic Wiener space (C1(R),Wo) and obtainthe average error estimations.     

On maximal monotone operators with relatively compact range

It is shown that every maximal monotone operator on a real Banach space with relatively compact range is of type NI. Moreover, if the space has a separable dual space then every maximally monotone operator T can be approximated by a sequence of maximal monotone operators of type NI, which converge to T in a reasonable sense (in the sense of Kuratowski-Painleve convergence).     

Properties of a quasi-uniformly monotone operator and its application to the electromagnetic p-curl systems

In this paper we propose a new concept of quasi-uniform monotonicity weaker than the uniform monotonicity which has been developed in the study of nonlinear operator equation Au = b. We prove that if A is a quasi-uniformly monotone and hemi-continuous operator, then A^?1 is strictly monotone, bounded and continuous, and thus the Galerkin approximations converge. Also we show an application of a quasi-uniformly monotone and hemi-continuous operator to the proof of the well-posedness and convergence of Galerkin approximations to the solution of steady-state electromagnetic p-curl systems.

     

On the method of alternating resolvents

The work of Hundal [H. Hundal, An alternating projection that does not converge in norm, Nonlinear Anal. 57 (1) (2004) 35-61] has revealed that the sequence generated by the method of alternating projections converges weakly, but not strongly in general. In this paper, we present several algorithms based on alternating resolvents of two maximal monotone operators, A and B, that can be used to approximate common zeros of A and B. In particular, we prove that the sequences generated by our algorithms converge strongly. A particular case of such algorithms enables one to approximate minimum values of certain convex functionals.     

Extragradient Methods for Solving Equilibrium Problems,Variational Inequalities,and Fixed Point Problems

In this paper, we propose the new extragradient algorithms for an α-inverse-strongly monotone operator and a relatively nonexpansive mapping in Banach spaces. We prove convergence theorems by this methods under suitable conditions. Applying our algorithms, we find a zero paint of maximal monotone operators. Using FMINCON optimization toolbox in MATLAB, we give an example to illustrate the usability of our results.     

A variant of forward-backward splitting method for the sum of two monotone operators with a new search strategy

In this paper, we propose variants of Forward-Backward splitting method for finding a zero of the sum of two operators. A classical modification of Forward-Backward method was proposed by Tseng, which is known to converge when the forward and the backward operators are monotone and with Lipschitz continuity of the forward operator. The conceptual algorithm proposed here improves Tseng’s method in some instances. The first and main part of our approach, contains an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. During the iteration process, the search performs only one calculation of the forward-backward operator in each tentative of the step. This achieves a considerable computational saving when the forward-backward operator is computationally expensive. The second part of the scheme consists in special projection steps. The convergence analysis of the proposed scheme is given assuming monotonicity on both operators, without Lipschitz continuity assumption on the forward operator.     

Progressive Regularization of Variational Inequalities and Decomposition Algorithms

For nonsymmetric operators involved in variational inequalities, the strong monotonicity of their possibly multivalued inverse operators (referred to as the Dunn property) appears to be the weakest requirement to ensure convergence of most iterative algorithms of resolution proposed in the literature. This implies the Lipschitz property, and both properties are equivalent for symmetric operators. For Lipschitz operators, the Dunn property is weaker than strong monotonicity, but is stronger than simple monotonicity. Moreover, it is always enforced by the Moreau–Yosida regularization and it is satisfied by the resolvents of monotone operators. Therefore, algorithms should always be applied to this regularized version or they should use resolvents: in a sense, this is what is achieved in proximal and splitting methods among others. However, the operation of regularization itself or the computation of resolvents may be as complex as solving the original variational inequality. In this paper, the concept of progressive regularization is introduced and a convergent algorithm is proposed for solving variational inequalities involving nonsymmetric monotone operators. Essentially, the idea is to use the auxiliary problem principle to perform the regularization operation and, at the same time, to solve the variational inequality in its approximately regularized version; thus, two iteration processes are performed simultaneously, instead of being nested in each other, yielding a global explicit iterative scheme. Parallel and sequential versions of the algorithm are presented. A simple numerical example demonstrates the behavior of these two versions for the case where previously proposed algorithms fail to converge unless regularization or computation of a resolvent is performed at each iteration. Since the auxiliary problem principle is a general framework to obtain decomposition methods, the results presented here extend the class of problems for which decomposition methods can be used.     

反向混合单调算子方程解的存在唯一性定理

运用锥与半序理论和非对称迭代方法,讨论半序Banach空间一类反向混合单调算子方程解的存在唯一性,并给出了迭代序列收敛于解的误差估计,作为其应用着重讨论了非反向混合单调算子方程解的存在唯一性,所得结果改进和推广了混合单调算子方程某些已知相应结果.     

An inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities

The augmented Lagrangian method is attractive in constraint optimizations. When it is applied to a class of constrained variational inequalities, the sub-problem in each iteration is a nonlinear complementarity problem (NCP). By introducing a logarithmic-quadratic proximal term, the sub-NCP becomes a system of nonlinear equations, which we call the LQP system. Solving a system of nonlinear equations is easier than the related NCP, because the solution of the NCP has combinatorial properties. In this paper, we present an inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities, in which the LQP system is solved approximately under a rather relaxed inexactness criterion. The generated sequence is Fejér monotone and the global convergence is proved. Finally, some numerical test results for traffic equilibrium problems are presented to demonstrate the efficiency of the method.      

Around Operator Monotone Functions

We show that the symmetrized product AB + BA of two positive operators A and B is positive if and only if f(A+B) ￡ f(A)+f(B){f(A+B)\leq f(A)+f(B)} for all non-negative operator monotone functions f on [0,∞) and deduce an operator inequality. We also give a necessary and sufficient condition for that the composition f °g{f \circ g} of an operator convex function f on [0,∞) and a non-negative operator monotone function g on an interval (a, b) is operator monotone and present some applications.     

Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations

For the non‐symmetric algebraic Riccati equations, we establish a class of alternately linearized implicit (ALI) iteration methods for computing its minimal non‐negative solutions by technical combination of alternate splitting and successive approximating of the algebraic Riccati operators. These methods include one iteration parameter, and suitable choices of this parameter may result in fast convergent iteration methods. Under suitable conditions, we prove the monotone convergence and estimate the asymptotic convergence factor of the ALI iteration matrix sequences. Numerical experiments show that the ALI iteration methods are feasible and effective, and can outperform the Newton iteration method and the fixed‐point iteration methods. Besides, we further generalize the known fixed‐point iterations, obtaining an extensive class of relaxed splitting iteration methods for solving the non‐symmetric algebraic Riccati equations. Copyright © 2006 John Wiley & Sons, Ltd.     

A Hybrid Proximal-Extragradient Algorithm with Inertial Effects

In this article, we incorporate inertial terms in the hybrid proximal-extragradient algorithm and investigate the convergence properties of the resulting iterative scheme designed to find the zeros of a maximally monotone operator in real Hilbert spaces. The convergence analysis relies on extended Fejér monotonicity techniques combined with the celebrated Opial Lemma. We also show that the classical hybrid proximal-extragradient algorithm and the inertial versions of the proximal point, the forward-backward and the forward-backward-forward algorithms can be embedded into the framework of the proposed iterative scheme.