Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

A regularized Newton method without line search for unconstrained optimization

In this paper, we propose a regularized Newton method without line search. The proposed method controls a regularization parameter instead of a step size in order to guarantee the global convergence. We show that the proposed algorithm has the following convergence properties. (a) The proposed algorithm has global convergence under appropriate conditions. (b) It has superlinear rate of convergence under the local error bound condition. (c) An upper bound of the number of iterations required to obtain an approximate solution \(x\) satisfying \(\Vert \nabla f(x) \Vert \le \varepsilon \) is \(O(\varepsilon ^{-2})\) , where \(f\) is the objective function and \(\varepsilon \) is a given positive constant.     

The Method of Alternating Resolvents Revisited

The purpose of this article is to prove a strong convergence result associated with a generalization of the method of alternating resolvents introduced by the authors in convergence of the method of alternating resolvents [4 O. A. Boikanyo and G. Moro?anu ( to appear ). Strong convergence of the method of alternating resolvents . J. Nonlinear Convex Anal.  [Google Scholar]] under minimal assumptions on the control parameters involved. Thus, this article represents a significant improvement of the article mentioned above.     

The truncated Euler–Maruyama method for stochastic differential delay equations

The numerical solutions of stochastic differential delay equations (SDDEs) under the generalized Khasminskii-type condition were discussed by Mao (Appl. Math. Comput. 217, 5512–5524 2011), and the theory there showed that the Euler–Maruyama (EM) numerical solutions converge to the true solutions in probability. However, there is so far no result on the strong convergence (namely in L ^p ) of the numerical solutions for the SDDEs under this generalized condition. In this paper, we will use the truncated EM method developed by Mao (J. Comput. Appl. Math. 290, 370–384 2015) to study the strong convergence of the numerical solutions for the SDDEs under the generalized Khasminskii-type condition.     

An improved local convergence analysis for a two-step Steffensen-type method

We study a class of Steffensen-type algorithm for solving nonsmooth variational inclusions in Banach spaces. We provide a local convergence analysis under ω-conditioned divided difference, and the Aubin continuity property. This work on the one hand extends the results on local convergence of Steffensen’s method related to the resolution of nonlinear equations (see Amat and Busquier in Comput. Math. Appl. 49:13–22, 2005; J. Math. Anal. Appl. 324:1084–1092, 2006; Argyros in Southwest J. Pure Appl. Math. 1:23–29, 1997; Nonlinear Anal. 62:179–194, 2005; J. Math. Anal. Appl. 322:146–157, 2006; Rev. Colomb. Math. 40:65–73, 2006; Computational Theory of Iterative Methods, 2007). On the other hand our approach improves the ratio of convergence and enlarges the convergence ball under weaker hypotheses than one given in Hilout (Commun. Appl. Nonlinear Anal. 14:27–34, 2007).     

On complete convergence in mean for double sums of independent random elements in Banach spaces

Conditions are provided under which a normed double sum of independent random elements in a real separable Rademacher type p Banach space converges completely to 0 in mean of order p. These conditions for the complete convergence in mean of order p are shown to provide an exact characterization of Rademacher type p Banach spaces. In case the Banach space is not of Rademacher type p, it is proved that the complete convergence in mean of order p of a normed double sum implies a strong law of large numbers.     

Joint functional convergence of partial sums and maxima for linear processes<Superscript>*</Superscript>

For linear processes with independent identically distributed innovations that are regularly varying with tail index α ∈ (0, 2), we study the functional convergence of the joint partial-sum and partial-maxima processes. We derive a functional limit theorem under certain assumptions on the coefficients of the linear processes, which enable the functional convergence in the space of ?²-valued càdlàg functions on [0, 1] with the Skorokhod weak M₂ topology.We also obtain a joint convergence in the M₂ topology on the first coordinate and in theM₁ topology on the second coordinate.     

A Kantorovich-type convergence analysis of the Newton–Josephy method for solving variational inequalities

We present a Kantorovich-type semilocal convergence analysis of the Newton–Josephy method for solving a certain class of variational inequalities. By using a combination of Lipschitz and center-Lipschitz conditions, and our new idea of recurrent functions, we provide an analysis with the following advantages over the earlier works (Wang 2009, Wang and Shen, Appl Math Mech 25:1291–1297, 2004) (under the same or less computational cost): weaker sufficient convergence conditions, larger convergence domain, finer error bounds on the distances involved, and an at least as precise information on the location of the solution.     

A note on the Douglas–Rachford splitting method for optimization problems involving hypoconvex functions

Recently, the convergence of the Douglas–Rachford splitting method (DRSM) was established for minimizing the sum of a nonsmooth strongly convex function and a nonsmooth hypoconvex function under the assumption that the strong convexity constant \(\beta \) is larger than the hypoconvexity constant \(\omega \). Such an assumption, implying the strong convexity of the objective function, precludes many interesting applications. In this paper, we prove the convergence of the DRSM for the case \(\beta =\omega \), under relatively mild assumptions compared with some existing work in the literature.     

On Local Convergence of the Method of Alternating Projections

The method of alternating projections is a classical tool to solve feasibility problems. Here we prove local convergence of alternating projections between subanalytic sets \(A,B\) under a mild regularity hypothesis on one of the sets. We show that the speed of convergence is \({\mathcal {O}}(k^{-\rho })\) for some \(\rho \in (0,\infty )\).     

Semilocal convergence for a class of improved multi-step Chebyshev–Halley-like methods under extended conditions

Semilocal convergence for a class of improved multi-step Chebyshev–Halley-like methods is considered in this paper. Compared with the results for the Chebyshev method in Hernández (J Comput Appl Math 126:131–143, 2000), the R-order of convergence is heightened and the Hölder continuity of second derivative is also relaxed. Moreover, an existence-uniqueness theorem is proved under the extended conditions.     

Random polarizations

We derive conditions under which random sequences of polarizations (two-point symmetrizations) on S^d${\mathbb{S}}^d$, R^d${\mathbb{R}}^d$, or H^d${\mathbb{H}}^d$ converge almost surely to the symmetric decreasing rearrangement. The parameters for the polarizations are independent random variables whose distributions need not be uniform. The proof of convergence hinges on an estimate for the expected distance from the limit that yields a bound on the rate of convergence. In the special case of i.i.d. sequences, almost sure convergence holds even for polarizations chosen at random from suitable small sets. As corollaries, we find bounds on the rate of convergence of Steiner symmetrizations that require no convexity assumptions, and show that full rotational symmetry can be achieved by randomly alternating Steiner symmetrizations in a finite number of directions that satisfy an explicit non-degeneracy condition. We also present some negative results on the rate of convergence and give examples where convergence fails.     

On the Existence in the Sense of Sequences of Stationary Solutions for Some Systems of Non-Fredholm Integro-differential Equations

We prove the existence in the sense of sequences of stationary solutions for some systems of reaction–diffusion type equations in the appropriate \(H^{2}\) spaces. It is established that, under reasonable technical conditions, the convergence in \(L^{1}\) of the integral kernels yields the existence and the convergence in \(H^{2}\) of the solutions. The nonlocal elliptic problems contain the second-order differential operators with and without Fredholm property.     

Complex D convergence and diagonal convergence of matrices

In this paper, types of convergence (also referred to as Schur stability) for complex matrices are studied. In particular, it is proven that for complex matrices of order $n?3$ diagonal convergence, $D_{\mathbb{C}}$ convergence and boundary convergence are all equivalent. An example of a 4 by 4 matrix that is $D_{\mathbb{C}}$ convergent but not diagonally convergent is constructed.     

Mixed problem for the wave equation with integrable potential in the case of two-point boundary conditions of distinct orders

We study a mixed problem for the wave equation with integrable potential and with two-point boundary conditions of distinct orders for the case in which the corresponding spectral problem may have multiple spectrum. Based on the resolvent approach in the Fourier method and the Krylov convergence acceleration trick for Fourier series, we obtain a classical solution u(x, t) of this problem under minimal constraints on the initial condition u(x, 0) = ?(x). We use the Carleson–Hunt theorem to prove the convergence almost everywhere of the formal solution series in the limit case of ?(x) ∈ L _p[0, 1], p > 1, and show that the formal solution is a generalized solution of the problem.     

Nonlocal Dezin’s problem for Lavrent’ev–Bitsadze equation

Using the method of spectral analysis, for the mixed type equation u_xx + (sgny)u_yy = 0 in a rectangular domain we establish a criterion of uniqueness of its solution satisfying periodicity conditions by the variable x, a nonlocal condition, and a boundary condition. The solution is constructed as the sum of a series in eigenfunctions for the corresponding one-dimensional spectral problem. At the investigation of convergence of the series, the problem of small denominators occurs. Under certain restrictions on the parameters of the problem and the functions, included in the boundary conditions, we prove uniform convergence of the constructed series and stability of the solution under perturbations of these functions.     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

A Variational Inequality Theory with Applications to $$-Laplacian Elliptic Inequalities

The main purpose of this paper is to establish variational inequality theory in connection with demicontinuous \(\psi_{p}\)-dissipative maps in reflexive smooth Banach spaces by considering the convergence of approximants. As an application of this variational inequality theory, existence, uniqueness and convergence of approximants of positive weak solution for \(p\)-Laplacian elliptic inequalities are obtained under suitable conditions.     

Optimal radius of convergence of interpolatory iterations for operator equations

The convergence of the class of direct interpolatory iterationsI _n for a simple zero of a non-linear operatorF in a Banach space of finite or infinite dimension is studied.A general convergence result is established and used to show that ifF is entire the radius of convergence goes to infinity withn while ifF is analytic in a ball of radiusR the radius of convergence increases to at leastR/2 withn.The research was supported in part by the National Science Foundation under Grant MCS 75-222-55 and the office of Naval Research under Contract N00014-76-C-0370, NR 044-422.