A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

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     

Nonlinear complementarity as unconstrained optimization

Several methods for solving the nonlinear complementarity problem (NCP) are developed. These methods are generalizations of the recently proposed algorithms of Mangasarian and Solodov (Ref. 1) and are based on an unconstrianed minimization formulation of the nonlinear complementarity problem. It is shown that, under certain assumptions, any stationary point of the unconstrained objective function is already a solution of NCP. In particulr, these assumptions are satisfied by the mangasarian and Soolodov implicit Lagranian functioin. Furthermore, a special Newton-type method is suggested, and conditions for its local quadratic convergence are given. Finally, some preliminary numerical results are presented.The author would like to thank Dr. Oswald Knoth (Leipzig) for pointing out that the equivalence of Lemma 2.2. is not true for complementarity problems which have no solutions. He is also grateful to the anonymous referencees for their helpful comments.     

Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms

For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

基于一个新的NCP函数的光滑牛顿法求解非线性互补问题

本文研究了非线性互补的光滑化问题.利用一个新的光滑NCP函数将非线性互补问题转化为等价的光滑方程组,并在此基础上建立了求解P0-函数非线性互补问题的一个完全光滑化牛顿法,获得了算法的全局收敛性和局部二次收敛性的结果.并给出数值实验验证了理论分析的正确性.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] 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 article an iterative algorithm is studied in connection with an implicit complementarity problem. 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, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

INEXACT DAMPED NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

Solution of the complex linear complementarity problem

In an earlier paper, it was shown that the linear and quadratic programming problems in complex space could be unified in the “complex linear complementarity problem” (complex LCP). An existence theory for this problem was provided. The present paper addresses the problem of actually solving the complex LCP and hence complex linear and quadratic programs as well. Two solution procedures are described and an example is given.     

Unconstrained minimization approaches to nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as unconstrained minimization problems by introducing merit functions. Under some assumptions, the solution set of the nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. These results were presented by Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow. In this note, we generalize some results of Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow to the case where the considered function is only directionally differentiable. Some results are strengthened in the smooth case. For example, it is shown that the strong monotonicity condition can be replaced by the P-uniform property for ensuring a stationary point of the reformulated unconstrained minimization problems to be a solution of the nonlinear complementarity problem. We also present a descent algorithm for solving the nonlinear complementarity problem in the smooth case. Any accumulation point generated by this algorithm is proved to be a solution of the nonlinear complementarity under the monotonicity condition.     

Error Bounds for the Solution Sets of Quadratic Complementarity Problems

In this article, two types of fractional local error bounds for quadratic complementarity problems are established, one is based on the natural residual function and the other on the standard violation measure of the polynomial equalities and inequalities. These fractional local error bounds are given with explicit exponents. A fractional local error bound with an explicit exponent via the natural residual function is new in the tensor/polynomial complementarity problems literature. The other fractional local error bounds take into account the sparsity structures, from both the algebraic and the geometric perspectives, of the third-order tensor in a quadratic complementarity problem. They also have explicit exponents, which improve the literature significantly.     

On active-set methods for the quadratic programming problem

The active-set Newton method developed earlier by the authors for mixed complementarity problems is applied to solving the quadratic programming problem with a positive definite matrix of the objective function. A theoretical justification is given to the fact that the method is guaranteed to find the exact solution in a finite number of steps. Numerical results indicate that this approach is competitive with other available methods for quadratic programming problems.     

The Generic Stability and Existence of Essentially Connected Components of Solutions for Nonlinear Complementarity Problems

The aim of this paper is to develop the general generic stability theory for nonlinear complementarity problems in the setting of infinite dimensional Banach spaces. We first show that each nonlinear complementarity problem can be approximated arbitrarily by a nonlinear complementarity problem which is stable in the sense that the small change of the objective function results in the small change of its solution set; and thus we say that almost all complementarity problems are stable from viewpoint of Baire category. Secondly, we show that each nonlinear complementarity problem has, at least, one connected component of its solutions which is stable, though in general its solution set may not have good behaviour (i.e., not stable). Our results show that if a complementarity problem has only one connected solution set, it is then always stable without the assumption that the functions are either Lipschitz or differentiable.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．     

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.     

依赖凝聚函数求解非线性互补问题的一种微分方程方法

利用凝聚函数一致逼近非光滑极大值函数的性质,将非线性互补问题转化为参数化光滑方程组.然后,对此方程组给出了一种微分方程解法,并且证明了非线性互补问题的解是微分方程系统的渐进稳定平衡点.在适当的假设条件下,证明了所给出的算法具有二次收敛速度.数值结果表明了此算法的有效性.     

A smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.