On the generation of updates for quasi-Newton methods

We present a unified technique for updating approximations to Jacobian or Hessian matrices when any linear structure can be imposed. The updates are derived by variational means, where an operator-weighted Frobenius norm is used, and are finally expressed as solutions of linear equations and/or unconstrained extrema. A certain behavior of the solutions is discussed for certain perturbations of the operator and the constraints. Multiple secant relations are then considered. For the nonsparse case, an explicit family of updates is obtained including Broyden, DFP, and BFGS. For the case where some of the matrix elements are prescribed, explicit solutions are obtained if certain conditions are satisfied. When symmetry is assumed, we show, in addition, the connection with the DFP and BFGS updates.This work was partially supported by a grant from Control Data     

Local and superlinear convergence of quasi-Newton methods based on modified secant conditions

For solving unconstrained minimization problems, quasi-Newton methods are popular iterative methods. The secant condition which employs only the gradient information is imposed on these methods. Several researchers paid attention to other secant conditions to get a better approximation of the Hessian matrix of the objective function. Recently, Zhang et al. [New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl. 102 (1999) 147–167] and Zhang and Xu [Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, J. Comput. Appl. Math. 137 (2001) 269–278] proposed the modified secant condition which uses both gradient and function value information in order to get a higher order accuracy in approximating the second curvature of the objective function. They showed the local and q-superlinear convergence property of the BFGS-like and DFP-like updates based on their proposed secant condition. In this paper, we incorporate one parameter into this secant condition to smoothly switch the standard secant condition and the secant condition of Zhang et al. We consider a modified Broyden family which includes the BFGS-like and the DFP-like updates proposed by Zhang et al. We prove the local and q-superlinear convergence of our method.     

Two classes of multisecant methods for nonlinear acceleration

Many applications in science and engineering lead to models that require solving large‐scale fixed point problems, or equivalently, systems of nonlinear equations. Several successful techniques for handling such problems are based on quasi‐Newton methods that implicitly update the approximate Jacobian or inverse Jacobian to satisfy a certain secant condition. We present two classes of multisecant methods which allow to take into account a variable number of secant equations at each iteration. The first is the Broyden‐like class, of which Broyden's family is a subclass, and Anderson mixing is a particular member. The second class is that of the nonlinear Eirola–Nevanlinna‐type methods. This work was motivated by a problem in electronic structure calculations, whereby a fixed point iteration, known as the self‐consistent field (SCF) iteration, is accelerated by various strategies termed ‘mixing’. Copyright © 2008 John Wiley & Sons, Ltd.     

一类弱非线性方程组的Picard-MHSS迭代方法

修正的Hermite/反Hermite分裂(MHSS)迭代方法是一类求解大型稀疏复对称线性代数方程组的无条件收敛的迭代算法.基于非线性代数方程组的特殊结构和性质,我们选取Picard迭代为外迭代方法,MHSS迭代作为内迭代方法,构造了求解大型稀疏弱非线性代数方程组的Picard-MHSS和非线性MHSS-like方法.这两类方法的优点是不需要在每次迭代时均精确计算和存储Jacobi矩阵,仅需要在迭代过程中求解两个常系数实对称正定子线性方程组.除此之外,在一定条件下,给出了两类方法的局部收敛性定理.数值结果证明了这两类方法是可行、有效和稳健的.     

多複變數非歐空間中黎曼曲率的估值問題

<正> §1.引言 用(z)=(z~1,…,z~n)代表n個複變数,並命z~k=x~k+iy~k,此處x~k,y~k(1≤k≤n)是實數。代表x~1,…,x~n,y~1,…,y~n所定義的2n維空間中的一個域。我們現在並不假定它是受囿,抑單連通等性質。命     

由一哈密尔顿矩阵或反哈密尔顿矩阵所定义的矩阵李环

<正> §1.导言设K为体,即乘法不一定交换的域.设K之特征数≠2.再设a→ā是及的一个对合性反自同构,即a→ā是将K映到K之上的一個——映射而适合以下条件:     

Symmetric minimum-norm updates for use in gibbs free energy calculations

This paper examines a type of symmetric quasi-Newton update for use in nonlinear optimization algorithms. The updates presented here impose additional properties on the Hessian approximations that do not result if the usual quasi-Newton updating schemes are applied to certain Gibbs free energy minimization problems. The updates derived in this paper are symmetric matrices that satisfy a given matrix equation and are least squares solutions to the secant equation. A general representation for this class of updates is given. The update in this class that has the minimum weighted Frobenius norm is also presented. This work was done at Sandia National Laboratories and supported by the US Dept. of Energy under contract no. DE-AC04-76DP00789.     

Disguised and new quasi-Newton methods for nonlinear eigenvalue problems

In this paper, we take a quasi-Newton approach to nonlinear eigenvalue problems (NEPs) of the type M(λ)v =?0, where \(M:\mathbb {C}\rightarrow \mathbb {C}^{n\times n}\) is a holomorphic function. We investigate which types of approximations of the Jacobian matrix lead to competitive algorithms, and provide convergence theory. The convergence analysis is based on theory for quasi-Newton methods and Keldysh’s theorem for NEPs. We derive new algorithms and also show that several well-established methods for NEPs can be interpreted as quasi-Newton methods, and thereby, we provide insight to their convergence behavior. In particular, we establish quasi-Newton interpretations of Neumaier’s residual inverse iteration and Ruhe’s method of successive linear problems.     

Computations of coefficients in the polynomials of Pade´approximations by solving systems of linear equations

We explore reliability, stability and accuracy of determining the polynomials which define the Pade´approximation to a given function h(x) by solving a system of linear equations to get the coefficients in the denominator polynomial B_n(x). The coefficients in the numerator polynomial A_m(x) follow directly from those for B_n(x). Our approach is in the main heuristic. For the numerics we use the models e^?x1n(1 +x), (1 +x)^{± 1/2} and the exponential integral, each with m=n. The system of equations, with matrix of Toeplitz type, was solved by Gaussian elimination (Crout algorithm) with equilibration and partial pivoting. For each model, the maximum number of incorrect figures in the coefficients is of the order n at least, thus indicating that the matrix becomes ill conditioned as n increases. Let δ_n(x)andω_n(x) be the errors in A_n(x) and B_n(x) respectively, due to errors in the coefficients of B_n(x). For x fixed, δ_n(x) and ω_n(x) and the corresponding relative errors increase as n increases. However, for a considerable range on n, the relative errors in A_n(x)B_n(x) are virtually nil. This has the following theoretical explanation. Now B_n(x)h(x) ?A_m(m) = 0 (x^{m+n+ 1}). It can be shown that ω_n(x)h(x) ? δ_m(x) = 0(x^{m+ 1}). In this sense both A_m(x)B_n(x)andδ_m(x)ω_n(x) are approximations to h(x). Thus if the difference of these two approximations and ω_n(x)B_n(x), the relative error in B_n(x), are sufficiently small, then the relative error in A_m(x)/B_n(x) is of no consequence.     

Set-valued approximations and Newton’s methods

n to R^m. Under the assumption of semi-smoothness of the mapping, we prove that the approximation can be obtained through the Clarke generalized Jacobian, Ioffe-Ralph generalized Jacobian, B-subdifferential and their approximations. As an application, we propose a generalized Newton’s method based on the point-based set-valued approximation for solving nonsmooth equations. We show that the proposed method converges locally superlinearly without the assumption of semi-smoothness. Finally we include some well-known generalized Newton’s methods in our method and consolidate the convergence results of these methods. Received October 2, 1995 / Revised version received May 5, 1998 Published online October 9, 1998     

Linearized factorization techniques for multidimensional reaction—diffusion equations

An iterative predictor—corrector technique for the elimination of the approximate factorization errors which result from the factorization of linearized θ-methods in multidimensional reaction—diffusion equations is proposed, and its convergence and linear stability are analyzed. Four approximate factorization techniques which do not account for the approximate factorization errors are developed. The first technique uses the full Jacobian matrix of the reaction terms, requires the inversion of, in general, dense matrices, and its approximate factorization errors are second-order accurate in time. The second and third methods approximate the Jacobian matrix by diagonal or triangular ones which are easily inverted but their approximate factorization errors are, however, first-order accurate in time. The fourth approximately factorized method has approximate factorization errors which are second-order accurate in time and requires the inversion of lower and upper triangular matrices. The techniques are applied to a nonlinear, two-species, two-dimensional system of reaction—diffusion equations in order to determine the approximate factorization errors and those resulting from the approximations to the Jacobian matrix as functions of the allocation of the reaction terms, space and time.     

A Multigrid Block LU-SGS Algorithm for Euler Equations on Unstructured Grids

We propose an efficient and robust algorithm to solve the steady Euler equa- tions on unstructured grids.The new algorithm is a Newton-iteration method in which each iteration step is a linear multigrid method using block lower-upper symmetric Gauss-Seidel(LU-SGS)iteration as its smoother To regularize the Jacobian matrix of Newton-iteration,we adopted a local residual dependent regularization as the replace- ment of the standard time-stepping relaxation technique based on the local CFL number The proposed method can be extended to high order approximations and three spatial dimensions in a nature way.The solver was tested on a sequence of benchmark prob- lems on both quasi-uniform and local adaptive meshes.The numerical results illustrated the efficiency and robustness of our algorithm.     

关于平行弦法的一点看法

但从实际计算的角度看,(2)不如(3),因为在每一步计算中,(2)需计算两个新值(f(x_n))和f(y_(n 1))并利用一个旧信息f(x_(n-1));而(3)仅需计算一个新值f(x_n)并利用一个旧信息f(x_(n-1))。这样,若命计算f(x)所花的代价为1,并以E_i(i=2,3)表示公式(i)     

Periodic solutions preserved by nonstandard finite-difference schemes for the Lotka–Volterra system: a different approach

The Lotka–Volterra predator–prey system x′ = x ? xy, y′ = ? y+xy is a good differential equation system for testing numerical methods. This model gives rise to mutually periodic solutions surrounding the positive fixed point (1,1), provided the initial conditions are positive. Standard finite-difference methods produce solutions that spiral into or out of the positive fixed point. Previously, the author [Roeger, J. Diff. Equ. Appl. 12(9) (2006), pp. 937–948], generalized three different classes of nonstandard finite-difference methods that when applied to the predator–prey system produced periodic solutions. These methods preserve weighted area; they are symplectic with respect to a noncanonical structure and have the property that the computed points do not spiral. In this paper, we use a different approach. We apply the Jacobian matrix procedure to find a fourth class of nonstandard finite-difference methods. The Jacobian matrix method gives more general nonstandard methods that also produce periodic solutions for the predator–prey model. These methods also preserve the positivity property of the solutions.     

A note on the secant method

It is conjectured that the secant method converges linearly to a root of multiplicitym. In support of this, it is proved that the linearized secant method produces a bounded sequence of approximations except for a restricted set of values of the two initial approximations.     

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

This paper was motivated by a conjecture of Brändén [P. Brändén, Actions on permutations and unimodality of descent polynomials, European J. Combin. 29 (2) (2008) 514-531] about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a (p,q)-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The (p,q)-analogue unifies and generalizes our recent results [H. Shin, J. Zeng, The q-tangent and q-secant numbers via continued fractions, European J. Combin. 31 (7) (2010) 1689-1705] and that of Josuat-Vergès [M. Josuat-Vergés, A q-enumeration of alternating permutations, European J. Combin. 31 (7) (2010) 1892-1906].     

Polyconvex potentials,invertible deformations,and thermodynamically consistent formulation of the nonlinear elasticity equations

It is shown that the nonstationary finite-deformation thermoelasticity equations in Lagrangian and Eulerian coordinates can be written in a thermodynamically consistent Godunov canonical form satisfying the Friedrichs hyperbolicity conditions, provided that the elastic potential is a convex function of entropy and of the minors of the elastic deformation Jacobian matrix. In other words, the elastic potential is assumed to be polyconvex in the sense of Ball. It is well known that Ball’s approach to proving the existence and invertibility of stationary elastic deformations assumes that the elastic potential essentially depends on the second-order minors of the Jacobian matrix (i.e., on the cofactor matrix). However, elastic potentials constructed as approximations of rheological laws for actual materials generally do not satisfy this requirement. Instead, they may depend, for example, only on the first-order minors (i.e., the matrix elements) and on the Jacobian determinant. A method for constructing and regularizing polyconvex elastic potentials is proposed that does not require an explicit dependence on the cofactor matrix. It guarantees that the elastic deformations are quasiisometries and preserves the Lame constants of the elastic material.     

A class of conjugate gradient methods for convex constrained monotone equations

The recent designed non-linear conjugate gradient method of Dai and Kou [SIAM J Optim. 2013;23:296–320] is very efficient currently in solving large-scale unconstrained minimization problems due to its simpler iterative form, lower storage requirement and its closeness to the scaled memoryless BFGS method. Just because of these attractive properties, this method was extended successfully to solve higher dimensional symmetric non-linear equations in recent years. Nevertheless, its numerical performance in solving convex constrained monotone equations has never been explored. In this paper, combining with the projection method of Solodov and Svaiter, we develop a family of non-linear conjugate gradient methods for convex constrained monotone equations. The proposed methods do not require the Jacobian information of equations, and even they do not store any matrix in each iteration. They are potential to solve non-smooth problems with higher dimensions. We prove the global convergence of the class of the proposed methods and establish its R-linear convergence rate under some reasonable conditions. Finally, we also do some numerical experiments to show that the proposed methods are efficient and promising.     

Finite element approximation of nonlocal parabolic problem

In this article, we present a finite element scheme combined with backward Euler method to solve a nonlocal parabolic problem. An important issue in the numerical solution of nonlocal problems while using Newton's method is related to its structure. In fact differently from the local case where the Jacobian matrix is sparse and banded, in the nonlocal case the Jacobian matrix is dense and computations are much more onerous compared to that for differential equations. In order to avoid this difficulty, we use the technique given by Gudi (SIAM J Numer Anal 50 (2012), 657–668) for elliptic nonlocal problem of Kirchhoff type. We discuss the well‐posedness of the weak formulation at continuous as well as at discrete levels. We also derive a priori error estimates for semidiscrete and fully discrete formulations in L² and H¹ norms. Results based on the usual finite element method are provided to confirm the theoretical estimates. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 786–813, 2017     

An Inexact PRP Conjugate Gradient Method for Symmetric Nonlinear Equations

In this article, without computing exact gradient and Jacobian, we proposed a derivative-free Polak-Ribière-Polyak (PRP) method for solving nonlinear equations whose Jacobian is symmetric. This method is a generalization of the classical PRP method for unconstrained optimization problems. By utilizing the symmetric structure of the system sufficiently, we prove global convergence of the proposed method with some backtracking type line search under suitable assumptions. Moreover, we extend the proposed method to nonsmooth equations by adopting the smoothing technique. We also report some numerical results to show its efficiency.