Convex hulls of monomial curves, and a sparse positivstellensatz

• 成果类型: Article
• 署名作者: Averkov, Gennadiy; Scheiderer, Claus
• 署名单位: Brandenburg University of Technology Cottbus; University of Konstanz
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02060-9
• 发表日期: 2025
• 页码: 113-131
• 关键词: moment-sos hierarchy; POLYNOMIALS; optimization; tssos

摘要

Consider the closed convex hull K of a monomial curve given parametrically as (tm1, horizontal ellipsis ,tmn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(t<^>{m_1},\ldots ,t<^>{m_n})$$\end{document}, with the parameter t varying in an interval I. We show, using constructive arguments, that K admits a lifted semidefinite description by O(d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(d)$$\end{document} linear matrix inequalities (LMIs), each of size n2+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left\lfloor \frac{n}{2} \right\rfloor +1$$\end{document}, where d=max{m1, horizontal ellipsis ,mn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d= \max \{m_1,\ldots ,m_n\}$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2k+1$$\end{document} monomials is non-negative on R+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}_+$$\end{document}, then p admits a representation p=t0 sigma 0+MIDLINE HORIZONTAL ELLIPSIS+td-k sigma d-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p = t<^>0 \sigma _0 + \cdots + t<^>{d-k} \sigma _{d-k}$$\end{document}, where the polynomials sigma 0, horizontal ellipsis ,sigma d-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma _0,\ldots ,\sigma _{d-k}$$\end{document} are sums of squares and deg(sigma i)<= 2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg (\sigma _i) \le 2k$$\end{document}. 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.