On construction of new NCP functions

We report a new method to construct complementarity functions for the nonlinear complementarity problem (NCP). Basic properties related to growth behavior, convexity and semismoothness of the newly discovered NCP functions are proved. We also present some variants, generalizations and other transformations of these NCP functions. Finally, we propose some interesting research directions that can be explored in the NCP research.     

Properties of Restricted NCP Functions for Nonlinear Complementarity Problems

In this paper, we study restricted NCP functions which may be used to reformulate the nonlinear complementarity problem as a constrained minimization problem. In particular, we consider three classes of restricted NCP functions, two of them introduced by Solodov and the other proposed in this paper. We give conditions under which a minimization problem based on a restricted NCP function enjoys favorable properties, such as equivalence between a stationary point of the minimization problem and the nonlinear complementarity problem, strict complementarity at a solution of the minimization problem, and boundedness of the level sets of the objective function. We examine these properties for three restricted NCP functions and show that the merit function based on the restricted NCP function proposed in this paper enjoys favorable properties compared with those based on the other restricted NCP functions.     

New NCP-Functions and Their Properties

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.     

Existence of optimal solutions for general stochastic linear complementarity problems

In this paper we show the solvability of the expected residual minimization (ERM) formulation for the general stochastic linear complementarity problem (SLCP) under mild assumptions. The properties of the ERM formulation are dependent on the choice of NCP functions. We focus on the ERM formulations defined by the “min” NCP function and the penalized FB function, both of which are nonconvex programs on the nonnegative orthant.     

A self-adaptive trust region method for the extended linear complementarity problems

By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions. This work is supported by National Natural Science Foundation of China (No. 10671126) and Shanghai Leading Academic Discipline Project (S30501).     

P_0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于Ｐ０函数非线性互补问题提出了一个基于Ｋａｎｚｏｗ光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性．特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Ｊａｃｏｂｉ阵是Ｌｉｐｓｃｈｉｔｚ连续的．文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的．本文提出的方法在每一次迭代只须解一个线性方程式组．     

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.     

具有分片线性NCP函数的QP-Free可行域方法

In this paper, a QP-free feasible method with piecewise NCP functions is proposed for nonlinear inequality constrained optimization problems. The new NCP functions are piecewise linear-rational, regular pseudo-smooth and have nice properties. This method is based on the solutions of linear systems of equation reformulation of KKT optimality conditions, by using the piecewise NCP functions. This method is implementable and globally convergent without assuming the strict complementarity condition, the isolatedness of accumulation points. Furthermore, the gradients of active constraints are not requested to be linearly independent. The submatrix which may be obtained by quasi-Newton methods, is not requested to be uniformly positive definite. Preliminary numerical results indicate that this new QP-free method is quite promising.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

Properties of a family of merit functions and a merit function method for the NCP

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.     

PIECEWISE LINEAR NCP FUNCTION FOR QP FREE FEASIBLE METHOD

In this paper,a QP-free feasible method with piecewise NCP functions is proposed for nonlinear inequality constrained optimization problems.The new NCP functions are piece- wise linear-rational,regular pseudo-smooth and have nice properties.This method is based on the solutions of linear systems of equation reformulation of KKT optimality conditions,by using the piecewise NCP functions.This method is implementable and globally convergent without assuming the strict complementarity condition,the isolatedness of accumulation points.Fur- thermore,the gradients of active constraints are not requested to be linearly independent.The submatrix which may be obtained by quasi-Newton methods,is not requested to be uniformly positive definite.Preliminary numerical results indicate that this new QP-free method is quite promising.     

Predictor-Corrector Smoothing Newton Method,Based on a New Smoothing Function,for Solving the Nonlinear Complementarity Problem with a P 0 Function

By smoothing a perturbed minimum function, we propose in this paper a new smoothing function. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. We investigate the boundedness of the iteration sequence generated by noninterior continuation/smoothing methods under the assumption that the solution set of the NCP is nonempty and bounded. Based on the new smoothing function, we present a predictor-corrector smoothing Newton algorithm for solving the NCP with a P ₀ function, which is shown to be globally linearly and locally superlinearly convergent under suitable assumptions. Some preliminary computational results are reported.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

Merit Functions for Complementarity and Related Problems: A Survey

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.     

A new hybrid method for nonlinear complementarity problems

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P ₀ function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P ₀ functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition.     

A GLOBALal DERIVTIVE-FREE DESCENT METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1. IntroductionConsider the nonlinear complementarity problem (NCP for short), which is to findan x E M" such thatwhere F: Wu - ac and the inequalities are taken componentwise. This problem havemany important applications in various fields. [13, 7, 5].Due to the less storage in computation, derivative--free descent method, which meansthe search direction used does not involye the Jacobian matrix of F, is popular infinding solutions of nonlinear complementarity Problems. We briefly view som…     

A Globally Derivative-Free Descent Method for Nonlinear Complementarity Problems

Based on a class of functions, which generalize the squared Fischer-Burmeister NCP function and have many desirable properties as the latter function has, we reformulate nonlinear complementarity problem (NCP for short) as an equivalent unconstrained optimization problem, for which we propose a derivative-free descent method in monotone case. We show its global convergence under some mild conditions. If $F$, the function involved in NCP, is $R_0$-function, the optimization problems has bounded level sets. A local property of the merit function is discussed. Finally,we report some numerical results.     

A LQP BASED INTERIOR PREDICTION-CORRECTION METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system of nonlinear equations （LQP system）. This paper presents a practical LQP method-based prediction-correction method for NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed restriction, and the new iterate （the corrector） is computed directly by an explicit formula derived from the original LQP method. The implementations are very easy to be carried out. Global convergence of the method is proved under the same mild assumptions as the original LQP method. Finally, numerical results for traffic equilibrium problems are provided to verify that the method is effective for some practical problems.     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.