Source-linked AI summary
Properties of Solution set of Tensor Complementarity Problem
Yisheng Song, Gaohang Yu
TL;DR
The paper studies which structural tensor properties govern feasibility and boundedness in tensor complementarity problems. It characterizes these properties and proves global solution bounds for strictly semi-positive tensors, relating the bounds to Pareto eigenvalues in the symmetric case.
Problem
The paper asks how the special structure of tensors shapes feasibility, boundedness, and other properties of the tensor complementarity problem.
Source: §1 · pp. 2–3Method
The paper derives equivalences involving S- and R0-tensors and establishes upper bounds using eigenvalue-linked constants for symmetric tensors and a new quantity for nonsymmetric tensors.
Source: §1 · p. 3, §5 · p. 12Results
A tensor is an S-tensor iff TCP(A,q) is feasible for every q, every Q-tensor is an S-tensor, and boundedness is equivalent to unique solvability at q=0.
Source: §1 · p. 3, §3.1 · p. 7Takeaways & Limitations
For strictly semi-positive tensors, global solution upper bounds are proved; symmetric-tensor bounds closely relate to the smallest Pareto H-(Z-)eigenvalue, while nonsymmetric bounds use a new quantity.
Source: §5 · p. 12
Abstract
from arXiv · showhide
The tensor complementarity problem is a specially structured nonlinear complementarity problem, then it has its particular and nice properties other than ones of the classical nonlinear complementarity problem. In this paper, it is proved that a tensor is an S-tensor if and only if the tensor complementarity problem is feasible, and each Q-tensor is an S-tensor. Furthermore, the boundedness of solution set of the tensor complementarity problem is equivalent to the uniqueness of solution for such a problem with zero vector. For the tensor complementarity problem with a strictly semi-positive tensor, we proved the global upper bounds for solution of such a problem. In particular, the upper bounds keep in close contact with the smallest Pareto $H-$($Z-$)eigenvalue.
1 Introduction
The introduction frames the tensor complementarity problem as a higher-order-tensor extension of classical complementarity that may have distinctive properties. It previews characterizations of feasibility and boundedness, along with global solution bounds for strictly semi-positive tensors.
1 Introduction
- The introduction situates complementarity research in a broad application landscape and notes the established study of linear complementarity, including existence and uniqueness conditions.Applications listed for classical complementarity include optimization, economic equilibrium, mechanics, traffic equilibrium, and optimal control; linear complementarity results are attributed to Cottle, Pang and Stone and others.Source: §1 · p. 2
- The tensor complementarity problem is presented as a natural extension of the linear complementarity problem with potentially distinctive properties arising from higher-order tensor structure.The introduction identifies studying those properties and their applications as the motivation for the paper.Source: §1 · p. 2
- Prior tensor work studied solution existence for structured tensors, sparsest solutions for Z-tensor problems, and links between symmetric semi-positivity and copositivity.The cited examples include Song and Qi [13] [16] and Luo, Qi, Xiu [15].Source: §1 · p. 2
- An S-tensor is equivalent to feasibility of the tensor complementarity problem for every q, every Q-tensor is an S-tensor, and boundedness is equivalent to unique solvability at zero.For strictly semi-positive tensors, the paper also establishes global solution upper bounds, linked to the smallest Pareto H-(Z-)eigenvalue.Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries establish tensor and complementarity notation, collect tensor classes and solvability results, and introduce Pareto eigenvalues used in later bounds.
2 Preliminaries
- A real tensor is a multi-array, and a symmetric tensor has entries invariant under permutations of its indices; tensor-vector operations also define a homogeneous polynomial of degree m.The preliminaries denote Ax^(m-1) as a vector and Ax^m as a degree-m homogeneous polynomial.Source: §2 · pp. 3–4
- A Q-tensor makes TCP(A,q) solvable for every q, while an R0-tensor makes TCP(A,0) have a unique solution.The text also defines the feasible region and distinguishes feasibility from solvability.Source: §2 · p. 4
- Every strictly semi-positive tensor is an R-tensor, every R-tensor is a Q-tensor, and a semi-positive R0-tensor is a Q-tensor.These implications are stated as Lemma 2.1, citing Song and Qi [13].Source: §2 · p. 5
- Pareto H- and Z-eigenvalues are introduced to characterize copositivity, and the smallest Pareto Z-eigenvalue of a strictly copositive symmetric tensor is positive.The minimum is denoted μ(A) and satisfies μ(A) > 0.Source: §2 · pp. 5–6
3 Solution of the TCP(A, q)
The section characterizes feasibility through S-tensors and boundedness through R0-tensors, then establishes global solution bounds for strictly semi-positive tensors. It also relates bounded solution sets to the zero-vector problem and gives upper-bound results for symmetric cases.
3.1 S-tensor and feasible solution of the TCP(A, q)
- A is an S-tensor if and only if TCP(A, q) is feasible for every q, and every Q-tensor is an S-tensor.Source: §3.1 · p. 7
3.2 R0-tensor and boundedness of solution set of the TCP (A, q)
- A is an R0-tensor if and only if the stated Γ sets are bounded and the solution set of TCP(A, q) is bounded for every q.Source: §3.2 · p. 7
- Strictly semi-positive tensors, and therefore P-tensors, have bounded TCP solution sets for every q.Source: §3.2 · p. 8
3.3 Solution of TCP(A, q) with strictly semi-positive tensors
- For strictly semi-positive symmetric tensors, the section states global upper bounds for TCP solutions, including bounds involving quantities defined through eigenvalue results.Source: §3.3 · pp. 8–9
- For symmetric tensors, strict semi-positivity is equivalent to strict copositivity, and q ≥ 0 yields the unique solution 0.Source: §3.3 · p. 9
- The section introduces β(A) for strictly semi-positive tensors and states a further solution upper bound using this quantity.Source: §3.3 · p. 10
- A strictly semi-positive tensor can induce a function that is not pseudo-monotone, while the corresponding complementarity problem has a solution.Source: §3.3 · pp. 10–11
4 Perspectives
The section identifies open questions about the scope and tightness of the paper’s global upper bounds for TCP solutions. It also asks whether a newly defined quantity for strictly semi-positive tensors has a global or local upper bound.
4 Perspectives
- The paper leaves open whether the upper bounds for TCP solutions with strictly semi-positive symmetric tensors are the smallest possible.Source: §4 · p. 11
- It asks whether strictly semi-positive tensors admit a positive lower bound for TCP solutions.Source: §4 · p. 11
- The paper asks whether Z-, B-, H-, and M-tensors have similar global upper bounds for TCP solutions.Source: §4 · p. 11
- For a strictly semi-positive tensor, it remains open whether the newly defined quantity β(A) has a global or local upper bound.Source: §4 · p. 11
5 Conclusions
The paper establishes equivalences between TCP feasibility and S-tensors, and between solution-set boundedness and R0-tensors. It also proves global upper bounds for TCP solutions with strictly semi-positive tensors, with distinct approaches for symmetric and nonsymmetric cases.
5 Conclusions
- TCP feasibility is equivalent to being an S-tensor, while boundedness of the solution set is equivalent to being an R0-tensor.Source: §5 · p. 12
- For strictly semi-positive symmetric tensors, global solution upper bounds are closely related to the smallest Pareto H-(Z-)eigenvalue.Source: §5 · p. 12
- For strictly semi-positive nonsymmetric tensors, global solution upper bounds are proved using a newly introduced quantity.Source: §5 · p. 12