ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 08 Jun 2019 13:20:07 +0200positive values of polynomialshttps://ask.sagemath.org/question/46829/positive-values-of-polynomials/Let $p$ be a quadratic multivariate polynomial in Sage, for example
sage: R.<x,y,z> = QQ[]
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: q = -x^2 - y^2 - z^2 + 3/2 * (x*y + x*z + y*z)
I want to test whether there exists a vector $(a,b,c)$ with positive entries such that $p(a,b,c) > 0$. With the above examples the answer is no for $p$ and yes for $q$ since $q(1,1,1) = 3/2$. Is there a way to achieve that in SageMath? It is a very particular instance of non-linear optimization but did not find anything relevant.Thu, 06 Jun 2019 11:29:44 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/Comment by FrédéricC for <p>Let $p$ be a quadratic multivariate polynomial in Sage, for example</p>
<pre><code>sage: R.<x,y,z> = QQ[]
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: q = -x^2 - y^2 - z^2 + 3/2 * (x*y + x*z + y*z)
</code></pre>
<p>I want to test whether there exists a vector $(a,b,c)$ with positive entries such that $p(a,b,c) > 0$. With the above examples the answer is no for $p$ and yes for $q$ since $q(1,1,1) = 3/2$. Is there a way to achieve that in SageMath? It is a very particular instance of non-linear optimization but did not find anything relevant.</p>
https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46832#post-id-46832Et dans QuadraticForm ?Thu, 06 Jun 2019 14:58:24 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46832#post-id-46832Comment by vdelecroix for <p>Let $p$ be a quadratic multivariate polynomial in Sage, for example</p>
<pre><code>sage: R.<x,y,z> = QQ[]
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: q = -x^2 - y^2 - z^2 + 3/2 * (x*y + x*z + y*z)
</code></pre>
<p>I want to test whether there exists a vector $(a,b,c)$ with positive entries such that $p(a,b,c) > 0$. With the above examples the answer is no for $p$ and yes for $q$ since $q(1,1,1) = 3/2$. Is there a way to achieve that in SageMath? It is a very particular instance of non-linear optimization but did not find anything relevant.</p>
https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46833#post-id-46833Sadly, the restriction to positive vectors $(a,b,c)$ is not the kind of things considered with QuadraticForm...Thu, 06 Jun 2019 18:32:06 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46833#post-id-46833Comment by dan_fulea for <p>Let $p$ be a quadratic multivariate polynomial in Sage, for example</p>
<pre><code>sage: R.<x,y,z> = QQ[]
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: q = -x^2 - y^2 - z^2 + 3/2 * (x*y + x*z + y*z)
</code></pre>
<p>I want to test whether there exists a vector $(a,b,c)$ with positive entries such that $p(a,b,c) > 0$. With the above examples the answer is no for $p$ and yes for $q$ since $q(1,1,1) = 3/2$. Is there a way to achieve that in SageMath? It is a very particular instance of non-linear optimization but did not find anything relevant.</p>
https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46857#post-id-46857Something like this is helpful in the given situation?
sage: b = lambda k: lambda c: c[k]
sage: q = lambda c: -( -c[0]^2 - c[1]^2 - c[2]^2 + 3/2 * (c[0]*c[1] + c[1]*c[2] + c[2]*c[0]) )
sage: p = lambda c: -( -c[0]^2 - c[1]^2 - c[2]^2 + 1 * (c[0]*c[1] + c[1]*c[2] + c[2]*c[0]) )
sage: mq = minimize_constrained( q, [b(0), b(1), b(2)], [2019, 2019, 2019] )
sage: mp = minimize_constrained( p, [b(0), b(1), b(2)], [2019, 2019, 2019] )
sage: q(mq), p(mp)
(-10049449.023793787, 1.4901161193847656e-08)
(There is no `maximize_constrained` for whatever reason, so i had to take the opposite of the objective function, then go to `minimize_constrained`. The starting point was taken far away, instead of the 0, 0, 0 point for the obvious reason.)Fri, 07 Jun 2019 19:30:46 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46857#post-id-46857Answer by Juanjo for <p>Let $p$ be a quadratic multivariate polynomial in Sage, for example</p>
<pre><code>sage: R.<x,y,z> = QQ[]
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: q = -x^2 - y^2 - z^2 + 3/2 * (x*y + x*z + y*z)
</code></pre>
<p>I want to test whether there exists a vector $(a,b,c)$ with positive entries such that $p(a,b,c) > 0$. With the above examples the answer is no for $p$ and yes for $q$ since $q(1,1,1) = 3/2$. Is there a way to achieve that in SageMath? It is a very particular instance of non-linear optimization but did not find anything relevant.</p>
https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?answer=46858#post-id-46858<p>From the examples in the O.P., I assume that we are dealing with homogeneous quadratic polynomials, that is, with quadratic forms.</p>
<p>Let us state the problem: given a quadratic form <span class="math">\(p\)</span> in <span class="math">\(\mathbb{R}^n\)</span>, determine the truth value of the proposition</p>
<blockquote>
<p>(<em>P</em>) there exists <span class="math">\(\mathbf{x}\in\mathbb{R}_+^n\)</span> such that <span class="math">\(p(\mathbf{x})>0\)</span>.</p>
</blockquote>
<p>Here, <span class="math">\(\mathbb{R}_+\)</span> stands for the set of positive real numbers. One can apply, at least, one of the following tests:</p>
<p><strong>Test 1</strong>. Let <span class="math">\(A\)</span> be the symmetric matrix associated to <span class="math">\(p\)</span>, i.e., <span class="math">\(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\)</span>. Compute the eigenvalues of <span class="math">\(A\)</span>. If all the eigenvalues are less than or equal to <span class="math">\(0\)</span>, then (<em>P</em>) is false. If there exists a positive eigenvalue <span class="math">\(\lambda\)</span> with an associated eigenvector <span class="math">\(\mathbf{v}\in\mathbb{R}_+^n\)</span>, then (<em>P</em>) is true.</p>
<p>Note that this test does not cover all the possibilities, since it only checks sufficient conditions.</p>
<p><strong>Test 2</strong>. Compute the maximum of <span class="math">\(p\)</span> on the set <span class="math">\(D=[0,1]^n\)</span>. Then (<em>P</em>) is true if and only if such a maximum is positive.</p>
<p>Test 1 can be implemented through the <code>eigenvalues()</code> and <code>eigenvectors_right()</code> methods for matrices. Test 2 can use the <code>minimize_constrained</code> function, already presented in @dan_fulea’s answer. Please note that maximize <span class="math">\(p\)</span> is equivalent to minimize <span class="math">\(-p\)</span>.</p>
<p>Let us apply them to the given polynomials.</p>
<p><strong>Example 1</strong>. Let <span class="math">\(p=-x^2 - y^2 - z^2 + xy + xz + yz\)</span>. We apply Test 1:</p>
<pre><code>sage: var("x,y,z");
sage: A = matrix([[-1,1/2,1/2],[1/2,-1,1/2],[1/2,1/2,-1]])
sage: A.eigenvalues()
[0, -3/2, -3/2]
</code></pre>
<p>By Test 1, (<em>P</em>) is false, since all the eigenvalues are less than or equal to <span class="math">\(0\)</span>. We could also apply Test 2:</p>
<pre><code>sage: var("x,y,z");
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: sol = minimize_constrained(-p, [[0,1]]*3, [0.1,0.9,0.5])
sage: print "Maximum is", p(*sol), "attained at", sol
Maximum is 0.0 attained at (0.4999999998931121, 0.5000000001068878, 0.5)
</code></pre>
<p>Since the maximum is not greater than <span class="math">\(0\)</span>, by Test 2, (<em>P</em>) is false.
The second argument of <code>minimize_constrained</code> is a list of the intervals where <span class="math">\(x\)</span>, <span class="math">\(y\)</span> and <span class="math">\(z\)</span> should be, that is, <span class="math">\([0,1]\)</span> for each variable. The last argument is a starting point of the iterative minimization process. In this example, if we take a different starting point, the maximum is also <span class="math">\(0\)</span>, but it can be reached at a different point (<span class="math">\(p\)</span> is <span class="math">\(0\)</span> on the line <span class="math">\(x=y=z\)</span>).</p>
<p><strong>Example 2</strong>. Let <span class="math">\(q= -x^2 - y^2 - z^2 + (3/2)(xy + xz + yz)\)</span>. We first use Test 1:</p>
<pre><code>sage: var("x,y,z");
sage: A = matrix([[-1,3/4,3/4],[3/4,-1,3/4],[3/4,3/4,-1]])
sage: A.eigenvalues()
[1/2, -7/4, -7/4]
sage: A.eigenvectors_right()
[(1/2, [(1, 1, 1)], 1), (-7/4, [(1, 0, -1), (0, 1, -1)], 2)]
</code></pre>
<p>The matrix <span class="math">\(A\)</span> has one positive eigenvalue, <span class="math">\(\lambda=1/2\)</span>, with an associated
eigenvector <span class="math">\(\mathbf{v}=(1,1,1)\)</span> belonging to <span class="math">\(\mathbb{R}_+^n\)</span>. Hence, (<em>P</em>) is true. Let us now apply Test 2:</p>
<pre><code>sage: var("x,y,z");
sage: q = -x^2 - y^2 - z^2 + (3/2)*(x*y + x*z + y*z)
sage: sol = minimize_constrained(-q,[[0,1]]*3, [0.1,0.9,0.5])
sage: print "Maximum is", q(*sol), "attained at", sol
Maximum is 1.5 attained at (1.0, 1.0, 1.0)
</code></pre>
<p>Since the maximum is positive, by Test 2, (<em>P</em>) is true.</p>
<p><strong>Rationale for Test 1</strong>. If <span class="math">\(A\)</span> does not have a positive eigenvalue, then <span class="math">\(A\)</span> is semidefinite negative, and so <span class="math">\(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\leq 0\)</span> for all <span class="math">\(\mathbf{x}\in\mathbb{R}^n\)</span>. Consequently, (<em>P</em>) is false. Likewise, if there exists a positive eigenvalue <span class="math">\(\lambda\)</span> with an associated eigenvector <span class="math">\(\mathbf{v}\in\mathbb{R}_+^n\)</span>, then <span class="math">\(p(\mathbf{v})=\mathbf{v}^TA\mathbf{v}=\lambda\mathbf{v}^T\mathbf{v}=\lambda\lVert\mathbf{v}\rVert^2>0\)</span>. Hence
(<em>P</em>) is true.</p>
<p><strong>Rationale for Test 2</strong>. Since <span class="math">\(p\)</span> is continuous and <span class="math">\(D\)</span> is compact, there always exists at least one point <span class="math">\(\mathbf{x}_0\in D\)</span> where <span class="math">\(p\)</span> attains a maximum value in <span class="math">\(D\)</span>, i.e. <span class="math">\(p(\mathbf{x}_0)\geq p(\mathbf{x})\)</span> for all <span class="math">\(\mathbf{x}\in D\)</span>. Now, if (<em>P</em>) is true, there exist <span class="math">\(\mathbf{x}_1\in \mathbb{R}_+^n\)</span> such that <span class="math">\(p(\mathbf{x}_1)>0\)</span>. Let <span class="math">\(\mathbf{x}_2=\mathbf{x}_1/\lVert\mathbf{x}_1\rVert\)</span>, which obviously belongs to <span class="math">\(D\)</span>. We deduce that
<span class="math">\[p(\mathbf{x}_0) \geq p(\mathbf{x}_2)=\frac{p(\mathbf{x}_1)}{\lVert\mathbf{x}_1\rVert^2}>0.\]</span>
Conversely, assume that <span class="math">\(p(\mathbf{x}_0)>0\)</span>. If <span class="math">\(\mathbf{x}_0\)</span> belongs to the interior of <span class="math">\(D\)</span>, then (<em>P</em>) holds with <span class="math">\(\mathbf{x}=\mathbf{x}_0\)</span>. If <span class="math">\(\mathbf{x}_0\)</span> is in the boundary of <span class="math">\(D\)</span> (so possibly with a null coordinate), by continuity of <span class="math">\(p\)</span>, there exists a ball <span class="math">\(B\)</span> centered at <span class="math">\(\mathbf{x}_0\)</span> where the sign of <span class="math">\(p\)</span> is that of <span class="math">\(p(\mathbf{x}_0)\)</span>, that is, <span class="math">\(p\)</span> is positive on <span class="math">\(B\)</span>. Since <span class="math">\(B\)</span> contains at least one point <span class="math">\(\mathbf{x}_3\)</span> in the interior of <span class="math">\(D\)</span>, then (<em>P</em>) holds with <span class="math">\(\mathbf{x}=\mathbf{x}_3\)</span>.</p>
Fri, 07 Jun 2019 22:47:46 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?answer=46858#post-id-46858Comment by vdelecroix for <p>From the examples in the O.P., I assume that we are dealing with homogeneous quadratic polynomials, that is, with quadratic forms.</p>
<p>Let us state the problem: given a quadratic form <span class="math">\(p\)</span> in <span class="math">\(\mathbb{R}^n\)</span>, determine the truth value of the proposition</p>
<blockquote>
<p>(<em>P</em>) there exists <span class="math">\(\mathbf{x}\in\mathbb{R}_+^n\)</span> such that <span class="math">\(p(\mathbf{x})>0\)</span>.</p>
</blockquote>
<p>Here, <span class="math">\(\mathbb{R}_+\)</span> stands for the set of positive real numbers. One can apply, at least, one of the following tests:</p>
<p><strong>Test 1</strong>. Let <span class="math">\(A\)</span> be the symmetric matrix associated to <span class="math">\(p\)</span>, i.e., <span class="math">\(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\)</span>. Compute the eigenvalues of <span class="math">\(A\)</span>. If all the eigenvalues are less than or equal to <span class="math">\(0\)</span>, then (<em>P</em>) is false. If there exists a positive eigenvalue <span class="math">\(\lambda\)</span> with an associated eigenvector <span class="math">\(\mathbf{v}\in\mathbb{R}_+^n\)</span>, then (<em>P</em>) is true.</p>
<p>Note that this test does not cover all the possibilities, since it only checks sufficient conditions.</p>
<p><strong>Test 2</strong>. Compute the maximum of <span class="math">\(p\)</span> on the set <span class="math">\(D=[0,1]^n\)</span>. Then (<em>P</em>) is true if and only if such a maximum is positive.</p>
<p>Test 1 can be implemented through the <code>eigenvalues()</code> and <code>eigenvectors_right()</code> methods for matrices. Test 2 can use the <code>minimize_constrained</code> function, already presented in @dan_fulea’s answer. Please note that maximize <span class="math">\(p\)</span> is equivalent to minimize <span class="math">\(-p\)</span>.</p>
<p>Let us apply them to the given polynomials.</p>
<p><strong>Example 1</strong>. Let <span class="math">\(p=-x^2 - y^2 - z^2 + xy + xz + yz\)</span>. We apply Test 1:</p>
<pre><code>sage: var("x,y,z");
sage: A = matrix([[-1,1/2,1/2],[1/2,-1,1/2],[1/2,1/2,-1]])
sage: A.eigenvalues()
[0, -3/2, -3/2]
</code></pre>
<p>By Test 1, (<em>P</em>) is false, since all the eigenvalues are less than or equal to <span class="math">\(0\)</span>. We could also apply Test 2:</p>
<pre><code>sage: var("x,y,z");
sage: p = -x^2 - y^2 - z^2 + x*y + x*z + y*z
sage: sol = minimize_constrained(-p, [[0,1]]*3, [0.1,0.9,0.5])
sage: print "Maximum is", p(*sol), "attained at", sol
Maximum is 0.0 attained at (0.4999999998931121, 0.5000000001068878, 0.5)
</code></pre>
<p>Since the maximum is not greater than <span class="math">\(0\)</span>, by Test 2, (<em>P</em>) is false.
The second argument of <code>minimize_constrained</code> is a list of the intervals where <span class="math">\(x\)</span>, <span class="math">\(y\)</span> and <span class="math">\(z\)</span> should be, that is, <span class="math">\([0,1]\)</span> for each variable. The last argument is a starting point of the iterative minimization process. In this example, if we take a different starting point, the maximum is also <span class="math">\(0\)</span>, but it can be reached at a different point (<span class="math">\(p\)</span> is <span class="math">\(0\)</span> on the line <span class="math">\(x=y=z\)</span>).</p>
<p><strong>Example 2</strong>. Let <span class="math">\(q= -x^2 - y^2 - z^2 + (3/2)(xy + xz + yz)\)</span>. We first use Test 1:</p>
<pre><code>sage: var("x,y,z");
sage: A = matrix([[-1,3/4,3/4],[3/4,-1,3/4],[3/4,3/4,-1]])
sage: A.eigenvalues()
[1/2, -7/4, -7/4]
sage: A.eigenvectors_right()
[(1/2, [(1, 1, 1)], 1), (-7/4, [(1, 0, -1), (0, 1, -1)], 2)]
</code></pre>
<p>The matrix <span class="math">\(A\)</span> has one positive eigenvalue, <span class="math">\(\lambda=1/2\)</span>, with an associated
eigenvector <span class="math">\(\mathbf{v}=(1,1,1)\)</span> belonging to <span class="math">\(\mathbb{R}_+^n\)</span>. Hence, (<em>P</em>) is true. Let us now apply Test 2:</p>
<pre><code>sage: var("x,y,z");
sage: q = -x^2 - y^2 - z^2 + (3/2)*(x*y + x*z + y*z)
sage: sol = minimize_constrained(-q,[[0,1]]*3, [0.1,0.9,0.5])
sage: print "Maximum is", q(*sol), "attained at", sol
Maximum is 1.5 attained at (1.0, 1.0, 1.0)
</code></pre>
<p>Since the maximum is positive, by Test 2, (<em>P</em>) is true.</p>
<p><strong>Rationale for Test 1</strong>. If <span class="math">\(A\)</span> does not have a positive eigenvalue, then <span class="math">\(A\)</span> is semidefinite negative, and so <span class="math">\(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\leq 0\)</span> for all <span class="math">\(\mathbf{x}\in\mathbb{R}^n\)</span>. Consequently, (<em>P</em>) is false. Likewise, if there exists a positive eigenvalue <span class="math">\(\lambda\)</span> with an associated eigenvector <span class="math">\(\mathbf{v}\in\mathbb{R}_+^n\)</span>, then <span class="math">\(p(\mathbf{v})=\mathbf{v}^TA\mathbf{v}=\lambda\mathbf{v}^T\mathbf{v}=\lambda\lVert\mathbf{v}\rVert^2>0\)</span>. Hence
(<em>P</em>) is true.</p>
<p><strong>Rationale for Test 2</strong>. Since <span class="math">\(p\)</span> is continuous and <span class="math">\(D\)</span> is compact, there always exists at least one point <span class="math">\(\mathbf{x}_0\in D\)</span> where <span class="math">\(p\)</span> attains a maximum value in <span class="math">\(D\)</span>, i.e. <span class="math">\(p(\mathbf{x}_0)\geq p(\mathbf{x})\)</span> for all <span class="math">\(\mathbf{x}\in D\)</span>. Now, if (<em>P</em>) is true, there exist <span class="math">\(\mathbf{x}_1\in \mathbb{R}_+^n\)</span> such that <span class="math">\(p(\mathbf{x}_1)>0\)</span>. Let <span class="math">\(\mathbf{x}_2=\mathbf{x}_1/\lVert\mathbf{x}_1\rVert\)</span>, which obviously belongs to <span class="math">\(D\)</span>. We deduce that
<span class="math">\[p(\mathbf{x}_0) \geq p(\mathbf{x}_2)=\frac{p(\mathbf{x}_1)}{\lVert\mathbf{x}_1\rVert^2}>0.\]</span>
Conversely, assume that <span class="math">\(p(\mathbf{x}_0)>0\)</span>. If <span class="math">\(\mathbf{x}_0\)</span> belongs to the interior of <span class="math">\(D\)</span>, then (<em>P</em>) holds with <span class="math">\(\mathbf{x}=\mathbf{x}_0\)</span>. If <span class="math">\(\mathbf{x}_0\)</span> is in the boundary of <span class="math">\(D\)</span> (so possibly with a null coordinate), by continuity of <span class="math">\(p\)</span>, there exists a ball <span class="math">\(B\)</span> centered at <span class="math">\(\mathbf{x}_0\)</span> where the sign of <span class="math">\(p\)</span> is that of <span class="math">\(p(\mathbf{x}_0)\)</span>, that is, <span class="math">\(p\)</span> is positive on <span class="math">\(B\)</span>. Since <span class="math">\(B\)</span> contains at least one point <span class="math">\(\mathbf{x}_3\)</span> in the interior of <span class="math">\(D\)</span>, then (<em>P</em>) holds with <span class="math">\(\mathbf{x}=\mathbf{x}_3\)</span>.</p>
https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46860#post-id-46860Thanks. If I am not mistaken, test 2 via **minimize_constrained** uses double floating point precision and does not provide any guarantee (ie proof). What can of course be done is to evaluate the provided solution with ball arithmetic but there might be situations where numerical approximation is not good enough.Sat, 08 Jun 2019 13:20:07 +0200https://ask.sagemath.org/question/46829/positive-values-of-polynomials/?comment=46860#post-id-46860