The modulus-based nonsmooth Newton’s method for solving a class of nonlinear complementarity problems of <Emphasis Type="Italic">P</Emphasis>-matrices

By applying the Newton’s iteration to the equivalent modulus equations of the nonlinear complementarity problems of P-matrices, a modulus-based nonsmooth Newton’s method is established. The nearly quadratic convergence of the new method is proved under some assumptions. The strategy of choosing the initial iteration vector is given, which leads to a modified method. Numerical examples show that the new methods have higher convergence precision and faster convergence rate than the known modulus-based matrix splitting iteration method.     

Improved convergence theorems of modulus-based matrix splitting iteration method for nonlinear complementarity problems of <Emphasis Type="Italic">H</Emphasis>-matrices

In this paper, the convergence conditions of the modulus-based matrix splitting iteration method for nonlinear complementarity problem of H-matrices are weakened. The convergence domain given by the proposed theorems is larger than the existing ones. Numerical examples show the advantages of the new theorems.     

A non-monotone inexact non-interior continuation method based on a parametric smoothing function for LWCP

This paper considers the linear weighted complementarity problem (denoted by LWCP). We introduce a parametric smoothing function which is a broad class of smoothing functions for the LWCP and enjoys some favourable properties. Based on this function, we propose a new non-interior continuation method for solving the LWCP. In general, the non-interior continuation method consists of finding an exact solution of a system of equations at each iteration, which may be cumbersome if one is solving a large-scale problem. To overcome this difficulty, our method uses an inexact Newton method to solve the corresponding linear system approximately and adopts a non-monotone line search to obtain a step size. Under suitable assumptions, we show that the proposed method is globally and locally quadratically convergent. Preliminary numerical results are also reported.     

Asynchronous multisplitting relaxation methods for linear complementarity problems

To solve the linear complementarity problems efficiently on the high-speed multiprocessor systems, we set up a class of asynchronous parallel matrix multisplitting accelerated over-relaxation (AOR) method by technical combination of the matrix multisplitting and the accelerated overrelaxation techniques. The convergence theory of this new method is thoroughly established under the condition that the system matrix of the linear complementarity problem is an H-matrix with positive diagonal elements. At last, we also make multi-parameter extension for this new asynchronous multisplitting AOR method, and investigate the convergence property of the resulted asynchronous multisplitting unsymmetric AOR method. Thereby, an extensive sequence of asynchronous parallel relaxed iteration methods in the sense of multisplitting is presented for solving the large scale linear complementarity problems in the asynchronous parallel computing environments. This not only affords various choices, but also presents systematic convergence theories about the asynchronous parallel relaxation methods for solving the linear complementarity problems.     

An infeasible active-set QP-free algorithm for general nonlinear programming

We propose an infeasible active set QP-free algorithm for general constrained optimization in this paper. It starts from an arbitrary initial point. At each iteration, only two or three reduced linear equations with the same coefficients are solved to obtain the search direction. To determine the working set, the method makes use of multipliers from the last iteration, eliminating the need to compute a new estimate, and no additional linear systems are solved to select linear independent constraint gradients. The infeasibility measure and the objective function value are controlled separately by the filter technique. Without the positive definiteness assumption on the Hessian estimate, the sequence generated by the algorithm still globally converges to a Karush-Kuhn-Tucker point. And the algorithm obtains superlinear convergence without the strict complementarity. At last, preliminary numerical results are reported.     

A separable programming approach to the linear complementarity problem

The linear complementarity problem (LCP) is reformulated as a nonconvex, separable program and solved with a general branch and bound algorithm. Unlike the principal alternatives, the approach offered here works for all linear complementarity problems regardless of their underlying matrix structure. In the reformulated version, the optimal value is known at the outset so a convergence check can be made at each iteration of the algorithm. This greatly improves its performance; in fact, a number of cases are given where immediate convergence can be expected.     

非线性互补问题的多分裂加性Schwarz迭代算法

§1.引言 非线性互补问题在科学与工程中有着广泛的应用,因此研究求解非线性互补问题的高效数值算法是非常必要的。迄今为止,人们已给出了许多各种各样的Schwarz迭代算法用来求解变分不等式和互补问题。这些方法都适合并行计算,而且计算效果也不错。     

Modified alternating direction-implicit iteration method for linear systems from the incompressible Navier–Stokes equations

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, Ran and Yuan [On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems, Appl. Math. Comput. 217 (2010), pp. 3050–3068] presented the block symmetric successive over-relaxation (BSSOR) and the modified BSSOR iteration methods based on the special structures of the coefficient matrices. In this study, we present the modified alternating direction-implicit (MADI) iteration method for solving the linear systems. Under suitable conditions, we establish convergence theorems for the MADI iteration method. In addition, the optimal parameter involved in the MADI iteration method is estimated in detail. Numerical experiments show that the MADI iteration method is a feasible and effective iterative solver.     

An efficient two-step iterative method for solving a class of complex symmetric linear systems

In this paper, a new two-step iterative method called the two-step parameterized (TSP) iteration method for a class of complex symmetric linear systems is developed. We investigate its convergence conditions and derive the quasi-optimal parameters which minimize the upper bound of the spectral radius of the iteration matrix of the TSP iteration method. Meanwhile, some more practical ways to choose iteration parameters for the TSP iteration method are proposed. Furthermore, comparisons of the TSP iteration method with some existing ones are given, which show that the upper bound of the spectral radius of the TSP iteration method is smaller than those of the modified Hermitian and skew-Hermitian splitting (MHSS), the preconditioned MHSS (PMHSS), the combination method of real part and imaginary part (CRI) and the parameterized variant of the fixed-point iteration adding the asymmetric error (PFPAE) iteration methods proposed recently. Inexact version of the TSP iteration (ITSP) method and its convergence properties are also presented. Numerical experiments demonstrate that both TSP and ITSP are effective and robust when they are used either as linear solvers or as matrix splitting preconditioners for the Krylov subspace iteration methods and they have comparable advantages over some known ones for the complex symmetric linear systems.     

Convergence analysis of modified PGSS methods for singular saddle-point problems

Recently, variants of shift-splitting iteration method have been proposed for solving singular saddle-point problems. However, these methods can only be proved to converge to one of the solutions of the consistent singular linear system, not knowing any further information about this solution. In this work, we consider a modified preconditioned generalized shift-splitting (MPGSS) iteration method for solving both consistent and inconsistent singular saddle-point problems. This method is proved to converge to the best least squares solution. Moreover, based on the iteration form, a preconditioner is obtained to accelerate Krylov subspace methods. Theoretical analysis shows that the preconditioned GMRES method also converges to the best least squares solution of the consistent singular saddle-point problem. In addition, numerical results are presented to show the effectiveness and robustness of the proposed iteration method and preconditioner.     

Iterative algorithms for the linear complementarity problem

Direct complementary pivot algorithms for the linear complementarity problem with P-matrices are known to have exponential computational complexity. The analog of Gauss-Seidel and SOR iteration for linear complementarity problems with P-matrices has not been extensively developed. This paper extends some work of van Bokhoven to a class of nonsymmetric P-matrices, and develops and compares several new iterative algorithms for the linear complementarity problem. Numerical results for several hundred test problems are presented. Such indirect iterative algorithms may prove useful for large sparse complementarity problems.     

Fast and Scalable Solvers for the Fluid Pressure Equations with Separating Solid Boundary Conditions

In this paper, we propose and evaluate fast, scalable approaches for solving the linear complementarity problems (LCP) arising from the fluid pressure equations with separating solid boundary conditions. Specifically, we present a policy iteration method, a penalty method, and a modified multigrid method, and demonstrate that each is able to properly handle the desired boundary conditions. Moreover, we compare our proposed methods against existing approaches and show that our solvers are more efficient and exhibit better scaling behavior; that is, the number of iterations required for convergence is essentially independent of grid resolution, and thus they are faster at larger grid resolutions. For example, on a 256³ grid our multigrid method was 30 times faster than the prior multigrid method in the literature.     

广义修正HSS迭代法的超松弛加逮

通过推广修正埃尔米特和反埃尔米特（MHSS）迭代法,我们进一步得到了求解大型稀疏非埃尔米特正定线性方程组的广义MHSS（GMHSS）迭代法．基于不动点方程,我们还将超松弛（SOR）技术运用到了GMHSS迭代法,得到了关于GMHSS迭代法的SOR加速,并分析了它的收敛性．数值算例表明,SOR技术能够大大提高加速GMHSS迭代法的收敛效率．     

An inexact Newton method for solving complementarity problems in hydrodynamic lubrication

We present an iterative procedure based on a damped inexact Newton iteration for solving linear complementarity problems. We introduce the method in the framework of a popular problem arising in mechanical engineering: the analysis of cavitation in lubricated contacts. In this context, we show how the perturbation and the damping parameter are chosen in our method and we prove the global convergence of the entire procedure. A Fortran implementation of the method is finally analyzed. First, we validate the procedure and analyze all its components, performing also a comparison with a recently proposed technique based on the Fischer–Burmeister–Newton iteration. Then, we solve a 2D problem and provide some insights on an efficient implementation of the method exploiting routines of the Lapack and of the PETSc packages for the solution of inner linear systems.     

Numerical methods for the minimal non‐negative solution of the non‐symmetric coupled algebraic Riccati equation

In this paper, base on the theory of the non‐symmetric algebraic Riccati equation and the coupled Riccati equation, we give the general form of the non‐symmetric coupled algebraic Riccati equation (NCARE). In order to effectively solve the minimal non‐negative solution of the NCARE, two numerical iteration methods are improved: inexact Newton method (INewton) and alternate linear implicit method (ALI). Further, we give the convergence theory of the two iteration methods. Finally, we offer numerical examples to show the effectiveness of the derived methods.     

Efficient preconditioned NHSS iteration methods for solving complex symmetric linear systems

Based on the new HSS (NHSS) iteration method introduced by Pour and Goughery (2015), we propose a preconditioned variant of NHSS (P*NHSS) and an efficient parameterized P*NHSS (PPNHSS) iteration methods for solving a class of complex symmetric linear systems. The convergence properties of the P*NHSS and the PPNHSS iteration methods show that the iterative sequences are convergent to the unique solution of the linear system for any initial guess when the parameters are properly chosen. Moreover, we discuss the quasi-optimal parameters which minimize the upper bounds for the spectral radius of the iteration matrices. Numerical results show that the PPNHSS iteration method is superior to several iteration methods whether the experimental optimal parameters are used or not.     

非Hermitian正定线性方程组的外推的广义HSS方法

探讨了如何高效求解非Hermitian正定线性方程组,提出了一种外推的广义Hermitian和反Hermitian (EGHSS) 迭代方法。首先,根据矩阵的广义Hermitian和反Hermitian分裂,构造出了一种新的非对称的二步迭代格式。接着,理论分析了新方法的收敛性,并给出了新方法收敛的充要条件。数值实验结果表明,在处理某些问题时,EGHSS迭代方法比GHSS迭代方法和EHSS迭代方法更有效。     

A modified projection method for linear feasibility problems

In this paper, we present a modified projection method for the linear feasibility problems （LFP）. Compared with the existing methods, the new method adopts a surrogate technique to obtain new iteration instead of the line search procedure with fixed stepsize. For the new method, we first show its global convergence under the condition that the solution set is nonempty, and then establish its linear convergence rate. Preliminary numerical experiments show that this method has good performance.     

Solution of a nonlinear time-delay model in biology via semi-analytical approaches

The delay logistic equations have been extensively used as models in biology and other sciences, with particular emphasis on population dynamics. In this work, the variational iteration and Adomian decomposition methods are applied to solve the delay logistic equation. The variational iteration method is based on the incorporation of a general Lagrange multiplier in the construction of correction functional for the equation. On the other hand, the Adomian decomposition method approximates the solution as an infinite series and usually converges to the accurate solution. Moreover, these techniques reduce the volume of calculations because they have no need of discretization of the variables, linearization or small perturbations. Illustrative examples are included to demonstrate the validity and applicability of the presented methods.     

An IMEX predictor–corrector method for pricing options under regime-switching jump-diffusion models

An efficient second-order method for pricing European and American options under regime-switching jump-diffusion models is presented and analysed for stability and convergence. The implicit–explicit (IMEX) nature of the proposed method avoids the need to invert a full matrix and leads to tridiagonal systems that can be efficiently solved by direct methods. The IMEX predictor–corrector method is coupled with the operator splitting method to solve the linear complementarity problem of the American options. Numerical experiments are performed to demonstrate the stability and second-order convergence of the method.