Details
Original language | English |
---|---|
Pages (from-to) | 15-32 |
Number of pages | 18 |
Journal | Linear Algebra and Its Applications |
Volume | 723 |
Early online date | 22 May 2025 |
Publication status | E-pub ahead of print - 22 May 2025 |
Abstract
We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of C⁎-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
Keywords
- De Finetti theorem, General probabilistic theories (GPTs), Nonnegative matrix rank, Polynomial optimization
ASJC Scopus subject areas
- Mathematics(all)
- Algebra and Number Theory
- Mathematics(all)
- Numerical Analysis
- Mathematics(all)
- Geometry and Topology
- Mathematics(all)
- Discrete Mathematics and Combinatorics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Linear Algebra and Its Applications, Vol. 723, 15.10.2025, p. 15-32.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank
AU - Plávala, Martin
AU - Ligthart, Laurens T.
AU - Gross, David
N1 - Publisher Copyright: © 2025 The Author(s)
PY - 2025/5/22
Y1 - 2025/5/22
N2 - We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of C⁎-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
AB - We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of C⁎-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
KW - De Finetti theorem
KW - General probabilistic theories (GPTs)
KW - Nonnegative matrix rank
KW - Polynomial optimization
UR - http://www.scopus.com/inward/record.url?scp=105007139810&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2025.05.019
DO - 10.1016/j.laa.2025.05.019
M3 - Article
AN - SCOPUS:105007139810
VL - 723
SP - 15
EP - 32
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
SN - 0024-3795
ER -