A semismooth equation approach to the solution of nonlinear complementarity problems

In this paper we present a new algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem. We exploit the recent extension of Newton's method to semismooth systems of equations and the fact that the natural merit function associated to the equation reformulation is continuously differentiable to develop an algorithm whose global and quadratic convergence properties can be established under very mild assumptions. Other interesting features of the new algorithm are an extreme simplicity along with a low computational burden per iteration. We include numerical tests which show the viability of the approach.     

A cubically convergent Newton-type method under weak conditions

Under weak conditions, we present an iteration formula to improve Newton's method for solving nonlinear equations. The method is free from second derivatives, permitting f^′(x)=0 in some points and per iteration it requires two evaluations of the given function and one evaluation of its derivative. Analysis of convergence demonstrates that the new method is cubically convergent. Some numerical examples illustrate that the algorithm is more efficient and performs better than classical Newton's method.     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.     

Experiments in numerical methods for a problem in combustion modeling

In this paper, we have shown that the numerical method of lines can be used effectively to solve time dependent combustion models in one spatial dimension. By the numerical method of lines (NMOL), we mean the reduction of a system of partial differential equations to a system of ordinary differential equations (ODE's), followed by the solution of this ODE system with an appropriate ODE solver. We used finite differences for the spatial discretization and a variant of the GEAR package for the ODE's.We have presented various solution methods of interest for the nonlinear algebraic system in this setting; that is, in the corrector iteration section of the GEAR package applied to combustion models. These methods include Newton/block SOR (SOR denotes successive over-relaxation), block SOR/Newton, Newton/block-diagonal Jacobian, Newton/kinetics-only Jacobian, and Newton/block symmetric SOR. These methods have in common their lack of frequent use in ODE software and their eady applicability to partial differential equations in more than one spatial dimension.Finally, we have given the results of numerical tests, run on the CDC-7600 and Cray-1 computers. By so doing, we indicate the more promising nonlinear system solvers for the NMOL solution of combustion models.     

Inexact Interior-Point Method

In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved.     

Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem

In this article, we first reformulate the generalized nonlinear complementarity problem (GNCP) over a polyhedral cone as a smoothing system of equations and then suggest a smoothing Broyden-like method for solving it. The proposed algorithm has to solve only one system of nonhomogeneous linear equations, perform only one line search and update only one matrix per iteration. We show that the iteration sequence generated by the proposed algorithm converges globally and superlinearly under suitable conditions. Furthermore, the algorithm has local quadratic convergence under mild assumptions. Some numerical examples are given to illustrate the performance and efficiency of the presented algorithm.     

特殊矩阵乘积在非线性数值计算中的应用

本文将Hadamard矩阵乘积引入到非线性数值计算,获得了简单的矩阵形式的非线性代数模拟方程,利用Hadamard矩阵乘积和Hadamard矩阵函数的方法,我们能够容易地构造快速收敛的简单迭代法解非线性代数方程组的迭代公式,使该法成为与Newton-Raphson法相比有竞争力的方法,我们也首次定义了一种新的特殊矩阵乘积—SJT矩阵乘积。运用SJT积,我们能够方便高效的计算Newton-Raphson法中Jacobi导数矩阵的精确解,利用Hadamard矩阵乘积的范数性质,我们也导出了非线性计算摄动误差的分析公式,此外,Hadamard积和SJT积能够被用于非线性数值解耦计算,这极大地减少了求解耦合的非线性偏微分方程组的计算工作量和内存需要量。     

Global convergence of some differential equation algorithms for solving equations involving positive variables

This paper describes some sufficient conditions for global convergence in five differential equation algorithms for solving systems of non-linear algebraic equations involving positive variables. The algorithms are continuous time versions of a modified steepest descent method, Newton's method, a modified Newton's method and two algorithms using the transpose of the Jacobian in place of the inverse of the Jacobian in Newton's method. It is shown that under a set of mildly restrictive conditions the Jacobian transpose algorithm has qualitatively the same convergence as Newton's method.     

Combination of the variational iteration method and numerical algorithms for nonlinear problems

A very simple and efficient local variational iteration method (LVIM), or variational iteration method with local property, for solving problems of nonlinear science is proposed in this paper. The analytical iteration formula of this method is derived first using a general form of first order nonlinear differential equations, followed by straightforward discretization using Chebyshev polynomials and collocation method. The resulting numerical algorithm is very concise and easy to use, only involving highly sparse matrix operations of addition and multiplication, and no inversion of the Jacobian in nonlinear problems. Apart from the simple yet efficient iteration formula, another extraordinary feature of LVIM is that in each local domain, all the collocation nodes participate in the calculation simultaneously, thus each local domain can be regarded as one “node” in calculation through GPU acceleration and parallel processing. For illustration, the proposed algorithm of LVIM is applied to various nonlinear problems including Blasius equations in fluid mechanics, buckled bar equations in solid mechanics, the Chandrasekhar equation in astrophysics, the low-Earth-orbit equation in orbital mechanics, etc. Using the built-in highly optimized ode45 function of MATLAB as a comparison, it is found that the LVIM is not only very accurate, but also much faster by an order of magnitude than ode45 in all the numerical examples, especially when the nonlinear terms are very complicated and difficult to evaluate.     

The numerical solution of a periodic parabolic problem subject to a nonlinear boundary condition

The numerical solution by finite differences of a periodic parabolic problem subject to a nonlinear boundary condition is considered. It is shown that Newton's method can be used to solve the nonlinear equations provided a suitable initial approximation is known, and a method for constructing this first approximation is given.     

A BFGS trust-region method with a new nonmonotone technique for nonlinear equations

In this paper, we consider a trust-region method for solving nonlinear equations which employs a new nonmonotone technique. A strong nonmonotone strategy and a weaker nonmonotone strategy can be obtained by choosing the parameter adaptively. Thus, the disadvantages of the traditional nonmonotone strategy can be avoided. It does not need to compute the Jacobian matrix at every iteration, so that the workload and time are decreased. Theoretical analysis indicates that the new algorithm preserves the global convergence under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed method for solving nonlinear equations.     

混合互补问题的光滑算法及收敛性

利用Fischer-Burmeister函数将混合互补问题转化为非线性方程组,由光滑函数逼近FB函数来求解非线性方程组．文中将信赖域方法和梯度法相结合,提出了Jacobian光滑化方法．算法在一定条件下的全局收敛性得到了证明,数值试验表明算法切实有效,有一定的优越性．     

Local convergence of an adaptive scalar method and its application in a nonoverlapping domain decomposition scheme

In this paper, we demonstrate a local convergence of an adaptive scalar solver which is practical for strongly diagonal dominant Jacobian problems such as in some systems of nonlinear equations arising from the application of a nonoverlapping domain decomposition method. The method is tested to a nonlinear interface problem of a multichip heat conduction problem. The numerical results show that the method performs slightly better than a Newton-Krylov method.     

Incomplete Newton-Ulm method for large scale nonlinear equations

This paper presents an incomplete Newton-Ulm method (INU) for nonlinear equations. This method uses parts of elements of Jacobian matrix to obtain the next iteration point and does not contain inverse operators in its expression. We discuss and analyze the convergence conditions and semilocal convergence of the new method. Some special INU algorithms are designed and numerical experiments are given. Numerical results show that INU method is effective for large scale nonlinear equations.     

A Nonsmooth L-M Method for Solving the Generalized Nonlinear Complementarity Problem over a Polyhedral Cone

In this paper the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone is reformulated as a system of nonsmooth equations. Based on this reformulation, the famous Levenberg-Marquardt (L-M) algorithm is employed to obtain its solution. Theoretical results that relate the stationary points of the merit function to the solution of the GNCP are presented. Under mild assumptions, we show that the L-M algorithm is both globally and superlinearly convergent. Moreover, a method to calculate a generalized Jacobian is given and numerical experimental results are presented.     

求解方程的一类迭代公式

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.     

A fast BIE iteration method for an arbitrary body in a flow of incompressible inviscid fluid

The paper is concerned with the new iteration algorithm to solve boundary integral equations arising in boundary value problems of mathematical physics. The stability of the algorithm is demonstrated on the problem of a flow around bodies placed in the incompressible inviscid fluid. With a discrete numerical treatment, we approximate the exact matrix by a certain Töeplitz one and then apply a fast algorithm for this matrix, on each iteration step. We illustrate the convergence of this iteration scheme by a number of numerical examples, both for hard and soft boundary conditions. It appears that the method is highly efficient for hard boundaries, being much less efficient for soft boundaries.     

Conservative finite-difference scheme for computer simulation of contrast 3D spatial-temporal structures induced by a laser pulse in a semiconductor

The numerical approach for computer simulation of femtosecond laser pulse interaction with a semiconductor is considered under the formation of 3D contrast time-dependent spatiotemporal structures. The problem is governed by the set of nonlinear partial differential equations describing a semiconductor characteristic evolution and a laser pulse propagation. One of the equations is a Poisson equation concerning electric field potential with Neumann boundary conditions that requires fulfillment of the well-known condition for Neumann problem solvability. The Poisson equation right part depends on free-charged particle concentrations that are governed by nonlinear equations. Therefore, the charge conservation law plays a key role for a finite-difference scheme construction as well as for solvability of the Neumann difference problem. In this connection, the iteration methods for the Poisson equation solution become preferable than using direct methods like the fast Fourier transform. We demonstrate the following: if the finite-difference scheme does not possess the conservatism property, then the problem solvability could be broken, and the numerical solution does not correspond to the differential problem solution. It should be stressed that for providing the computation in a long-time interval, it is crucial to use a numerical method that possessing asymptotic stability property. In this regard, we develop an effective numerical approach—the three-stage iteration process. It has the same economic computing expenses as a widely used split-step method, but, in contrast to the split-step method, our method possesses conservatism and asymptotic stability properties. Computer simulation results are presented.     

An efficient step size control for continuation methods

In solving a nonlinear equation by the use of a continuation method one of the crucial problems is the choice of the step sizes. We present a model for the total computational cost of a standard numerical continuation process and solve the problem of optimal step size control for this model. Using the theoretical results as a basis, we develop an adaptive step size algorithm for Newton's method. This procedure is computationally inexpensive and it gives quite satisfactory results compared to some other numerical experiments found in the literature.     

New third-order method for solving systems of nonlinear equations

In this paper, we present a new iterative method to solve systems of nonlinear equations. The main advantages of the method are: it has order three, it does not require the evaluation of any second or higher order Fréchet derivative and it permits that the Jacobian be singular at some points. Thus, the problem due to the fact that the Jacobian is numerically singular is solved. The third order convergence in both one dimension and for the multivariate case are given. The numerical results illustrate the efficiency of the method for systems of nonlinear equations.