5
$\begingroup$

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$

$f_2[x_1,x_2,x_3]=x_3x_2-x_1$

\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)?

R=RR[x1,x2];
f=x1-x2;
intervals=ideal(x1-0.1,-x1+0.5,x2-0.2,-x2+1);     
f%intervals
i4 : f%intervals
o4 = 0
o4 : R

and verified with

R2=RR[x1,x2]/(x1-0.1,-x1+0.5,x2-0.2,-x2+1);
f2=x1-x2

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?

$\endgroup$

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.