Pivoting in Linear Complementarity: Two Polynomial-Time Cases

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty’s least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris’s highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP.     

求解一类非单调线性互补问题的宽邻域内点方法及其计算复杂性

对于一类非单调线性互补问题给出了一种新的算法——宽邻域内点算法，并讨论了其计算复杂性。     

A note on a characterization of P-matrices

In this note we show that the characterization results for P-matrices due to K.G. Murty and A. Tamir which state that a given square matrixM of ordern is a P-matrix if and only if the linear complementarity problem (q, M) has a unique solution for allq in a specified finite subset of ⁿ depending onM are incorrect whenn > 3.Research supported by Dr. K.S. Krishnan (DAE) fellowship for research in Mathematics and Computer Science, Bombay, India.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

A Recursive Test for P-Matrices

The time complexity for testing whether an n-by-n real matrix is a P-matrix is reduced from O(2ⁿ n ³) to O(2 ⁿ ) by applying recursively a criterion for P-matrices based on Schur complementation. A Matlab program implementing the associated algorithm is provided.     

Stability and convex hulls of matrix powers

Invertibility of all convex combinations of A and I is equivalent to the real eigenvalues of A, if any, being positive. Invertibility of all matrices whose rows are convex combinations of the respective rows of A and I is equivalent to A having positive principal minors (i.e. being a P-matrix). These results are extended by considering convex combinations of higher powers of A and of their rows. The invertibility of matrices in these convex hulls is associated with the eigenvalues of A lying in open sectors of the right-half plane and provides a general context for the theory of matrices with P-matrix powers.     

正P-矩阵的逆零完成问题(英文)

本文基于不完备P-矩阵的1-通弦图和1-通弦块图的完成问题,获得了不完备正P-矩阵在一定条件下的k-通弦图和k-通弦块图的完成,同时解决了不完备正P-矩阵在k-通弦图和k-通弦块图下的逆零完成问题(k为大于1的整数).     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.