On the convergence of multipoint iterations

Summary. This note gives a new convergence proof for iterations based on multipoint formulas. It rests on the very general assumption that if the desired fixed point appears as an argument in the formula then the formula returns the fixed point. Received March 24, 1993 / Revised version received January 1994     

On the convergence order of accelerated root iterations

Summary A Gauss-Seidel procedure for accelerating the convergence of the generalized method of the root iterations type of the (k+2)-th order (kN) for finding polynomial complex zeros, given in [7], is considered in this paper. It is shown that theR-order of convergence of the accelerated method is at leastk+1+ _n (k), where _n (k)>1 is the unique positive root of the equation ⁿ --k-1 = 0 andn is the degree of the polynomial. The examples of algebraic equations in ordinary and circular arithmetic are given.     

Second-order iterations with guaranteed convergence

Recent results on optimal extrapolations of first-order stationary iterations have shown that they are necessarily divergent in a wide class of problems. This paper examines a second-order iterative process which is guaranteed to converge — in particular when applied to the solution of an arbitrary equation system. A general convergence theory for semi-iterative techniques is established at the same time.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

Strong convergence of modified Mann iterations for a countable family of nonexpansive mappings

In this paper we propose a new modified Mann iteration for computing common fixed points of nonexpansive mappings in a Banach space. We give certain different control conditions for the modified Mann iteration. Then, we prove strong convergence theorems for a countable family of nonexpansive mappings in uniformly smooth Banach spaces. These results improve and extend results of Kim and Xu [T.H. Kim, H.K. Xu, Strong convergence of modified Mann iterations, Nonlinear Anal. 61 (2005) 51–60], Yao, et al. [Y. Yao, R. Chen and J. Yao, Strong convergence and certain control conditions for modified Mann iteration, Nonlinear Anal. 68 (2008) 1687–1693], Qin and Su [X. Qin, Y. Su, Approximation of a zero point of accretive operator in Banach spaces, J. Math. Anal. Appl. 329 (2007) 415–424], and many others.     

Semilocal convergence for a family of Chebyshev-Halley like iterations under a mild differentiability condition

The semilocal convergence of a family of Chebyshev-Halley like iterations for nonlinear operator equations is studied under the hypothesis that the first derivative satisfies a mild differentiability condition. This condition includes the usual Lipschitz condition and the H?lder condition as special cases. The method employed in the present paper is based on a family of recurrence relations. The R-order of convergence of the methods is also analyzed. As well, an application to a nonlinear Hammerstein integral equation of the second kind is provided. Furthermore, two numerical examples are presented to demonstrate the applicability and efficiency of the convergence results.     

On the convergence of modified Noor iterations with errors for asymptotically nonexpansive mappings

In this paper, several weak and strong convergence theorems are established for a modified Noor iterative scheme with errors for three asymptotically nonexpansive mappings in Banach spaces. Mann-type, Ishikawa-type, and Noor-type iterations are covered by the new iteration scheme. Our results extend and improve the recently announced ones [B.L. Xu, M.A. Noor, Fixed point iterations for asymptotically nonexpansive mappings in Banach spaces, J. Math. Anal. Appl. 267 (2002) 444-453; Y.J. Cho, H. Zhou, G. Guo, Weak and strong convergence theorems for three-step iterations with errors for asymptotically nonexpansive mappings, Comput. Math. Appl. 47 (2004) 707-717] and many others.     

CONVERGENCE BALL OF ITERATIONS WITH ONE PARAMETER

§1Introduction OfthevariousiterationmethodsusedtosolvetheequationF(x)=0,thefamilyof iterativemethodswithoneparameter xn+1=xn-I+12PF(I-αPF)-1F′(xn)-1F(xn),PF(x)=F′(x)-1F″(x)F′(x)-1F(x),α∈[0,1],(1)isremarkablebecauseitincludesthesuper-Halleymethod,theChebyshevmethodand Halley'smethodasitsspecialcaseswhenαisequalto1,0and1/2,respectively.Thereareanumberofpapersconcerningtheabovethreeiterations.In[1-7],Halley's methodisstudied.Amongthesereferences,[1]givestheconvergenceofHalley'sme…     

On the number of iterations of local improvement algorithms

A general model of local improvement algorithms in combinatorial optimization accurately confirms performance characteristics often observed in individual cases. The model predicts exponentially bad worst case and low order polynomial average run times for single optimum problems including some linear complementarity problems and linear programming. For problems with multiple local optima, most notably those that are NP-complete, average speed is linearly bounded but accuracy is poor.     

On the superlinear local convergence of a filter-SQP method

Transition to superlinear local convergence is shown for a modified version of the trust-region filter-SQP method for nonlinear programming introduced by Fletcher, Leyffer, and Toint [8]. Hereby, the original trust-region SQP-steps can be used without an additional second order correction. The main modification consists in using the Lagrangian function value instead of the objective function value in the filter together with an appropriate infeasibility measure. Moreover, it is shown that the modified trust-region filter-SQP method has the same global convergence properties as the original algorithm in [8].Mathematics Subject Classification (2000): 90C55, 65K05, 90C30     

A family of Steffensen type methods with seventh-order convergence

In this paper, based on some known fourth-order Steffensen type methods, we present a family of three-step seventh-order Steffensen type iterative methods for solving nonlinear equations and nonlinear systems. For nonlinear systems, a development of the inverse first-order divided difference operator for multivariable function is applied to prove the order of convergence of the new methods. Numerical experiments with comparison to some existing methods are provided to support the underlying theory.     

Strong convergence of averaging iterations of nonexpansive nonself-mappings

Let C be a closed convex subset of Hilbert space H, T a nonexpansive nonself-mapping from C into H, and x₀,x,y₀,y elements of C. In this paper, we study the convergence of the two sequences generated by

     

On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

Upper bounds for convergence rates of acceleration methods with initial iterations

GMRES(n,k), a version of GMRES for the solution of large sparse linear systems, is introduced. A cycle of GMRES(n,k) consists of n Richardson iterations followed by k iterations of GMRES. Such cycles can be repeated until convergence is achieved. The advantage in this approach is in the opportunity to use moderate k, which results in time and memory saving. Because the number of inner products among the vectors of iteration is about k^2/2, using a moderate k is particularly attractive on message-passing parallel architectures, where inner products require expensive global communication. The present analysis provides tight upper bounds for the convergence rates of GMRES(n,k) for problems with diagonalizable coefficient matrices whose spectra lie in an ellipse in 0. The advantage of GMRES(n,k) over GMRES(k) is illustrated numerically.     

On the convergence of series over local fields

Sufficient conditions are considered for the convergence of superpositions of formal sums of series over local fields. Applications of these conditions to the convergence of π₀ ⁿ-primary elements are studied. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Steklova AN SSSR, Vol. 198, pp. 28–30, 1991.     

On the local convergence of a derivative-free algorithm for least-squares minimization

In Zhang et al. (accepted by SIAM J. Optim., 2010), we developed a class of derivative-free algorithms, called DFLS, for least-squares minimization. Global convergence of the algorithm as well as its excellent numerical performance within a limited computational budget was established and discussed in the same paper. Here we would like to establish the local quadratic convergence of the algorithm for zero residual problems. Asymptotic convergence performance of the algorithm for both zero and nonzero problems is tested. Our numerical experiments indicate that the algorithm is also very promising for achieving high accuracy solutions compared with software packages that do not exploit the special structure of the least-squares problem or that use finite differences to approximate the gradients.     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

Techniques which accelerate the convergence of first order iterations automatically

This paper describes a way of approximating the optimal extrapolation of iterative techniques for solving equation systems. The approximations avoid auxiliary eigenvalue calculations and can be revised automatically during the iterative process. These extrapolations are cheap to compute and are particularly suited to solving nonlinear systems where the iteration matrix is path dependent.     

Forcing strong convergence of proximal point iterations in a Hilbert space

This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible since it amounts, at most, to solving a linear system of two equations in two unknowns. Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999