Abstract
Bi-quadratic programming over unit spheres is a fundamental problem in quantum mechanics introduced by pioneer work of Einstein, Schrödinger, and others. It has been shown to be NP-hard; so it must be solve by efficient heuristic algorithms such as the block improvement method (BIM). This paper focuses on the maximization of bi-quadratic forms, which leads to a rank-one approximation problem that is equivalent to computing the M-spectral radius and its corresponding eigenvectors. Specifically, we provide a tight upper bound of the M-spectral radius for nonnegative fourth-order partially symmetric (PS) tensors, which can be considered as an approximation of the M-spectral radius. Furthermore, we showed that the proposed upper bound can be obtained more efficiently, if the nonnegative fourth-order PS-tensors is a member of certain monoid semigroups. Furthermore, as an extension of the proposed upper bound, we derive the exact solutions of the M-spectral radius and its corresponding M-eigenvectors for certain classes of fourth-order PS-tensors. Lastly, as an application of the proposed bound, we obtain a practically testable sufficient condition for nonsingular elasticity M-tensors with strong ellipticity condition. We conduct several numerical experiments to demonstrate the utility of the proposed results. The results show that: (a) our proposed method can attain a tight upper bound of the M-spectral radius with little computational burden, and (b) such tight and efficient upper bounds greatly enhance the convergence speed of the BIM-algorithm, allowing it to be applicable for large-scale problems in applications.
Introduction
Biquadratic programming over unit spheres involves maximizing a fourth-order polynomial function $f(\mathbf{x}, \mathbf{y})$ subject to $\|\mathbf{x}\| = 1$ and $\|\mathbf{y}\| = 1$. This problem is central to various scientific domains, including quantum mechanics for entanglement detection and solid mechanics for evaluating material stability via the strong ellipticity condition. Given that this problem is NP-hard, researchers typically rely on the Block Improvement Method (BIM), an iterative algorithm. However, the efficiency of BIM is highly dependent on a "shift parameter" $\tau$. If this parameter is too loose, convergence is extremely slow; if too small, convergence is not guaranteed. This paper addresses the need for tighter, more efficient bounds for this parameter.
Methodology
The core contribution is a new method to estimate the M-spectral radius (the maximum M-eigenvalue) of fourth-order partially symmetric (PS) tensors. The researchers introduce Elasticity Structure (ES) Matrices, which are derived by "unfolding" the 4D tensor into a set of 2D symmetric matrices. By analyzing the maximum eigenvalues of these smaller matrices, a significantly tighter upper bound is obtained compared to previous entry-wise sum approaches.
Key theoretical developments include:
- Mean Elasticity Structure (MES) Matrices: Used to establish rigorous lower bounds.
- The Position Theorem: Identifies specific tensor slices that contain the spectral radius information for tensors within certain monoid semigroups.
- Optimized BIM: The tighter upper bound is integrated as the shift parameter $\tau$, reducing the spectral gap and accelerating the iterative process.
Experimental Results
The proposed methods were tested on 1,000 synthetic tensors and physical models from solid mechanics. The results consistently demonstrated that the new bound is tighter than previous state-of-the-art methods.
Convergence Acceleration
A critical finding is the massive speedup in BIM convergence. By using the tighter shift parameter, the algorithm achieves the required accuracy in significantly fewer iterations. As illustrated in the comparison below, the proposed method (red) converges in under 50 iterations, while standard parameters (black) can require over 350 iterations—representing a roughly 7x improvement in computational efficiency.
Practical Utility in Solid Mechanics
The researchers successfully applied their bound to derive a practically testable sufficient condition for the stability of elasticity tensors. This provides a robust computational tool for engineers to verify the strong ellipticity condition in complex material systems.
Conclusion
This research demonstrates that leveraging matrix-tensor duality through ES matrices provides a powerful way to handle NP-hard biquadratic optimization. The resulting tighter bounds drastically improve the performance of iterative algorithms like BIM, making them viable for large-scale applications. Future work will explore extending these bounds to tensors with negative entries and further reducing the initial computational overhead for high-dimensional data.
Summary updated