¿Nos podemos probar si un polinomio tiene sólo valores no negativos en el orthant no negativo?

Question

EDIT: Siéntase libre de reemplazar "no negativo sobre la no-negativo orthant" con "no-negativo sobre un conjunto convexo, de cono o de cualquier otra clase de conjuntos que incluye la orthant".

Una forma popular para establecer que un polinomio sólo se lleva a no valores negativos, o no es negativo, es comprobar si se puede expresar como una suma de cuadrados. Esto puede hacerse numéricamente utilizando algunos convexo programa.

Sin embargo, como se discutió en aquí, hay muchos polinomios que son no-negativos, pero no puede ser expresado como una suma de cuadrados. Además, muchos de los polinomios que no son no-negativos en todas partes son no negativos sobre la no-negativo orthant, por ejemplo, cualquier extraño polinomio con coeficientes positivos.

Mis preguntas son (siento que se superponen un poco):

$1$- Lo que se conoce acerca de los polinomios con coeficientes reales, $f:\mathbb{R}^n\rightarrow\mathbb{R}$, que satisfacen

$$x\in\{y\in\mathbb{R}^n:y_i\geq 0\quad\forall i=1,\dots,n\}\Rightarrow f(x)\geq0?$$

$2$- Manejable formas de comprobar si un determinado polinomio que satisface la anterior?

Gracias de antemano.

Answer 1

Es posible llegar a un computacionalmente tratable$-$suficiente, pero no necesaria$-$ensayo.

Podemos reformular "¿el polinomio $f$ devolver siempre un no número real negativo cuando se evaluó sobre la no-negativo orthant?" como "es el conjunto semialgebraic

$$\{x\in\mathbb{R}^n:f(x)<0,x_1\geq0,x_2\geq0,\dots,x_n\geq0\}$$

vacía?". Como se discutió en aquí, una suficiente prueba de si el conjunto de$-$o, de hecho, si cualquier semialgebraic set$-$está vacía puede ser llevado a cabo en el polinomio de tiempo. Voy a resumir rápidamente la idea principal:

Considere el siguiente teorema demostrado por Stengle en 1974:

---

Teorema (Stengle del Positivstellensatz). Deje $\{f_j\},\{g_k\},\{h_l\}\subseteq\mathbb{R}[x_1,x_2\dots,x_n]$ finita de conjuntos de polinomios con verdaderos valores de los coeficientes. Deje $P$ ser el cono generado por $\{f_j\}$, $M$ el multiplicativo monoid generado por $\{g_k\}$, e $I$ el ideal generado por $\{h_l\}$$-$para definiciones precisas, consulte la Sección 4 del documento. A continuación,

$$\{x\in\mathbb{R}^n : f_j(x)\geq 0,\quad g_k(x)\neq 0,\quad h_l(x)=0, \quad\quad\forall (i,j,k\}$$

es vacío si y sólo si existe $f\in P$, $g\in M$ y, $h\in I$ tal que $f+g^2+h=0$.

---

El triplete $(f,g,h)$ se llama una inviabilidad certificado o una refutación. Como se discutió en la sección 5 del documento, una condición suficiente para la existencia de dichos certificados es que un determinado semidefinite programa es viable$-$esto realmente se basa en la herramienta mencionada en la pregunta que puede poner a prueba si un polinomio es una suma de cuadrados. Una vez que el programa está solucionado, el certificado puede ser recuperado de su solución. Incluso hay un libre Matlab paquete que ha sido desarrollado exclusivamente para este propósito.

---

De LADO: Esta es la primera vez que me he respondido a mi propia pregunta. Me encontré con el de arriba un poco después de la publicación de la pregunta y pensé que valía la pena mencionar en caso de que sea de alguna utilidad para alguien más.