Revision history [back]
 | 1 | initial version |
From the examples in the O.P., I assume that we are dealing with homogeneous quadratic polynomials, that is, with quadratic forms.
Let us state the problem: given a quadratic form \(p\) in \(\mathbb{R}^n\), determine the truth value of the proposition
(P) there exists \(\mathbf{x}\in\mathbb{R}_+^n\) such that \(p(\mathbf{x})>0\).
Here, \(\mathbb{R}_+\) stands for the set of positive real numbers. One can apply, at least, one of the following tests:
Test 1. Let \(A\) be the symmetric matrix \(A\) associated to \(p\), i.e., \(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\). Compute the eigenvalues of \(A\). If all the eigenvalues are less than or equal to \(0\), then (P) is false.
Test 2. Compute the maximum of \(p\) on the set \(D=[0,1]^n\). Then (P) is true if and only if such a maximum is positive.
Test 1 can be implemented through the eigenvalues() method for matrices. Test 2 can use the minimize_constrained function, already presented in @dan_fulea’s comment. Please note that maximize \(p\) is equivalent to minimize \(-p\).
Let us apply them to the given polynomials.
Example 1. Let \(p=-x^2 - y^2 - z^2 + xy + xz + yz\). We apply Test 1:
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]
By Test 1, (P) is false. We could also apply Test 2:
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, [1,1,1])
sage: print "Maximum is", p(*sol), "attained at", sol
Maximum is 0.0 attained at (1.0, 1.0, 1.0)
Since the maximum is not greater than \(0\), by Test 2, (P) is false. The second argument of minimize_constrained is a list of the intervals where \(x\), \(y\) and \(z\) should be, that is, \([0,1]\) for each variable. The last argument is a starting point of the iterative minimization process.
Example 2. Let \(q= -x^2 - y^2 - z^2 + (3/2)(xy + xz + yz)\). We first use Test 1:
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]
Since \(A\) has one positive eigenvalue, Test 1 fails. We need to apply Test 2:
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, [1,1,1])
sage: print "Maximum is", q(*sol), "attained at", sol
Maximum is 1.5 attained at (1.0, 1.0, 1.0)
Since the maximum is positive, by Test 2, (P) is true.
Rationale for Test 1. If \(A\) does not have a positive eigenvalue, then \(A\) is semidefinite negative, and so \(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\leq 0\) for all \(\mathbf{x}\in\mathbb{R}^n\). Consequently, (P) is false.
Rationale for Test 2. Since \(p\) is continuous and \(D\) is compact, there always exists at least one point \(\mathbf{x}_0\in D\) where \(p\) attains a maximum value in \(D\), i.e. \(p(\mathbf{x}_0)\geq p(\mathbf{x})\) for all \(\mathbf{x}\in D\). Now, if (P) is true, there exist \(\mathbf{x}_1\in \mathbb{R}_+^n\) such that \(p(\mathbf{x}_1)>0\). Let \(\mathbf{x}_2=\mathbf{x}_1/\lVert\mathbf{x}_1\rVert\), which obviously belongs to \(D\). We deduce that \[p(\mathbf{x}_0) \geq p(\mathbf{x}_2)=\frac{p(\mathbf{x}_1)}{\lVert\mathbf{x}_1\rVert^2}>0.\] Conversely, assume that \(p(\mathbf{x}_0)>0\). If \(\mathbf{x}_0\) belongs to the interior of \(D\), then (P) holds with \(\mathbf{x}=\mathbf{x}_0\). If \(\mathbf{x}_0\) is in the boundary of \(D\) (so possibly with a null coordinate), by continuity of \(p\), there exists a ball \(B\) centered at \(\mathbf{x}_0\) where the sign of \(p\) is that of \(p(\mathbf{x}_0)\), that is, \(p\) is positive on \(B\). Since \(B\) contains at least one point \(\mathbf{x}_3\) in the interior of \(D\), then (P) holds with \(\mathbf{x}=\mathbf{x}_3\).
| | 2 | No.2 Revision |
From the examples in the O.P., I assume that we are dealing with homogeneous quadratic polynomials, that is, with quadratic forms.
Let us state the problem: given a quadratic form \(p\) in \(\mathbb{R}^n\), determine the truth value of the proposition
(P) there exists \(\mathbf{x}\in\mathbb{R}_+^n\) such that \(p(\mathbf{x})>0\).
Here, \(\mathbb{R}_+\) stands for the set of positive real numbers. One can apply, at least, one of the following tests:
Test 1. Let \(A\) be the symmetric matrix \(A\) associated to \(p\), i.e., \(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\). Compute the eigenvalues of \(A\). If all the eigenvalues are less than or equal to \(0\), then (P) is false.false. If there exists a positive eigenvalue \(\lambda\) with an associated eigenvector \(\mathbf{v}\in\mathbb{R}_+^n\), then (P) is true.
Note that this test does not cover all the possibilities, since it only checks sufficient conditions.
Test 2. Compute the maximum of \(p\) on the set \(D=[0,1]^n\). Then (P) is true if and only if such a maximum is positive.
Test 1 can be implemented through the eigenvalues() method and eigenvectors_right() methods for matrices. Test 2 can use the minimize_constrained function, already presented in @dan_fulea’s comment. answer. Please note that maximize \(p\) is equivalent to minimize \(-p\).
Let us apply them to the given polynomials.
Example 1. Let \(p=-x^2 - y^2 - z^2 + xy + xz + yz\). We apply Test 1:
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]
By Test 1, (P) is false. false, since all the eigenvalues are less than or equal to \(0\). We could also apply Test 2:
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, [1,1,1])
[0.1,0.9,0.5])
sage: print "Maximum is", p(*sol), "attained at", sol
Maximum is 0.0 attained at (1.0, 1.0, 1.0)
(0.4999999998931121, 0.5000000001068878, 0.5)
Since the maximum is not greater than \(0\), by Test 2, (P) is false. false.
The second argument of minimize_constrained is a list of the intervals where \(x\), \(y\) and \(z\) should be, that is, \([0,1]\) for each variable. The last argument is a starting point of the iterative minimization process.process. In this example, if we take a different starting point, the maximum is also \(0\), but it can be reached at a different point (\(p\) is \(0\) on the line \(x=y=z\)).
Example 2. Let \(q= -x^2 - y^2 - z^2 + (3/2)(xy + xz + yz)\). We first use Test 1:
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)]
Since The matrix \(A\) has one positive eigenvalue, Test 1 fails. We need \(\lambda=1/2\), with an associated
eigenvector \(\mathbf{v}=(1,1,1)\) belonging to \(\mathbb{R}_+^n\). Hence, (P) is true. Let us now apply Test 2:
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, [1,1,1])
[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)
Since the maximum is positive, by Test 2, (P) is true.
Rationale for Test 1. If \(A\) does not have a positive eigenvalue, then \(A\) is semidefinite negative, and so \(p(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\leq 0\) for all \(\mathbf{x}\in\mathbb{R}^n\). Consequently, (P) is false.false. Likewise, if there exists a positive eigenvalue \(\lambda\) with an associated eigenvector \(\mathbf{v}\in\mathbb{R}_+^n\), then \(p(\mathbf{v})=\mathbf{v}^TA\mathbf{v}=\lambda\mathbf{v}^T\mathbf{v}=\lambda\lVert\mathbf{v}\rVert^2>0\). Hence
(P) is true.
Rationale for Test 2. Since \(p\) is continuous and \(D\) is compact, there always exists at least one point \(\mathbf{x}_0\in D\) where \(p\) attains a maximum value in \(D\), i.e. \(p(\mathbf{x}_0)\geq p(\mathbf{x})\) for all \(\mathbf{x}\in D\). Now, if (P) is true, there exist \(\mathbf{x}_1\in \mathbb{R}_+^n\) such that \(p(\mathbf{x}_1)>0\). Let \(\mathbf{x}_2=\mathbf{x}_1/\lVert\mathbf{x}_1\rVert\), which obviously belongs to \(D\). We deduce that \[p(\mathbf{x}_0) \geq p(\mathbf{x}_2)=\frac{p(\mathbf{x}_1)}{\lVert\mathbf{x}_1\rVert^2}>0.\] Conversely, assume that \(p(\mathbf{x}_0)>0\). If \(\mathbf{x}_0\) belongs to the interior of \(D\), then (P) holds with \(\mathbf{x}=\mathbf{x}_0\). If \(\mathbf{x}_0\) is in the boundary of \(D\) (so possibly with a null coordinate), by continuity of \(p\), there exists a ball \(B\) centered at \(\mathbf{x}_0\) where the sign of \(p\) is that of \(p(\mathbf{x}_0)\), that is, \(p\) is positive on \(B\). Since \(B\) contains at least one point \(\mathbf{x}_3\) in the interior of \(D\), then (P) holds with \(\mathbf{x}=\mathbf{x}_3\).
