Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

Globally Convergent Inexact Quasi-Newton Methods for Solving Nonlinear Systems

Large scale nonlinear systems of equations can be solved by means of inexact quasi-Newton methods. A global convergence theory is introduced that guarantees that, under reasonable assumptions, the algorithmic sequence converges to a solution of the problem. Under additional standard assumptions, superlinear convergence is preserved.     

Fast Iterative Methods for Solving of Boundary Nonlinear Integral Equations with Singularity

A very efficient and fully discrete method for numerical solution of boundary nonlinear integral equation is described. There seems a lack of rigorous numerical analysis because of singular or hypersingular behavior. In this paper, we suggest variants of methods for solving numerical solutions. Moreover, our aim has been to show how the iterations can be effectively and efficiently regularized for solving ill-posed problems by using the preconditioner. We have compared these methods with CPU time and iterations. Finally, some numerical examples show the efficiency of the proposed methods.     

解决大规模信赖域子问题的一种新算法

信赖域方法是解决无约束优化问题的一类有效的方法,而求解信赖域子问题又是信赖域方法的一个重要的组成部分。在本文中,我们首先介绍Hager[4]的序列子空间方法,并分析了对于不同的子空间序列,该算法所具有的性质。随后我们在以上分析的启发下,给出SSM算法的一种改进算法,改进后的算法不仅是全局收敛的,而且进一步减少了矩阵运算量。最后我们给出一些初步的数值试验报告。     

Convergence Rate of The Trust Region Method for Nonlinear Equations Under Local Error Bound Condition

In this paper, we present the new trust region method for nonlinear equations with the trust region converging to zero. The new method preserves the global convergence of the traditional trust region methods in which the trust region radius will be larger than a positive constant. We study the convergence rate of the new method under the local error bound condition which is weaker than the nonsingularity. An example given by Y.X. Yuan shows that the convergence rate can not be quadratic. Finally, some numerical results are given. This work is supported by Chinese NSFC grants 10401023 and 10371076, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Computational Sciences of Shanghai Universities. An erratum to this article is available at .     

Lagrangian Globalization Methods for Nonlinear Complementarity Problems

This paper extends the Lagrangian globalization (LG) method to the nonsmooth equation arising from a nonlinear complementarity problem (NCP) and presents a descent algorithm for the LG phase. The aim of this paper is not to present a new method for solving the NCP, but to find such that when the NCP has a solution and is a stationary point but not a solution.     

MATLAB中大型线性方程组的非定常迭代法

科学研究和大型工程设计中很多问题以非线性数学模型来描述,而这些数学模型求解常常归结为各种大型线性方程组的求解,因而能否有效地求解大型线性方程组,特别是病态的方程组,是非常关键的.本文介绍了MATLAB中求解大型线性方程组常用的非定常迭代法,并以GMRES算法为例介绍了算法的数学描述.     

New Version of the Newton Method for Nonsmooth Equations

In this paper, an inexact Newton scheme is presented which produces a sequence of iterates in which the problem functions are differentiable. It is shown that the use of the inexact Newton scheme does not reduce the convergence rate significantly. To improve the algorithm further, we use a classical finite-difference approximation technique in this context. Locally superlinear convergence results are obtained under reasonable assumptions. To globalize the algorithm, we incorporate features designed to improve convergence from an arbitrary starting point. Convergence results are presented under the condition that the generalized Jacobian of the problem function is nonsingular. Finally, implementations are discussed and numerical results are presented.     

一类非线性互补问题的信赖域算法

In this paper,an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed.A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration,thus avoiding the need for solving a quadratic subproblem with a trust region bound.Under some conditions,it is proven that this algorithm is globally and locally superlinear convergent.The limited numerical examples show its efficiency.     

Inexact trust region method for large sparse systems of nonlinear equations

The main purpose of this paper is to prove the global convergence of the new trust region method based on the smoothed CGS algorithm. This method is surprisingly convenient for the numerical solution of large sparse systems of nonlinear equations, as is demonstrated by numerical experiments. A modification of the proposed trust region method does not use matrices, so it can be used for large dense systems of nonlinear equations.     

Smoothing Newton-Like Method for the Solution of Nonlinear Systems of Equalities and Inequalities

In this paper, we present a smoothing Newton-like method for solving non-linear systems of equalities and inequalities. By using the so-called max function, we transfer the inequalities into a system of semismooth equalities. Then a smoothing Newton-like method is proposed for solving the reformulated system, which only needs to solve one system of linear equations and to perform one line search at each iteration. The global and local quadratic convergence are studied under appropriate assumptions. Numerical examples show that the new approach is effective.     

非线性二元算子方程组的迭代求解方法

Using the cone and partial ordering theory and mixed monotone operator theory, the existence and uniqueness of solutions for some classes of systems of nonlinear two binary operator equations in a Banach space with a partial ordering are discussed. And the error estimates that the iterative sequences converge to solutions are also given. Some relevant results of solvability of two binary operator equations and systems of operator equations are improved and generalized.     

Monotone Convergence of Iterative Methods for Singular Linear Systems

In this paper, monotonicity of iterative methods for solving general solvable singularly systems is discussed. The monotonicity results given by Berman, Plemmons, and Semal are generalized to singular systems. It is shown that for an iterative method introduced by a nonnegative splitting of the coefficient matrix there exist some initial guesses such that the iterative sequence converges towards a solution of the system from below or from above. The monotonicity of the block Gauss-Seidel method for solving a p-cyclic system and Markov chain is considered.     

Nonlinear Stability of General Linear Methods for Delay Differential Equations

This paper is devoted to a study of nonlinear stability of general linear methods for the numerical solution of delay differential equations in Hilbert spaces. New stability concepts are further introduced. The stability properties of (k,p,q)-algebraically stable general linear methods with piecewise constant or linear interpolation procedure are investigated. We also discuss stability of linear multistep methods viewed as a special subset of the class of general linear methods.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

A New Family of Trust Region Algorithms for Unconstrained Optimization

Trust region(TR)algorithms are a class of recently developed alogrthms for nonlinear optimization.A new family of TR algorithms for unconstrained optimization,which is the extension of the usual TR method,is pressented in this paper.When the objective function is bounded below and continuously differentiable,and the norm of the Hesse approximations increases at most linearly with the iteration number,we prove the global convergence of the algorithms.Limited numerical results are repoted,which indicate that our new TR algorithm is competitive.     

比例延迟微分方程的连续有限元法

利用连续有限元法求解比例延迟微分方程,在一致网格下,给出比例延迟微分方程连续有限元解的整体收敛阶,数值实验验证了理论结果的正确性.     

Predictor-Corrector Smoothing Newton Method,Based on a New Smoothing Function,for Solving the Nonlinear Complementarity Problem with a P 0 Function

By smoothing a perturbed minimum function, we propose in this paper a new smoothing function. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. We investigate the boundedness of the iteration sequence generated by noninterior continuation/smoothing methods under the assumption that the solution set of the NCP is nonempty and bounded. Based on the new smoothing function, we present a predictor-corrector smoothing Newton algorithm for solving the NCP with a P ₀ function, which is shown to be globally linearly and locally superlinearly convergent under suitable assumptions. Some preliminary computational results are reported.     

On the Convergence of a Trust-Region Method for Solving Constrained Nonlinear Equations with Degenerate Solutions

This paper presents a trust-region method for solving the constrained nonlinear equation F(x) = 0, x , where R ⁿ is a nonempty and closed convex set, F is defined on the open set containing and is continuously differentiable. The iterates generated by the method are feasible. The method is globally and quadratically convergent under local error bounded assumption on F. The results obtained are extensions of the work of Yamashita Fukushima (Ref. 1) and Fan Yuan (Ref. 2) for unconstrained nonlinear equations. Numerical results show that the new algorithm works quite well.