X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fcone%2Fdoubly_nonnegative.py;h=5e10e1aebaad4c17de9e129681a57bb736e72886;hb=7af2b9d146a6bf2fb8acc3c342983de577b417ce;hp=89bacb9ffff8ede8a76643e219a86da92d6ffa64;hpb=f32328c79ac937b3cbbbbfa92e93741f0d373261;p=sage.d.git diff --git a/mjo/cone/doubly_nonnegative.py b/mjo/cone/doubly_nonnegative.py index 89bacb9..5e10e1a 100644 --- a/mjo/cone/doubly_nonnegative.py +++ b/mjo/cone/doubly_nonnegative.py @@ -1,4 +1,4 @@ -""" +r""" The doubly-nonnegative cone in `S^{n}` is the set of all such matrices that both, @@ -13,14 +13,9 @@ It is represented typically by either `\mathcal{D}^{n}` or from sage.all import * -# Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we -# have to explicitly mangle our sitedir here so that "mjo.cone" -# resolves. -from os.path import abspath -from site import addsitedir -addsitedir(abspath('../../')) -from mjo.cone.symmetric_psd import factor_psd, is_symmetric_psd - +from mjo.cone.symmetric_psd import (factor_psd, + random_symmetric_psd) +from mjo.basis_repr import basis_repr def is_doubly_nonnegative(A): @@ -36,6 +31,10 @@ def is_doubly_nonnegative(A): Either ``True`` if ``A`` is doubly-nonnegative, or ``False`` otherwise. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_doubly_nonnegative + EXAMPLES: Every completely positive matrix is doubly-nonnegative:: @@ -58,13 +57,78 @@ def is_doubly_nonnegative(A): raise ValueError.new(msg) # Check that all of the entries of ``A`` are nonnegative. - if not all([ a >= 0 for a in A.list() ]): + if not all( a >= 0 for a in A.list() ): return False # It's nonnegative, so all we need to do is check that it's # symmetric positive-semidefinite. - return is_symmetric_psd(A) + return A.is_positive_semidefinite() + + + +def is_admissible_extreme_rank(r, n): + r""" + The extreme matrices of the doubly-nonnegative cone have some + restrictions on their ranks. This function checks to see whether the + rank ``r`` would be an admissible rank for an ``n``-by-``n`` matrix. + + INPUT: + + - ``r`` - The rank of the matrix. + + - ``n`` - The dimension of the vector space on which the matrix acts. + + OUTPUT: + + Either ``True`` if a rank ``r`` matrix could be an extreme vector of + the doubly-nonnegative cone in `$\mathbb{R}^{n}$`, or ``False`` + otherwise. + + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_admissible_extreme_rank + + EXAMPLES: + + For dimension 5, only ranks zero, one, and three are admissible:: + + sage: is_admissible_extreme_rank(0,5) + True + sage: is_admissible_extreme_rank(1,5) + True + sage: is_admissible_extreme_rank(2,5) + False + sage: is_admissible_extreme_rank(3,5) + True + sage: is_admissible_extreme_rank(4,5) + False + sage: is_admissible_extreme_rank(5,5) + False + + When given an impossible rank, we just return false:: + + sage: is_admissible_extreme_rank(100,5) + False + + """ + if r == 0: + # Zero is in the doubly-nonnegative cone. + return True + if r > n: + # Impossible, just return False + return False + + # See Theorem 3.1 in the cited reference. + if r == 2: + return False + + if n.mod(2) == 0: + # n is even + return r <= max(1, n-3) + else: + # n is odd + return r <= max(1, n-2) def has_admissible_extreme_rank(A): @@ -89,13 +153,43 @@ def has_admissible_extreme_rank(A): 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993. http://projecteuclid.org/euclid.rmjm/1181071993. + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import has_admissible_extreme_rank + EXAMPLES: The zero matrix has rank zero, which is admissible:: - sage: A = zero_matrix(QQ, 5, 5) - sage: has_admissible_extreme_rank(A) - True + sage: A = zero_matrix(QQ, 5, 5) + sage: has_admissible_extreme_rank(A) + True + + Likewise, rank one is admissible for dimension 5:: + + sage: v = vector(QQ, [1,2,3,4,5]) + sage: A = v.column()*v.row() + sage: has_admissible_extreme_rank(A) + True + + But rank 2 is never admissible:: + + sage: v1 = vector(QQ, [1,0,0,0,0]) + sage: v2 = vector(QQ, [0,1,0,0,0]) + sage: A = v1.column()*v1.row() + v2.column()*v2.row() + sage: has_admissible_extreme_rank(A) + False + + In dimension 5, three is the only other admissible rank:: + + sage: v1 = vector(QQ, [1,0,0,0,0]) + sage: v2 = vector(QQ, [0,1,0,0,0]) + sage: v3 = vector(QQ, [0,0,1,0,0]) + sage: A = v1.column()*v1.row() + sage: A += v2.column()*v2.row() + sage: A += v3.column()*v3.row() + sage: has_admissible_extreme_rank(A) + True """ if not A.is_symmetric(): @@ -106,20 +200,72 @@ def has_admissible_extreme_rank(A): r = rank(A) n = ZZ(A.nrows()) # Columns would work, too, since ``A`` is symmetric. - if r == 0: - # Zero is in the doubly-nonnegative cone. - return True + return is_admissible_extreme_rank(r,n) - # See Theorem 3.1 in the cited reference. - if r == 2: - return False - if n.mod(2) == 0: - # n is even - return r <= max(1, n-3) - else: - # n is odd - return r <= max(1, n-2) +def stdE(matrix_space, i,j): + """ + Return the ``i``,``j``th element of the standard basis in + ``matrix_space``. + + INPUT: + + - ``matrix_space`` - The underlying matrix space of whose basis + the returned matrix is an element + + - ``i`` - The row index of the single nonzero entry + + - ``j`` - The column index of the single nonzero entry + + OUTPUT: + + A basis element of ``matrix_space``. It has a single \"1\" in the + ``i``,``j`` row,column and zeros elsewhere. + + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import stdE + + EXAMPLES:: + + sage: M = MatrixSpace(ZZ, 2, 2) + sage: stdE(M,0,0) + [1 0] + [0 0] + sage: stdE(M,0,1) + [0 1] + [0 0] + sage: stdE(M,1,0) + [0 0] + [1 0] + sage: stdE(M,1,1) + [0 0] + [0 1] + sage: stdE(M,2,1) + Traceback (most recent call last): + ... + IndexError: Index `i` is out of bounds. + sage: stdE(M,1,2) + Traceback (most recent call last): + ... + IndexError: Index `j` is out of bounds. + + """ + # We need to check these ourselves, see below. + if i >= matrix_space.nrows(): + raise IndexError('Index `i` is out of bounds.') + if j >= matrix_space.ncols(): + raise IndexError('Index `j` is out of bounds.') + + # The basis here is returned as a one-dimensional list, so we need + # to compute the offset into it based on ``i`` and ``j``. Since we + # compute the index ourselves, we need to do bounds-checking + # manually. Otherwise for e.g. a 2x2 matrix space, the index (0,2) + # would be computed as offset 3 into a four-element list and we + # would succeed incorrectly. + idx = matrix_space.ncols()*i + j + return list(matrix_space.basis())[idx] + def is_extreme_doubly_nonnegative(A): @@ -127,6 +273,20 @@ def is_extreme_doubly_nonnegative(A): Returns ``True`` if the given matrix is an extreme matrix of the doubly-nonnegative cone, and ``False`` otherwise. + REFERENCES: + + 1. Hamilton-Jester, Crista Lee; Li, Chi-Kwong. Extreme Vectors of + Doubly Nonnegative Matrices. Rocky Mountain Journal of Mathematics + 26 (1996), no. 4, 1371--1383. doi:10.1216/rmjm/1181071993. + http://projecteuclid.org/euclid.rmjm/1181071993. + + 2. Berman, Abraham and Shaked-Monderer, Naomi. Completely Positive + Matrices. World Scientific, 2003. + + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import is_extreme_doubly_nonnegative + EXAMPLES: The zero matrix is an extreme matrix:: @@ -135,15 +295,249 @@ def is_extreme_doubly_nonnegative(A): sage: is_extreme_doubly_nonnegative(A) True + Any extreme vector of the completely positive cone is an extreme + vector of the doubly-nonnegative cone:: + + sage: v = vector([1,2,3,4,5,6]) + sage: A = v.column() * v.row() + sage: A = A.change_ring(QQ) + sage: is_extreme_doubly_nonnegative(A) + True + + We should be able to generate the extreme completely positive + vectors randomly:: + + sage: v = vector(map(abs, random_vector(ZZ, 4))) + sage: A = v.column() * v.row() + sage: A = A.change_ring(QQ) + sage: is_extreme_doubly_nonnegative(A) + True + sage: v = vector(map(abs, random_vector(ZZ, 10))) + sage: A = v.column() * v.row() + sage: A = A.change_ring(QQ) + sage: is_extreme_doubly_nonnegative(A) + True + + The following matrix is completely positive but has rank 3, so by a + remark in reference #1 it is not extreme:: + + sage: A = matrix(QQ, [[1,2,1],[2,6,3],[1,3,5]]) + sage: is_extreme_doubly_nonnegative(A) + False + + The following matrix is completely positive (diagonal) with rank 2, + so it is also not extreme:: + + sage: A = matrix(QQ, [[1,0,0],[2,0,0],[0,0,0]]) + sage: is_extreme_doubly_nonnegative(A) + False + """ - r = A.rank() + if not A.base_ring().is_exact() and not A.base_ring() is SR: + msg = 'The base ring of ``A`` must be either exact or symbolic.' + raise ValueError(msg) - if r == 0: + if not A.base_ring().is_field(): + raise ValueError('The base ring of ``A`` must be a field.') + + if not A.base_ring() is SR: + # Change the base field of ``A`` so that we are sure we can take + # roots. The symbolic ring has no algebraic_closure method. + A = A.change_ring(A.base_ring().algebraic_closure()) + + # Step 1 (see reference #1) + k = A.rank() + + if k == 0: # Short circuit, we know the zero matrix is extreme. return True - if not is_admissible_extreme_rank(r): + if not A.is_positive_semidefinite(): return False - raise NotImplementedError() + # Step 1.5, appeal to Theorem 3.1 in reference #1 to short + # circuit. + if not has_admissible_extreme_rank(A): + return False + + # Step 2 + X = factor_psd(A) + + # Step 3 + # + # Begin with an empty spanning set, and add a new matrix to it + # whenever we come across an index pair `$(i,j)$` with + # `$A_{ij} = 0$`. + spanning_set = [] + for j in range(A.ncols()): + for i in range(j): + if A[i,j] == 0: + M = A.matrix_space() + S = X.transpose() * (stdE(M,i,j) + stdE(M,j,i)) * X + spanning_set.append(S) + + # The spanning set that we have at this point is of matrices. We + # only care about the dimension of the spanned space, and Sage + # can't compute the dimension of a set of matrices anyway, so we + # convert them all to vectors and just ask for the dimension of the + # resulting vector space. + (phi, phi_inverse) = basis_repr(A.matrix_space()) + vectors = map(phi,spanning_set) + + V = span(vectors, A.base_ring()) + d = V.dimension() + + # Needed to safely divide by two here (we don't want integer + # division). We ensured that the base ring of ``A`` is a field + # earlier. + two = A.base_ring()(2) + return d == (k*(k + 1)/two - 1) + + +def random_doubly_nonnegative(V, accept_zero=True, rank=None): + """ + Generate a random doubly nonnegative matrix over the vector + space ``V``. That is, the returned matrix will be a linear + transformation on ``V``, with the same base ring as ``V``. + + We take a very loose interpretation of "random," here. Otherwise we + would never (for example) choose a matrix on the boundary of the + cone. + + INPUT: + + - ``V`` - The vector space on which the returned matrix will act. + + - ``accept_zero`` - Do you want to accept the zero matrix (which + is doubly nonnegative)? Default to ``True``. + + - ``rank`` - Require the returned matrix to have the given rank + (optional). + + OUTPUT: + + A random doubly nonnegative matrix, i.e. a linear transformation + from ``V`` to itself. + + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import (is_doubly_nonnegative, + ....: random_doubly_nonnegative) + + EXAMPLES: + + Well, it doesn't crash at least:: + + sage: V = VectorSpace(QQ, 2) + sage: A = random_doubly_nonnegative(V) + sage: A.matrix_space() + Full MatrixSpace of 2 by 2 dense matrices over Rational Field + sage: is_doubly_nonnegative(A) + True + + A matrix with the desired rank is returned:: + + sage: V = VectorSpace(QQ, 5) + sage: A = random_doubly_nonnegative(V,False,1) + sage: A.rank() + 1 + sage: A = random_doubly_nonnegative(V,False,2) + sage: A.rank() + 2 + sage: A = random_doubly_nonnegative(V,False,3) + sage: A.rank() + 3 + sage: A = random_doubly_nonnegative(V,False,4) + sage: A.rank() + 4 + sage: A = random_doubly_nonnegative(V,False,5) + sage: A.rank() + 5 + + """ + + # Generate random symmetric positive-semidefinite matrices until + # one of them is nonnegative, then return that. + A = random_symmetric_psd(V, accept_zero, rank) + + while not all( x >= 0 for x in A.list() ): + A = random_symmetric_psd(V, accept_zero, rank) + + return A + + + +def random_extreme_doubly_nonnegative(V, accept_zero=True, rank=None): + """ + Generate a random extreme doubly nonnegative matrix over the + vector space ``V``. That is, the returned matrix will be a linear + transformation on ``V``, with the same base ring as ``V``. + + We take a very loose interpretation of "random," here. Otherwise we + would never (for example) choose a matrix on the boundary of the + cone. + + INPUT: + + - ``V`` - The vector space on which the returned matrix will act. + + - ``accept_zero`` - Do you want to accept the zero matrix + (which is extreme)? Defaults to ``True``. + + - ``rank`` - Require the returned matrix to have the given rank + (optional). WARNING: certain ranks are not possible + in any given dimension! If an impossible rank is + requested, a ValueError will be raised. + + OUTPUT: + + A random extreme doubly nonnegative matrix, i.e. a linear + transformation from ``V`` to itself. + + SETUP:: + + sage: from mjo.cone.doubly_nonnegative import (is_extreme_doubly_nonnegative, + ....: random_extreme_doubly_nonnegative) + + EXAMPLES: + + Well, it doesn't crash at least:: + + sage: V = VectorSpace(QQ, 2) + sage: A = random_extreme_doubly_nonnegative(V) + sage: A.matrix_space() + Full MatrixSpace of 2 by 2 dense matrices over Rational Field + sage: is_extreme_doubly_nonnegative(A) + True + + Rank 2 is never allowed, so we expect an error:: + + sage: V = VectorSpace(QQ, 5) + sage: A = random_extreme_doubly_nonnegative(V, False, 2) + Traceback (most recent call last): + ... + ValueError: Rank 2 not possible in dimension 5. + + Rank 4 is not allowed in dimension 5:: + + sage: V = VectorSpace(QQ, 5) + sage: A = random_extreme_doubly_nonnegative(V, False, 4) + Traceback (most recent call last): + ... + ValueError: Rank 4 not possible in dimension 5. + + """ + + if rank is not None and not is_admissible_extreme_rank(rank, V.dimension()): + msg = 'Rank %d not possible in dimension %d.' + raise ValueError(msg % (rank, V.dimension())) + + # Generate random doubly-nonnegative matrices until + # one of them is extreme, then return that. + A = random_doubly_nonnegative(V, accept_zero, rank) + + while not is_extreme_doubly_nonnegative(A): + A = random_doubly_nonnegative(V, accept_zero, rank) + + return A