Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
复制标题
线性互补问题的Bard型算法有向图模型
DOI：
--
复制
发表时间：
1978
影响因子：
1.7
通讯作者：
L. Watson
中科院分区：
文献类型：
--
作者：
Alan Stickney;L. Watson
对于 M ε En×n 和 q ε En，线性互补问题是找到向量 w，z ε En 使得 w-Mz = q，w ≥ 0，z ≥ 0，wtz = 0。用于解决该问题的基于互补枢轴的一系列算法通过有向图建模。这些有向图表明，此类算法甚至可以针对对称、正定 M 进行循环，并提供对算法行为的一些了解。对于一个P-矩阵M，证明了如果互补问题的解可以通过k个主枢轴得到，那么它也可以通过k个Bard型主元得到。此外，有向图还提供了 Murty 的一些代数结果的简单几何证明。有向图除了用作模型之外，还提出了一些有趣的图论问题。
For M ∈ En×n and q ∈ En, the linear complementarity problem is to find vectors w, z ∈ En such that w-Mz = q, w ≥ 0, z ≥ 0, wtz = 0. A family of algorithms based on complementary pivoting for solving this problem is modelled by digraphs. These digraphs show that such algorithms can cycle even for symmetric, positive deFinite M, and provide some insight into the algorithms' behavior. For a P-matrix M, it is proved that if the solution to the complementarity problem can be obtained by k principal pivots, then it can be obtained by k Bard-type pivots. Furthermore, the digraphs provide simple geometric proofs of some of Murty's algebraic results. The digraphs, apart from their use as models, also raise some interesting graph-theoretic questions.