Convex hulls of monomial curves, and a sparse positivstellensatz
Mathematical Programming · 2025-01 · 209 (1-2) · 113-131
DOI: 10.1007/s10107-024-02060-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 16.02.2024. Verfasst von Gennadiy Averkov und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Brandenburgische TU Cottbus-Senftenberg.
Abstract (Originalsprache)
Consider the closed convex hull K of a monomial curve given parametrically as $$(t^{m_1},\ldots ,t^{m_n})$$ ( t m 1 , … , t m n ) , with the parameter t varying in an interval I . We show, using constructive arguments, that K admits a lifted semidefinite description by $$\mathcal {O}(d)$$ O ( d ) linear matrix inequalities (LMIs), each of size $$\left\lfloor \frac{n}{2} \right\rfloor +1$$ n 2 + 1 , where $$d= \max \{m_1,\ldots ,m_n\}$$ d = max { m 1 , … , m n } is the degree of the curve. On the dual side, we show that if a univariate polynomial p ( t ) of degree d with at most $$2k+1$$ 2 k + 1 monomials is non-negative on $${\mathbb {R}}_+$$ R + , then p admits a representation $$p = t^0 \sigma _0 + \cdots + t^{d-k} \sigma _{d-k}$$ p = t 0 σ 0 + ⋯ + t d - k σ d - k , where the polynomials $$\sigma _0,\ldots ,\sigma _{d-k}$$ σ 0 , … , σ d - k are sums of squares and $$\deg (\sigma _i) \le 2k$$ deg ( σ i ) ≤ 2 k . The latter is a univariate positivstellensatz for sparse polynomials, with non-negativity of p being certified by sos polynomials whose degree only depends on the sparsity of p . Our results fit into the general attempt of formulating polynomial optimization problems as semidefinite problems with LMIs of small size. Such small-size descriptions are much more tractable from a computational viewpoint.
Förderung
- Brandenburgische TU Cottbus-Senftenberg
Zitieren
APA
Averkov, G., & Scheiderer, C. (2025). Convex hulls of monomial curves, and a sparse positivstellensatz. Mathematical Programming, 209(1-2), 113-131. https://doi.org/10.1007/s10107-024-02060-9
Vancouver
Averkov G, Scheiderer C. Convex hulls of monomial curves, and a sparse positivstellensatz. Mathematical Programming. 2025;209(1-2):113-131. doi:10.1007/s10107-024-02060-9
BibTeX
@article{Averkov2025,
author = {Averkov, Gennadiy and Scheiderer, Claus},
title = {Convex hulls of monomial curves, and a sparse positivstellensatz},
journal = {Mathematical Programming},
year = {2025},
volume = {209},
number = {1-2},
pages = {113--131},
doi = {10.1007/s10107-024-02060-9}
}
EUVIMED