0
$\begingroup$

Context: I am trying to code a function in Mathematica by which I can check whether a polynomial is non-negative in some compact polytope such as specified by interval values for each variable. This is very much relevant to this publication here on Handelman's theorem. Relevant problems here with focus on Mathematics and here with focus on programming.

Consider a polynomial. Can we make Mathematica to return terms in PolynomialReduce command such that each term is positive and remainder zero otherwise alert that no solution?

How to find the positive linear combination of products of members of $\{\beta_i\}$ for a polynomial $f$ where each $\beta_i$ corresponds to a constraint on variables of $f$?

Example

I need to find out a way to specify to Mathematica that each term must be positive in the return.

The third term $-x_1$ is negative because $0.2\leq x_1\leq 0.5$. We transform the inequalities to linear form and then try to apply the Handelman's theorem, originally also inequality $0\leq x_2\leq 1$ and $x_3=1$

PolynomialReduce[
 x3 - x1*x2 - 2, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1, 
  x3 - 1, -x3 + 1}, {x1, x2, x3}]
PolynomialReduce[
 x3 - x1*x2, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1, x3 - 1, -x3 + 1}, {x1,
   x2, x3}]
PolynomialReduce[
 x3 - x1*x2 - 1, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1, 
  x3 - 1, -x3 + 1}, {x1, x2, x3}]

and its picture, where the result of PolynomialReduce cannot be used because of the negative terms. The Handelman requires to find positive linear combination of products of members of $\{\beta_i\}$ where $\beta_i$ terms are the linearised form of each inequality.

$\endgroup$
  • 3
    $\begingroup$ (1) Actual code is much better than an image of code. (2) You should recheck documentation for PolynomialReduce. Giving a pair of polynomials such as x-1/5,x-1/2 is tantamount to stating that 1 is in the ideal. (3) Almost certainly it is the wrong tool for this situation. Some form of quantifier elimination might be needed. $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 17:01
  • $\begingroup$ Re, "compact polytope" - polytopes are compact by definition. $\endgroup$ – alancalvitti Aug 2 '16 at 17:13
  • 1
    $\begingroup$ Polytopes can be unbounded. $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 17:29
  • 2
    $\begingroup$ Compact means bounded, yes, Also means weak inequalities, that is to say, it includes its boundary. $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 21:02
  • 1
    $\begingroup$ Think of PolynomialReduce as working on equations (it most certainly does not deal with inequalities). If you have equations {x==1/5,x==1/2} then your ideal contains 1: In[435]:= GroebnerBasis[{x == 1/5, x == 1/2}, x] Out[435]= {1} $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 21:08
1
$\begingroup$

One way to check whether a polynomial can go negative on a polytope is to find the minimum. In this case it can be as small as -3/2.

Minimize[{x3 - x1*x2 - 2, {1/5 <= x1 <= 1/2, 0 <= x2 <= 1, 
   x3 == 1}}, {x1, x2, x3}]

(* Out[434]= {-(3/2), {x1 -> 1/2, x2 -> 1, x3 -> 1}} *)
$\endgroup$
  • $\begingroup$ How can you solve the non-negativity with some algebraic geometric method without minimizing directly? See Example 2 where each inequality corresponds to a product term $\beta_i$ to form the set $\{\beta_i\}$. The problem is to find $f=a_1\beta_1+\ldots+a_n\beta_n$ where remainder is zero to use the Handelman's theorem without minimizing the function directly. $\endgroup$ – hhh Aug 2 '16 at 21:26
  • 1
    $\begingroup$ My point is simply that it will be very difficult to write it as a nonnegative sum on that polytope, since it happens not to be nonnegative thereon. $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 21:46
  • $\begingroup$ Prof. Handelman sees in terms of product of simplices (apparently simplicial complexes) & aff equivalance here: "if the polytope is not so equivalent, then the positivity condition is much more difficult" -- he refers to his more recent publication but I cannot understand it: what is "praise" in title "In praise of order units"? They show that ordered rings associated to compact convex polyhedra with interior satisfy a positivity property known as order unit cancellation. Can you understand how this could be used for algebraic geometric solution? $\endgroup$ – hhh Aug 2 '16 at 22:02
  • 1
    $\begingroup$ This area is not familiar to me. $\endgroup$ – Daniel Lichtblau Aug 2 '16 at 22:14
  • 1
    $\begingroup$ (1) I don't follow that at all. A polynomial can be positive on some part of a polytope and negative on other parts, hence is neither positive nor negative everywhere. (2) If the idea is to split the polynomial into a difference of two positive parts, it won't work. Reason: there must be points where it is zero, and existence of such points means Handelman's result does not apply (hypotheses are not met). $\endgroup$ – Daniel Lichtblau Aug 4 '16 at 15:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.