Generalized mildly nonlinear complementarity problems for fuzzy mappings

In this paper, we introduce and study a new class of generalized mildly nonlinear complementarity problems for fuzzy mappings. We use the change of variables technique to establish the equivalence between the generalized mildly nonlinear complementarity problems and the Wiener-Hopf equations. This equivalence is used to suggest and analyze a number of iterative algorithm for solving the generalized mildly nonlinear complementarity problems.     

A Finite Algorithm for Almost Linear Complementarity Problems

We present an algorithm for solving a class of nonlinear complementarity problems called the almost linear complementarity problem (ALCP), which can be used to simulate free boundary problems. The algorithm makes use of a procedure for identifying an active index subset of an ALCP by bounding its solution with an interval vector. It is shown that an acceptable solution of the given ALCP can be obtained by solving at most n systems of equations. Numerical results are reported to illustrate the efficiency of the algorithm for large-scale problems.     

Smooth methods of multipliers for complementarity problems

This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems. Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999     

A Gauss-Seidel iteration method for nonlinear variational inequality problems over rectangles

This paper presents a simple yet practically useful Gauss-Seidel iterative method for solving a class of nonlinear variational inequality problems over rectangles and of nonlinear complementarity problems. This scheme is a nonlinear generalization of a robust iterative method for linear complementarity problems developed by Mangasarian. Global convergence is presented for problems with Z-functions. It is noted that the suggested method can be viewed as a specific case of a class of linear approximation methods studied by Pang and others.     

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.     

对广义互补问题迭代方法收敛性分析的统一途径

1．介绍非线性互补问题，记作NCP（F0）；是指求XRn使得其中的：RNCP有各种不同形式的推广．例如，一种广泛的互补问题，记作NCP（F1，F2，…，FN），是指求xRn使得其中马：＊”＋＊”，马杜）是马（x）的第7个分量·NCP（凡）的发展及其应用在数学规划领域己经有很长的历...     

A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China.     

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.     

A Linearly Convergent Derivative-Free Descent Method for Strongly Monotone Complementarity Problems

We establish the first rate of convergence result for the class of derivative-free descent methods for solving complementarity problems. The algorithm considered here is based on the implicit Lagrangian reformulation [26, 35] of the nonlinear complementarity problem, and makes use of the descent direction proposed in [42], but employs a different Armijo-type linesearch rule. We show that in the strongly monotone case, the iterates generated by the method converge globally at a linear rate to the solution of the problem.     

Convergence of modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems

Numerical Algorithms - In this paper, we discuss the modulus-based matrix splitting iteration method for solving a class of nonlinear complementarity problems under a weakened condition, and...     

Generalized equations and the generalized Newton method

We give some convergence results on the generalized Newton method (referred to by some authors as Newton's method) and the chord method when applied to generalized equations. The main results of the paper extend the classical Kantorovich results on Newton's method to (nonsmooth) generalized equations. Our results also extend earlier results on nonsmooth equations due to Eaves, Robinson, Josephy, Pang and Chan. We also propose inner-iterative schemes for the computation of the generalized Newton iterates. These schemes generalize popular iterative methods (Richardson's method, Jacobi's method and the Gauss-Seidel method) for the solution of linear equations and linear complementarity problems and are shown to be convergent under natural generalizations of classical convergence criteria. Our results are applicable to equations involving single-valued functions and also to a class of generalized equations which includes variational inequalities, nonlinear complementarity problems and some nonsmooth convex minimization problems.     

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.     

Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP

In this paper, we propose a general smoothing Broyden-like quasi-Newton method for solving a class of nonsmooth equations. Under appropriate conditions, the proposed method converges to a solution of the equation globally and superlinearly. In particular, the proposed method provides the possibility of developing a quasi-Newton method that enjoys superlinear convergence even if strict complementarity fails to hold. We pay particular attention to semismooth equations arising from nonlinear complementarity problems, mixed complementarity problems and variational inequality problems. We show that under certain conditions, the related methods based on the perturbed Fischer–Burmeister function, Chen–Harker–Kanzow–Smale smoothing function and the Gabriel–Moré class of smoothing functions converge globally and superlinearly.     

A full-Newton step non-interior continuation algorithm for a class of complementarity problems

In this paper, we investigate a class of nonlinear complementarity problems arising from the discretization of the free boundary problem, which was recently studied by Sun and Zeng [Z. Sun, J. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math. 235 (5) (2011) 1261–1274]. We propose a new non-interior continuation algorithm for solving this class of problems, where the full-Newton step is used in each iteration. We show that the algorithm is globally convergent, where the iteration sequence of the variable converges monotonically. We also prove that the algorithm is globally linearly and locally superlinearly convergent without any additional assumption, and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate the effectiveness of the proposed algorithm.     

一类弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法

本文提出一类求解弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法，并给出了系数矩阵为H₊-矩阵时该方法的收敛性分析.数值实验表明新方法是有效的.     

An extended Gauss–Seidel method for a class of multi-valued complementarity problems

The complementarity problem is one of the basic topics in nonlinear analysis; however, the methods for solving complementarity problems are usually developed for problems with single-valued mappings. In this paper we examine a class of complementarity problems with multi-valued mappings and propose an extension of the Gauss–Seidel algorithm for finding its solution. Its convergence is proved under off-diagonal antitonicity assumptions. Applications to Walrasian type equilibrium problems and to nonlinear input–output problems are also given. In this work, the authors were supported by Brescia University grant PRIN - 2006: “Oligopolistic models and order monotonicity properties”, the third author was also supported by the joint RFBR–NNSF grant, project No. 07-01-92101.     

A class of asynchronous parallel nonlinear accelerated overrelaxation methods for the nonlinear complementarity problems

In accordance with the principle of using sufficiently the delayed information, and by making use of the nonlinear multisplitting and the nonlinear relaxation techniques, we present in this paper a class of asynchronous parallel nonlinear multisplitting accelerated overrelaxation (AOR) methods for solving the large sparse nonlinear complementarity problems on the high-speed MIMD multiprocessor systems. These new methods, in particular, include the so-called asynchronous parallel nonlinear multisplitting AOR-Newton method, the asynchronous parallel nonlinear multisplitting AOR-chord method and the asynchronous parallel nonlinear multisplitting AOR-Steffensen method. Under suitable constraints on the nonlinear multisplitting and the relaxation parameters, we establish the local convergence theory of this class of new methods when the Jacobi matrix of the involved nonlinear mapping at the solution point of the nonlinear complementarity problem is an H-matrix.     

The convergence of a modified smoothing-type algorithm for the symmetric cone complementarity problem

The symmetric cone complementarity problem (denoted by SCCP) is a broad class of optimization problems, which contains the semidefinite complementarity problem, the second-order cone complementarity problem, and the nonlinear complementarity problem. In this paper we first extend the smoothing function proposed by Huang et al. (Sci. China 44:1107–1114, 2001) for the nonlinear complementarity problem to the context of symmetric cones and show that it is coercive under suitable assumptions. Based on this smoothing function, a smoothing-type algorithm, which is a modified version of the Qi-Sun-Zhou method (Qi et al. in Math. Program. 87:1–35, 2000), is proposed for solving the SCCP. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results for some second-order cone complementarity problems are reported which indicate that the proposed algorithm is effective.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

Local path-following property of inexact interior methods in nonlinear programming

We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199?C222, 2008). The purpose of the present paper is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results.