This paper addresses the generalized linear complementarity problem (GLCP) over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over...This paper addresses the generalized linear complementarity problem (GLCP) over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over a closed polyhedral cone, and then propose a new type of method to solve the GLCP based on the error bound estimation. The global and R-linear convergence rate is established. The numerical experiments show the efficiency of the method.展开更多
In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient proje...In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient projection method is given for solving the stochastic generalized linear complementarity problems. The global convergence of the conjugate gradient projection method is proved and the related numerical results are also reported.展开更多
Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm ...Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm from an infeasible-starting-point for a class of non-monotone linear complementarity problem. Its polynomial complexity is analyzed. After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region. Key words linear complementarity problems - infeasible-starting-point - P-matrix - potential function CLC number O 221 Foundation item: Supported by the National Natural Science Foundation of China (70371032) and the Doctoral Educational Foundation of China of the Ministry of Education (20020486035)Biography: Wang Yan-jin (1976-), male, Ph. D candidate, research direction: optimal theory and method.展开更多
A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solve...A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).展开更多
A polynomial interior-point algorithm is presented for monotone linear complementarity problem (MLCP) based on a class of kernel functions with the general barrier term, which are called general kernel functions. Un...A polynomial interior-point algorithm is presented for monotone linear complementarity problem (MLCP) based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.展开更多
A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of...A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of X-row sufficiency or X-colunm monotonicity is proved. As a result, a sufficient condition for existence and boundedness of solution to the XLCP are obtained.展开更多
The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by ...The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is designed for solving the ELCP. The proposed algorithm is proved to be globally convergent under suitable assumptions.展开更多
In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix spl...In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix splitting iteration method,for solving the linear complementarity problems whose coefficient matrix in R^(n×n)is large sparse and positive definite.From the convergence analysis,it is appreciable to see that the proposed method will converge to its accurate solution under appropriate conditions.Numerical examples demonstrate that the presented method precede to other methods in practical implementation.展开更多
It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_*(κ) linear complementarity problems.This paper presents an extension of t...It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_*(κ) linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra's second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O(4κ + 3)√14κ + 5 nlog(x0)Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.展开更多
In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear ...In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear growth term to derive the search direction,and by introducing new technical results and selecting suitable parameters,we prove that the iteration bound of the algorithm is as good as best-known polynomial complexity of interior-point methods.Furthermore,numerical results illustrate the efficiency of the proposed method.展开更多
Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made...Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made about the rate of convergence. In this paper, we develop a modified globally linearly convergent PC method for linear complementarity problems. Both the method and the convergence proofs are very simple. The method can also be used to solve some linear variational inequalities. Several computational experiments are presented to indicate that the method is surprising good for solving some known difficult problems.展开更多
Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive d...Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive diagonal elements. Moreover, block and multi-parameter variants of the new methods, together with their convergence properties, are investigated in detail. Numerical results show that these new methods can achieve high parallel efficiency for solving the large sparse linear complementarity problems on multiprocessor systems.展开更多
Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting met...Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting method; Information on the convergence theories; Details on the parallel chaotic multisplitting relaxation methods.展开更多
In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P.(a)-linear complementari...In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P.(a)-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.展开更多
Linear complementarity problems have drawn considerable attention in recent years due to their wide applications.In this article,we introduce the two-step two-sweep modulus-based matrix splitting(TSTM)iteration method...Linear complementarity problems have drawn considerable attention in recent years due to their wide applications.In this article,we introduce the two-step two-sweep modulus-based matrix splitting(TSTM)iteration method and two-sweep modulus-based matrix splitting type II(TM II)iteration method which are a combination of the two-step modulus-based method and the two-sweep modulus-based method,as two more effective ways to solve the linear complementarity problems.The convergence behavior of these methods is discussed when the system matrix is either a positive-definite or an H+-matrix.Finally,numerical experiments are given to show the efficiency of our proposed methods.展开更多
As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence resu...As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence result is presented.Numerical experiments show that the proposed method is efficient and outperforms the modulus-based matrix splitting iteration method.展开更多
In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used b...In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and theμ-center of the problem.We derive the complexity analysis for the algorithm,both with large and small updates.展开更多
This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O(n log...This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O(n log(n /ε))iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.展开更多
We present an algebraic version of an iterative multigrid method for obstacle problems,called projected algebraic multigrid(PAMG)here.We show that classical algebraic multigrid algorithms can easily be extended to dea...We present an algebraic version of an iterative multigrid method for obstacle problems,called projected algebraic multigrid(PAMG)here.We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem.This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising,for example,in financial engineering.展开更多
Interior-Point Methods(IPMs)not only are the most effective methods in practice but also have polynomial-time complexity.Many researchers have proposed IPMs for Linear Optimization(LO)and achieved plentiful results.In...Interior-Point Methods(IPMs)not only are the most effective methods in practice but also have polynomial-time complexity.Many researchers have proposed IPMs for Linear Optimization(LO)and achieved plentiful results.In many cases these methods were extendable for LO to Linear Complementarity Problems(LCPs)successfully.In this paper,motivated by the complexity results for linear optimization based on the study of H.Mansouri et al.(Mansouri and Zangiabadi in J.Optim.62(2):285–297,2013),we extend their idea for LO to LCP.The proposed algorithm requires two types of full-Newton steps are called,feasibility steps and(ordinary)centering steps,respectively.At each iteration both feasibility and optimality are reduced exactly at the same rate.In each iteration of the algorithm we use the largest possible barrier parameter valueθwhich lies between the two values 117n and 113n,this makes the algorithm faster convergent for problems having a strictly complementarity solution.展开更多
基金supported by National Natural Science Foundation of China (No. 10771120)
文摘This paper addresses the generalized linear complementarity problem (GLCP) over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over a closed polyhedral cone, and then propose a new type of method to solve the GLCP based on the error bound estimation. The global and R-linear convergence rate is established. The numerical experiments show the efficiency of the method.
文摘In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient projection method is given for solving the stochastic generalized linear complementarity problems. The global convergence of the conjugate gradient projection method is proved and the related numerical results are also reported.
文摘Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm from an infeasible-starting-point for a class of non-monotone linear complementarity problem. Its polynomial complexity is analyzed. After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region. Key words linear complementarity problems - infeasible-starting-point - P-matrix - potential function CLC number O 221 Foundation item: Supported by the National Natural Science Foundation of China (70371032) and the Doctoral Educational Foundation of China of the Ministry of Education (20020486035)Biography: Wang Yan-jin (1976-), male, Ph. D candidate, research direction: optimal theory and method.
文摘A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).
基金supported by the National Natural Science Foundation of China (Grant No.10771133)the Shanghai Pujiang Program (Grant No.06PJ14039)
文摘A polynomial interior-point algorithm is presented for monotone linear complementarity problem (MLCP) based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.
文摘A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of X-row sufficiency or X-colunm monotonicity is proved. As a result, a sufficient condition for existence and boundedness of solution to the XLCP are obtained.
基金Supported by the NNSF of China(11071041, 11171257)
文摘The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is designed for solving the ELCP. The proposed algorithm is proved to be globally convergent under suitable assumptions.
基金This work is supported by the National Natural Science Foundation of China with No.11461046the Natural Science Foundation of Jiangxi Province of China with Nos.20181ACB20001 and 20161ACB21005.
文摘In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix splitting iteration method,for solving the linear complementarity problems whose coefficient matrix in R^(n×n)is large sparse and positive definite.From the convergence analysis,it is appreciable to see that the proposed method will converge to its accurate solution under appropriate conditions.Numerical examples demonstrate that the presented method precede to other methods in practical implementation.
基金supported by the Natural Science Foundation of Hubei Province of China(2008CDZ047)
文摘It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_*(κ) linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra's second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O(4κ + 3)√14κ + 5 nlog(x0)Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.
基金Supported by University Science Research Project of Anhui Province(2023AH052921)Outstanding Youth Talent Project of Anhui Province(gxyq2021254)。
文摘In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear growth term to derive the search direction,and by introducing new technical results and selecting suitable parameters,we prove that the iteration bound of the algorithm is as good as best-known polynomial complexity of interior-point methods.Furthermore,numerical results illustrate the efficiency of the proposed method.
文摘Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made about the rate of convergence. In this paper, we develop a modified globally linearly convergent PC method for linear complementarity problems. Both the method and the convergence proofs are very simple. The method can also be used to solve some linear variational inequalities. Several computational experiments are presented to indicate that the method is surprising good for solving some known difficult problems.
基金Subsidized by The Special Funds For Major State Basic Research Projects G1999032803.
文摘Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive diagonal elements. Moreover, block and multi-parameter variants of the new methods, together with their convergence properties, are investigated in detail. Numerical results show that these new methods can achieve high parallel efficiency for solving the large sparse linear complementarity problems on multiprocessor systems.
基金the National Natural Science Foundation of China (19601036) and Subsidized by the SpecialFunds for Major State Basic Research
文摘Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting method; Information on the convergence theories; Details on the parallel chaotic multisplitting relaxation methods.
基金Supported by a grant from IPM (Grant No. 8890027)
文摘In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P.(a)-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.
文摘Linear complementarity problems have drawn considerable attention in recent years due to their wide applications.In this article,we introduce the two-step two-sweep modulus-based matrix splitting(TSTM)iteration method and two-sweep modulus-based matrix splitting type II(TM II)iteration method which are a combination of the two-step modulus-based method and the two-sweep modulus-based method,as two more effective ways to solve the linear complementarity problems.The convergence behavior of these methods is discussed when the system matrix is either a positive-definite or an H+-matrix.Finally,numerical experiments are given to show the efficiency of our proposed methods.
基金This research is supported by National Science Foundation of China(41725017)National Basic Research Program of China under grant number 2014CB845906+1 种基金It is also partially supported by the CAS/CAFEA international partnership Program for creative research teams(No.KZZD-EW-TZ-19 and KZZD-EW-TZ-15)Strategic Priority Research Program of the Chinese Academy of Sciences(No.XDB18010202)。
文摘As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence result is presented.Numerical experiments show that the proposed method is efficient and outperforms the modulus-based matrix splitting iteration method.
文摘In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and theμ-center of the problem.We derive the complexity analysis for the algorithm,both with large and small updates.
基金Supported by the National Natural Science Foundation of China(71071119)
文摘This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O(n log(n /ε))iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.
文摘We present an algebraic version of an iterative multigrid method for obstacle problems,called projected algebraic multigrid(PAMG)here.We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem.This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising,for example,in financial engineering.
基金The authors are indebted to the referees for their careful reading of the manuscript and for their suggestions which helped to improve the paper.The authors also wish to thank Shahrekord University for financial support.
文摘Interior-Point Methods(IPMs)not only are the most effective methods in practice but also have polynomial-time complexity.Many researchers have proposed IPMs for Linear Optimization(LO)and achieved plentiful results.In many cases these methods were extendable for LO to Linear Complementarity Problems(LCPs)successfully.In this paper,motivated by the complexity results for linear optimization based on the study of H.Mansouri et al.(Mansouri and Zangiabadi in J.Optim.62(2):285–297,2013),we extend their idea for LO to LCP.The proposed algorithm requires two types of full-Newton steps are called,feasibility steps and(ordinary)centering steps,respectively.At each iteration both feasibility and optimality are reduced exactly at the same rate.In each iteration of the algorithm we use the largest possible barrier parameter valueθwhich lies between the two values 117n and 113n,this makes the algorithm faster convergent for problems having a strictly complementarity solution.