Spectral Methods for Polynomial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912496506372096 |
|---|---|
| author | Moreno, Elvira Chandrasekaran, Venkat |
| author_facet | Moreno, Elvira Chandrasekaran, Venkat |
| contents | We present a hierarchy of tractable relaxations to obtain lower bounds on the minimum value of a polynomial over a constraint set defined by polynomial equations. In contrast to previous convex relaxation techniques for this problem, our method is based on computing the smallest generalized eigenvalue of a pair of matrices derived from the problem data, which can be accomplished for large problem instances using off-the-shelf software. We characterize the algebraic structure in a problem that facilitates the application of our framework, and we observe that our method is applicable for all polynomial optimization problems with bounded constraint sets. Our construction also yields a nested sequence of structured convex outer approximations of a bounded algebraic variety with the property that linear optimization over each approximation reduces to an eigenvalue computation. Finally, we present numerical experiments on representative problems in which we demonstrate the scalability of our approach compared to convex relaxation methods derived from sums-of-squares certificates of nonnegativity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral Methods for Polynomial Optimization Moreno, Elvira Chandrasekaran, Venkat Optimization and Control We present a hierarchy of tractable relaxations to obtain lower bounds on the minimum value of a polynomial over a constraint set defined by polynomial equations. In contrast to previous convex relaxation techniques for this problem, our method is based on computing the smallest generalized eigenvalue of a pair of matrices derived from the problem data, which can be accomplished for large problem instances using off-the-shelf software. We characterize the algebraic structure in a problem that facilitates the application of our framework, and we observe that our method is applicable for all polynomial optimization problems with bounded constraint sets. Our construction also yields a nested sequence of structured convex outer approximations of a bounded algebraic variety with the property that linear optimization over each approximation reduces to an eigenvalue computation. Finally, we present numerical experiments on representative problems in which we demonstrate the scalability of our approach compared to convex relaxation methods derived from sums-of-squares certificates of nonnegativity. |
| title | Spectral Methods for Polynomial Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.16272 |