Introduction
Geometric Programming (GP) serves as a cornerstone for optimization in diverse fields, ranging from circuit design to statistical modeling. While GP is traditionally considered "efficiently solvable" in a continuous arithmetic model, its complexity within the Turing model—which accounts for bit-size representations and precision—has historically been less defined. This paper addresses this gap by establishing bit-complexity estimates for a broad class of GP problems and applying these results to the spectral theory of nonnegative tensors.
Geometric Programming and the Ellipsoid Method
The authors consider a GP problem formulated as the minimization of a function $f$, defined as the supremum of finitely many log-Laplace transforms of discrete nonnegative measures. The central challenge in the Turing model is determining the "search space" size: how many bits are required to represent an $\varepsilon$-minimizer?
To solve this, the paper introduces a coercivity constant $\nu$. This constant quantifies the growth of the objective function as the input vector approaches infinity. By establishing explicit bit-size bounds based on $\nu$, the authors demonstrate that the ellipsoid method can compute an $\varepsilon$-minimizer in time polynomial in the input size and $|\log \varepsilon|$. Furthermore, the paper provides iteration complexity bounds for Interior-Point Methods (IPM) applied to these minimax problems, bridging the gap between theoretical complexity and practical optimization algorithms.
Spectral Radius of Nonnegative Tensors
A significant application of these GP results lies in the study of nonnegative tensors. The spectral radius $\rho(F)$ of a tensor is a generalization of the largest eigenvalue of a matrix. While computing the spectral radius is NP-hard in general, the authors prove that for weakly irreducible nonnegative tensors, $\rho(F)$ can be approximated within $\varepsilon$ in polynomial time.
The Logarithmic Loophole
A key insight involves the representation of eigenvectors. In the tensor setting, the coordinates of an eigenvector can grow doubly exponentially relative to the input size. This makes it impossible to represent the eigenvector itself in polynomial time. However, the authors observe that the logarithm of these coordinates remains well-behaved. Consequently, while the eigenvector is elusive, the log-eigenvector is poly-time computable for strongly irreducible tensors.
Applications to Hypergraphs and Homogeneous Forms
The theoretical framework extends to several combinatorial and algebraic problems. The paper demonstrates that the maximum of a nonnegative homogeneous $d$-form over a unit ball (with respect to the $d$-Hölder norm) is polynomial-time computable. This result has direct implications for bounding the clique number of uniform hypergraphs and analyzing higher-order Markov chains.
Limitations and Open Questions
Despite the positive results for coercive functions, the general feasibility problem for GP remains an open challenge. The authors show that the "Phase I" approach (finding a feasible starting point) can require an exponential number of bits in certain cases, suggesting that feasibility testing may be intrinsically harder than optimization once a feasible point is known. Additionally, while iteration bounds for IPMs are established, the full bit-complexity of the rounding steps in each iteration requires further investigation to be definitively placed within the class P.
Summary updated