On the complexity of detecting positive eigenvectors of nonlinear cone maps (Q1639628)

A map \(f\) on the nonnegative orthant \(\mathbb{R}^n_+\) of the \(n\)-dimensional real Euclidean space is called \textit{order-preserving} if \(f(x) \leq f(y)\) whenever \(x \leq y\) (note that both \(x\) and \(y\) are nonnegative). Here, \(x \leq y\) is used to denote the fact that \(y-x \in \mathbb{R}^n_+\). \(f\) is said to be \textit{homogeneous} if \(f(\lambda x)=\lambda f(x)\) for all \(\lambda \geq 0\) and \(x \in \mathbb{R}^n_+\). Recently, the first author in a joint work with \textit{B. Lins} and \textit{R. Nussbaum} [Isr. J. Math. 224, 231--262 (2018; Zbl 1420.47020)] presented an algorithm to detect the existence of a positive eigenvector (a vector each of whose coordinates is positive) for continuous order-preserving homogeneous maps on the nonnegative orthant. In the present work, the authors show that the minimum number of iterations that this algorithm requires is equal to the so-called illumination number of the unit ball corresponding to the \textit{variation norm}. This number is determined here and provides a sharp lower bound for the running time of the algorithm.