A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

A Newton-type method for positive-semidefinite linear complementarity problems

The paper presents a damped and perturbed Newton-type method for solving linear complementarity problems with positive-semidefinite matricesM. In particular, the following properties hold: all occurring subproblems are linear equations; each subproblem is uniquely solvable without any assumption; every accumulation point generated by the method solves the linear complementarity problem. The additional property ofM to be an R₀-matrix is sufficient, but not necessary, for the boundedness of the iterates. Provided thatM is positive definite on a certain subspace, the method converges Q-quadratically.The author would like to thank the anonymous referees and Dr. K. Schönefeld for their valuable comments and suggestions. He is also grateful to Prof. Dr. J. W. Schmidt for his continuous interest in this study.     

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.     

A preconditioning proximal newton method for nondifferentiable convex optimization

We propose a proximal Newton method for solving nondifferentiable convex optimization. This method combines the generalized Newton method with Rockafellar’s proximal point algorithm. At each step, the proximal point is found approximately and the regularization matrix is preconditioned to overcome inexactness of this approximation. We show that such a preconditioning is possible within some accuracy and the second-order differentiability properties of the Moreau-Yosida regularization are invariant with respect to this preconditioning. Based upon these, superlinear convergence is established under a semismoothness condition. This work is supported by the Australian Research Council.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

A new Filter-Levenberg-Marquardt method with disturbance for solving nonlinear complementarity problems

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₂-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 with the disturbance . Under the assumption that the lever set of the problem is compact, we prove its global convergence.     

Integral global optimization method for solution of nonlinear complementarity problems

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.     

A projection-filter method for solving nonlinear complementarity problems

The Josephy-Newton method attacks nonlinear complementarity problems which consists of solving, possibly inexactly, a sequence of linear complementarity problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. Utilizing the filter method, we presented a new globalization strategy for this Newton method applied to nonlinear complementarity problem without any merit function. The strategy is based on the projection-proximal point and filter methodology. Our linesearch procedure uses the regularized Newton direction to force global convergence by means of a projection step which reduces the distance to the solution of the problem. The resulting algorithm is globally convergent to a solution. Under natural assumptions, locally superlinear rate of convergence was established.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

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.     

New third-order method for solving systems of nonlinear equations

In this paper, we present a new iterative method to solve systems of nonlinear equations. The main advantages of the method are: it has order three, it does not require the evaluation of any second or higher order Fréchet derivative and it permits that the Jacobian be singular at some points. Thus, the problem due to the fact that the Jacobian is numerically singular is solved. The third order convergence in both one dimension and for the multivariate case are given. The numerical results illustrate the efficiency of the method for systems of nonlinear equations.      

A hybrid inexact Logarithmic-Quadratic Proximal method for nonlinear complementarity problems

Inspired by the Logarithmic-Quadratic Proximal method [A. Auslender, M. Teboulle, S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl. 12 (1999) 31-40], we present a new prediction-correction method for solving the nonlinear complementarity problems. In our method, an intermediate point is produced by approximately solving a nonlinear equation system based on the Logarithmic-Quadratic Proximal method; and the new iterate is obtained by convex combination of the previous point and the one generated by the improved extragradient method at each iteration. The proposed method allows for constant relative errors and this yields a more practical Logarithmic-Quadratic Proximal type method. The global convergence is established under mild conditions. Preliminary numerical results indicate that the method is effective for large-scale nonlinear complementarity problems.     

Inexact algorithm for continuous complementarity problems on measure spaces

In this paper, we discuss a type of complementarity problem posed over a measure space. We give some conditions under which there exists a solution for the problem and work toward a new inexact algorithm for its solution. A general convergence proof for this algorithm is given and the advantage of using this approach is discussed.The authors thank the referees for their helpful suggestions and comments.     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

On certain two-sided analogues of Newton’s method for solving nonlinear eigenvalue problems

Iterative algorithms for finding two-sided approximations to the eigenvalues of nonlinear algebraic eigenvalue problems are examined. These algorithms use an efficient numerical procedure for calculating the first and second derivatives of the determinant of the problem. Computational aspects of this procedure as applied to finding all the eigenvalues from a given complex-plane domain in a nonlinear eigenvalue problem are analyzed. The efficiency of the algorithms is demonstrated using some model problems.     

An improved LQP-based method for solving nonlinear complementarity problems

The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported to verify the theoretical assertions.     

Feasible descent algorithms for mixed complementarity problems

In this paper we consider a general algorithmic framework for solving nonlinear mixed complementarity problems. The main features of this framework are: (a) it is well-defined for an arbitrary mixed complementarity problem, (b) it generates only feasible iterates, (c) it has a strong global convergence theory, and (d) it is locally fast convergent under standard regularity assumptions. This framework is applied to the PATH solver in order to show viability of the approach. Numerical results for an appropriate modification of the PATH solver indicate that this framework leads to substantial computational improvements. Received April 9, 1998 / Revised version received November 23, 1998?Published online March 16, 1999     

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

Improving the convergence of non-interior point algorithms for nonlinear complementarity problems

Recently, based upon the Chen-Harker-Kanzow-Smale smoothing function and the trajectory and the neighbourhood techniques, Hotta and Yoshise proposed a noninterior point algorithm for solving the nonlinear complementarity problem. Their algorithm is globally convergent under a relatively mild condition. In this paper, we modify their algorithm and combine it with the superlinear convergence theory for nonlinear equations. We provide a globally linearly convergent result for a slightly updated version of the Hotta-Yoshise algorithm and show that a further modified Hotta-Yoshise algorithm is globally and superlinearly convergent, with a convergence -order , under suitable conditions, where is an additional parameter.