Background: Representing polynomials by positive linear functions on compact convex polyhedra by David Handelman

Consider a polynomial $f\in K[x_1,\ldots,x_n]$ in a compact polytope, related question on trying to formulate the polytope algebraically, where each variable $x_i$ is defined in some compact set such as $x_1\in [0.2,0.5]$.

Example 1: is $f$ non-negative in $K$? Yes for $f_1$, no for $f_2$.

$f_1[x_1,x_2,x_3]=x_3-x_1 x_2$


\begin{eqnarray*} x_{1} & \in & [0.2,0.5]\\ x_{2} & \in & [0,1]\\ x_{3} & \in & [1,1] \end{eqnarray*}

Example 2: is $f(x_{1},x_{2})=x_{1}-x_{2}$ positive on the polytope $K$ restricted by the intervals?

The answer is no in the example below but how do we use Handelman's theorem on this?

\begin{eqnarray*} 0.1<x_{1}<0.5 & \Leftrightarrow & x_{1}>0.1,-x_{1}>-0.5\\ 0.2<x_{2}<1 & \Leftrightarrow & x_{2}>0.2,-x_{2}>-1\\ & \Rightarrow & \begin{cases} \beta_{1}=x_{1}-0.1\\ \beta_{2}=-x_{1}+0.5\\ \beta_{3}=x_{2}-0.2\\ \beta_{4}=-x_{2}+1 \end{cases} \end{eqnarray*}

where $\{\beta_i\}=\{\beta_1,\beta_2,\beta_3,\beta_4\}$ and we guess the right "positive linear combination of products of members of $\{\beta_i\}$" (but it may not easy to come up with it)

\begin{eqnarray*} f & = & a\beta_{1}+b\beta_{2}+c\beta_{3}+d\beta_{4}\\ & = & a(x_{1}-0.1)+b(-x_{1}+0.5)+c(x_{2}-0.2)+d(-x_{2}+1)\\ & = & x_{1}(a-b)+x_{2}(c-d)+(-0.1a+0.5b-0.2c+d)\\ & \underset{f_{1}}{=} & x_{1}-x_{2}\\ & \Rightarrow & a-b=1,c-d=-1,-0.1a+0.5b-0.2c+d=0\\ & \Rightarrow & \begin{cases} b-a=c-d\\ 0.9a-0.5b+0.8c+d=0 \end{cases}\Rightarrow\begin{cases} d=c+a-b\\ 0.9a-0.5b+0.8c+d=0 \end{cases}\\ & \Rightarrow & 0.9a-0.5b+0.8c=0 \end{eqnarray*}

where the positivity actually means that $a,b,c,d\geq 0$ and all values of $a,b,c,d$ cannot be zero at the same time. Since $a-b=1\Rightarrow a=1,b=0$ (only case satisfying this). $c-d=-1$ so $c=0,d=1$ (similar as earlier). So

$$-0.1a+0.5b-0.2c+d=0 \Leftrightarrow 1+4b+8d=0$$

which cannot be true since $b,d$ are not negative. So no function $f$ exists in the basis so by Handelman's theorem f is not non-negative in the polytope restricted by the inequalities. No positive linear combination of products of members of $\{\beta_i\}$ terms can express $x_1-x_2$ so $f$ is not non-negative.

How can I computationally check the condition on the positivity?

I. Macaulay2 example with hand-on examples and trying to define the ideal for the intervals error here. Define quotient ring for the $\{\beta_i\}$ (originating from inequalities)?

i4 : f%intervals
o4 = 0
o4 : R

and verified with


i11 : f2
o11 = 0
o11 : R2

that is a contradictive result: we showed that $x_1-x_2$ on $K$ can be expressed as a positive linear combination of products of members of $\{\beta_i\}$, did we? We know by the Handelman's theorem that this should not be possible -- $x_1-x_2$ is negative when $x_1=0.1$ and $x_2=1$ so we should not be able to express it in terms of the products.

Numeric notice in dealing with numeric real values, I_0+I_2==f should be true (but false because of the small $\epsilon=-5.55112e-17$)

i35: R=RR[x1,x2];f=x1+x2-0.3;I=ideal(x1-0.1,-x1+0.5,x2-0.2,-x2+1); I_0+I_2 - f 
o34=  -5.55112e-17

so with exact arithmetics

i1 : R=RR[x1,x2];f=x1+x2-3/10;I=ideal(x1-1/10,-x1+1/2,x2-1/5,-x2+1); I_0+I_2 - f    
o3 : Ideal of R
o4 = 0
o4 : R

II. Mathematica where PolynomialReduce but cannot find a way to specify that each quotient term positive and remainder zero.

How does Handelman's Theorem work to check non-negativity of $f$ in some compact polytope?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.