On the maxmin-ω eigenspaces and their over-approximation by zones

Maxmin-ω dynamical systems were previously introduced as a generalization of dynamical systems expressed by tropical linear algebra. To describe steady states of such systems, one has to study an eigenproblem of the form A ⊗_ω x = λ + x where ⊗_ω is the maxmin-ω matrix-vector multiplication. This eigenproblem can be viewed in a more general framework of nonlinear Perron-Frobenius theory. However, instead of studying these eigenspaces directly, we develop a different approach: over-approximation by zones. These are traditionally convex sets of a special kind, which have proved highly useful in computer science and are also relevant to tropical convexity. We first construct a sequence of zones over-approximating a maxmin-ω eigenspace. Next, the limit of this sequence is refined in a heuristic procedure, which yields a refined zone and also the eigenvalue λ with a high success rate. Based on the numerical experiments, in successful cases, there is a column of the difference-bound matrix (DBM) representation of the refined zone that yields an eigenvector.