In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.1...In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.134:108344,2022).The convergence analysis of the proposed method is established,which can improve the existing results.Numerical examples show that the proposed method is efficient with the two-step technique.展开更多
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.展开更多
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 (ⅲ).展开更多
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.展开更多
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,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.展开更多
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.展开更多
In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty...In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty set. We propose the notion of the p-robust counterpart and the p-robust solution of uncertain linear complementarity problems. We discuss uncertain linear complementarity problems with three different uncertainty sets, respectively, including an unknown-but-bounded uncertainty set, an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set, and present some sufficient and necessary （or sufficient） conditions which p-robust solutions satisfy. Some special eases are investigated in this paper.展开更多
In this paper,a wide-neighborhood predictor-corrector feasible interiorpoint algorithm for linear complementarity problems is proposed.The algorithm is based on using the classical affine scaling direction as a part i...In this paper,a wide-neighborhood predictor-corrector feasible interiorpoint algorithm for linear complementarity problems is proposed.The algorithm is based on using the classical affine scaling direction as a part in a corrector step,not in a predictor step.The convergence analysis of the algorithm is shown,and it is proved that the algorithm has the polynomial complexity O(√n logε^(−1))which coincides with the best known iteration bound for this class of mathematical problems.The numerical results indicate the efficiency of the algorithm.展开更多
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.展开更多
Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator...Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary conditions of T having the GUS-property.Our approach is based on properties of the Jordan product and the technique from functional analysis,which is different from the pioneer works given by Gowda and Sznajder(2007) in the case of finite-dimensional spaces.展开更多
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.展开更多
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.展开更多
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.展开更多
Judice and Pires developed in recent years principal pivoting methods for the solving of the so-called box linear complementarity problems(BLCPs)where the constraint matrices are restrictedly supposed to be of P-matri...Judice and Pires developed in recent years principal pivoting methods for the solving of the so-called box linear complementarity problems(BLCPs)where the constraint matrices are restrictedly supposed to be of P-matrices.This paper aims at presenting a new principal pivoting scheme for BLCPs where the constraint matricesare loosely supposed to be row sufficient.This scheme can be applied to the solving of convex quadratic programs subject to linear constraints and arbitrary upper and lower bound constraints on variables.展开更多
Judice and Pires developed in recent years principal pivoting methods for the solving of the so called box linear complementarity problems (BLCPs) where the constraint matrices are restrictedly supposed to be of P ...Judice and Pires developed in recent years principal pivoting methods for the solving of the so called box linear complementarity problems (BLCPs) where the constraint matrices are restrictedly supposed to be of P matrices. This paper aims at presenting a new principal pivoting scheme for BLCPs where the constraint matrices are loosely supposed to be row sufficient.This scheme can be applied to the solving of convex quadratic programs subject to linear constraints and arbitrary upper and lower bound constraints on variables.展开更多
Presents a study of the numerical behaviors of the relaxed asynchronous multisplitting methods for linear complementarity problems by solving typical problems from practical applications on a real multiprocessor syste...Presents a study of the numerical behaviors of the relaxed asynchronous multisplitting methods for linear complementarity problems by solving typical problems from practical applications on a real multiprocessor system. Description of the tested problems and computing environment used in the computations; Description of the asynchronous multisplitting unsymmetric accelerated overrelaxation method; Discussion of results.展开更多
Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not ...Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not only includes all the existing relaxation methods for the linear complementarity problems,but also yields a lot of novel ones in the sense of multisplitting.We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H matrix with positive diagonal elements.展开更多
基金supported by the Scientific Computing Research Innovation Team of Guangdong Province(no.2021KCXTD052)the Science and Technology Development Fund,Macao SAR(no.0096/2022/A,0151/2022/A)+3 种基金University of Macao(no.MYRG2020-00035-FST,MYRG2022-00076-FST)the Guangdong Key Construction Discipline Research Capacity Enhancement Project(no.2022ZDJS049)Technology Planning Project of Shaoguan(no.210716094530390)the ScienceFoundation of Shaoguan University(no.SZ2020KJ01).
文摘In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.134:108344,2022).The convergence analysis of the proposed method is established,which can improve the existing results.Numerical examples show that the proposed method is efficient with the two-step technique.
文摘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.
文摘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 (ⅲ).
文摘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.
基金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.
基金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 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.
基金Supported by the National Natural Science Foundation of China(No.10671010,10871144 and 10671145)
文摘In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty set. We propose the notion of the p-robust counterpart and the p-robust solution of uncertain linear complementarity problems. We discuss uncertain linear complementarity problems with three different uncertainty sets, respectively, including an unknown-but-bounded uncertainty set, an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set, and present some sufficient and necessary （or sufficient） conditions which p-robust solutions satisfy. Some special eases are investigated in this paper.
文摘In this paper,a wide-neighborhood predictor-corrector feasible interiorpoint algorithm for linear complementarity problems is proposed.The algorithm is based on using the classical affine scaling direction as a part in a corrector step,not in a predictor step.The convergence analysis of the algorithm is shown,and it is proved that the algorithm has the polynomial complexity O(√n logε^(−1))which coincides with the best known iteration bound for this class of mathematical problems.The numerical results indicate the efficiency of the algorithm.
基金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.
基金supported by National Natural Science Foundation of China(Grant No. 10871144)the Natural Science Foundation of Tianjin Province (Grant No. 07JCYBJC05200)
文摘Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary conditions of T having the GUS-property.Our approach is based on properties of the Jordan product and the technique from functional analysis,which is different from the pioneer works given by Gowda and Sznajder(2007) in the case of finite-dimensional spaces.
文摘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.
文摘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.
文摘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.
文摘Judice and Pires developed in recent years principal pivoting methods for the solving of the so-called box linear complementarity problems(BLCPs)where the constraint matrices are restrictedly supposed to be of P-matrices.This paper aims at presenting a new principal pivoting scheme for BLCPs where the constraint matricesare loosely supposed to be row sufficient.This scheme can be applied to the solving of convex quadratic programs subject to linear constraints and arbitrary upper and lower bound constraints on variables.
文摘Judice and Pires developed in recent years principal pivoting methods for the solving of the so called box linear complementarity problems (BLCPs) where the constraint matrices are restrictedly supposed to be of P matrices. This paper aims at presenting a new principal pivoting scheme for BLCPs where the constraint matrices are loosely supposed to be row sufficient.This scheme can be applied to the solving of convex quadratic programs subject to linear constraints and arbitrary upper and lower bound constraints on variables.
基金the Special Funds for Major State Basic Research Projects G1999032803Supported by the National Natural Science Foundation of China (19601036).
文摘Presents a study of the numerical behaviors of the relaxed asynchronous multisplitting methods for linear complementarity problems by solving typical problems from practical applications on a real multiprocessor system. Description of the tested problems and computing environment used in the computations; Description of the asynchronous multisplitting unsymmetric accelerated overrelaxation method; Discussion of results.
文摘Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not only includes all the existing relaxation methods for the linear complementarity problems,but also yields a lot of novel ones in the sense of multisplitting.We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H matrix with positive diagonal elements.
