Bit-complexity estimates in geometric programming, and application to the polynomial-time computation of the spectral radius of nonnegative tensors

Shmuel Friedland, Stéphane Gaubert

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.

Table of contents highlighting the diverse applications of the proposed bit-complexity estimates, including hypergraphs and posynomial maps.

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

Abstract

We consider a geometric programming problem consisting in minimizing a function given by the supremum of finitely many log-Laplace transforms of discrete nonnegative measures on a Euclidean space. Under a coerciveness assumption, we show that a $\varepsilon$-minimizer can be computed in a time that is polynomial in the input size and in $|\log\varepsilon|$. This is obtained by establishing bit-size estimates on approximate minimizers and by applying the ellipsoid method. We also derive polynomial iteration complexity bounds for the interior point method applied to the same class of problems. We deduce that the spectral radius of a partially symmetric, weakly irreducible nonnegative tensor can be approximated within $\varepsilon$ error in poly-time. For strongly irreducible tensors, we also show that the logarithm of the positive eigenvector is poly-time computable. Our results also yield that the the maximum of a nonnegative homogeneous $d$-form in the unit ball with respect to $d$-H\"older norm can be approximated in poly-time. In particular, the spectral radius of uniform weighted hypergraphs and some known upper bounds for the clique number of uniform hypergraphs are poly-time computable.
BibTeX
@misc{friedland2023bit,
  author = {Shmuel Friedland and Stéphane Gaubert},
  title = {{Bit-complexity estimates in geometric programming, and application to the polynomial-time computation of the spectral radius of nonnegative tensors}},
  year = {2023},
  eprint = {2301.10637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.10637},
}
Figure