Adjoint-based quasi-Newton methods for partially separable problems

In this paper the concepts of partitioned quasi-Newton methods are applied to adjoint Broyden updates. Consequently a corresponding partitioned adjoint Broyden update is presented and local convergence results are given. Numerical results compare the partitioned adjoint Broyden update methods to the corresponding unpartitioned quasi-Newton method and to Newton's method for nonlinear equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fifth-order iterative method for finding multiple roots of nonlinear equations

This paper presents a fifth-order iterative method as a new modification of Newton’s method for finding multiple roots of nonlinear equations with unknown multiplicity m. Its convergence order is analyzed and proved. Moreover, several numerical examples demonstrate that the proposed iterative method is superior to the existing methods.     

Modified Newton’s method for systems of nonlinear equations with singular Jacobian

It is well known that Newton’s method for a nonlinear system has quadratic convergence when the Jacobian is a nonsingular matrix in a neighborhood of the solution. Here we present a modification of this method for nonlinear systems whose Jacobian matrix is singular. We prove, under certain conditions, that this modified Newton’s method has quadratic convergence. Moreover, different numerical tests confirm the theoretical results and allow us to compare this variant with the classical Newton’s method.     

A Hybrid of the Newton-GMRES and Electromagnetic Meta-Heuristic Methods for Solving Systems of Nonlinear Equations

Solving systems of nonlinear equations is perhaps one of the most difficult problems in all numerical computation. Although numerous methods have been developed to attack this class of numerical problems, one of the simplest and oldest methods, Newton’s method is arguably the most commonly used. As is well known, the convergence and performance characteristics of Newton’s method can be highly sensitive to the initial guess of the solution supplied to the method. In this paper a hybrid scheme is proposed, in which the Electromagnetic Meta-Heuristic method (EM) is used to supply a good initial guess of the solution to the finite difference version of the Newton-GMRES method (NG) for solving a system of nonlinear equations. Numerical examples are given in order to compare the performance of the hybrid of the EM and NG methods. Empirical results show that the proposed method is an efficient approach for solving systems of nonlinear equations.     

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     

On the applicability of two Newton methods for solving equations in Banach space

In this study we examine the applicability of Newton’s method and the modified Newton’s method for approximating a locally unique solution of a nonlinear equation in a Banach space. We assume that the Newton-Kantorovich hypothesis for Newton’s method is violated, but the corresponding condition for the modified Newton method holds. Under these conditions there is no guarantee that Newton’s method starting from the same initial guess as the modified Newton’s method converges. Hence, it seems that we must always use the modified Newton method under these conditions. However, we provide a numerical example to demonstrate that in practice this may not be a good decision.     

On the Convergence of Newton’s Method for Polynomial Equations and Applications in Radiative Transfer

 Newton’s method is used to approximate a locally unique zero of a polynomial operator F of degree in Banach space. So far, convergence conditions have been found for Newton’s method based on the Newton-Kantorovich hypothesis that uses Lipschitz-type conditions and information only on the first Fréchet-derivative of F. Here we provide a new semilocal convergence theorem for Newton’s method that uses information on all Fréchet-derivatives of F except the first. This way, we obtain sufficient convergence conditions different from the Newton-Kantorovich hypothesis. Our results are extended to include the case when F is a nonlinear operator whose kth Fréchet-derivative satisfies a H?lder continuity condition. An example is provided to show that our conditions hold where all previous ones fail. Moreover, some applications of our results to the solution of polynomial systems and differential equations are suggested. Furthermore, our results apply to solve a nonlinear integral equation appearing in radiative transfer in connection with the problem of determination of the angular distribution of the radiant-flux emerging from a plane radiation field. Received 9 December 1997 in revised form 30 March 1998     

Accurate fourteenth-order methods for solving nonlinear equations

We establish new iterative methods of local order fourteen to approximate the simple roots of nonlinear equations. The considered three-step eighth-order construction can be viewed as a variant of Newton’s method in which the concept of Hermite interpolation is used at the third step to reduce the number of evaluations. This scheme includes three evaluations of the function and one evaluation of the first derivative per iteration, hence its efficiency index is 1.6817. Next, the obtained approximation for the derivative of the Newton’s iteration quotient is again taken into consideration to furnish novel fourteenth-order techniques consuming four function and one first derivative evaluations per iteration. In providing such new fourteenth-order methods, we also take a special heed to the computational burden. The contributed four-step methods have 1.6952 as their efficiency index. Finally, various numerical examples are given to illustrate the accuracy of the developed techniques.     

Simple geometric constructions of quadratically and cubically convergent iterative functions to solve nonlinear equations

In this paper, we derive one-parameter families of Newton, Halley, Chebyshev, Chebyshev-Halley type methods, super-Halley, C-methods, osculating circle and ellipse methods respectively for finding simple zeros of nonlinear equations, permitting f ′ (x) = 0 at some points in the vicinity of the required root. Halley, Chebyshev, super-Halley methods and, as an exceptional case, Newton method are seen as the special cases of the family. All the methods of the family and various others are cubically convergent to simple roots except Newton’s or a family of Newton’s method.      

On new iterative method for solving systems of nonlinear equations

Solving systems of nonlinear equations is a relatively complicated problem for which a number of different approaches have been proposed. In this paper, we employ the Homotopy Analysis Method (HAM) to derive a family of iterative methods for solving systems of nonlinear algebraic equations. Our approach yields second and third order iterative methods which are more efficient than their classical counterparts such as Newton’s, Chebychev’s and Halley’s methods.     

Partitioned quasi-Newton methods for sparse nonlinear equations

In this paper, we present two partitioned quasi-Newton methods for solving partially separable nonlinear equations. When the Jacobian is not available, we propose a partitioned Broyden’s rank one method and show that the full step partitioned Broyden’s rank one method is locally and superlinearly convergent. By using a well-defined derivative-free line search, we globalize the method and establish its global and superlinear convergence. In the case where the Jacobian is available, we propose a partitioned adjoint Broyden method and show its global and superlinear convergence. We also present some preliminary numerical results. The results show that the two partitioned quasi-Newton methods are effective and competitive for solving large-scale partially separable nonlinear equations.     

Several New Third-Order Iterative Methods for Solving Nonlinear Equations

In this paper, we present some new third-order iterative methods for finding a simple root α of nonlinear scalar equation f(x)=0 in R. A geometric approach based on the circle of curvature is used to construct the new methods. Analysis of convergence shows that the new methods have third-order convergence, that is, the sequence {x _n }₀^∞ generated by each of the presented methods converges to α with the order of convergence three. The efficiency of the methods are tested on several numerical examples. It is observed that our methods can compete with Newton’s method and the classical third-order methods.     

Split Newton iterative algorithm and its application

Inspired by some implicit-explicit linear multistep schemes and additive Runge-Kutta methods, we develop a novel split Newton iterative algorithm for the numerical solution of nonlinear equations. The proposed method improves computational efficiency by reducing the computational cost of the Jacobian matrix. Consistency and global convergence of the new method are also maintained. To test its effectiveness, we apply the method to nonlinear reaction-diffusion equations, such as Burger’s-Huxley equation and fisher’s equation. Numerical examples suggest that the involved iterative method is much faster than the classical Newton’s method on a given time interval.     

Practical Quasi-Newton algorithms for singular nonlinear systems

Quasi-Newton methods for solving singular systems of nonlinear equations are considered in this paper. Singular roots cause a number of problems in implementation of iterative methods and in general deteriorate the rate of convergence. We propose two modifications of QN methods based on Newton’s and Shamanski’s method for singular problems. The proposed algorithms belong to the class of two-step iterations. Influence of iterative rule for matrix updates and the choice of parameters that keep iterative sequence within convergence region are empirically analyzed and some conclusions are obtained.     

A trust-region method applied to parameter identification of a simple prey–predator model

In this paper, the calibration of the non linear Lotka–Volterra model is used to compare the robustness and efficiency (CPU time) of different optimisation algorithms.Five versions of a quasi-Newton trust-region algorithm are developed and compared with a widely used quasi-Newton method. The trust-region algorithms is more robust and three of them are numerically cheaper than the more usual line search approach.Computation of the first derivatives of the objective function is cheaper with the backward differentiation (or adjoint model) technique than with the forward method as soon as the number of parameter is greater than a few ones. In the optimisation problem, the additional information about the Jacobian matrix made available by the forward method reduces the number of iterations but does not compensate for the increased numerical costs.A quasi-Newton trust-region algorithm with backward differentiation and BFGS update after both successful and unsuccessful iterations represents a robust and efficient algorithm that can be used to calibrate very demanding dynamic models.     

Strategies for time-dependent PDE control with inequality constraints using an integrated modeling and simulation environment

In Neitzel et al. (Strategies for time-dependent PDE control using an integrated modeling and simulation environment. Part one: problems without inequality constraints. Technical Report 408, Matheon, Berlin, 2007) we have shown how time-dependent optimal control for partial differential equations can be realized in a modern high-level modeling and simulation package. In this article we extend our approach to (state) constrained problems. “Pure” state constraints in a function space setting lead to non-regular Lagrange multipliers (if they exist), i.e. the Lagrange multipliers are in general Borel measures. This will be overcome by different regularization techniques. To implement inequality constraints, active set methods and barrier methods are widely in use. We show how these techniques can be realized in a modeling and simulation package. We implement a projection method based on active sets as well as a barrier method and a Moreau Yosida regularization, and compare these methods by a program that optimizes the discrete version of the given problem. Ira Neitzel’s research was supported by the DFG Schwerpunktprogramm SPP 1253. Uwe Prüfert’s research was supported by the DFG Research Center Matheon. Thomas Slawig’s research was supported by the DFG Cluster of Excellence The Future Ocean and the DFG Schwerpunktprogramm SPP 1253. Website     

The <Emphasis Type="Italic">Q</Emphasis> Method for Symmetric Cone Programming

The Q method of semidefinite programming, developed by Alizadeh, Haeberly and Overton, is extended to optimization problems over symmetric cones. At each iteration of the Q method, eigenvalues and Jordan frames of decision variables are updated using Newton’s method. We give an interior point and a pure Newton’s method based on the Q method. In another paper, the authors have shown that the Q method for second-order cone programming is accurate. The Q method has also been used to develop a “warm-starting” approach for second-order cone programming. The machinery of Euclidean Jordan algebra, certain subgroups of the automorphism group of symmetric cones, and the exponential map is used in the development of the Newton method. Finally we prove that in the presence of certain non-degeneracies the Jacobian of the Newton system is nonsingular at the optimum. Hence the Q method for symmetric cone programming is accurate and can be used to “warm-start” a slightly perturbed symmetric cone program.     

Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

The asymptotic convergence of parameterized variants of Newton’s method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable path leading to a solution of the original system, the scalar parameter determining the progress along the path. A path-following algorithm, which involves an inner iteration in which the perturbed systems are approximately solved, is outlined. It is shown that asymptotically, a single linear system is solved per update of the scalar parameter. It turns out that a componentwise Q-superlinear rate may be attained, both in the direct error and in the residuals, under standard assumptions, and that this rate may be made arbitrarily close to quadratic. Numerical experiments illustrate the results and we discuss the relationships that this method shares with interior methods in constrained optimization. Received: September 8, 2000 / Accepted: September 17, 2001?Published online February 14, 2002     

Numerical treatment of a twisted tail using extrapolation methods

Highly oscillatory integral, called a twisted tail, is proposed as a challenge in The SIAM 100-digit challenge. A Study in High-Accuracy Numerical Computing, where Drik Laurie developed numerical algorithms based on the use of Aitken’s Δ²-method, complex integration and transformation to a Fourier integral. Another algorithm is developed by Walter Gautschi based on Longman’s method; Newton’s method for solving a nonlinear equation; Gaussian quadrature; and the epsilon algorithm of Wynn for accelerating the convergence of infinite series. In the present work, nonlinear transformations for improving the convergence of oscillatory integrals are applied to the integration of this wildly oscillating function. Specifically, the transformation and its companion the W algorithm, and the G transformation are all used in the analysis of the integral. A Fortran program is developed employing each of the methods, and accuracies of up to 15 correct digits are reached in double precision.     

A Globally Convergent Trust-Region Method for Large-Scale Symmetric Nonlinear Systems

This study presents a novel adaptive trust-region method for solving symmetric nonlinear systems of equations. The new method uses a derivative-free quasi-Newton formula in place of the exact Jacobian. The global convergence and local quadratic convergence of the new method are established without the nondegeneracy assumption of the exact Jacobian. Using the compact limited memory BFGS, we adapt a version of the new method for solving large-scale problems and develop the dogleg scheme for solving the associated trust-region subproblems. The sufficient decrease condition for the adapted dogleg scheme is established. While the efficiency of the present trust-region approach can be improved by using adaptive radius techniques, utilizing the compact limited memory BFGS adjusts this approach to handle large-scale symmetric nonlinear systems of equations. Preliminary numerical results for both medium- and large-scale problems are reported.