Perron-Certified Monotone Solvers for Z-Tensor Complementarity

Many equilibrium and obstacle-type problems ask for a nonnegative vector $x$ such that a polynomial "force" $\mathcal{A}x^{m-1}+q$ is also nonnegative, and such that each coordinate has either $x_i=0$ or a zero force. Here $\mathcal{A}$ is an order-$m$ array of coefficients (a tensor) and $\mathcal{A}x^{m-1}$ is the vector of degree-$(m-1)$ polynomials it defines. This is the tensor complementarity problem (TCP). Existing solvers treat it as a generic nonsmooth root-finding problem, and their speed hinges on hand-set gains. We propose to exploit a sign structure that appears often in practice. When every off-diagonal coefficient of $\mathcal{A}$ is nonpositive (a Z-tensor), the map behind the problem preserves order. Order-preserving homogeneous maps are exactly the setting of the nonlinear Perron–Frobenius theorem, which describes the unique positive eigenvector and its eigenvalue for nonnegative arrays. That theory gives three things. It supplies a solver that climbs monotonically to a solution from below. It gives a two-sided bracket that certifies how far the current iterate is from the answer. And it gives a cheap test of copositivity, meaning $\mathcal{A}x^m\ge 0$ for all $x\ge 0$, which is NP-hard for general tensors.

The practical payoff is a TCP solver that needs no gain, shift or step size set by hand. Its internal parameters (Newton damping, inner linear-solve accuracy, stopping) are set online from a single monitored quantity, the width of the bracket. The same computation reports whether the problem is solvable and whether its solution is unique.

Core Claim

Write a Z-tensor as $\mathcal{A}=\mathcal{D}-\mathcal{B}$, where $\mathcal{D}$ is diagonal with $d_i=a_{i\cdots i}$ and $\mathcal{B}$ is entrywise nonnegative. Define the map

$$ T(x)_i=\Big[\max\big(0,\ ((\mathcal{B}x^{m-1})_i-q_i)/d_i\big)\Big]^{1/(m-1)} . $$

$T$ is order-preserving. Every fixed point of $T$ solves $\mathrm{TCP}(\mathcal{A},q)$: where $x_i>0$ the force vanishes, and where $x_i=0$ one gets $(\mathcal{A}x^{m-1}+q)_i=q_i-(\mathcal{B}x^{m-1})_i\ge 0$. Iterating $T$ from $x=0$ gives a nondecreasing sequence. Iterating from any supersolution gives a nonincreasing one. The lower sequence converges to the least solution and the upper sequence to the greatest solution below the starting point. Together they form a Collatz–Wielandt-style sandwich: the gap between the two sequences is a rigorous error bound, and a gap that fails to close signals multiple solutions.

Whether a supersolution exists is governed by a Perron quantity. For symmetric $\mathcal{A}$ with $\mathcal{D}=s\mathcal{I}$, the Perron root $\rho(\mathcal{B})$ is the maximum of $\mathcal{B}x^m$ over the nonnegative part of the unit $\ell_m$ sphere, so

$$ \min_{x\ge 0,\ \|x\|_m=1}\mathcal{A}x^m \;=\; s-\rho(\mathcal{B}). $$

A symmetric Z-tensor is therefore copositive exactly when it is an $\mathcal{M}$-tensor. The copositivity margin can be computed, with certified upper and lower bounds, by Perron solvers such as Newton–Noda iterations.

For a general tensor, set its positive off-diagonal entries to zero. The result is a Z-tensor that bounds $\mathcal{A}x^m$ from below on $x\ge 0$. This yields a cheap sufficient certificate of copositivity. It is sufficient only, and we will measure how often it succeeds.

The new object is a monotone, safeguarded Newton–Noda solver for Z-tensor TCPs whose damping, inner tolerance and stopping rule are all driven by the Perron-type bracket. It comes paired with a Perron-based certificate of solvability and copositivity.

Relation to Prior Work

Several papers supply the theory this proposal starts from. Positive-Definite Tensors to Nonlinear Complementarity Problems proves that copositive or positive-definite tensors give nonempty compact TCP solution sets and that diagonalizable ones give uniqueness. That work is non-constructive; we trade generality (Z-sign structure only) for an algorithm and checkable certificates. $\mathcal{M}$-tensors and nonsingular $\mathcal{M}$-tensors characterizes nonsingular $\mathcal{M}$-tensors by semi-positivity and monotonicity, which is the property that makes a supersolution exist. A Unifying Perron-Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps casts tensor eigenproblems as fixed points of order-preserving maps. We apply the same viewpoint to complementarity, which that theory does not cover.

Two papers supply methods we reuse. Noda Iteration for Computing Generalized Tensor Eigenpairs gives positivity-preserving Newton–Noda iterations for $\mathcal{M}$-tensor pairs, but it has no inequality constraints, no shift vector $q$, and fixed inner tolerances. A Variational Characterization and A Line Search Newton-Noda Method for the unifying spectral problem of nonnegative tensors adds a positivity-preserving line search with quadratic convergence and names inexact Newton steps as future work. We borrow its safeguard idea, replacing "stay positive" with "stay a subsolution", and add adaptive inexactness.

Other work motivates the proposal by exposing the gap. Gradient Dynamic Approach to the Tensor Complementarity Problem and Modified gradient dynamic approach to the tensor complementarity problem solve TCPs with a Fischer–Burmeister gradient flow. The flow is scaled by a fixed gain $\gamma=10^6$, and the authors call adaptive tuning open. Their convergence proofs need strong $P$-tensors, and they ignore spectral structure entirely.

An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs is the model for replacing a fixed shift with a curvature-driven one. It works on the unconstrained sphere, however, and can show small monotonicity violations. Our monotonicity comes from order preservation rather than tolerance heuristics.

Copositivity for a Class of Fourth-Order Symmetric Tensors Given by Scalar Dark Matter derives analytic copositivity conditions for a physics-motivated tensor class. It provides ground-truth instances for testing how often our sufficient certificate fires.

Research Program

The first component is analysis. We will prove that the lower and upper iterations of $T$ converge to the least solution and to the greatest solution below the start. We will show that a strong $\mathcal{M}$-tensor guarantees a supersolution, obtained by scaling a positive vector $u$ with $\mathcal{A}u^{m-1}>0$. The linear convergence rate should be governed by the Perron root of the diagonally scaled tensor $\mathcal{D}^{-1}\mathcal{B}$, by analogy with Jacobi splittings of $\mathcal{M}$-matrices.

We will also settle when the copositivity–Perron identity holds for nonsymmetric Z-tensors, where the symmetric variational argument no longer applies directly. The matrix version is classical. We found no tensor TCP analogue with an accelerated algorithm in the file.

The second component is the accelerated solver. At a subsolution $x_k$, meaning $T(x_k)\ge x_k$, we fix the working set of coordinates that are positive or have negative force. We then take a Newton step on $(\mathcal{A}x^{m-1}+q)_i=0$ over that set. The Jacobian $(m-1)\mathcal{A}x^{m-2}$ is a Z-matrix there, and we expect it to be a nonsingular $\mathcal{M}$-matrix below the solution.

The step is accepted only if the new point is still a subsolution, which costs one tensor–vector product to check. Otherwise the step is damped back toward $T(x_k)$. The inner linear solve runs to a relative tolerance proportional to the current bracket width. This is the adaptive-inexactness rule A Variational Characterization and A Line Search Newton-Noda Method for the unifying spectral problem of nonnegative tensors leaves open. The goal is monotone global convergence with a locally superlinear rate, and no user-set parameters.

The third component is certification. The Perron root step (Newton–Noda on $\mathcal{B}$) returns Collatz–Wielandt bounds, and these decide whether the problem is copositive, solvable for every $q$, or neither. For non-Z tensors the same routine applied to the Z-truncation gives a sufficient copositivity test. For non-Z TCPs we do not claim a monotone solver. We will report honestly where the method stops applying.

Baselines

The naive reference is the plain monotone iteration of $T$ from zero, with no Newton acceleration. It is parameter-free and globally convergent, so it isolates what the Newton step and adaptive tolerance add.

The TCP baseline from the literature is the nonlinear gradient dynamical system of Modified gradient dynamic approach to the tensor complementarity problem. We run it with the smooth power-sigmoid activation it reports as fastest and with the published $\gamma=10^6$. It is integrated by a standard adaptive ODE solver under the same wall-clock budget, and we also give it a small grid over $\gamma$ matching our tuning budget of zero hand-set parameters plus the grid. On its own Examples 5.1–5.3 it reports residuals $\|\Phi(x)\|_2$ between $10^{-10}$ and $10^{-16}$ "in fractions of a second". Beating it means matching that accuracy on those examples and staying robust, with no failures, on larger and worse-conditioned Z-tensor instances where a single $\gamma$ is not tuned per instance.

The strongest general competitor is semismooth Newton on the Fischer–Burmeister reformulation with a standard line search. The file contains no citation or reported number for it on TCPs, so it is implemented by us. It gets identical starting points, tolerances and linear algebra.

For the certification step, the Perron-root baseline is GNNI from Noda Iteration for Computing Generalized Tensor Eigenpairs. It reports reaching $10^{-13}$ in 3 iterations and about 6.5 seconds on a $4\times50\times50\times50$ instance, against 161 seconds for MTNI. GEAP serves as a secondary baseline, and LS-NNM reports 8 iterations versus 395 for the power method PM1 on a $3\times3\times3$ example.

Two ablations isolate the key ingredient. The first uses a fixed inner tolerance instead of the bracket-driven one. The second drops the subsolution safeguard, which turns the method into an unsafeguarded active-set Newton.

Why not just…?

Why not just make the gain $\gamma$ in the gradient flow adaptive? When the flow is simulated on a computer, $\gamma$ only rescales time, and an adaptive-step ODE integrator already undoes that rescaling. An "adaptive $\gamma$" therefore mostly relabels step-size control. It would not add global guarantees beyond the strong $P$-tensor class covered by Modified gradient dynamic approach to the tensor complementarity problem. The gain matters for analog hardware, which is outside our scope. Running the flow under an adaptive integrator in our comparison tests this argument directly.

Why not just run semismooth Newton on the Fischer–Burmeister equation? This is the real threat. It is locally quadratic, generic, and may well match our wall-clock time on uniquely solvable, well-conditioned instances. What it lacks is threefold: monotone convergence from an arbitrary Z-tensor instance, control over which solution is found when several exist, and any certificate of distance to the solution. Example 5.3 of the gradient-dynamics papers was built to have multiple solutions depending on $q$, and it is the natural test. If semismooth Newton equals us in speed and reliability on the Z-tensor suite, our contribution reduces to the certificates, and we will say so.

Why not just reduce to a linear complementarity problem or unfold the tensor? Unfolding turns a degree-$(m-1)$ system into a linear one and changes its solution set. Evidence from spectral problems shows that pairwise reductions lose accuracy: A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning reports Iris error 0.117 for pairwise versus 0.094 for the tensor method. We will include a linearize-and-solve-LCP heuristic only as a sanity check on residuals.

Why not just use an exact copositivity test? Exact tests scale exponentially in general. For Z-tensors our test is exact and uses a polynomial-cost Perron computation. For other tensors it is only sufficient, and the dark-matter experiment measures how much it misses.

Proposed Experiments

We will use four instance families. The first is Examples 5.1–5.3 from the gradient-dynamics papers; we will check whether each is a Z-tensor, and use non-Z ones only for the semismooth comparison and the truncation certificate. The second is random strong $\mathcal{M}$-tensor TCPs of order 3–5 with $n$ from 10 up to 50, matching the GNNI $4\times50\times50\times50$ scale, with $q$ drawn to give mixed active sets. The third is shifted hypergraph adjacency tensors $s\mathcal{I}-\mathcal{H}$. $\mathcal{H}$ comes from the 3-uniform 1984 Congressional Voting hypergraph used in Projected Tensor Power Method for Hypergraph Community Recovery, with $s$ swept through $\rho(\mathcal{H})$ to probe the solvability boundary. The fourth is the fourth-order scalar dark-matter tensors, with analytic copositivity labels from Song & Li.

The metrics are the complementarity residual $\|\min(x,\mathcal{A}x^{m-1}+q)\|$, iterations, tensor–vector products and wall-clock time, and failure rate over random starts. We also record whether the least solution was returned and the final bracket width. For the dark-matter family we report the fraction of truly copositive instances that the certificate confirms.

Four outcomes are decisive. First, the safeguarded Newton solver should never lose monotonicity and should reach $10^{-13}$ residual in a small, $n$-insensitive number of outer iterations, while the plain iteration slows as $\rho(\mathcal{D}^{-1}\mathcal{B})\to 1$. Second, on the $s$-sweep, the certificate's switch from "solvable" to "not certified" should coincide with $s=\rho(\mathcal{H})$ to within the Collatz–Wielandt gap. Third, on multiple-solution instances, the non-closing bracket should flag non-uniqueness while semismooth Newton lands on different solutions depending on the start. Fourth, the fixed-tolerance ablation should cost measurably more inner work at equal accuracy; if it does not, the adaptive component is unnecessary and we drop it.