Vol. 12, No. 1, 2019

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Addresses Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
On the complexity of detecting positive eigenvectors of nonlinear cone maps

Bas Lemmens and Lewis White

Vol. 12 (2019), No. 1, 141–150
Abstract

In recent work with Lins and Nussbaum, the first author gave an algorithm that can detect the existence of a positive eigenvector for order-preserving homogeneous maps on the standard positive cone. The main goal of this paper is to determine the minimum number of iterations this algorithm requires. It is known that this number is equal to the illumination number of the unit ball ${B}_{v}$ of the variation norm, $\parallel x{\parallel }_{v}:=\underset{i}{max}{x}_{i}-\underset{i}{min}{x}_{i}$ on ${V}_{0}:=\left\{x\in {ℝ}^{n}:{x}_{n}=0\right\}$. In this paper we show that the illumination number of ${B}_{v}$ is equal to $\left(\genfrac{}{}{0}{}{n}{⌈n∕2⌉}\right)$, and hence provide a sharp lower bound for the running time of the algorithm.

Keywords
nonlinear maps on cones, positive eigenvectors, illumination problem, Hilbert's metric
Mathematical Subject Classification 2010
Primary: 47H07, 47H09
Secondary: 37C25