Search

We propose a smoothing Newton method for solving nonlinear complementarity problems based on a new smoothing function. We adopt a variant merit function. Under suitable conditions, we obtain the global convergence and local quadratic convergence of the proposed algorithm. Some numerical results indicate that our algorithm is effective for the given problems.

The nonlinear complementarity or NCP functions were introduced by Mangasarian and these functions are proved to be useful in constrained optimization and elsewhere. Interestingly enough there are only two general methods to derive such functions, while the known or used NCP functions are either individual constructions or modifications of the few individual NCP functions such as the Fischer-Burmeister function. In the paper we analyze the elementary properties of NCP functions and the various techniques used to obtain such functions from old ones. We also prove some new nonexistence results on the possible forms of NCP functions. Then we develop and analyze several new methods for the construction of nonlinear complementarity functions that are based on various geometric arguments or monotone transformations. The appendix of the paper contains the list and source of the known NCP functions.

A family of merit functions are proposed, which are the generalization of several existing merit functions. A number of favorable properties of the proposed merit functions are established. By using these properties, a merit function method for solving nonlinear complementarity problem is investigated, and the global convergence of the proposed algorithm is proved under some standard assumptions. Some preliminary numerical results are given.

In this paper, we study several NCP-functions for the nonlinear complementarity problem (NCP) which are indeed based on the generalized Fischer–Burmeister function, ϕp(a, b) = ||(a, b)||p - (a + b). It is well known that the NCP can be reformulated as an equivalent unconstrained minimization by means of merit functions involving NCP-functions. Thus, we aim to investigate some important properties of these NCP-functions that will be used in solving and analyzing the reformulation of the NCP.

Recently Tseng (Math Program 83:159–185, 1998) extended a class of merit functions, proposed by Luo and Tseng (A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, pp. 204–225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.

This paper is a follow-up of the work [Chen, J.-S.: J. Optimiz. Theory Appl., Submitted for publication (2004)] where an NCP-function and a descent method were proposed for the nonlinear complementarity problem. An unconstrained reformulation was formulated due to a merit function based on the proposed NCP-function. We continue to explore properties of the merit function in this paper. In particular, we show that the gradient of the merit function is globally Lipschitz continuous which is important from computational aspect. Moreover, we show that the merit function is SC 1 function which means it is continuously differentiable and its gradient is semismooth. On the other hand, we provide an alternative proof, which uses the new properties of the merit function, for the convergence result of the descent method considered in [Chen, J.-S.: J. Optimiz. Theory Appl., Submitted for publication (2004)].

Merit functions have become important tools for solving various mathematical problems arising from engineering sciences and economic systems. In this paper, we are surveying basic principles and properties of merit functions and some of their applications. As a particular case we will consider the nonlinear complementarity problem (NCP) and present a collection of different merit functions. We will also introduce and study a class of smooth merit functions for the NCP.

In this paper we reformulate several NCP-functions for the nonlinear complementarity problem (NCP) from their merit function forms and study some important properties of these NCP-functions. We point out that some of these NCP-functions have all the nice properties investigated by Chen, Chen and Kanzow [2] for a modified Fischer-Burmeister function, while some other NCP-functions may lose one or several of these properties. We also provide a modified normal map and a smoothing technique to overcome the limitation of these NCP-functions. A numerical comparison for the behaviour of various NCP-functions is provided.

Recently, Luo and Tseng proposed a class of merit functions for the nonlinear complementarity problem (NCP) and showed that it enjoys several interesting properties under some assumptions. In this paper, adopting a similar idea to that of Luo and Tseng, we present new merit functions for the NCP, which can be decomposed into component functions. We show that these merit functions not only share many properties with the one proposed by Luo and Tseng but also enjoy additional favorable properties owing to their decomposable structure. In particular, we present fairly mild conditions under which these merit functions have bounded level sets.

Recently, Tseng extended several merit functions for the nonlinear complementarity problem to the semidefinite complementarity problem (SDCP) and investigated various properties of those functions. In this paper, we propose a new merit function for the SDCP based on the squared Fischer-Burmeister function and show that it has some favorable properties. Particularly, we give conditions under which the function provides a global error bound for the SDCP and conditions under which it has bounded level sets. We also present a derivative-free method for solving the SDCP and prove its global convergence under suitable assumptions.

We investigate the numerical behavior of a new, simple algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a recently proposed merit function which possesses some interesting theoretical properties. One of the aims of the paper is to show that algorithms based on this merit function can be viable also from the numerical point of view.