Loading [MathJax]/extensions/tex2jax.js

The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank

Research output: Contribution to journalArticleResearchpeer review

Authors

Research Organisations

External Research Organisations

  • University of Siegen
  • University of Cologne
  • Nederlandse Organisatie voor toegepast-natuurwetenschappelijk onderzoek (TNO)

Details

Original languageEnglish
Pages (from-to)15-32
Number of pages18
JournalLinear Algebra and Its Applications
Volume723
Early online date22 May 2025
Publication statusE-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

Cite this

The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank. / Plávala, Martin; Ligthart, Laurens T.; Gross, David.
In: Linear Algebra and Its Applications, Vol. 723, 15.10.2025, p. 15-32.

Research output: Contribution to journalArticleResearchpeer review

Download
@article{83cd8199f9fa4bfcb208b7c6208b89d2,
title = "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank",
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",
author = "Martin Pl{\'a}vala and Ligthart, {Laurens T.} and David Gross",
note = "Publisher Copyright: {\textcopyright} 2025 The Author(s)",
year = "2025",
month = may,
day = "22",
doi = "10.1016/j.laa.2025.05.019",
language = "English",
volume = "723",
pages = "15--32",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

Download

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 -

By the same author(s)