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$
8
  • 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$ Aug 2, 2016 at 17:01
  • $\begingroup$ Re, "compact polytope" - polytopes are compact by definition. $\endgroup$ Aug 2, 2016 at 17:13
  • 1
    $\begingroup$ Polytopes can be unbounded. $\endgroup$ Aug 2, 2016 at 17:29
  • 2
    $\begingroup$ Compact means bounded, yes, Also means weak inequalities, that is to say, it includes its boundary. $\endgroup$ Aug 2, 2016 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$ Aug 2, 2016 at 21:08

1 Answer 1

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$
7
  • $\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, 2016 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$ Aug 2, 2016 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, 2016 at 22:02
  • 1
    $\begingroup$ This area is not familiar to me. $\endgroup$ Aug 2, 2016 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$ Aug 4, 2016 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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