Loading [MathJax]/extensions/tex2jax.js

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

Publikation: Beitrag in FachzeitschriftArtikelForschungPeer-Review

Autorschaft

Organisationseinheiten

Externe Organisationen

  • Universität Siegen
  • Universität zu Köln
  • Niederländische Organisation für Angewandte Naturwissenschaftliche Forschung (TNO)

Details

OriginalspracheEnglisch
Seiten (von - bis)15-32
Seitenumfang18
FachzeitschriftLinear Algebra and Its Applications
Jahrgang723
Frühes Online-Datum22 Mai 2025
PublikationsstatusElektronisch veröffentlicht (E-Pub) - 22 Mai 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.

ASJC Scopus Sachgebiete

Zitieren

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, Jahrgang 723, 15.10.2025, S. 15-32.

Publikation: Beitrag in FachzeitschriftArtikelForschungPeer-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 -

Von denselben Autoren