Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear op...Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.展开更多
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.展开更多
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.展开更多
SDD_(k)matrices are a subclass of the nonsingular H-matrices.The infinity norm of the inverse for SDD_(k)matrices has been given.In the paper,we utilize this result in the context of the linear complementarity problem...SDD_(k)matrices are a subclass of the nonsingular H-matrices.The infinity norm of the inverse for SDD_(k)matrices has been given.In the paper,we utilize this result in the context of the linear complementarity problem,and the error bounds of the linear complementarity problem for SDD_(k)matrices are obtained.By the relationship between the SDD matrices and the SDD_(k)matrices,we further obtain the error bounds of the linear complementarity problem for SDD matrices.In addition,it is proved that the bounds presented in this paper are sharper than the well-known bounds under some conditions.Finally,numerical examples are provided to demonstrate the effectiveness of our results.展开更多
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.展开更多
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.展开更多
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.展开更多
对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)之间取满足算法要求的最大值,使得算法快速收敛于问题的一个ε-近似解.展开更多
The class of E＇-matrices introduced in [4] is a subclass of Q0-matrices whose proper principal submatrices are Q--matrices. In this paper, we investigate the relation of the class E＇ to other known matrix classes an...The class of E＇-matrices introduced in [4] is a subclass of Q0-matrices whose proper principal submatrices are Q--matrices. In this paper, we investigate the relation of the class E＇ to other known matrix classes and obtain a series of necessary and sufficient conditions for E＇-matrices.展开更多
基金Supported by the Natural Science Foundation of Hubei Province(Grant No.2008CDZ047)
文摘Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.
基金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.
文摘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.
基金supported by the Natural Science Foundation of Shaanxi Province,China(Grant No.2020JM-622)the Postgraduate Innovative Research Project of Baoji University of Arts and Sciences(Grant No.YJSCX25YB39).
文摘SDD_(k)matrices are a subclass of the nonsingular H-matrices.The infinity norm of the inverse for SDD_(k)matrices has been given.In the paper,we utilize this result in the context of the linear complementarity problem,and the error bounds of the linear complementarity problem for SDD_(k)matrices are obtained.By the relationship between the SDD matrices and the SDD_(k)matrices,we further obtain the error bounds of the linear complementarity problem for SDD matrices.In addition,it is proved that the bounds presented in this paper are sharper than the well-known bounds under some conditions.Finally,numerical examples are provided to demonstrate the effectiveness of our results.
文摘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 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.
基金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.
文摘对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 YSF of Guangdong University of Technology(062058)
文摘The class of E＇-matrices introduced in [4] is a subclass of Q0-matrices whose proper principal submatrices are Q--matrices. In this paper, we investigate the relation of the class E＇ to other known matrix classes and obtain a series of necessary and sufficient conditions for E＇-matrices.
