Search

In the context of complementarity problems, various concepts of solution regularity are known, each of them playing a certain role in the related theoretical and algorithmic developments. Despite the existence of rich literature on this subject, it appears that the exact relations between some of these regularity concepts remained unknown. In this note, we not only summarize the existing results on the subject but also establish the missing relations filling all the gaps in the current understanding of how different regularity concepts relate to each other. In particular, we demonstrate that strong regularity is in fact equivalent to nonsingularity of all matrices in the natural outer estimates of the generalized Jacobians of the most widely used residual mappings for complementarity problems. On the other hand, we show that CD-regularity of the natural residual mapping does not imply even BD-regularity of the Fischer-Burmeister residual mapping. As a result, we provide the complete picture of relations between the most important regularity conditions for mixed complementarity problems, with a special emphasis on those conditions used to justify the related numerical methods. A special attention is paid to the particular cases of a nonlinear complementarity problem and of a Karush-Kuhn-Tucker system. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new generalized penalized Fischer-Burmeister merit function, and show that the function possesses a system of favorite properties. Moreover, for the merit function, we establish the boundedness of level set under a weaker condition. We also propose a derivative-free algorithm for nonlinear complementarity problems with a nonmonotone line search. More specifically, we show that the proposed algorithm is globally convergent and has a locally linear convergence rate. Numerical comparisons are also made with the merit function used by Chen (J Comput Appl Math 232:455-471, ), which confirm the superior behaviour of the new merit function. [ABSTRACT FROM AUTHOR]

In this paper we propose a class of new large-update primal-dual interior-point algorithms for P( κ) nonlinear complementarity problem (NCP), which are based on a class of kernel functions investigated by Bai et al. in their recent work for linear optimization (LO). The arguments for the algorithms are followed as Peng et al.'s for P( κ) complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, Princeton, 2002]. It is worth mentioning that since this class of kernel functions includes a class of non-self-regular functions as special case, so our algorithms are different from Peng et al.'s and the corresponding analysis is simpler than theirs. The ultimate goal of the paper is to show that the algorithms based on these functions have favorable polynomial complexity. [ABSTRACT FROM AUTHOR]

The nonlinear complementarity problem (denoted by NCP( F)) can be reformulated as the solution of a nonsmooth system of equations. In this paper, we propose a new smoothing and regularization Newton method for solving nonlinear complementarity problem with P-function ( P-NCP). Without requiring strict complementarity assumption at the P-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter ε in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods. [ABSTRACT FROM AUTHOR]

In this paper we propose a non-interior-point smoothing algorithm for solving the monotone nonlinear complementarity problem (NCP). The proposed algorithm is simpler than many existing non-interior-point smoothing algorithms in the sense that it only needs to solve one system of linear equations and to perform one line search at each iteration. We show that the proposed algorithm is globally convergent under the assumption that the NCP concerned has a nonempty solution set. Such assumption is weaker than those required by most other non-interior-point smoothing algorithms. In particular, we prove that the solution obtained by the proposed algorithm is a maximally complementary solution of the NCP concerned. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

In this paper we focus on the problem of identifying the index sets P(x):={i|x[sub i]>0}, N(x):={i|F[sub i](x)>0} and C(x):={i|x[sub i]=F[sub i](x)=0} for a solution x of the monotone nonlinear complementarity problem NCP(F). The correct identification of these sets is important from both theoretical and practical points of view. Such an identification enables us to remove complementarity conditions from the NCP and locally reduce the NCP to a system which can be dealt with more easily. We present a new technique that utilizes a sequence generated by the proximal point algorithm (PPA). Using the superlinear convergence property of PPA, we show that the proposed technique can identify the correct index sets without assuming the nondegeneracy and the local uniqueness of the solution. [ABSTRACT FROM AUTHOR]

In this paper we propose a variable dimension simplicial algorithm for solving the variational inequality problem on the cross product of the nonnegative orthant R+m of the m-dimensional Euclidean space Rm and the n-dimensional unit simplex Sn of Rn+1. Starting from an arbitrary point (u, v) ∈R+m ⊗ Sn, the algorithm generates a piecewise linear path in R+m ⊗ Sn. The path is traced by making alternately linear programming pivot operations and replacement steps in an appropriate simplicial subdivision of R+m ⊗ Sn. The algorithm differs from the thus far known algorithm in the number of directions in which it may leave the starting point. More precisely, the algorithm has (n + l)2m rays to leave the starting point whereas the existing algorithm has n + m + 1 rays. A convergence condition is presented and the accuracy estimation of an approximate solution generated is also given. [ABSTRACT FROM AUTHOR]