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.展开更多
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.展开更多
We present a direct algorithm for solving the vertical generalized linear complementarity problem, first considered by Cottle and Dantzig, when the associated matrix is a vertical block P-matrix. The algorithm converg...We present a direct algorithm for solving the vertical generalized linear complementarity problem, first considered by Cottle and Dantzig, when the associated matrix is a vertical block P-matrix. The algorithm converges to a unique solution in a finite number of steps, without an assumption of nondegeneracy on the given problem. The algorithm is simple, efficient, and easy to implement.展开更多
Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dikin-type affine scaling algorithm for solving the P-*(kappa)-matrix linear complementarity prob...Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dikin-type affine scaling algorithm for solving the P-*(kappa)-matrix linear complementarity problem (LCP). Form using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically O((kappa + 1)root nL) and O((kappa + 1)n(3)L) respectively.展开更多
This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The ma...This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The main iteration consists of a feasibility step and several centrality steps.The authors introduce a specific kernel function instead of the classic logarithmical barrier function to induce the feasibility step,so the analysis of the feasibility step is different from that of Roos' s.This kernel function has a finite value on the boundary.The result of iteration complexity coincides with the currently known best one for infeasible interior-point methods for P_*(κ) LCP.Some numerical results are reported as well.展开更多
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.展开更多
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.展开更多
对P*(κ)线性互补问题提出了一种自适应全-Newton步不可行内点算法.算法是对Mansouri等人(H.Mansouri and M.Pirhaji in Journal of Operations Research Society of China 1:523-536,2013)提出的单调线性互补问题的自适应不可行内点算...对P*(κ)线性互补问题提出了一种自适应全-Newton步不可行内点算法.算法是对Mansouri等人(H.Mansouri and M.Pirhaji in Journal of Operations Research Society of China 1:523-536,2013)提出的单调线性互补问题的自适应不可行内点算法的推广.在算法的每一次迭代中,障碍校正参数θ的取值并不固定,它总在1/(51n(1+4κ)2)和1/(14n(1+4κ)2)之间取满足算法要求的最大值,使得算法快速收敛于问题的一个ε-近似解.展开更多
基金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.
文摘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.
文摘We present a direct algorithm for solving the vertical generalized linear complementarity problem, first considered by Cottle and Dantzig, when the associated matrix is a vertical block P-matrix. The algorithm converges to a unique solution in a finite number of steps, without an assumption of nondegeneracy on the given problem. The algorithm is simple, efficient, and easy to implement.
文摘Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dikin-type affine scaling algorithm for solving the P-*(kappa)-matrix linear complementarity problem (LCP). Form using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically O((kappa + 1)root nL) and O((kappa + 1)n(3)L) respectively.
基金supported by the Natural Science Foundation of Hubei Province under Grant No.2008CDZ047
文摘This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The main iteration consists of a feasibility step and several centrality steps.The authors introduce a specific kernel function instead of the classic logarithmical barrier function to induce the feasibility step,so the analysis of the feasibility step is different from that of Roos' s.This kernel function has a finite value on the boundary.The result of iteration complexity coincides with the currently known best one for infeasible interior-point methods for P_*(κ) LCP.Some numerical results are reported as well.
基金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.
文摘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.
文摘对P*(κ)线性互补问题提出了一种自适应全-Newton步不可行内点算法.算法是对Mansouri等人(H.Mansouri and M.Pirhaji in Journal of Operations Research Society of China 1:523-536,2013)提出的单调线性互补问题的自适应不可行内点算法的推广.在算法的每一次迭代中,障碍校正参数θ的取值并不固定,它总在1/(51n(1+4κ)2)和1/(14n(1+4κ)2)之间取满足算法要求的最大值,使得算法快速收敛于问题的一个ε-近似解.
