P-Tensors, P$_0$-Tensors, and Tensor Complementarity Problem

Weiyang Ding, Ziyan Luo, Liqun QiarXiv 2015 · DOI · arXiv

This paper, published in 2018, provides a significant theoretical bridge between classical matrix theory and the burgeoning field of multilinear algebra (tensor analysis). It addresses a specific technical gap in how we define "P-tensors"—a class of tensors that are essential for solving complex optimization problems.

TL;DR

The authors introduce a new, "homogeneous" definition for P-tensors and $P_0$-tensors that works for both even and odd orders, fixing a major deficiency in previous definitions. They prove that this new class of tensors encompasses many important structures (like Laplacian and M-tensors) and guarantees that the Tensor Complementarity Problem (TCP) has a well-behaved solution set.

What Problem Does This Paper Address?

In matrix theory, P-matrices are those where all principal minors are positive. They are famous because they guarantee that a "Linear Complementarity Problem" (a type of optimization problem used in economics and engineering) has a unique solution.

As researchers moved from matrices (2D arrays) to tensors (multi-dimensional arrays), they tried to generalize this concept. However, previous definitions of "P-tensors" had a glaring flaw: they didn't work for tensors of odd order (e.g., a 3x3x3 tensor). Under the old rules, no odd-order P-tensors could exist. This paper aims to fix that "odd-order gap" by proposing a definition that is mathematically consistent regardless of the tensor's dimensions or order.

Methods

The authors employ a homogeneous formula to redefine P-tensors.

Specifically, while previous definitions looked at the sign of the product $x_i(Ax^{m-1})_i$, this paper proposes looking at $x_i^{m-1}(Ax^{m-1})_i$. By raising the $x_i$ term to the power of $m-1$ (where $m$ is the order of the tensor), they ensure the formula behaves predictably whether $m$ is even or odd.

The paper is primarily a theoretical proof-based work. The authors use tools from:

  • Spectral Theory of Tensors: Analyzing H-eigenvalues (real eigenvalues).
  • Complementarity Theory: Using fixed-point theorems and degree theory to analyze solution sets.
  • Structured Tensor Analysis: Testing their definition against known classes like M-tensors, H-tensors, and Cauchy tensors.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and counterexamples rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Homogeneity Fix: The simple act of changing the exponent in the definition allows P-tensors to exist in odd orders. This isn't just a neat trick; it allows the theory of tensors to align more closely with the behavior of multivariate polynomials.
  • Spectral Characterization: A P-tensor (under this new definition) is shown to have no non-positive H-eigenvalues. This provides a bridge between the algebraic structure of the tensor and its geometric/spectral properties.
  • Unification of Classes: The authors show that their definition is "broad" enough to include many important structured tensors, such as:
  • Nonsingular M-tensors (important in probability and physics).
  • Laplacian tensors of uniform hypergraphs (crucial for network science).
  • Strictly diagonally dominant tensors.
  • Counterpart to PSD: For odd-order tensors, $P_0$-tensors can be viewed as the natural extension of Positive Semidefinite (PSD) tensors, which are usually only defined for even orders.

Key Results

  • TCP Solvability: The most significant application is the Tensor Complementarity Problem (TCP). The authors prove that if a tensor $A$ is a P-tensor, the TCP is guaranteed to have a solution set that is both non-empty and compact.
  • Inheritance: They prove that every principal subtensor of a P-tensor is also a P-tensor, maintaining consistency with matrix theory.
  • Topological Properties: They demonstrate that the set of $P_0$-tensors is the "closure" of the set of P-tensors, meaning you can approximate any $P_0$-tensor with a sequence of P-tensors.

Limitations and Future Work

  • Uniqueness: Unlike the matrix case (where P-matrices guarantee a unique solution), P-tensors only guarantee that a solution exists and is bounded. The solutions are not necessarily unique, which remains a challenge for certain optimization algorithms.
  • Non-Convexity: The authors acknowledge that the set (cone) of $P_0$-tensors is not convex. This makes certain types of global optimization more difficult.
  • Computational Complexity: While the paper defines these tensors, checking if a general tensor is a P-tensor is likely NP-hard (though the authors don't explicitly prove the complexity class here, it is a known trait of similar tensor properties). Future work could involve finding more "easily checkable" sufficient conditions for the P-property.

Summary updated

Abstract

The concepts of P- and P$_0$-matrices are generalized to P- and P$_0$-tensors of even and odd orders via homogeneous formulae. Analog to the matrix case, our P-tensor definition encompasses many important classes of tensors such as the positive definite tensors, the nonsingular M-tensors, the nonsingular H-tensors with positive diagonal entries, the strictly diagonally dominant tensors with positive diagonal entries, etc. As even-order symmetric PSD tensors are exactly even-order symmetric P$_0$-tensors, our definition of P$_0$-tensors, to some extent, can be regarded as an extension of PSD tensors for the odd-order case. Along with the basic properties of P- and P$_0$-tensors, the relationship among P$_0$-tensors and other extensions of PSD tensors are then discussed for comparison. Many structured tensors are also shown to be P- and P$_0$-tensors. As a theoretical application, the P-tensor complementarity problem is discussed and shown to possess a nonempty and compact solution set.
BibTeX
@misc{ding2015p,
  author = {Weiyang Ding and Ziyan Luo and Liqun Qi},
  title = {{P-Tensors, P$\_0$-Tensors, and Tensor Complementarity Problem}},
  year = {2015},
  eprint = {1507.06731},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.06731},
}

Loading related content...

Figure