It is known that special types of linear complementarity problems can be solved in polynomial time, although the general problem is NP-complete. One example is the case where the defining matrix is nondegenerate and for which the n-step property holds. In this dissertation the property is extended to the degenerate case.; Specifically, the concept of an extended n-step vector is introduced, which gives rise to a class of matrices called ENS matrices. It is shown that the LCP defined by a matrix of this type is polynomially solvable, and that the matrix is in fact strictly semimonotone.; Matrix-theoretic studies of these matrices are conducted. Among the major results established are the derivations of necessary conditions and sufficient conditions for a real square matrix whose principal minors are nonnegative to belong to the ENS class. Each of these conditions defines a collection of matrices that properly contains the class of matrices for which the transpose is hidden Minkowski.; In addition, geometric and set-theoretic properties of the set of extended n-step vectors are investigated, under the assumption that the associated matrix has nonnegative principal minors. A geometric property relating the set in question to complementary cones is given. It is also proven that under the usual perturbation of the matrix, the set increases monotonically with the perturbation parameter.; A separate but related topic is also explored in this thesis. It involves the connection between those matrices with nonnegative principal minors and those characterized by non-strict semimonotonicity. Two different sets of conditions under which the two matrix classes coincide are derived and proven.
展开▼
机译：众所周知，特殊类型的线性互补问题可以在多项式时间内解决，尽管一般问题是NP-完全问题。一个例子是定义矩阵是非简并的并且具有 n -step属性的情况。本文将性质扩展到简并的情况。具体来说，引入了扩展的 n 步长矢量的概念，这产生了称为ENS矩阵的一类矩阵。结果表明，由这种类型的矩阵定义的LCP是可多项式可解的，并且该矩阵实际上是严格半单调的。对这些矩阵进行了矩阵理论研究。在确定的主要结果中，包括一个主次要非负属于ENS类的实平方矩阵的必要条件和充分条件的推导。这些条件中的每一个都定义了一组矩阵，这些矩阵正确地包含转置被隐藏的Minkowski的矩阵类别。此外，在关联矩阵具有非负主要次要假设的情况下，研究了扩展的 n 步骤向量集的几何和集合理论性质。给出了将所讨论的集合与互补圆锥相关的几何性质。还证明了在矩阵的通常扰动下，该集合随扰动参数单调增加。本文还探讨了一个单独但相关的主题。它涉及那些具有非负主要未成年人的矩阵与那些具有非严格半单调性的矩阵之间的联系。得出并证明了两个矩阵类别重合的两组不同条件。
展开▼
