Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.25033 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914512923262976 |
|---|---|
| author | Khajavirad, Aida |
| author_facet | Khajavirad, Aida |
| contents | We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of variables that attain binary values at optimality and shows how the remaining continuous variables can be eliminated locally when they appear in small, weakly coupled blocks, yielding a reduction to a structured binary optimization problem that can be solved efficiently. Our result extends the classical tractability result for binary polynomial optimization, namely, that problems with bounded treewidth are solvable in polynomial time, to box-constrained polynomial optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25033 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A polynomial-time solvable class of sparse box-constrained polynomial optimization problems Khajavirad, Aida Optimization and Control We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of variables that attain binary values at optimality and shows how the remaining continuous variables can be eliminated locally when they appear in small, weakly coupled blocks, yielding a reduction to a structured binary optimization problem that can be solved efficiently. Our result extends the classical tractability result for binary polynomial optimization, namely, that problems with bounded treewidth are solvable in polynomial time, to box-constrained polynomial optimization. |
| title | A polynomial-time solvable class of sparse box-constrained polynomial optimization problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.25033 |