EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Convex hulls of monomial curves, and a sparse positivstellensatz

Gennadiy Averkov, Claus Scheiderer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →