Some implementation issues associated with multidimensional interval Newton methods

This paper presents the development of an optimal interval Newton method for systems of nonlinear equations. The context of solving such systems of equations is that of optimization of nonlinear mathematical programs. The modifications of the interval Newton method presented in this paper provide computationally effective enhancements to the general interval Newton method. The paper demonstrates the need to compute an optimal step length in the interval Newton method in order to guarantee the generation of a sequence of improving solutions. This method is referred to as the optimal Newton method and is implemented in multiple dimensions. Secondly, the paper demonstrates the use of the optimal interval Newton method as a feasible direction method to deal with non-negativity constraints. Also, included in this implementation is the use of a matrix decomposition technique to reduce the computational effort required to compute the Hessian inverse in the interval Newton method. The methods are demonstrated on several problems. Included in these problems are mathematical programs with perturbations in the problem coefficients. The numerical results clearly demonstrate the effectiveness and efficiency of these approaches.     

Convergence of the modified SOR–Newton method for non-smooth equations

Motivated by Chen [On the convergence of SOR methods for nonsmooth equations. Numer. Linear Algebra Appl. 9 (2002), pp. 81–92], in this paper, we further investigate a modified SOR–Newton (MSOR–Newton) method for solving a system of nonlinear equations F(x)=0, where F is strongly monotone and locally Lipschitz continuous but not necessarily differentiable. The convergence interval of the parameter in the MSOR–Newton method is given. Compared with that of the SOR–Newton method, this interval can be enlarged. Furthermore, when the B-differential of F(x) is difficult to compute, a simple replacement can be used, which can reduce the computational load. Numerical examples show that at the same cost of computational complexity, this MSOR–Newton method can converge faster than the corresponding SOR–Newton method by choosing a suitable parameter.     

Parallel Two-Grid Semismooth Newton-Krylov-Schwarz Method for Nonlinear Complementarity Problems

We develop scalable parallel domain decomposition algorithms for nonlinear complementarity problems including, for example, obstacle problems and free boundary value problems. Semismooth Newton is a popular approach for such problems, however, the method is not suitable for large scale calculations because the number of Newton iterations is not scalable with respect to the grid size; i.e., when the grid is refined, the number of Newton iterations often increases drastically. In this paper, we introduce a family of Newton-Krylov-Schwarz methods based on a smoothed grid sequencing method, a semismooth inexact Newton method, and a two-grid restricted overlapping Schwarz preconditioner. We show numerically that such an approach is totally scalable in the sense that the number of Newton iterations and the number of linear iterations are both nearly independent of the grid size and the number of processors. In addition, the method is not sensitive to the sharp discontinuity often associated with obstacle problems. We present numerical results for several large scale calculations obtained on machines with hundreds of processors.     

Newton-Type method for a class of mathematical programs with complementarity constraints

In this paper, we present a Newton-type method for a class of mathematical programs with complementarity constraints. Under the MPEC-LICQ, we use the definition of B-stationary point to construct a constrained equations model, and apply the Newton method to solve the problem. At the end of this paper, numerical results are reported to show our method's validity.     

无线传感网络中拥塞控制与路由的跨层设计:分布式牛顿法

无线传感网络应用广泛, 其性能与路由选择和拥塞控制密切相关. 致力于拥塞控制与多径路由的跨层优化, 以实现在链路容量受限和节点能量受限情况下的无线传感网络效用最大化. 针对对偶次梯度算法具有收敛速度慢与信息交互量大等缺陷, 设计了具有二阶收敛性能的分布式牛顿算法来实现网络效用最大化. 通过矩阵分裂技术, 实现了只需单跳信息交互的牛顿对偶方向的分布式求解方法. 仿真结果表明, 分布式牛顿算法的收敛性能显著优于对偶次梯度算法.     

A monotone Newton multisplitting method for the nonlinear complementarity problem with a nonlinear source term

In this paper, we develop a Newton multisplitting method for the nonlinear complementarity problem with a nonlinear source term in which the multisplitting method is used as secondary iterations to approximate the solutions for the resulting linearized subproblems. We prove the monotone convergence theorem for the proposed method under proper conditions.     

Finite‐Time Average Consensus Based Approach for Distributed Convex Optimization

In this paper, we consider a distributed convex optimization problem where the objective function is an average combination of individual objective function in multi‐agent systems. We propose a novel Newton Consensus method as a distributed algorithm to address the problem. This method utilises the efficient finite‐time average consensus method as an information fusion tool to construct the exact Newtonian global gradient direction. Under suitable assumptions, this strategy can be regarded as a distributed implementation of the classical standard Newton method and eventually has a quadratic convergence rate. The numerical simulation and comparison experiment show the superiority of the algorithm in convergence speed and performance.     

代数Riccati方程的一种快速解法——单输入情况

为解决线性定常系统在二次性能指标下的最优调节器设计问题,本文通过坐标变换,从系统的可控标准形出发,解决了用Newton迭代法求解代数Riccati方程时出现的两个主要困难:选取初始迭代矩阵与迭代求解Lyapunov方程。最后给出了求解的步骤与计算实例。     

A Semi-smooth Newton Method for Regularized State-constrained Optimal Control of the Navier-Stokes Equations

In this paper, we study semi-smooth Newton methods for the numerical solution of regularized pointwise state-constrained optimal control problems governed by the Navier-Stokes equations. After deriving an appropriate optimality system for the original problem, a class of Moreau-Yosida regularized problems is introduced and the convergence of their solutions to the original optimal one is proved. For each regularized problem a semi-smooth Newton method is applied and its local superlinear convergence verified. Finally, selected numerical results illustrate the behavior of the method and a comparison between the max-min and the Fischer-Burmeister as complementarity functionals is carried out.     

On the use of a modified Newton method for nonlinear finite element analysis

In this paper, the usefulness of modified Newton methods for solving certain minimization problems arising in nonlinear finite element analysis is investigated. The application considered is nonlinear elasticity, in particular geometrically nonlinear shells. On a test problem, it is demonstrated that a particular implementation of a modified Newton method using both descent directions and directions of negative curvature is able to identify a minimizer, whereas an unmodified Newton method and modified Newton methods using only descent directions fail to converge to the minimizer. The use of modified Newton methods is suggested as a useful complement to the present continuation methods used for nonlinear finite element analysis.     

An approximate Newton method for solving non-smooth equations with infinite max functions

In this paper, a new version of an approximate Newton method for solving non-smooth equations with infinite max function is presented. This method uses a difference approximation of the generalized Jacobian based on a weak consistently approximated Jacobian. Numerical example is reported for the generalized Newton method using two versions of approximation.     

A non-monotone inexact regularized smoothing Newton method for solving nonlinear complementarity problems

In the paper [S.P. Rui and C.X. Xu, A smoothing inexact Newton method for nonlinear complementarity problems, J. Comput. Appl. Math. 233 (2010), pp. 2332–2338], the authors proposed an inexact smoothing Newton method for nonlinear complementarity problems (NCP) with the assumption that F is a uniform P function. In this paper, we present a non-monotone inexact regularized smoothing Newton method for solving the NCP which is based on Fischer–Burmeister smoothing function. We show that the proposed algorithm is globally convergent and has a locally superlinear convergence rate under the weaker condition that F is a P ₀ function and the solution of NCP is non-empty and bounded. Numerical results are also reported for the test problems, which show the effectiveness of the proposed algorithm.     

Numerical experience with newton-like methods for nonlinear algebraic systems

In this paper we present an extensive computational experience with several Newton-like methods, namely Newton’s method, the ABS Huang method, the ABS row update method and six Quasi-Newton methods. The methods are first tested on 31 families of problems with dimensionsn=10, 50, 100 and two starting points. Newton’s method appears to be the best in terms of number of solved problems, followed closely by the ABS Huang method. Broyden’s “bad” method and Greenstadt’s second method show a very poor performance. The other four Quasi-Newton methods perform similarly, strongly suggesting that Greenstadt’s first method and Martínez’ column update method are locally and superlinearly convergent, a result that has yet to be proven theoretically. Thomas’ method appears to be marginally more robust and fast and provides moreover a better approximation to the Jacobian. An interesting and somewhat unexpected observation is that the number of iterations for satisfying the convergence test increases very little with the dimension of the problem. In a second set of experiments we look at the structure of the regions of convergence/nonconvergence by starting the methods from all nodes of a regular grid and assigning to each node a number according to the outcome of the iteration. The obtained regions have clearly a fractal type structure, which, on the two tested problems, is much simpler for Newton’s method than for the other methods. Newton’s method also is the one with the smallest nonconvergence region. Among the Quasi-Newton methods Thomas’ method shows a definitely smaller nonconvergence region.     

Extended interval Newton method based on the precise quotient set

The interval Newton method can be used for computing an enclosure of a single simple zero of a smooth function in an interval domain. It can practically be extended to allow computing enclosures of all zeros in a given interval. This paper deals with the extended interval Newton method. An essential operation of the method is division by an interval that contains zero (extended interval division). This operation has been studied by many researchers in recent decades, but inconsistency in the research has occurred again and again. This paper adopts the definition of extended interval division redefined in recent documents (Kulisch in Arithmetic operations for floating-point intervals, 2009; Pryce in P1788: IEEE standard for interval arithmetic version 02.2, 2010). The result of the division is called the precise quotient set. Earlier definitions differ in the overestimation of the quotient set in particular cases, causing inefficiency in Newton’s method and even leading to redundant enclosures of a zero. The paper reviews and compares some extended interval quotient sets defined during the last few decades. As a central theorem, we present the fundamental properties of the extended interval Newton method based on the precise quotient set. On this basis, we develop an algorithm and a convenient program package for the extended interval Newton method. Statements on its convergence are also given. We then demonstrate the performance of the algorithm through nine carefully selected very sensitive numerical examples and show that it can compute correct enclosures of all zeros of the functions with high efficiency, particularly in cases where earlier methods are less effective.     

等谱流问题的李群算法

§1.引言 非均匀介质中声波传播的研究,有着重要的应用:一个是声波在地壳中的传播,可以用来研究地质结构;一个是在海洋中的传播,可以用来研究海洋中物体的情况.在声波传播的研究中,需要研究Helmhotz方程     

On finite Newton method for support vector regression

In this paper, we propose a Newton iterative method of solution for solving an ε-insensitive support vector regression formulated as an unconstrained optimization problem. The proposed method has the advantage that the solution is obtained by solving a system of linear equations at a finite number of times rather than solving a quadratic optimization problem. For the case of linear or kernel support vector regression, the finite termination of the Newton method has been proved. Experiments were performed on IBM, Google, Citigroup and Sunspot time series. The proposed method converges in at most six iterations. The results are compared with that of the standard, least squares and smooth support vector regression methods and of the exact solutions clearly demonstrate the effectiveness of the proposed method.     

Inexact Methods in the Numerical Solution of Stiff Initial Value Problems

Inexact Newton methods can be effectively used in codes for large stiff initial value problems for ordinary differential equations. In this paper we give a new convergence result for Inexact Newton methods. Further, we indicate how this general result can be used and actually implemented to obtain an efficient code for solving stiff initial value problems. Received: March 12, 1998; revised March 31, 1999     

A generalized Newton method for non-Hermitian positive definite linear complementarity problem

In this paper, based on the implicit fixed-point equation of the linear complementarity problem (LCP), a generalized Newton method is presented to solve the non-Hermitian positive definite linear complementarity problem. Some convergence properties of the proposed generalized Newton method are discussed. Numerical experiments are presented to illustrate the efficiency of the proposed method.     

Recurrence relations for rational cubic methods I: The Halley method

In this paper we present a system of a priori error bounds for the Halley method in Banach spaces. Our theorem supplies sufficient conditions on the initial point to ensure the convergence of Halley iterates, by means of a system of “recurrence relations”, analogous to those given for the Newton method by Kantorovich, improving previous results by Döring [4]. The error bounds presented are optimal for second degree polynomials. Other rational cubic methods, as the Chebyshev method, will be treated in a subsequent paper.     

Multiple positive solutions for a Schrödinger–Newton system with sign-changing potential

In this paper, we study the Schrödinger–Newton systems with sign-changing potential in a bounded domain. By using the variational method and analytic techniques, the existence and multiplicity of positive solutions are established.