Search

Some modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem are presented, and convergence analyses of the methods are given. Numerical experiments confirm the theoretical analysis, and show that the proposed methods are efficient.

The nonlinear complementarity problem (denoted by NCP(F)) has attracted much attention due to its various applications in economics, engineering and management science. In this paper, we propose a smoothing Broyden-like method for solving nonlinear complementarity problem. The algorithm considered here is based on the smooth approximation Fischer–Burmeister function and makes use of the derivative-free line search rule of Li in [D.H. Li, M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Meth. Software 13(3) (2000) 181–201]. We show that, under suitable conditions, the iterates generated by the proposed method converge to a solution of the nonlinear complementarity problem globally and superlinearly.

In this paper, nonlinear complementarity problem with P"0-function is studied. Based on a new smoothing function, the problem is approximated by a family of parameterized smooth equations and we present a new one-step smoothing Newton method to solve it. At each iteration, the proposed method only need to solve one system of linear equations and perform one Armijo-type line search. The algorithm is proved to be convergent globally and superlinearly without requiring strict complementarity at the solution. Numerical experiments demonstrate the feasibility and efficiency of the new algorithm.

Recently, so-called derivative-free methods have attracted much attention, which do not require computation of derivatives of function and are particularly suitable for problems which the derivatives are not available or are extremely expensive to compute. This paper presents a new derivative-free algorithm for nonlinear complementarity problem, which makes use of the efficiency of the filter technique. The algorithm is shown, under the monotonicity assumption, to globally converge to the solution of the nonlinear complementarity problem. The numerical results show the algorithm is feasible.

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a possibly inconsistent nonsmooth system of equations. Based on the ideas developed in smoothing Newton methods, we approximated the problem of the least l2-norm solution of the equivalent nonsmooth equations of NCP(F) with a family of parameterized optimization problem with twice continuously differentiable objective functions by making use of a new smoothing function. Then we presented a smoothing Levenberg–Marquardt method to solve the parameterized smooth optimization problem. By using the smooth and semismooth technique, the local quadratic convergence of the proposed method is proved under some suitable assumptions.

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the least l2-norm solution of a optimization problem. By introducing a new smoothing function, the problem is approximated by a family of parameterized optimization problems with twice continuously differentiable objective functions. Then a smoothing Levenberg–Marquardt method is applied to solve the parameterized optimization problems. The global convergence of the proposed method is proved under an assumption that the level set of the problem is compact. 2007 Elsevier Inc. All rights reserved.

In this paper, an additive Schwarz algorithm is considered for solving the finite-dimensional nonlinear complementarity problem with M-function. The monotone convergence of the algorithm is obtained with special choices of initial values. Moreover, the weighted max-norm bound is obtained for the iterative errors.

In this paper, we establish a direct preconditioned modulus-based iteration method for solving a class of nonlinear complementarity problems with the system matrix being an H-matrix. The convergence theorems of the proposed method are given, which generalize and improve the existing ones. Numerical examples show that the proposed method is efficient.

A modulus-based nonmonotone line search method is proposed for nonlinear complementarity problem. The considered problem is first reformulated to a nonsmooth nonlinear system based on the modulus-based decomposition. Then a nonmonotone line search method using simulated annealing rule is generalized to solve the resulting system. The global convergence of the proposed method is established under some suitable assumptions. Preliminary numerical experiments show that, compared with some existing methods, the proposed method is feasible and effective.

To overcome the dependence of the convergence rate on the grid size in the existing modulus-based method, we present a modulus-based multigrid method to efficiently solve the nonlinear complementarity problems. In this paper, the nonlinear complementarity problems under consideration arise from free boundary problems with nonlinear source terms. The two-grid local Fourier analysis is given to predict the asymptotic convergence factor and the optimal relaxation parameter of the presented modulus-based multigrid method, and the predictions are agreement with the experimental results. Numerical results also show that both W- and F-cycles significantly outperform the existing modulus-based method and achieve asymptotic optimality in terms of grid-independent convergence rate and linear CPU time when the grid is refined.

We propose a penalty method for a finite-dimensional nonlinear complementarity problem (NCP) arising from the discretization of the infinite-dimensional free boundary/obstacle problem governing the valuation of American options under transaction costs. In this method, the NCP is approximated by a system of nonlinear equations containing a power penalty term. We show that the mapping involved in the system is continuous and strongly monotone. Thus, the unique solvability of both the NCP and the penalty equation and the exponential convergence of the solution to the penalty equation to that of the NCP are guaranteed by an existing theory. Numerical results will be presented to demonstrate the convergence rates and usefulness of this penalty method.

In this work, we first translate the nonlinear complementarity problem (denoted by NCP(F)) into Newton equation with disturbance. When Jacobian of the NCP function is not invertible, we use the Broyden-like formulae to update it. Taking advantage of the virtue of filter technique, we propose a filter method for the nonlinear complementarity problem with derivative-free line search. The proposed algorithm is proved to be globally convergent under mild assumptions. Furthermore, we get superlinear convergence of the method under the proper conditions.

The goal of this paper is to study Nash Equilibrium (NE) existence of some game-theoretic pricing models. In Soon et al. [17] , deterministic pricing models incorporating a complete demand system were proposed. As in those models, the demand function is defined via a Nonlinear Complementarity Problem (NCP), the models’ pricing constraints include complementarity conditions. When incorporated within a game, the best response problem facing each seller is a Mathematical Program with Equilibrium Constraints. A randomized version of this pricing problem will be introduced in this work and the issue of NE existence will be discussed for both the deterministic and random pricing games.

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 0 -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.

In this paper, we present an algorithm for solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs. The path cost function considered is comprised of two attributes, travel time and toll, that are combined into a nonlinear generalized cost. Travel demand is determined endogenously according to a travel disutility function. Travelers choose routes with the minimum overall generalized costs. The algorithm involves two components: a bicriteria shortest path routine to implicitly generate the set of non-dominated paths and a projection and contraction method to solve the nonlinear complementarity problem (NCP) describing the traffic equilibrium problem. Numerical experiments are conducted to demonstrate the feasibility of the algorithm to this class of traffic equilibrium problems.

The smoothing-type algorithm has been successfully applied to solve various optimization problems. In general, the smoothing-type algorithm is designed based on some monotone line search. However, in order to achieve better numerical results, the non-monotone line search technique has been used in the numerical computations of some smoothing-type algorithms. In this paper, we propose a smoothing-type algorithm for solving the nonlinear complementarity problem with a non-monotone line search. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The preliminary numerical results are also reported.

This paper addresses the convergence of two nonmonotone Levenberg-Marquardt algorithms for nonlinear complementarity problem. Under some mild assumptions, and requiring only the solution of a linear system at each iteration, the nonmonotone Levenberg-Marquardt algorithms are shown to be globally convergent.

Recently, filter methods are extensively studied to handle nonlinear programming problems. Because of good numerical results, filter techniques are attached importance to. The nonlinear complementarity problem can be reformulated as the least l"2-norm solution of an optimization problem. In this paper, basing on the filter technique and the new smoothing function, we present a new Filter-Levenberg-Marquardt method for solving the equation system @J(z^k)+[M(z^k)+@l"kI]@Dz^k=@b"kz@? with the disturbance @b"kz@?. Under the assumption that the lever set of the problem is compact, we prove its global convergence.

In this paper, we describe H -differential of the implicit Lagrangian function. We show how, under appropriate regularity conditions on an H -differential of f , minimizing the implicit Lagrangian function corresponding to f leads to a solution of the nonlinear complementarity problem. Our results give a unified treatment of such results for C 1 -functions and for locally Lipschitzian functions.

The nonlinear complementarity problem can be reformulated as a nonsmooth equation. In this paper we propose a new smoothing quasi-Newton method for the solution of the nonlinear complementarity problems by constructing a new smoothing approximation function. Global and local superlinear convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in the paper.

Error bound theory play an important role in many mathematical programming problems. In this paper, we propose a new assumption condition under which we establish a global Lipshitzian error bound for the semidefinite complementarity problem (SDCP). As corollaries, two results involving the assumptions of strong monotonicity and BD-regularity are given. When the SDCP reduces to the nonlinear complementarity problem (NCP), our results strictly generalize the well-known error bound results which were established under the assumptions of strong monotonicity and uniform P-property. We also establish a new error bound for the NCP under BD-regularity and some R"0-type condition.

The alternating direction method is mainly adopted to solve large-scale variational inequality problems with separable structure. The method is effective because it solves the original high-dimensional variational inequality problem by solving a series of much easier low-dimensional subproblems. In this paper, we present an inexact alternating directions method. Compared with the quadratic proximal alternating direction methods, the proposed method solves a series of related systems of nonlinear equations instead of a series of sub-VIs. The inexact criteria are more relaxed than the ones used by He et al. [7]. The generated sequence is Fejer monotone with respect to the solution set and the convergence is proved under suitable conditions.

In the paper, we consider a continuation approach for the binary quadratic program (BQP) based on a class of NCP-functions. More specifically, we recast the BQP as an equivalent minimization and then seeks its global minimizer via a global continuation method. Such approach had been considered in [11] which is based on the Fischer–Burmeister function. We investigate this continuation approach again by using a more general function, called the generalized Fischer–Burmeister function. However, the theoretical background for such extension can not be easily carried over. Indeed, it needs some subtle analysis.

The nonlinear complementarity problems (denoted by NCPs) usually are reformulated as the solution of a nonsmooth system of equations. In this paper, we will present a regularized smoothing Newton method for solving nonlinear complementarity problems with P 0 -function ( P 0 -NCPs) based on the generalized smoothing Fischer–Burmeister NCP-function ϕ p ( μ , a , b ) with p > 1, where μ is smoothing parameter. Without requiring strict complementarity assumption at the P 0 -NCPs solution, the proposed algorithm is proved to be globally and superlinearly convergent under suitable assumptions. Furthermore, the algorithm is locally quadratic convergent under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter e in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many existing literatures.

This paper is concerned with several structural properties of a homotopy path for nonlinear continuous semi-monotone complementarity problems. Especially, several sufficient conditions are established for the existence and boundedness of this homotopy path. Under the P"0 property, all these sufficient conditions guarantee the uniqueness and continuity of this path. The concept of @m-exceptional family plays a key role in the analysis throughout this paper.

Filter methods are extensively studied to handle nonlinear programming problems recently. Because of good numerical results, filter techniques are attached importance to. In this paper, filter approaches are employed to tackle nonlinear complementarity problems (NCPs). Firstly, NCP conditions are transformed into a nonlinear programming problem. Then, to obtain a trial step, the corresponding nonlinear programming problems are solved by some existing strategies. Moreover, filter criterion is utilized to evaluate a trial iterate. The purpose in this paper is to employ filter approaches to attack NCPs. In essence, multi-objective view is utilized to attack NCPs because the idea of filter methods stems from multi-objective problems. Furthermore, a new filter method, based on the special two objects which differs from others, is brought forward. Moreover, Maratos effects are overcome in our new filter approach by weakening acceptable conditions.

In this work, nonlinear complementarity problems (NCPs) are considered. Some NCPs, which come from practice, have no derivatives or it is very difficult to obtain their derivatives. Derivative-free methods are hence considered. Generalized pattern search (GPS) method, as a kind of derivative-free method, plays a very significant role. We combine generalized pattern search method with filter method to attack NCPs because one can analyze the theory of generalized pattern search filter method without sufficient reduction conditions and avoid using of derivatives. Some interesting results are obtained in this work without sufficient reduction conditions. Furthermore, generalized pattern search filter method is efficient to some special problems.

In accordance with the principle of sufficiently using delayed information, and making use of the nonlinear multisplitting and the nonlinear relaxation techniques, we present in this paper a class of asynchronous parallel nonlinear multisplitting successive overrelaxation (SOR) methods for solving large sparse nonlinear complementarity problems on high-speed MIMD multiprocessor systems. These new methods particularly include the so-called asynchronous parallel nonlinear multisplitting SOR-Newton method, asynchronous parallel nonlinear multisplitting SOR-chord method and asynchronous parallel nonlinear multisplitting SOR-Steffensen method. Under suitable conditions we establish the local convergence theory of this class of new methods. Numerical imitations show that our new methods are feasible and efficient for solving the nonlinear complementarity problems on the MIMD multiprocessor systems.

The Chow-Yorke algorithm is a scheme for developing homotopy methods that are globally convergent with probability one. Homotopy maps leading to globally convergent algorithms have been created for Brouwer fixed-point problems, certain classes of nonlinear systems of equations, the nonlinear complementarity problem, some nonlinear two-point boundary-value problems, and convex optimization problems. The Chow-Yorke algorithm has been successfully applied to a wide range of engineering problems, particularly those for which quasi-Newton and locally convergent iterative techniques are inadequate. Some of those engineering applications are surveyed here.