一类改进BFGS算法及其收敛性分析

本文针对无约束最优化问题,基于目标函数的局部二次模型近似,提出一类改进的BFGS算法,称为 MBFGS算法。其修正 B_k的公式中含有一个参数θ∈[0,l],当 θ= 1时即得经典的BFGS公式;当θ∈[0、l）时,所得公式已不属于拟Newton类。在目标函数一致凸假设下,证明了所给算法的全局收敛性及局部超线性收敛性。     

Blended extended linear multistep methods for the accurate numerical integration of stiff initial value problems

A class of blended extended linear multistep methods suitable for the approximate numerical integration of stiff systems of first order ordinary differential equations is described. These methods are formulated as a result of combining the second derivative extended backward differentiation formulae of Cash and the blended linear multistep methods of Skeel and Kong. The new methods combine a high order or accuracy with good stability properties and, as a direct consequence, they are often suitable for the numerical integration of stiff differential systems when high accuracy is requested. In the first part of the present paper we consider the derivation of these new blended methods and give the coefficients and stability regions for formulae of order up to and including 10. In the second half we consider their practical implementation. In particular we describe a variable order/variable step package based on these blended formulae and we evaluate the performance of this package on the well known DETEST test set. It is shown that the new code is reliable on this test set and is competitive with the well known second derivative method of Enright.     

A Quasi-Newton Algorithm Without Calculating Derivatives for Unconstrained Optimization

1.IntroductionWeconsidertheunconstrainedoptimizationproblemMinf(x)(1-1)wheref(x):M-misarealcontinuouslydifferentiablefunction.Manyalgorithmshavebeenproposedforsolving(1.1).TypicallygivenbothanaPproximationHto[V'f(x)]-'andgthegradientVf(x)atthecurrentpointx,aquasiNewtonalgorithInstartseachiterationbytakingastepx =x~aHg,(1'2)wherethesteplentha>oischosensothatandaresatisfied,whereaE(o,1/2)andTE(a,1);andthentoformH ,anestimateof[7'f(x)]-'byusinganupdatingformulasatisfyingthequasi-Newtoncondi…     

用加权平均方法构造新的隐式线性多步法公式

在已知的线性多步法公式中,用两个较适合的线性多步法进行加权平均就能构造出一系列新的隐式线性多步法公式,而且其中有些公式可能具有较好的性质,如稳定域增大.从而使得解刚性方程时,可以根据对稳定域与截断误差不同的需求来选择公式,以达到在适合的稳定域下,截断误差最小.经过数值试验验证,本文举出的实例中用加权平均方法构造出的有些新公式的稳定域大于原来两个公式任一个的稳定域,可应用于求解常微分方程初值问题的刚性问题.     

Argumentation update in YALLA (Yet Another Logic Language for Argumentation)

This article proposes a complete framework for handling the dynamics of an abstract argumentation system. This frame can encompass several belief bases under the form of several argumentation systems, more precisely it is possible to express and study how an agent who has her own argumentation system can interact on a target argumentation system (that may represent a state of knowledge at a given stage of a debate). The two argumentation systems are defined inside a reference argumentation system called the universe which constitutes a kind of “common language”. This paper establishes three main results. First, we show that change in argumentation in such a framework can be seen as a particular case of belief update. Second, we have introduced a new logical language called YALLA in which the structure of an argumentation system can be encoded, enabling to express all the basic notions of argumentation theory (defense, conflict-freeness, extensions) by formulae of YALLA. Third, due to previous works about dynamics in argumentation we have been in position to provide a set of new properties that are specific for argumentation update.     

Notes on the Dai-Yuan-Yuan modified spectral gradient method

In this paper, we give some notes on the two modified spectral gradient methods which were developed in [10]. These notes present the relationship between their stepsize formulae and some new secant equations in the quasi-Newton method. In particular, we also introduce another two new choices of stepsize. By using an efficient nonmonotone line search technique, we propose some new spectral gradient methods. Under some mild conditions, we show that these proposed methods are globally convergent. Numerical experiments on a large number of test problems from the CUTEr library are also reported, which show that the efficiency of these proposed methods.     

Methods of judging shape of solitary wave and solution formulae for some evolution equations with nonlinear terms of high order

In this paper, we present several methods of judging shape of the solitary wave and solution formulae for some nonlinear evolution equations by means of Lienard equations. Then, using the judgement methods and solution formulae, we obtain solutions of the solitary wave for some of important nonlinear evolution equations, which include generalized modified Boussinesq, generalized nonlinear wave, generalized Fisher, generalized Klein-Gordon and generalized Zakharov equations. Some new solitary-wave solutions are found for the equations.     

Analysis on a superlinearly convergent augmented Lagrangian method

The augmented Lagrangian method is a classical method for solving constrained optimization.Recently,the augmented Lagrangian method attracts much attention due to its applications to sparse optimization in compressive sensing and low rank matrix optimization problems.However,most Lagrangian methods use first order information to update the Lagrange multipliers,which lead to only linear convergence.In this paper,we study an update technique based on second order information and prove that superlinear convergence can be obtained.Theoretical properties of the update formula are given and some implementation issues regarding the new update are also discussed.     

A class of rank-two ellipsoid algorithms for convex programming

In this paper, we develop a method for constructing minimum volume ellipsoids containing a wedge-shaped subset of a given ellipsoid. This construction yields a class of ellipsoid algorithms for convex programming that use rank-two update formulae. Research supported by the National Science Foundation, Grant No. MC582-01790.     

Construction of Newton-like iteration methods for solving nonlinear equations

In this paper, we present a simple, and yet powerful and easily applicable scheme in constructing the Newton-like iteration formulae for the computation of the solutions of nonlinear equations. The new scheme is based on the homotopy analysis method applied to equations in general form equivalent to the nonlinear equations. It provides a tool to develop new Newton-like iteration methods or to improve the existing iteration methods which contains the well-known Newton iteration formula in logic; those all improve the Newton method. The orders of convergence and corresponding error equations of the obtained iteration formulae are derived analytically or with the help of Maple. Some numerical tests are given to support the theory developed in this paper.     

Interpolatory quadrature formulae with Chebyshev abscissae of the third or fourth kind

We consider interpolatory quadrature formulae, relative to the Legendre weight function on [−1, 1], having as nodes the zeros of the nth-degree Chebyshev polynomial of the third or fourth kind. Szegö has shown that the weights of these formulae are all positive. We derive explicit formulae for the weights, and subsequently use them to establish the convergence of the quadrature formulae for functions having a monotonic singularity at one or both endpoints of [−1, 1]. Moreover, we generate two new quadrature formulae, by adding 1, −1 to the sets of nodes considered previously, and show that these new formulae have almost all weights positive, exceptions occurring only among the weights corresponding to 1, −1. Also, we determine the precise degree of exactness of all the quadrature formulae in consideration, we obtain asymptotically optimal error bounds for these formulae, and show that almost all of them are nondefinite, exceptions occurring only among the formulae with a small number of nodes.     

From moments of sum to moments of product

We provide an identity that relates the moment of a product of random variables to the moments of different linear combinations of the random variables. Applying this identity, we obtain new formulae for the expectation of the product of normally distributed random variables and the product of quadratic forms in normally distributed random variables. In addition, we generalize the formulae to the case of multivariate elliptically distributed random variables. Unlike existing formulae in the literature, our new formulae are extremely efficient for computational purposes.     

A GENERALIZED QUASI-NEWTON EQUATION AND COMPUTATIONAL EXPERIENCE

The quasi-Newton equation has played a central role in the quasi-Newton methods forsolving systems of nonlinear equations and/or unconstrained optimization problems.In-stead,Pan suggested a new equation,and showed that it is of the second order while thetraditional of the first order,in certain approximation sense[12].In this paper,we makea generalization of the two equations to include them as special cases.The generalizedequation is analyzed,and new updates are derived from it.A DFP-like new update out-performed the traditional DFP update in computational experiments on a set of standardtest problems.     

New formulae for higher order derivatives and applications

We present new formulae (the Slevinsky–Safouhi formulae I and II) for the analytical development of higher order derivatives. These formulae, which are analytic and exact, represent the kth derivative as a discrete sum of only k+1 terms. Involved in the expression for the kth derivative are coefficients of the terms in the summation. These coefficients can be computed recursively and they are not subject to any computational instability. As examples of applications, we develop higher order derivatives of Legendre functions, Chebyshev polynomials of the first kind, Hermite functions and Bessel functions. We also show the general classes of functions to which our new formula is applicable and show how our formula can be applied to certain classes of differential equations. We also presented an application of the formulae of higher order derivatives combined with extrapolation methods in the numerical integration of spherical Bessel integral functions.     

Broyden修正算法

对于求解非线性方程组F (x) =0的Broyden秩1方法的计算格式提出一种修正算法,尝试利用矩阵的奇异值分解求解迭代方程组,并且配合使用加速技巧,从而大大提高了算法的安全性和收敛速度.数值算例表明了新算法的有效性.     

New reliability bounds for coherent systems

In 1970, Esary and Proschan proposed simple formulae for the system reliability lower bound and system reliability upper bound. Their formulae of reliability bounds have been classic and have been incorporated into almost all recent textbooks on reliability. In this paper, we decompose a coherent system into several consecutive-k-out-of-n : F(G) systems, and then based upon their exact formulae for system reliabilities, we develop new formulae for both reliability lower bound and reliability upper bound for the coherent system. In addition, we show that the new proposed reliability bounds are superior to those of Esary and Proschan for all coherent systems when the minimal cut/path sets have elements in common. Numerical results are reported, compared and discussed for various systems.     

Convergence properties of some block Krylov subspace methods for multiple linear systems

In the present paper, we give some convergence results of the global minimal residual methods and the global orthogonal residual methods for multiple linear systems. Using the Schur complement formulae and a new matrix product, we give expressions of the approximate solutions and the corresponding residuals. We also derive some useful relations between the norm of the residuals.     

Updating preconditioners for modified least squares problems

In this paper, we analyze how to update incomplete Cholesky preconditioners to solve least squares problems using iterative methods when the set of linear relations is updated with some new information, a new variable is added or, contrarily, some information or variable is removed from the set. Our proposed method computes a low-rank update of the preconditioner using a bordering method which is inexpensive compared with the cost of computing a new preconditioner. Moreover, the numerical experiments presented show that this strategy gives, in many cases, a better preconditioner than other choices, including the computation of a new preconditioner from scratch or reusing an existing one.     

Time domain analog circuit simulation

Recent developments of new methods for simulating electric circuits are described. Emphasis is put on methods that fit existing datastructures for backward differentiation formulae methods. These methods can be modified to apply to hierarchically organized datastructures, which allows for efficient simulation of large designs of circuits in the electronics industry.