A note on Halley's method

Summary We introduce the degree of logarithmic convexity which provides a measure of the convexity of a function at each point. Making use of this concept we obtain a new theorem of global convergence for Halley's method.     

Euler级数的收敛性与组合学技巧

通过优序列方法，建立了Ｅｕｌｅｒ级数，即反函数的幂级数的收敛性，而且，我们发现Ｅｕｌｅｒ级数的系数和具有ｎ个元素的Ｓｃｈｒｏｄｅｒ系的个数之间的联系，以及Ｅｕｌｅｒ级数收敛半径的确切下界可通过相应的指母函数的收敛半径得到 。     

求解方程的一类迭代公式

Using the forms of Newton iterative function, the iterative function of Newton's method to handle the problem of multiple roots and the Halley iterative function, we give a class of iterative formulae for solving equations in one variable in this paper and show that their convergence order is at least quadratic. At last we employ our methods to solve some non-linear equations and compare them with Newton's method and Halley's method. Numerical results show that our iteration schemes are convergent if we choose two suitable parametric functions λ(x) and μ(x). Therefore, our iteration schemes are feasible and effective.     

THE ERROR ESTIMATES OF HALLEY''''S METHOD

In this paper we give an almost sharp error estimate of Halley's iteration for the majorizing sequence. Compared with the corresponding results in [6,14], it is far better. Meanwhile,the convergence theorem is established .for Halley's iteration in Banach spaces.     

Convergence of votex methods in a bounded domain using linear finite elements

In this work, the vortex method for the initial boundary valueproblem of Euler's equation is considered. We analyze linearfinite element methods to solve the Poisson equation, whichrequire less operations to compute the velocity field from thevorticity. We prove that the rate of convergence of the linearfinite element scheme is independent of the vortex blob parameters.     

A family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations

In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

算子稳定随机向量序列的一些极限结果

对于独立同分布的没有Gauss分量的指数为可逆线性算子A的算子稳定的R~d值随机向量序列,本文通过积分检验讨论了其部分和及加权和(包括一些经典的加权和,如Cesàro加权和,后置和方式,Euler可和方式,Borel可和方式,几何加权和等)的极限结果.由此得到了部分和及加权和在相对于A的谱分解下的Chover型重对数律,这是与A的特征值的实部有关的结果.     

Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems

It is well known that the sufficient descent condition is very important to the global convergence of the nonlinear conjugate gradient method. In this paper, some modified conjugate gradient methods which possess this property are presented. The global convergence of these proposed methods with the weak Wolfe–Powell (WWP) line search rule is established for nonconvex function under suitable conditions. Numerical results are reported. This work is supported by Guangxi University SF grands X061041 and China NSF grands 10761001.     

Sequential quadratic programming with a flexible step acceptance strategy

A new sequential quadratic programming (SQP) method for nonlinear inequality constrained optimization is proposed. The aim of this paper is to promote global convergence for SQP methods using a flexible step acceptance strategy which combines merit functions and filter techniques. Global convergence is proved under some reasonable assumptions and preliminary numerical results are reported.     

A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used. In this paper, we propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

     

Convergence of the Tamed Euler Method for Stochastic Differential Equations with Piecewise Continuous Arguments Under Non-global Lipschitz Continuous Coefficients

In this paper, we deal with the strong convergence of numerical methods for stochastic differential equations with piecewise continuous arguments (SEPCAs) with at most polynomially growing drift coefficients and global Lipschitz continuous diffusion coefficients. An explicit and time-saving tamed Euler method is used to solve this type of SEPCAs. We show that the tamed Euler method is bounded in pth moment. And then the convergence of the tamed Euler method is proved. Moreover, the convergence order is one-half. Several numerical simulations are shown to verify the convergence of this method.     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global A-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

CG Global Convergence Properties with Goldstein Linesearch*

This paper explores the convergence of nonlinear conjugate gradient methods with Goldstein line search without regular restarts. Under this line search, global convergence for a subsequence is given for the famous conjugate gradient methods, Fletcher-Reeves method. The same result can be obtained for Polak-Ribiére-Polyak method and others. *This work was partially supported by National Hitech Program (863,2002AA104540) and National Natural Science Foundation of China (No.60373060).     

Predictor-Corrector Smoothing Methods for Monotone LCP

In this paper, we analyze the global and local convergence properties of two predictor-corrector smoothing methods, which are based on the framework of the method in [1], for monotone linear complementarity problems (LCPs). The difference between the algorithm in [1] and our algorithms is that the neighborhood of smoothing central path in our paper is different to that in [1]. In addition, the difference between Algorithm 2.1 and the algorithm in [1] exists in the calculation of the predictor step. Comparing with the results in [1],the global and local convergence of the two methods can be obtained under very mild conditions. The global convergence of the two methods do not need the boundness of the inverse of the Jacobian. The superlinear convergence of Algorithm 2.1‘ is obtained under the assumption of nonsingularity of generalized Jacobian of Φ(x,y) at the limit point and Algorithm 2.1 obtains superlinear convergence under the assumption of strict complementarity at the solution. The efficiency of the two methods is tested by numerical experiments.     

Strong-norm error estimates for the projective-difference method for approximately solving abstract parabolic equations

Solutions continuously differentiable with respect to time of parabolic equations in Hilbert space are obtained by the projective-difference method approximately. The discretization of the problem is carried out in the spatial variables using Galerkin's method, and in the time variable using Euler's implicit method. Strong-norm error estimates for approximate solutions are obtained. These estimates not only allow one to establish the convergence of the approximate solutions to the exact ones but also yield numerical characteristics of the rates of convergence. In particular, order-sharp error estimates for finite element subspaces are obtained. Translated fromMatematicheskie Zametki, Vol. 63, No. 3, pp. 898–909, March, 1998. Translated by N. K. Kulman     

A new high order method of regula falsi type for computing a root of an equation

A hybrid method of order five (eight) which uses three (four) function evaluations per step is presented together with an algorithm which ensures global convergence. The method is compared with its closest competitors (among globally convergent methods which do not use derivatives) in a series of numerical examples. An ALGOL procedure of the method is included.     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global $A$-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

A new general form of conjugate gradient methods with guaranteed descent and strong global convergence properties

Although the study of global convergence of the Polak–Ribière–Polyak (PRP), Hestenes–Stiefel (HS) and Liu–Storey (LS) conjugate gradient methods has made great progress, the convergence of these algorithms for general nonlinear functions is still erratic, not to mention under weak conditions on the objective function and weak line search rules. Besides, it is also interesting to investigate whether there exists a general method that converges under the standard Armijo line search for general nonconvex functions, since very few relevant results have been achieved. So in this paper, we present a new general form of conjugate gradient methods whose theoretical significance is attractive. With any formula β _k  ≥ 0 and under weak conditions, the proposed method satisfies the sufficient descent condition independently of the line search used and the function convexity, and its global convergence can be achieved under the standard Wolfe line search or even under the standard Armijo line search. Based on this new method, convergence results on the PRP, HS, LS, Dai–Yuan–type (DY) and Conjugate–Descent–type (CD) methods are established. Preliminary numerical results show the efficiency of the proposed methods.     

Newton’s method and its use in optimization

Newton’s method is a basic tool in numerical analysis and numerous applications, including operations research and data mining. We survey the history of the method, its main ideas, convergence results, modifications, its global behavior. We focus on applications of the method for various classes of optimization problems, such as unconstrained minimization, equality constrained problems, convex programming and interior point methods. Some extensions (non-smooth problems, continuous analog, Smale’s results, etc.) are discussed briefly, while some others (e.g., versions of the method to achieve global convergence) are addressed in more details.