The prediction–correction approach to nonlinear complementarity problems

This paper presents a prediction–correction approach to solving the nonlinear complementarity problem (NCP). Each iteration of the new method consists of a prediction and a correction. The predictor is produced by an inexact Logarithmic-Quadratic Proximal method; and then it is corrected by the Proximal Point Algorithm. Convergence of the new method is proved under mild assumptions. Comparison to existing methods shows the superiority of the new method. Numerical experiments including the application to traffic equilibrium problems demonstrate that the new method is attractive in practice.     

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.     

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.     

An LQP Method for Pseudomonotone Variational Inequalities

In this paper, we proposed a modified Logarithmic-Quadratic Proximal (LQP) method [Auslender et al.: Comput. Optim. Appl. 12, 31–40 (1999)] for solving variational inequalities problems. We solved the problem approximately, with constructive accuracy criterion. We show that the method is globally convergence under that the operator is pseudomonotone which is weaker than the monotonicity and the solution set is nonempty. Some preliminary computational results are given.The author was supported by the NSFC grants Nos: 70571033 and 10571083.     

对广义互补问题迭代方法收敛性分析的统一途径

1．介绍非线性互补问题，记作NCP（F0）；是指求XRn使得其中的：RNCP有各种不同形式的推广．例如，一种广泛的互补问题，记作NCP（F1，F2，…，FN），是指求xRn使得其中马：＊”＋＊”，马杜）是马（x）的第7个分量·NCP（凡）的发展及其应用在数学规划领域己经有很长的历...     

Finding solutions of implicit complementarity problems by isotonicity of the metric projection

Isac and Németh [G. Isac and A. B. Németh, Projection method, isotone projection cones and the complementarity problem, J. Math. Anal. App., 153, 258-275(1990)] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this paper, the notion of *-isotone projection cones is employed and an iterative algorithm is presented in connection with an implicit complementarity problem on *-isotone projection cones. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by *-isotone projection cones. The question of finding nonzero solutions of these problems is also studied.     

A class of asynchronous parallel nonlinear accelerated overrelaxation methods for the nonlinear complementarity problems

In accordance with the principle of using sufficiently the delayed information, and by making use of the nonlinear multisplitting and the nonlinear relaxation techniques, we present in this paper a class of asynchronous parallel nonlinear multisplitting accelerated overrelaxation (AOR) methods for solving the large sparse nonlinear complementarity problems on the high-speed MIMD multiprocessor systems. These new methods, in particular, include the so-called asynchronous parallel nonlinear multisplitting AOR-Newton method, the asynchronous parallel nonlinear multisplitting AOR-chord method and the asynchronous parallel nonlinear multisplitting AOR-Steffensen method. Under suitable constraints on the nonlinear multisplitting and the relaxation parameters, we establish the local convergence theory of this class of new methods when the Jacobi matrix of the involved nonlinear mapping at the solution point of the nonlinear complementarity problem is an H-matrix.     

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 Logarithmic-Quadratic Proximal Prediction-Correction Method for Structured Monotone Variational Inequalities

Inspired by the Logarithmic-Quadratic Proximal (LQP) method for variational inequalities, we present a prediction-correction method for structured monotone variational inequalities. Each iteration of the new method consists of a prediction and a correction. Both the predictor and the corrector are obtained easily with tiny computational load. In particular, the LQP system that appears in the prediction is approximately solved under significantly relaxed inexactness restriction. Global convergence of the new method is proved under mild assumptions. In addition, we present a self-adaptive version of the new method that leads to easier implementations. Preliminary numerical experiments for traffic equilibrium problems indicate that the new method is effectively applicable in practice. Presented at the 6th International conference on Optimization: Techniques and Applications, Ballarat Australia, December 9–11, 2004. This author was supported by NSFC Grant 10571083, the MOEC grant 20020284027 and Jiangsu NSF grant BK2002075     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this article an iterative algorithm is studied in connection with an implicit complementarity problem. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by isotone projection cones, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

一类弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法

本文提出一类求解弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法，并给出了系数矩阵为H₊-矩阵时该方法的收敛性分析.数值实验表明新方法是有效的.     

Generalized mildly nonlinear complementarity problems for fuzzy mappings

In this paper, we introduce and study a new class of generalized mildly nonlinear complementarity problems for fuzzy mappings. We use the change of variables technique to establish the equivalence between the generalized mildly nonlinear complementarity problems and the Wiener-Hopf equations. This equivalence is used to suggest and analyze a number of iterative algorithm for solving the generalized mildly nonlinear complementarity problems.     

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.     

Unconstrained minimization approaches to nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as unconstrained minimization problems by introducing merit functions. Under some assumptions, the solution set of the nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. These results were presented by Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow. In this note, we generalize some results of Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow to the case where the considered function is only directionally differentiable. Some results are strengthened in the smooth case. For example, it is shown that the strong monotonicity condition can be replaced by the P-uniform property for ensuring a stationary point of the reformulated unconstrained minimization problems to be a solution of the nonlinear complementarity problem. We also present a descent algorithm for solving the nonlinear complementarity problem in the smooth case. Any accumulation point generated by this algorithm is proved to be a solution of the nonlinear complementarity under the monotonicity condition.     

A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China.     

Global Convergence of a Smooth Approximation Method for Mathematical Programs with Complementarity Constraints

A new smoothing approach was given for solving the mathematical programs with complementarity constraints (MPCC) by using the aggregation technique. As the smoothing parameter tends to zero, if the KKT point sequence generated from the smoothed problems satisfies the second-order necessary condition, then any accumulation point of the sequence is a B-stationary point of MPCC if the linear independence constraint qualification (LICQ) and the upper level strict complementarity (ULSC) condition hold at the limit point. The ULSC condition is weaker than the lower level strict complementarity (LLSC) condition generally used in the literatures. Moreover, the method can be easily extended to the mathematical programs with general vertical complementarity constraints.     

A Gauss-Seidel iteration method for nonlinear variational inequality problems over rectangles

This paper presents a simple yet practically useful Gauss-Seidel iterative method for solving a class of nonlinear variational inequality problems over rectangles and of nonlinear complementarity problems. This scheme is a nonlinear generalization of a robust iterative method for linear complementarity problems developed by Mangasarian. Global convergence is presented for problems with Z-functions. It is noted that the suggested method can be viewed as a specific case of a class of linear approximation methods studied by Pang and others.     

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.     

求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.