The link between $1$-norm approximation and effective Positivstellensatze for the hypercube
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916529304502272 |
|---|---|
| author | de Klerk, Etienne Lizcano, Juan Vera |
| author_facet | de Klerk, Etienne Lizcano, Juan Vera |
| contents | The Schmüdgen's Positivstellensatz gives a certificate to verify positivity of a strictly positive polynomial $f$ on a compact, basic, semi-algebraic set $\mathbf{K} \subset \mathbb{R}^n$. A Positivstellensatz of this type is called effective if one may bound the degrees of the polynomials appearing in the certificate in terms of properties of $f$. If $\mathbf{K} = [-1,1]^n$ and $0 < f_\min := \min_{x \in \mathbf{K}} f(x)$, then the degrees of the polynomials appearing in the certificate may be bounded by $O\left(\sqrt{\frac{f_\max - f_\min}{f_\min}}\right)$, where $f_\max := \max_{x \in \mathbf{K}} f(x)$, as was recently shown by Laurent and Slot [Optimization Letters 17:515-530, 2023]. The big-O notation suppresses dependence on $n$ and the degree $d$ of $f$. In this paper we show a similar result, but with a better dependence on $n$ and $d$. In particular, our bounds depend on the $1$-norm of the coefficients of $f$, that may readily be calculated. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04190 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The link between $1$-norm approximation and effective Positivstellensatze for the hypercube de Klerk, Etienne Lizcano, Juan Vera Optimization and Control 90C23, 90C22 The Schmüdgen's Positivstellensatz gives a certificate to verify positivity of a strictly positive polynomial $f$ on a compact, basic, semi-algebraic set $\mathbf{K} \subset \mathbb{R}^n$. A Positivstellensatz of this type is called effective if one may bound the degrees of the polynomials appearing in the certificate in terms of properties of $f$. If $\mathbf{K} = [-1,1]^n$ and $0 < f_\min := \min_{x \in \mathbf{K}} f(x)$, then the degrees of the polynomials appearing in the certificate may be bounded by $O\left(\sqrt{\frac{f_\max - f_\min}{f_\min}}\right)$, where $f_\max := \max_{x \in \mathbf{K}} f(x)$, as was recently shown by Laurent and Slot [Optimization Letters 17:515-530, 2023]. The big-O notation suppresses dependence on $n$ and the degree $d$ of $f$. In this paper we show a similar result, but with a better dependence on $n$ and $d$. In particular, our bounds depend on the $1$-norm of the coefficients of $f$, that may readily be calculated. |
| title | The link between $1$-norm approximation and effective Positivstellensatze for the hypercube |
| topic | Optimization and Control 90C23, 90C22 |
| url | https://arxiv.org/abs/2404.04190 |