A smoothing conic trust region filter method for the nonlinear complementarity problem

This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition.     

A modified damped Newton method for linear complementarity problems

We present a modified damped Newton method for solving large sparse linear complementarity problems, which adopts a new strategy for determining the stepsize at each Newton iteration. The global convergence of the new method is proved when the system matrix is a nondegenerate matrix. We then apply the matrix splitting technique to this new method, deriving an inexact splitting method for the linear complementarity problems. The global convergence of the resulting inexact splitting method is proved, too. Numerical results show that the new methods are feasible and effective for solving the large sparse linear complementarity problems.     

非线性互补问题的组合同伦算法

针对拟P_*-映射和P(τ,α,β)-映射所对应的非线性互补问题,本文对其解的存在性及有效求解算法进行了研究.文中利用组合同伦方法给出了这两类非线性互补问题存在有界解的构造性证明,并利用预估校正方法对同伦路径进行跟踪,得到了互补问题的解.通过数值算例验证了该算法的有效性.     

Optimal Control Formulation for Complementarity Dynamical Systems

In this paper, we show that the complementarity dynamical systems can be reformulated as optimal control problems. By using this reformulation, we present a pseudospectral scheme to discretize the complementarity dynamical systems. Applying this discretization, the complementarity dynamical system is reduced to a sequence of nonlinear programming problems. Numerical examples and comparison with two other methods are included to demonstrate the capability of the proposed method.     

Solution Sets of Quadratic Complementarity Problems

In this paper, we study quadratic complementarity problems, which form a subclass of nonlinear complementarity problems with the nonlinear functions being quadratic polynomial mappings. Quadratic complementarity problems serve as an important bridge linking linear complementarity problems and nonlinear complementarity problems. Various properties on the solution set for a quadratic complementarity problem, including existence, compactness and uniqueness, are studied. Several results are established from assumptions given in terms of the comprising matrices of the underlying tensor, henceforth easily checkable. Examples are given to demonstrate that the results improve or generalize the corresponding quadratic complementarity problem counterparts of the well-known nonlinear complementarity problem theory and broaden the boundary knowledge of nonlinear complementarity problems as well.     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

Improved smoothing Newton methods for symmetric cone complementarity problems

There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems.     

Finding solutions of implicit complementarity problems by isotonicity of the metric projection

Isac and Németh [G. Isac and A. B. Németh, Projection method, isotone projection cones and the complementarity problem, J. Math. Anal. App., 153, 258-275(1990)] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this paper, the notion of *-isotone projection cones is employed and an iterative algorithm is presented in connection with an implicit complementarity problem on *-isotone projection cones. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by *-isotone projection cones. The question of finding nonzero solutions of these problems is also studied.     

An algorithm for a class of nonlinear complementarity problems with non-Lipschitzian functions

In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective.     

A Modified Projection and Contraction Method for a Class of Linear Complementarity Problems

1.Intr0ducti0nLetL={1,..',l},ICL,Mbeanlxlpositivesemi-definitematrir(butnotnecessarilysymmetric)andqERl.F0rgeneralizedlinearcomplementaxitypr0blems\xehavepresentedagloballyconvergentprojecti0nandc0ntractionmethod(PCmeth0d)[4T1iismethodisaniterativeprocedurewhichrequire8ineachsteponlytwomatrir-vPctorn1ultiplications,andperformsnotransformationofthematrixelements.Theluethodthereforeallowstheoptimalexploitationofthesparsity0fthec0nstraintmatrixa11dmaythusbeefficientforlargesparseproblemsl4].…     

Continuation method for nonlinear complementarity problems via normal maps

In a recent paper by Chen and Mangasarian (C. Chen, O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications 2 (1996), 97–138) a class of parametric smoothing functions has been proposed to approximate the plus function present in many optimization and complementarity related problems. This paper uses these smoothing functions to approximate the normal map formulation of nonlinear complementarity problems (NCP). Properties of the smoothing function are investigated based on the density functions that defines the smooth approximations. A continuation method is then proposed to solve the NCPs arising from the approximations. Sufficient conditions are provided to guarantee the boundedness of the solution trajectory. Furthermore, the structure of the subproblems arising in the proposed continuation method is analyzed for different choices of smoothing functions. Computational results of the continuation method are reported.     

A regularized projection method for complementarity problems with non-Lipschitzian functions

We consider complementarity problems involving functions which are not Lipschitz continuous at the origin. Such problems arise from the numerical solution for differential equations with non-Lipschitzian continuity, e.g. reaction and diffusion problems. We propose a regularized projection method to find an approximate solution with an estimation of the error for the non-Lipschitzian complementarity problems. We prove that the projection method globally and linearly converges to a solution of a regularized problem with any regularization parameter. Moreover, we give error bounds for a computed solution of the non-Lipschitzian problem. Numerical examples are presented to demonstrate the efficiency of the method and error bounds.

     

改进的分块模方法求解对角占优线性互补问题

为了高效求解中小型线性互补问题,本文提出了改进的分块模方法,并证明了关于严格对角占优（对角元素均为正数）线性互补问题的收敛性.对于广义对角占优线性互补问题,先将其转化为严格对角占优线性互补问题,再采用改进的分块模方法求解.数值结果表明,改进的分块模方法在求解广义对角占优线性互补问题时在内迭代次数和计算时间上均明显优于分块模方法.     

Global Optimization Techniques for Mixed Complementarity Problems

We investigate the theoretical and numerical properties of two global optimization techniques for the solution of mixed complementarity problems. More precisely, using a standard semismooth Newton-type method as a basic solver for complementarity problems, we describe how the performance of this method can be improved by incorporating two well-known global optimization algorithms, namely a tunneling and a filled function method. These methods are tested and compared with each other on a couple of very difficult test examples.     

二阶锥线性互补问题的低阶罚函数算法

本文研究了二阶锥线性互补问题的低阶罚函数算法.利用低阶罚函数算法将二阶锥线性互补问题转化为低阶罚函数方程组,获得了低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥线性互补问题解的结果,推广了二阶锥线性互补问题的幂罚函数算法.数值实验结果验证了算法的有效性.     

Nonmonotone Inexact Newton Method for the Extended Linear Complementarity Problem

This paper presents a nonmonotone inexact Newton-type method for the extended linear complementarity problem (ELCP). We first reformulate the optimization system of the ELCP problem into a system of smoothed equations. Then we solve this system by a nonmonotone inexact Newton-type algorithm. The global convergence is obtained and numerical tests for some classes of ELCP include linear complementarity, horizontal linear complementarity, and generalized linear complementarity problems are also given to show the e?ciency of the proposed algorithm.     

A new method for solving Pareto eigenvalue complementarity problems

In this paper, we introduce a new method, called the Lattice Projection Method (LPM), for solving eigenvalue complementarity problems. The original problem is reformulated to find the roots of a nonsmooth function. A semismooth Newton type method is then applied to approximate the eigenvalues and eigenvectors of the complementarity problems. The LPM is compared to SNM_min and SNM_FB, two methods widely discussed in the literature for solving nonlinear complementarity problems, by using the performance profiles as a comparing tool (Dolan, Moré in Math. Program. 91:201–213, 2002). The performance measures, used to analyze the three solvers on a set of matrices mostly taken from the Matrix Market (Boisvert et al. in The quality of numerical software: assessment and enhancement, pp. 125–137, 1997), are computing time, number of iterations, number of failures and maximum number of solutions found by each solver. The numerical experiments highlight the efficiency of the LPM and show that it is a promising method for solving eigenvalue complementarity problems. Finally, Pareto bi-eigenvalue complementarity problems were solved numerically as an application to confirm the efficiency of our method.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

隐互补问题的极小化变形及其稳定点

1 引言 互补问题在最优化中有着广泛的应用,例如线性规划中的对偶问题,非线性规划中求稳定点的KKT条件以及变分不等式的求解都可以转化为互补问题,另外,某些均衡网络设计问题、信号最优化问题以及交通配置等问题也可利用互补问题来求解.