The non-interior continuation methods for solving theP0 function nonlinear complementarity problem

In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions. Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP ₀ function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP ₀ function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for solving the NCP     

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 continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

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

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

A new smoothing and regularization Newton method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP

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.     

A smoothing Newton method for the second-order cone complementarity problem

In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.     

Properties of a Class of Nonlinear Transformations Over Euclidean Jordan Algebras with Applications to Complementarity Problems

For any function φ from ?^r to ?^r, Tao and Gowda [Math. Oper. Res., 30 (2005), pp. 985–1004] introduced a corresponding nonlinear transformation R_φ over a Euclidean Jordan algebra (which is called a relaxation transformation) and established some useful relations between φ and R_φ. In this paper, we further investigate some interconnections between properties of φ and properties of R_φ, including the properties of continuity, (local) Lipschitz continuity, directional differentiability, (continuous) differentiability, semismoothness, monotonicity, the P₀-property, and the uniform P-property. As an application, we investigate the symmetric cone complementarity problem with a relaxation transformation. A property of the solution set of this class of problems is given. We also investigate a smoothing algorithm for solving this class of problems and show that the algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty.     

Smoothing Newton method for NCP with the identification of degenerate indices

We present a new smoothing Newton method for nonlinear complementarity problems (NCP(F)) by using an NCP function to reformulate the problem to its equivalent form. Compared with most current smoothing methods, our method contains an estimating technique based on the active-set strategy. This technique focuses on the identification of the degenerate set for a solution x^∗ of the NCP(F). The proposed method has the global convergence, each accumulation point is a solution of the problem. The introduction of the active-set strategy effectively reduces the scale of the problem. Under some regularity assumption, the degenerate set can be identified correctly near the solution and local superlinear convergence is obtained as well.     

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

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

A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

A variant smoothing Newton method for P0-NCP based on a new smoothing function

In this paper, we present a new one-step smoothing Newton method proposed for solving the non-linear complementarity problem with _P0$P_0$-function based on a new smoothing NCP$NCP$-function. We adopt a variant merit function. Our algorithm needs only to solve one linear system of equations and perform one line search per iteration. It shows that any accumulation point of the iteration sequence generated by our algorithm is a solution of _P0-NCP$P_0\text{-}NCP$. Furthermore, under the assumption that the solution set is non-empty and bounded, we can guarantee at least one accumulation point of the generated sequence. Numerical experiments show the feasibility and efficiency of the algorithm.     

Strong convergence properties of a modified nonmonotone smoothing algorithm for the SCCP

The smoothing algorithms have been successfully applied to solve the symmetric cone complementarity problem (denoted by SCCP), which in general have the global and local superlinear/quadratic convergence if the solution set of the SCCP is nonempty and bounded. Huang, Hu and Han [Science in China Series A: Mathematics, 52: 833–848, 2009] presented a nonmonotone smoothing algorithm for solving the SCCP, whose global convergence is established by just requiring that the solution set of the SCCP is nonempty. In this paper, we propose a new nonmonotone smoothing algorithm for solving the SCCP by modifying the version of Huang-Hu-Han’s algorithm. We prove that the modified nonmonotone smoothing algorithm not only is globally convergent but also has local superlinear/quadratical convergence if the solution set of the SCCP is nonempty. This convergence result is stronger than those obtained by most smoothing-type algorithms. Finally, some numerical results are reported.     

A Non-Interior Continuation Algorithm for the P0 or P* LCP with Strong Global and Local Convergence Properties

We propose a non-interior continuation algorithm for the solution of the linear complementarity problem (LCP) with a P₀ matrix. The proposed algorithm differentiates itself from the current continuation algorithms by combining good global convergence properties with good local convergence properties under unified conditions. Specifically, it is shown that the proposed algorithm is globally convergent under an assumption which may be satisfied even if the solution set of the LCP is unbounded. Moreover, the algorithm is globally linearly and locally superlinearly convergent under a nonsingularity assumption. If the matrix in the LCP is a P_* matrix, then the above results can be strengthened to include global linear and local quadratic convergence under a strict complementary condition without the nonsingularity assumption.     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

Reformulating the traffic equilibrium problem via a smooth gap function

This paper proposes an alternate formulation of the traffic assignment problem using route flows and the shortest Origin-Destination (OD) travel times as the decision variables. This is accomplished through defining a gap function to convert the Nonlinear Complementarity Problem (NCP) formulation to an equivalent Mathematical Program (MP). This formulation has two advantages:

• 1.(i) it can model assignment problems with general route costs which cannot be accomplished with existing formulations that use link-flow variables
• 2.(ii) the objective function is smooth, convex, and bounded, which permits efficient MP algorithms for its solution.

Two solution approaches are developed to solve the proposed formulation. The first is based on a set of working routes, which are modeled as “known a priori” based on travelers' preferences or interviews. The second approach uses a column generation procedure to generate a new route in each iteration on a need basis. For each approach, we use a Successive Quadratic Programming (SQP) algorithm to solve for the solutions.To show that the formulation is correct, we solve a small example with a general route cost and compare it to the classic traffic equilibrium problem which assumes an additive route cost function. Finally, numerical results for a medium-sized network are provided to demonstrate the feasibility of the solution approach.