A family of three-point methods of optimal order for solving nonlinear equations

A family of three-point iterative methods for solving nonlinear equations is constructed using a suitable parametric function and two arbitrary real parameters. It is proved that these methods have the convergence order eight requiring only four function evaluations per iteration. In this way it is demonstrated that the proposed class of methods supports the Kung-Traub hypothesis (1974) [3] on the upper bound 2ⁿ of the order of multipoint methods based on n+1 function evaluations. Consequently, this class of root solvers possesses very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed with only few function evaluations.     

A class of Steffensen type methods with optimal order of convergence

In this paper, a family of Steffensen type methods of fourth-order convergence for solving nonlinear smooth equations is suggested. In the proposed methods, a linear combination of divided differences is used to get a better approximation to the derivative of the given function. Each derivative-free member of the family requires only three evaluations of the given function per iteration. Therefore, this class of methods has efficiency index equal to 1.587. Kung and Traub conjectured that the order of convergence of any multipoint method without memory cannot exceed the bound 2^d-1, where d is the number of functional evaluations per step. The new class of methods agrees with this conjecture for the case d=3. Numerical examples are made to show the performance of the presented methods, on smooth and nonsmooth equations, and to compare with other ones.     

Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition

We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods. Received: April, 2004 The last author gratefully acknowledges the support from the Austrian Science Foundation FWF Project P12660-MAT.     

解非线性方程组的一类离散的Newton算法

1．引言考虑非线性方程组设xi是当前的迭代点，为计算下一个迭代点，Newton法是求解方程若用差商代替导数，离散Newton法要解如下的方程其中这里为了计算J（；；h），需计算n‘个函数值．为了提高效能，Brown方法l‘］使用代入消元的办法来减少函数值计算量．它是再通过一次内选代从h得到下一个迭代点14＋1．设n；＝（《1，…，Zn尸，t二（ti，…，t＊”，t为变量．BfOWll方法的基本思想如下．对人（x）在X；处做线性近似解出然后代入第二个函数，得到这是关于tZ，…，tn的函数．当（tZ，…，t。尸一（ZZ，…，Z。厂时，由（1．4），…     

Minimax efficient finite-difference stochastic gradient estimators using black-box function evaluations

Standard approaches to stochastic gradient estimation, with only noisy black-box function evaluations, use the finite-difference method or its variants. Though natural, it is open to our knowledge whether their statistical accuracy is the best possible. This paper argues so by showing that central finite-difference is a nearly minimax optimal zeroth-order gradient estimator for a suitable class of objective functions and mean squared risk, among both the class of linear estimators and the much larger class of all (nonlinear) estimators.     

一个阶为2+\sqrt{6}的Newton改进算法

针对非线性方程求单根问题,提出了一种新的Newton预测-校正格式.通过每步迭代增加计算一个函数值和一阶导数值,使得每步迭代需要估计两个函数值和两个一阶导数值.与标准的Newton算法的二阶收敛速度相比,新算法具有更高阶的收敛速度2+\sqrt{6}.通过测试函数对新算法进行测试, 与相关算法比较,表明算法在迭代次数、运算时间及最优值方面都具有较明显的优势. 最后,将这种新格式推广到多维向量值函数, 采用泰勒公式证明了其收敛性,并给出了两个二维算例来验证其收敛的有效性.     

Quasi-regression

Quasi-regression is introduced for approximation of functions on the unit cube in s dimensions. It is computationally efficient, compared to kriging, for problems requiring a large number of function evaluations. This paper describes how to implement quasi-regression and shows how to estimate the approximation error using the same data used to build the approximation. Four example functions are investigated numerically.     

Convex Optimization on Banach Spaces

Greedy algorithms which use only function evaluations are applied to convex optimization in a general Banach space \(X\). Along with algorithms that use exact evaluations, algorithms with approximate evaluations are treated. A priori upper bounds for the convergence rate of the proposed algorithms are given. These bounds depend on the smoothness of the objective function and the sparsity or compressibility (with respect to a given dictionary) of a point in \(X\) where the minimum is attained.     

A variant of Chebyshev’s method with sixth-order convergence

In this paper, we present a new variant of Chebyshev’s method for solving non-linear equations. Analysis of convergence shows that the new method has sixth-order convergence. Per iteration the new method requires two evaluations of the function, one of its first derivative and one of its second derivative. Thus the efficiency, in term of function evaluations, of the new method is better than that of Chebyshev’s method. Numerical examples verifying the theory are given.      

Stage reduction on P-stable Numerov type methods of eighth order

We present an implicit hybrid two step method for the solution of second order initial value problem. It costs only six function evaluations per step and attains eighth algebraic order. The method satisfy the P-stability property requiring one stage less. We conclude dealing with implementation issues for the methods of this type and give some first pleasant results from numerical tests.     

EfficientP-stable methods for periodic initial value problems

Efficient families ofP-stable formulae are developed for the numerical integration of periodic initial value problems where the required solution has an unknown period. Formulae of orders 4 and 6 requiring respectively 2 and 4 function evaluations per step are derived and some numerical results are given.     

Families of two-step fourth order P-stable methods for second order differential equations

This paper deals with a class of symmetric (hybrid) two-step fourth order P-stable methods for the numerical solution of special second order initial value problems. Such methods were proposed independently by Cash [1] and Chawla [3] and normally require three function evaluations per step. The purpose of this paper is to point out that there are some values of the (free) parameters available in the methods proposed which can reduce this work; we study two classes of such methods. The first is the class of ‘economical’ methods (see Definition 3.1) which reduce this work to two function evaluations per step, and the second is the class of ‘efficient’ methods (see Definition 3.2) which reduce this work with respect to implementation for nonlinear problems. We report numerical experiments to illustrate the order, acuracy and implementational aspects of these two classes of methods.     

Nonmonotonic trust region algorithm

A nonmonotonic trust region method for unconstrained optimization problems is presented. Although the method allows the sequence of values of the objective function to be nonmonotonic, convergence properties similar to those for the usual trust region method are proved under certain conditions, including conditions on the approximate solutions to the subproblem. To make the solution satisfy these conditions, an algorithm to solve the subproblem is also established. Finally, some numerical results are reported which show that the nonmonotonic trust region method is superior to the usual trust region method according to both the number of gradient evaluations and the number of function evaluations.The authors would like to thank Professor L. C. W. Dixon for his useful suggestions.     

On the economization of explicit Runge-Kutta methods

A modification to explicit Runge-Kutta (RK) methods is proposed. Schemes are constructed which require less derivative-evaluations to achieve a certain order than the classical RK methods do. As an example, we give a second-order method requiring one evaluation, two third-order methods using one and two evaluations, respectively and finally a fourth-order method which requires two evaluations. Numerical examples illustrate the behaviour of these schemes.     

Global and local convergence of a class of penalty-free-type methods for nonlinear programming

We present a class of trust region algorithms without using a penalty function or a filter for nonlinear inequality constrained optimization and analyze their global and local convergence. In each iteration, the algorithms reduce the value of objective function or the measure of constraints violation according to the relationship between optimality and feasibility. A sequence of steps focused on improving optimality is referred to as an f-loop, while some restoration phase focuses on improving feasibility and is called an h-loop. In an f-loop, the algorithms compute trial step by solving a classic QP subproblem rather than using composite-step strategy. Global convergence is ensured by requiring the constraints violation of each iteration not to exceed an progressively tighter bound on constraints violation. By using a second order correction strategy based on active set identification technique, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are encouraging.     

一类无需线性搜索的记忆梯度法

提出一类新的求解无约束优化问题的记忆梯度法,证明了算法的全局收敛性.当目标函数为一致凸函数时,对其线性收敛速率进行了分析.新算法在迭代过程中无需对步长进行线性搜索,仅需对算法中的一些参数进行预测估计,从而减少了目标函数及梯度的迭代次数,降低了算法的计算量和存储量.数值试验表明算法是有效的.     

A Steffensen-like method and its higher-order variants

For solving nonlinear equations, we suggest a second-order parametric Steffensen-like method, which is derivative free and only uses two evaluations of the function in one step. We also suggest a variant of the Steffensen-like method which is still derivative free and uses four evaluations of the function to achieve cubic convergence. Moreover, a fast Steffensen-like method with super quadratic convergence and a fast variant of the Steffensen-like method with super cubic convergence are proposed by using a parameter estimation. The error equations and asymptotic convergence constants are obtained for the discussed methods. The numerical results and the basins of attraction support the proposed methods.     

Modified Jarratt method with sixth-order convergence

In this paper, we present a variant of Jarratt method with order of convergence six for solving non-linear equations. Per iteration the method requires two evaluations of the function and two of its first derivatives. The new multistep iteration scheme, based on the new method, is developed and numerical tests verifying the theory are also given.     

Lower bounds on the convergence rate of the Markov symmetric random search

The convergence rate of the Markov random search algorithms designed for finding the extremizer of a function is investigated. It is shown that, for a wide class of random search methods that possess a natural symmetry property, the number of evaluations of the objective function needed to find the extremizer accurate to cannot grow slower than |ln ɛ|.     

解非线性方程组的一类算法

§1.引言 求解线性方程组 a_i~Tx=b_i,i=1,2,…,n,(1.1)其中a_1,a_2,…,a_n线性无关. 设y~((1))为初值,U~((1))为任意非奇异n阶矩阵,我们用如下方法求解方程组(1.1). 先考虑前k-1个方程组成的亚定方程组 a_i~Tx=b_i,i=1,2,…,k-1.设{U~((k))}={a_1,a_2,…,a_(k-1)},这里{U~((k))}表示由U~((k))的列组成的子空间.显然,rank(U~((k)))=n-b+1.若y~((k))是相应的亚定方程的一个特解,则将其看作方程组