Complexity of Geometric programming in the Turing model and application to nonnegative tensors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912409713639424 |
|---|---|
| author | Friedland, Shmuel Gaubert, Stéphane |
| author_facet | Friedland, Shmuel Gaubert, Stéphane |
| contents | We consider a version of geometric programming problem consisting in minimizing a function given by the maximum of finitely many log-Laplace transforms of discrete nonnegative measures on a Euclidean space. Under a coerciveness assumption, we show that an $\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 an $\varepsilon$-error in polynomial time. For strongly irreducible tensors, we show in addition that the logarithm of the positive eigenvector is polynomial time approximable. Our results also yield that the the maximum of a nonnegative homogeneous $d$-form in the $\ell_d$ unit ball can be approximated in polynomial time. In particular, the spectral radius of uniform weighted hypergraphs and some known upper bounds for the clique number of uniform hypergraphs are polynomial time computable. In contrast, we provide an example showing that the Phase I approach needs exponentially many bits to solve the feasibility problem in geometric programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_10637 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity of Geometric programming in the Turing model and application to nonnegative tensors Friedland, Shmuel Gaubert, Stéphane Optimization and Control Computational Complexity 05C50, 05C65, 15A69, 68W25, 90C25 We consider a version of geometric programming problem consisting in minimizing a function given by the maximum of finitely many log-Laplace transforms of discrete nonnegative measures on a Euclidean space. Under a coerciveness assumption, we show that an $\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 an $\varepsilon$-error in polynomial time. For strongly irreducible tensors, we show in addition that the logarithm of the positive eigenvector is polynomial time approximable. Our results also yield that the the maximum of a nonnegative homogeneous $d$-form in the $\ell_d$ unit ball can be approximated in polynomial time. In particular, the spectral radius of uniform weighted hypergraphs and some known upper bounds for the clique number of uniform hypergraphs are polynomial time computable. In contrast, we provide an example showing that the Phase I approach needs exponentially many bits to solve the feasibility problem in geometric programming. |
| title | Complexity of Geometric programming in the Turing model and application to nonnegative tensors |
| topic | Optimization and Control Computational Complexity 05C50, 05C65, 15A69, 68W25, 90C25 |
| url | https://arxiv.org/abs/2301.10637 |