In this paper, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required...In this paper, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration, thus avoiding the need for solving a quadratic subproblem with a trust region bound. Under some conditions, it is proven that this algorithm is globally and locally superlinear convergent. The limited numerical examples show its efficiency.展开更多
We applied the projection and contraction method to nonlinear complementarity problem (NCP). Moveover, we proposed an inexact implicit method for (NCP) and proved the convergence.
In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global c...In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global convergence on the algorithms. Some numerical results are also reported.展开更多
A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theore...A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.展开更多
A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization pro...A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.展开更多
By using a smoothing function,the P nonlinear complementarity problem(P NCP)can be reformulated as a parameterized smooth equation.A Newton method is proposed to solve this equation.The iteration sequence generated by...By using a smoothing function,the P nonlinear complementarity problem(P NCP)can be reformulated as a parameterized smooth equation.A Newton method is proposed to solve this equation.The iteration sequence generated by the proposed algorithm is bounded and this algorithm is proved to be globally convergent under an assumption that the P NCP has a nonempty solution set.This assumption is weaker than the ones used in most existing smoothing algorithms.In particular,the solution obtained by the proposed algorithm is shown to be a maximally complementary solution of the P NCP without any additional assumption.展开更多
In this paper,we present a modulus-based multisplitting iteration method based on multisplitting of the system matrix for a class of weakly nonlinear complementarity problem.And we prove the convergence of the method ...In this paper,we present a modulus-based multisplitting iteration method based on multisplitting of the system matrix for a class of weakly nonlinear complementarity problem.And we prove the convergence of the method when the system matrix is an H_(+)-matrix.Finally,we give two numerical examples.展开更多
In this paper, we present a new successive approximation damped Newton method for the nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we obtain the global conv...In this paper, we present a new successive approximation damped Newton method for the nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we obtain the global convergence result of the proposed algorithms. Some numerical results are also reported.展开更多
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 fo...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 the P0 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 the P0 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.展开更多
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 ...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.展开更多
The nonlinear complementarity problem can be reformulated as a nonsmooth equation. In this paper we propose a new smoothing Newton algorithm for the solution of the nonlinear complementarity problem by constructing a ...The nonlinear complementarity problem can be reformulated as a nonsmooth equation. In this paper we propose a new smoothing Newton algorithm for the solution of the nonlinear complementarity problem by constructing a new smoothing approximation function. Global and local superlinear convergence results of the algorithm are obtained under suitable conditions. Numerical experiments confirm the good theoretical properties of the algorithm.展开更多
We propose the two-step modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problems.The corresponding convergence the-ory is established when the system matrix is an H_(+)-matrix...We propose the two-step modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problems.The corresponding convergence the-ory is established when the system matrix is an H_(+)-matrix.Theoretical analysis gives the choice of parameter matrix involved based on the H-compatible splitting of the sys-tem matrix.Moreover,in actual implementation,the choices of iterative parameters for two-step modulus-based accelerated overrelaxation methods are studied.Numeri-cal experiments show that the method is efficient and further verify the convergence theorems.展开更多
In this work, null space techniques are employed to tackle nonlinear complementarity problems (NCPs). NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The...In this work, null space techniques are employed to tackle nonlinear complementarity problems (NCPs). NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.展开更多
In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.(k) nonlinear complementarity problem (NCP), which are based on a class of kernel functions investigated by Bai et a...In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.(k) 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.(n) 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.展开更多
We consider several synchronous and asynchronous multisplitting iteration schemes for solving a class of nonlinear complementarity problems with the system matrix being an H-matrix. We establish the convergence theore...We consider several synchronous and asynchronous multisplitting iteration schemes for solving a class of nonlinear complementarity problems with the system matrix being an H-matrix. We establish the convergence theorems for the schemes. The numerical experiments show that the schemes are efficient for solving the class of nonlinear complementarity problems.展开更多
In this paper, a new Schwarz method called restricted additive Schwarz method (RAS) is presented and analyzed for a kind of nonlinear complementarity problem (NCP). The method is proved to be convergent by using w...In this paper, a new Schwarz method called restricted additive Schwarz method (RAS) is presented and analyzed for a kind of nonlinear complementarity problem (NCP). The method is proved to be convergent by using weighted maximum norm. Besides, the effect of overlap on RAS is also considered. Some preliminary numerical results are reported to compare the performance of RAS and other known methods for NCP.展开更多
In this paper, we propose an inexact damped Newtonmethod for solving nonlinear complementarity problems based on the equivalent B differentiable equations.Global convergence and locally quadratic convergence are ...In this paper, we propose an inexact damped Newtonmethod for solving nonlinear complementarity problems based on the equivalent B differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.展开更多
Recently, Ye et al.[2] proved that the predictor-corrector method proposed by Mizuno et al[1] maintains O( L)-iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild con...Recently, Ye et al.[2] proved that the predictor-corrector method proposed by Mizuno et al[1] maintains O( L)-iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a ( log(1/ε))-iteration complexity while maintaining the quadratic asymptotic convergence.展开更多
In this paper,the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints,and a SQP algorithm for this reformulation based on a damped Gauss Newton type method is ...In this paper,the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints,and a SQP algorithm for this reformulation based on a damped Gauss Newton type method is presented.It is shown that the algorithm is globally and locally superlinearly (quadratically) convergent without the assumption of monotonicity.展开更多
A class of strongly nonlinear implicit complementarity problems for set-valued mappings in Hilbert spaces is studied,Thereupon a new existence theorem is established and proved to be a solution to that kind of problems.
基金Supported by the Natural Science Foundation of Hainan Province(80552)
文摘In this paper, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration, thus avoiding the need for solving a quadratic subproblem with a trust region bound. Under some conditions, it is proven that this algorithm is globally and locally superlinear convergent. The limited numerical examples show its efficiency.
基金Supported by the National Natural Science Foundation of China (No. 202001036)
文摘We applied the projection and contraction method to nonlinear complementarity problem (NCP). Moveover, we proposed an inexact implicit method for (NCP) and proved the convergence.
文摘In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global convergence on the algorithms. Some numerical results are also reported.
文摘A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.10571137,10771162)
文摘A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.
基金Supported by China Postdoctoral Science Foundation(No.20060390660)Science and Technology Development Plan of Tianjin(No.06YFGZGX05600)+1 种基金Scientific Research Foundation of Liu Hui Center for Applied MathematicsNankai University-Tianjin University.
文摘By using a smoothing function,the P nonlinear complementarity problem(P NCP)can be reformulated as a parameterized smooth equation.A Newton method is proposed to solve this equation.The iteration sequence generated by the proposed algorithm is bounded and this algorithm is proved to be globally convergent under an assumption that the P NCP has a nonempty solution set.This assumption is weaker than the ones used in most existing smoothing algorithms.In particular,the solution obtained by the proposed algorithm is shown to be a maximally complementary solution of the P NCP without any additional assumption.
基金This work was supported by the National Natural Science Foundation of China(Grant No.11771275)the Science and Technology Program of Shandong Universities(No.J16LI04).
文摘In this paper,we present a modulus-based multisplitting iteration method based on multisplitting of the system matrix for a class of weakly nonlinear complementarity problem.And we prove the convergence of the method when the system matrix is an H_(+)-matrix.Finally,we give two numerical examples.
文摘In this paper, we present a new successive approximation damped Newton method for the nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we obtain the global convergence result of the proposed algorithms. Some numerical results are also reported.
基金the National Natural Science Foundation of China (Grant Nos. 19871016 and 19731001).
文摘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 the P0 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 the P0 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.
文摘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.
基金This work is supported by the National Natural Science Foundation of China.
文摘The nonlinear complementarity problem can be reformulated as a nonsmooth equation. In this paper we propose a new smoothing Newton algorithm for the solution of the nonlinear complementarity problem by constructing a new smoothing approximation function. Global and local superlinear convergence results of the algorithm are obtained under suitable conditions. Numerical experiments confirm the good theoretical properties of the algorithm.
基金This work was supported by the National Natural Science Foundation of China(No.11271289,11701221)the Fundamental Research Funds for the Central Universities.
文摘We propose the two-step modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problems.The corresponding convergence the-ory is established when the system matrix is an H_(+)-matrix.Theoretical analysis gives the choice of parameter matrix involved based on the H-compatible splitting of the sys-tem matrix.Moreover,in actual implementation,the choices of iterative parameters for two-step modulus-based accelerated overrelaxation methods are studied.Numeri-cal experiments show that the method is efficient and further verify the convergence theorems.
基金Supported by the National Natural Science Foundation of China(No.10501019)the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry
文摘In this work, null space techniques are employed to tackle nonlinear complementarity problems (NCPs). NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.
基金Supported by Natural Science Foundation of Hubei Province (Grant No. 2008CDZ047)Acknowledgements Thanks my supervisor Prof. M. W. Zhang for long-last guidance during the course of study.
文摘In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.(k) 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.(n) 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.
基金The work was done in the state key laboratory of advanced design and manufacture for vehicle body of Hunan university973 national project of China granted 2004CB719402the National Natural Science Foundation of China(No.10371035)
文摘We consider several synchronous and asynchronous multisplitting iteration schemes for solving a class of nonlinear complementarity problems with the system matrix being an H-matrix. We establish the convergence theorems for the schemes. The numerical experiments show that the schemes are efficient for solving the class of nonlinear complementarity problems.
基金The authors would like to thank the anonymous referees for their valuable suggestions and comments, which improved the paper greatly. The work was supported by Natural Science Foundation of Guangdong Province,China (Grant No.S2012040007993) and Educational Commission of Guangdong Province, China (Grant No. 2012LYM_0122), NNSF of China (Grand No.11126147), NNSF of China (Grand No.11201197) and NNSF of China (Grand No.11271069).
文摘In this paper, a new Schwarz method called restricted additive Schwarz method (RAS) is presented and analyzed for a kind of nonlinear complementarity problem (NCP). The method is proved to be convergent by using weighted maximum norm. Besides, the effect of overlap on RAS is also considered. Some preliminary numerical results are reported to compare the performance of RAS and other known methods for NCP.
文摘In this paper, we propose an inexact damped Newtonmethod for solving nonlinear complementarity problems based on the equivalent B differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.
文摘Recently, Ye et al.[2] proved that the predictor-corrector method proposed by Mizuno et al[1] maintains O( L)-iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a ( log(1/ε))-iteration complexity while maintaining the quadratic asymptotic convergence.
基金Supported by the National Natural Science Foundation of China(1 9971 0 0 2 )
文摘In this paper,the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints,and a SQP algorithm for this reformulation based on a damped Gauss Newton type method is presented.It is shown that the algorithm is globally and locally superlinearly (quadratically) convergent without the assumption of monotonicity.
文摘A class of strongly nonlinear implicit complementarity problems for set-valued mappings in Hilbert spaces is studied,Thereupon a new existence theorem is established and proved to be a solution to that kind of problems.