Source-linked AI summary
The Sparsest Solutions to $Z$-Tensor Complementarity Problems
Ziyan Luo, Liqun Qi, Naihua Xiu
TL;DR
Finding sparsest solutions to tensor complementarity problems is generally NP-hard because the ℓ0 objective is nonconvex and discontinuous. The paper uses Z-tensor structure and least-element theory to obtain an exact linear-objective polynomial-programming relaxation, with conditions that are easy to verify. Under the stated feasibility and sign conditions, the relaxation recovers a sparsest solution and has a unique solution.
Problem
Sparsest tensor complementarity is generally NP-hard, and nonlinear complementarity constraints make existing linear-system exact-relaxation conditions unsuitable.
Method
The paper employs Z-tensors and least-element theory to replace ℓ0 minimization with polynomial programming having a linear objective.
Results
Under nonnegative b, a Z-tensor A, and feasibility, the relaxation has a unique solution that is also a sparsest tensor complementarity solution.
Takeaways & Limitations
The proposed conditions provide an exact relaxation for the targeted Z-tensor problems and are easy to verify compared with existing general nonlinear conditions.
Abstract
from arXiv · showhide
Finding the sparsest solutions to a tensor complementarity problem is generally NP-hard due to the nonconvexity and noncontinuity of the involved $\ell_0$ norm. In this paper, a special type of tensor complementarity problems with $Z$-tensors has been considered. Under some mild conditions, we show that to pursuit the sparsest solutions is equivalent to solving polynomial programming with a linear objective function. The involved conditions guarantee the desired exact relaxation and also allow to achieve a global optimal solution to the relaxed nonconvex polynomial programming problem. Particularly, in comparison to existing exact relaxation conditions, such as RIP-type ones, our proposed conditions are easy to verify.
1 Introduction
The introduction frames sparsest tensor complementarity as a difficult nonlinear sparse-optimization problem and proposes an exact linear-objective relaxation for Z-tensors under verifiable conditions.
- Research goal: The paper asks whether a Z-type condition can provide an exact relaxation for sparse polynomial complementarity problems.This extends the use of Z-matrices in sparse linear complementarity to more general polynomial cases.
- Problem setting: Tensor complementarity extends polynomial systems through tensor representations of homogeneous polynomial mappings.For F(x)=H(x)−b, the coefficient tensor A represents H(x) as Ax^(m−1).
- Motivation: Finding sparsest solutions is generally NP-hard because the ℓ0 objective is nonconvex and discontinuous, while complementarity constraints are nonlinear.Existing exact-relaxation conditions are mainly designed for linear systems and are less appropriate here.
- Contribution: For nonnegative b and a Z-tensor A, a sparsest tensor complementarity solution can be obtained by solving a polynomial program with a linear objective.The relaxation uses the all-one vector e, yielding e^T x under the relevant constraints.
- Contribution: The proposed coefficient conditions are easier to verify than existing exact-relaxation conditions for general nonlinear sparse optimization.The introduction identifies this verifiability as the paper’s main contribution.
2 Z-Tensors and Z-Functions
This section develops Z-tensor and Z-function concepts as higher-order analogues of Z-matrix structure, then establishes properties used in tensor complementarity analysis.
- Z-functions: A Z-function is characterized through complementarity implications and, for differentiable mappings, by having a Z-matrix Jacobian at every nonnegative point.The section connects the nonlinear definition to the matrix criterion via Proposition 1 and Lemma 1.
- Definitions: A Z-tensor generalizes a Z-matrix by requiring all off-diagonal tensor entries to be nonpositive.For order m=2, Z-tensors and partially Z-tensors reduce to Z-matrices.
- Definitions: A partially Z-tensor imposes nonpositive coefficients when the first index does not occur among the remaining indices.Every Z-tensor is partially Z, but the converse need not hold.
- Properties: These properties support later complementarity results, including existence of a unique least feasible element when the Z-tensor complementarity problem is feasible.The least element is also a tensor complementarity solution.
- Properties: For a Z-tensor A, the polynomial mapping F(x)=Ax^(m−1) is a Z-function.The proof uses the tensor sign structure to establish the required implication.
3 Z-Tensor Complementarity Problems
For feasible Z-tensor complementarity problems, the feasible set has a unique least element that is also a complementarity solution. Under additional nonnegative-data and tensor conditions, feasibility can be related to a nonnegative constrained multilinear equation.
- Z-function structure: The Z-tensor framework exploits least-element theory for nonlinear complementarity problems to characterize solutions and feasibility.The associated tensor polynomial mapping is a Z-function, enabling the least-element result.
- Z-tensor complementarity properties: A feasible Z-tensor complementarity problem has a unique least feasible element, and that element solves the complementarity problem.This follows because the associated mapping is a continuous Z-function.
- Equivalent formulations: With nonnegative b and a partially Z-tensor A, the tensor complementarity problem is equivalent to a multilinear equation with nonnegative constraints.The equivalence connects complementarity feasibility with consistency of the constrained equation system.
- M-tensors: A Z-tensor is represented as A = sI − B with B nonnegative, while M-tensor and strong M-tensor conditions require s ≥ ρ(B) and s > ρ(B), respectively.The strong M-tensor condition is used in the feasibility argument.
- Feasibility: For a strong M-tensor with nonnegative B and suitable b, a fixed-point mapping provides a nonnegative solution to Ax^(m−1) = b.The mapping is increasing and continuous, and its fixed point yields the required nonnegative solution.
4 Exact Relaxation
The paper establishes an exact relaxation for sparsest tensor complementarity solutions under Z-tensor structure. The resulting linear-objective polynomial program uniquely recovers a solution of the original sparsity problem, with an extension based on permuting equations.
- Exact relaxation theorem: If (P0) is feasible, it has a solution x* that is also the unique solution of (P1).The proof uses the unique least element of the feasible set and the equivalence with the nonnegative multilinear system.
- Exact relaxation theorem: The unique solution of (P1) is also an optimal solution to (P0), establishing exactness of the relaxation.This conclusion follows from the preceding proposition and theorem.
- Extension by permutation: Permuting the multilinear equations preserves their solution set, allowing the exact-relaxation result to extend to tensors transformable into Z-tensors by permutation matrices.The paper denotes this class by PZ_m,n.
- Extension by permutation: The operator induced by an invertible matrix maps the tensor space onto itself but does not generally preserve the Z-property.This limits direct use of arbitrary invertible transformations for maintaining Z-tensor structure.
5 Conclusions
The conclusion states that sparsest Z-tensor complementarity solutions can be obtained through a polynomial program with a linear objective under an easily verifiable exact-relaxation condition.
- Conclusions: The original sparsity problem is NP-hard, but a sparsest solution can be obtained in polynomial time by solving a linear-objective polynomial program under the proposed condition.The paper cites the Gauss-Seidel iteration method as an example for solving the relaxed problem.
- Conclusions: The input-data condition guarantees exact relaxation and is easier to verify than existing conditions such as RIP-type conditions.The conclusion identifies sparse optimization with general nonlinear complementarity constraints as an avenue for further study.