Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
复制标题
可通过多项式有界旋转算法解决的线性互补问题
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
R. Chandrasekaran
中科院分区：
文献类型：
--
作者：
J. Pang;R. Chandrasekaran
给出了一个充分条件，在此条件下参数主元算法将计算由n × n P-矩阵定义的线性互补问题在不超过n个主元上的唯一解.然后，该条件被证明是由一个P-矩阵，其中有一个隐藏的Z转置，因此特别是，由一个H-矩阵与正对角以及严格对角占优矩阵满足。同样的条件也被证明是足够的Lemke的几乎互补算法来计算一个解决方案的线性互补问题所定义的一个n乘n非退化矩阵在最多n+1枢轴。最后，一个多项式测试程序的条件。
A sufficient condition is given under which the parametric principal pivoting algorithm will compute the unique solution to a linear complementarity problem defined by an n by n P-matrix in no more than n pivots. The condition is then shown to be satisfied by a P-matrix which has a hidden Z transpose and thus in particular, by an H-matrix with positive diagonals as well as by a strictly diagonally dominant matrix. The same condition is also shown to be sufficient for Lemke’s almost complementary algorithm to compute a solution to a linear complementarity problem defined by an n by n nondegenerate matrix in at most n+1 pivots. Finally, a polynomial testing procedure for the condition is described.