X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=test%2Fsymmetric_linear_game_test.py;h=bba2f7ccfcb48c38312e5d5849aae892d40eac31;hb=2b44481f8a79cbab75ddc0f73eea813b66e17d62;hp=69c352ace384e0fda2f60023d6577bc37baaf315;hpb=59a1dcf2bf416a2527f9fdfb377afbbfa6cef696;p=dunshire.git

diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py
index 69c352a..bba2f7c 100644
--- a/test/symmetric_linear_game_test.py
+++ b/test/symmetric_linear_game_test.py
@@ -2,272 +2,88 @@
 Unit tests for the :class:`SymmetricLinearGame` class.
 """
 
-from math import sqrt
-from random import randint, uniform
 from unittest import TestCase
 
-from cvxopt import matrix
-from dunshire.cones import NonnegativeOrthant, IceCream
+from dunshire.cones import NonnegativeOrthant
 from dunshire.games import SymmetricLinearGame
-from dunshire.matrices import (append_col, append_row, eigenvalues_re,
-                               identity, inner_product)
+from dunshire.matrices import eigenvalues_re, inner_product
 from dunshire import options
+from .randomgen import (RANDOM_MAX, random_icecream_game,
+                        random_ll_icecream_game, random_ll_orthant_game,
+                        random_nn_scaling, random_orthant_game,
+                        random_positive_orthant_game, random_translation)
 
+EPSILON = (1 + RANDOM_MAX)*options.ABS_TOL
+"""
+This is the tolerance constant including fudge factors that we use to
+determine whether or not two numbers are equal in tests.
+
+Often we will want to compare two solutions, say for games that are
+equivalent. If the first game value is low by ``ABS_TOL`` and the second
+is high by ``ABS_TOL``, then the total could be off by ``2*ABS_TOL``. We
+also subject solutions to translations and scalings, which adds to or
+scales their error. If the first game is low by ``ABS_TOL`` and the
+second is high by ``ABS_TOL`` before scaling, then after scaling, the
+second could be high by ``RANDOM_MAX*ABS_TOL``. That is the rationale
+for the factor of ``1 + RANDOM_MAX`` in ``EPSILON``. Since ``1 +
+RANDOM_MAX`` is greater than ``2*ABS_TOL``, we don't need to handle the
+first issue mentioned (both solutions off by the same amount in opposite
+directions).
+"""
 
-def random_matrix(dims):
-    """
-    Generate a random square matrix.
-
-    Parameters
-    ----------
-
-    dims : int
-        The number of rows/columns you want in the returned matrix.
-
-    Returns
-    -------
-
-    matrix
-        A new matrix whose entries are random floats chosen uniformly from
-        the interval [-10, 10].
-
-    Examples
-    --------
-
-        >>> A = random_matrix(3)
-        >>> A.size
-        (3, 3)
-
-    """
-    return matrix([[uniform(-10, 10) for _ in range(dims)]
-                   for _ in range(dims)])
-
-
-def random_nonnegative_matrix(dims):
-    """
-    Generate a random square matrix with nonnegative entries.
-
-    Parameters
-    ----------
-
-    dims : int
-        The number of rows/columns you want in the returned matrix.
-
-    Returns
-    -------
-
-    matrix
-        A new matrix whose entries are random floats chosen uniformly from
-        the interval [0, 10].
-
-    Examples
-    --------
-
-        >>> A = random_nonnegative_matrix(3)
-        >>> A.size
-        (3, 3)
-        >>> all([entry >= 0 for entry in A])
-        True
-
-    """
-    L = random_matrix(dims)
-    return matrix([abs(entry) for entry in L], (dims, dims))
-
-
-def random_diagonal_matrix(dims):
-    """
-    Generate a random square matrix with zero off-diagonal entries.
-
-    These matrices are Lyapunov-like on the nonnegative orthant, as is
-    fairly easy to see.
-
-    Parameters
-    ----------
-
-    dims : int
-        The number of rows/columns you want in the returned matrix.
-
-    Returns
-    -------
-
-    matrix
-        A new matrix whose diagonal entries are random floats chosen
-        uniformly from the interval [-10, 10] and whose off-diagonal
-        entries are zero.
-
-    Examples
-    --------
-
-        >>> A = random_diagonal_matrix(3)
-        >>> A.size
-        (3, 3)
-        >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
-        True
-
-    """
-    return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)]
-                   for j in range(dims)])
-
-
-def random_skew_symmetric_matrix(dims):
+# Tell pylint to shut up about the large number of methods.
+class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
     """
-    Generate a random skew-symmetrix matrix.
-
-    Parameters
-    ----------
-
-    dims : int
-        The number of rows/columns you want in the returned matrix.
-
-    Returns
-    -------
-
-    matrix
-        A new skew-matrix whose strictly above-diagonal entries are
-        random floats chosen uniformly from the interval [-10, 10].
-
-    Examples
-    --------
-
-        >>> A = random_skew_symmetric_matrix(3)
-        >>> A.size
-        (3, 3)
-
-        >>> from dunshire.matrices import norm
-        >>> A = random_skew_symmetric_matrix(randint(1, 10))
-        >>> norm(A + A.trans()) < options.ABS_TOL
-        True
-
+    Tests for the SymmetricLinearGame and Solution classes.
     """
-    strict_ut = [[uniform(-10, 10)*int(i < j) for i in range(dims)]
-                 for j in range(dims)]
-
-    strict_ut = matrix(strict_ut, (dims, dims))
-    return strict_ut - strict_ut.trans()
-
-
-def random_lyapunov_like_icecream(dims):
-    r"""
-    Generate a random matrix Lyapunov-like on the ice-cream cone.
-
-    The form of these matrices is cited in Gowda and Tao
-    [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
-    notation) are easy to generate. The submatrix ``D`` is a little
-    trickier, but it can be found noticing that :math:`C + C^{T} = 0`
-    for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
-    + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
-    :math:`aI` with each of :math:`C,C^{T}` and let those be our
-    :math:`D,D^{T}`.
-
-    Parameters
-    ----------
-
-    dims : int
-        The dimension of the ice-cream cone (not of the matrix you want!)
-        on which the returned matrix should be Lyapunov-like.
-
-    Returns
-    -------
-
-    matrix
-        A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
-        dimensions, whose free entries are random floats chosen uniformly
-        from the interval [-10, 10].
+    def assert_within_tol(self, first, second, modifier=1):
+        """
+        Test that ``first`` and ``second`` are equal within a multiple of
+        our default tolerances.
 
-    References
-    ----------
+        Parameters
+        ----------
 
-    .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
-       proper cone and Lyapunov-like transformations. Mathematical
-       Programming, 147:155-170, 2014.
+        first : float
+            The first number to compare.
 
-    Examples
-    --------
+        second : float
+            The second number to compare.
 
-        >>> L = random_lyapunov_like_icecream(3)
-        >>> L.size
-        (3, 3)
-        >>> x = matrix([1,1,0])
-        >>> s = matrix([1,-1,0])
-        >>> abs(inner_product(L*x, s)) < options.ABS_TOL
-        True
+        modifier : float
+            A scaling factor (default: 1) applied to the default
+            ``EPSILON`` for this comparison. If you have a poorly-
+            conditioned matrix, for example, you may want to set this
+            greater than one.
 
-    """
-    a = matrix([uniform(-10, 10)], (1, 1))
-    b = matrix([uniform(-10, 10) for _ in range(dims-1)], (dims-1, 1))
-    D = random_skew_symmetric_matrix(dims-1) + a*identity(dims-1)
-    row1 = append_col(a, b.trans())
-    row2 = append_col(b, D)
-    return append_row(row1, row2)
+        """
+        self.assertTrue(abs(first - second) < EPSILON*modifier)
 
 
-def random_orthant_params():
-    """
-    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
-    random game over the nonnegative orthant.
-    """
-    ambient_dim = randint(1, 10)
-    K = NonnegativeOrthant(ambient_dim)
-    e1 = [uniform(0.5, 10) for _ in range(K.dimension())]
-    e2 = [uniform(0.5, 10) for _ in range(K.dimension())]
-    L = random_matrix(K.dimension())
-    return (L, K, matrix(e1), matrix(e2))
+    def assert_solution_exists(self, G):
+        """
+        Given  a SymmetricLinearGame, ensure that it has a solution.
+        """
+        soln = G.solution()
 
+        expected = G.payoff(soln.player1_optimal(), soln.player2_optimal())
+        self.assert_within_tol(soln.game_value(), expected, G.condition())
 
-def random_icecream_params():
-    """
-    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
-    random game over the ice-cream cone.
-    """
-    # Use a minimum dimension of two to avoid divide-by-zero in
-    # the fudge factor we make up later.
-    ambient_dim = randint(2, 10)
-    K = IceCream(ambient_dim)
-    e1 = [1] # Set the "height" of e1 to one
-    e2 = [1] # And the same for e2
-
-    # If we choose the rest of the components of e1,e2 randomly
-    # between 0 and 1, then the largest the squared norm of the
-    # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
-    # need to make it less than one (the height of the cone) so
-    # that the whole thing is in the cone. The norm of the
-    # non-height part is sqrt(dim(K) - 1), and we can divide by
-    # twice that.
-    fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0))
-    e1 += [fudge_factor*uniform(0, 1) for _ in range(K.dimension() - 1)]
-    e2 += [fudge_factor*uniform(0, 1) for _ in range(K.dimension() - 1)]
-    L = random_matrix(K.dimension())
-
-    return (L, K, matrix(e1), matrix(e2))
 
 
-# Tell pylint to shut up about the large number of methods.
-class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
-    """
-    Tests for the SymmetricLinearGame and Solution classes.
-    """
-    def assert_within_tol(self, first, second):
-        """
-        Test that ``first`` and ``second`` are equal within our default
-        tolerance.
+    def test_condition_lower_bound(self):
         """
-        self.assertTrue(abs(first - second) < options.ABS_TOL)
+        Ensure that the condition number of a game is greater than or
+        equal to one.
 
-
-    def assert_solution_exists(self, L, K, e1, e2):
-        """
-        Given the parameters needed to construct a SymmetricLinearGame,
-        ensure that that game has a solution.
+        It should be safe to compare these floats directly: we compute
+        the condition number as the ratio of one nonnegative real number
+        to a smaller nonnegative real number.
         """
-        # The matrix() constructor assumes that ``L`` is a list of
-        # columns, so we transpose it to agree with what
-        # SymmetricLinearGame() thinks.
-        G = SymmetricLinearGame(L.trans(), K, e1, e2)
-        soln = G.solution()
-
-        expected = inner_product(L*soln.player1_optimal(),
-                                 soln.player2_optimal())
-        self.assert_within_tol(soln.game_value(), expected)
+        G = random_orthant_game()
+        self.assertTrue(G.condition() >= 1.0)
+        G = random_icecream_game()
+        self.assertTrue(G.condition() >= 1.0)
 
 
     def test_solution_exists_orthant(self):
@@ -278,8 +94,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         optimal solutions should give us the optimal game value when we
         apply the payoff operator to them.
         """
-        (L, K, e1, e2) = random_orthant_params()
-        self.assert_solution_exists(L, K, e1, e2)
+        G = random_orthant_game()
+        self.assert_solution_exists(G)
 
 
     def test_solution_exists_icecream(self):
@@ -287,8 +103,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Like :meth:`test_solution_exists_nonnegative_orthant`, except
         over the ice cream cone.
         """
-        (L, K, e1, e2) = random_icecream_params()
-        self.assert_solution_exists(L, K, e1, e2)
+        G = random_icecream_game()
+        self.assert_solution_exists(G)
 
 
     def test_negative_value_z_operator(self):
@@ -304,18 +120,15 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 
 
-    def assert_scaling_works(self, L, K, e1, e2):
+    def assert_scaling_works(self, G):
         """
         Test that scaling ``L`` by a nonnegative number scales the value
         of the game by the same number.
         """
-        game1 = SymmetricLinearGame(L, K, e1, e2)
-        value1 = game1.solution().game_value()
-
-        alpha = uniform(0.1, 10)
-        game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
-        value2 = game2.solution().game_value()
-        self.assert_within_tol(alpha*value1, value2)
+        (alpha, H) = random_nn_scaling(G)
+        value1 = G.solution().game_value()
+        value2 = H.solution().game_value()
+        self.assert_within_tol(alpha*value1, value2, H.condition())
 
 
     def test_scaling_orthant(self):
@@ -323,8 +136,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Test that scaling ``L`` by a nonnegative number scales the value
         of the game by the same number over the nonnegative orthant.
         """
-        (L, K, e1, e2) = random_orthant_params()
-        self.assert_scaling_works(L, K, e1, e2)
+        G = random_orthant_game()
+        self.assert_scaling_works(G)
 
 
     def test_scaling_icecream(self):
@@ -332,46 +145,41 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         The same test as :meth:`test_nonnegative_scaling_orthant`,
         except over the ice cream cone.
         """
-        (L, K, e1, e2) = random_icecream_params()
-        self.assert_scaling_works(L, K, e1, e2)
+        G = random_icecream_game()
+        self.assert_scaling_works(G)
 
 
-    def assert_translation_works(self, L, K, e1, e2):
+    def assert_translation_works(self, G):
         """
         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
         the value of the associated game by alpha.
         """
         # We need to use ``L`` later, so make sure we transpose it
         # before passing it in as a column-indexed matrix.
-        game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
-        soln1 = game1.solution()
+        soln1 = G.solution()
         value1 = soln1.game_value()
         x_bar = soln1.player1_optimal()
         y_bar = soln1.player2_optimal()
 
-        alpha = uniform(-10, 10)
-        tensor_prod = e1*e2.trans()
-
         # This is the "correct" representation of ``M``, but COLUMN
         # indexed...
-        M = L + alpha*tensor_prod
-
-        # so we have to transpose it when we feed it to the constructor.
-        game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
-        value2 = game2.solution().game_value()
+        (alpha, H) = random_translation(G)
+        value2 = H.solution().game_value()
 
-        self.assert_within_tol(value1 + alpha, value2)
+        self.assert_within_tol(value1 + alpha, value2, H.condition())
 
         # Make sure the same optimal pair works.
-        self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
+        self.assert_within_tol(value2,
+                               H.payoff(x_bar, y_bar),
+                               H.condition())
 
 
     def test_translation_orthant(self):
         """
         Test that translation works over the nonnegative orthant.
         """
-        (L, K, e1, e2) = random_orthant_params()
-        self.assert_translation_works(L, K, e1, e2)
+        G = random_orthant_game()
+        self.assert_translation_works(G)
 
 
     def test_translation_icecream(self):
@@ -379,37 +187,37 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         The same as :meth:`test_translation_orthant`, except over the
         ice cream cone.
         """
-        (L, K, e1, e2) = random_icecream_params()
-        self.assert_translation_works(L, K, e1, e2)
+        G = random_icecream_game()
+        self.assert_translation_works(G)
 
 
-    def assert_opposite_game_works(self, L, K, e1, e2):
+    def assert_opposite_game_works(self, G):
         """
         Check the value of the "opposite" game that gives rise to a
         value that is the negation of the original game. Comes from
         some corollary.
         """
-        # We need to use ``L`` later, so make sure we transpose it
-        # before passing it in as a column-indexed matrix.
-        game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
-
         # This is the "correct" representation of ``M``, but
         # COLUMN indexed...
-        M = -L.trans()
+        M = -G.L().trans()
 
         # so we have to transpose it when we feed it to the constructor.
-        game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
+        # Note: the condition number of ``H`` should be comparable to ``G``.
+        H = SymmetricLinearGame(M.trans(), G.K(), G.e2(), G.e1())
 
-        soln1 = game1.solution()
+        soln1 = G.solution()
         x_bar = soln1.player1_optimal()
         y_bar = soln1.player2_optimal()
-        soln2 = game2.solution()
+        soln2 = H.solution()
 
-        self.assert_within_tol(-soln1.game_value(), soln2.game_value())
+        self.assert_within_tol(-soln1.game_value(),
+                               soln2.game_value(),
+                               H.condition())
 
         # Make sure the switched optimal pair works.
         self.assert_within_tol(soln2.game_value(),
-                               inner_product(M*y_bar, x_bar))
+                               H.payoff(y_bar, x_bar),
+                               H.condition())
 
 
     def test_opposite_game_orthant(self):
@@ -417,8 +225,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Test the value of the "opposite" game over the nonnegative
         orthant.
         """
-        (L, K, e1, e2) = random_orthant_params()
-        self.assert_opposite_game_works(L, K, e1, e2)
+        G = random_orthant_game()
+        self.assert_opposite_game_works(G)
 
 
     def test_opposite_game_icecream(self):
@@ -426,28 +234,25 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Like :meth:`test_opposite_game_orthant`, except over the
         ice-cream cone.
         """
-        (L, K, e1, e2) = random_icecream_params()
-        self.assert_opposite_game_works(L, K, e1, e2)
+        G = random_icecream_game()
+        self.assert_opposite_game_works(G)
 
 
-    def assert_orthogonality(self, L, K, e1, e2):
+    def assert_orthogonality(self, G):
         """
         Two orthogonality relations hold at an optimal solution, and we
         check them here.
         """
-        # We need to use ``L`` later, so make sure we transpose it
-        # before passing it in as a column-indexed matrix.
-        game = SymmetricLinearGame(L.trans(), K, e1, e2)
-        soln = game.solution()
+        soln = G.solution()
         x_bar = soln.player1_optimal()
         y_bar = soln.player2_optimal()
         value = soln.game_value()
 
-        ip1 = inner_product(y_bar, L*x_bar - value*e1)
-        self.assert_within_tol(ip1, 0)
+        ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1())
+        self.assert_within_tol(ip1, 0, G.condition())
 
-        ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
-        self.assert_within_tol(ip2, 0)
+        ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar)
+        self.assert_within_tol(ip2, 0, G.condition())
 
 
     def test_orthogonality_orthant(self):
@@ -455,8 +260,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Check the orthgonality relationships that hold for a solution
         over the nonnegative orthant.
         """
-        (L, K, e1, e2) = random_orthant_params()
-        self.assert_orthogonality(L, K, e1, e2)
+        G = random_orthant_game()
+        self.assert_orthogonality(G)
 
 
     def test_orthogonality_icecream(self):
@@ -464,8 +269,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         Check the orthgonality relationships that hold for a solution
         over the ice-cream cone.
         """
-        (L, K, e1, e2) = random_icecream_params()
-        self.assert_orthogonality(L, K, e1, e2)
+        G = random_icecream_game()
+        self.assert_orthogonality(G)
 
 
     def test_positive_operator_value(self):
@@ -476,53 +281,51 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
         This test theoretically applies to the ice-cream cone as well,
         but we don't know how to make positive operators on that cone.
         """
-        (K, e1, e2) = random_orthant_params()[1:]
-        L = random_nonnegative_matrix(K.dimension())
+        G = random_positive_orthant_game()
+        self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 
-        game = SymmetricLinearGame(L, K, e1, e2)
-        self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 
-
-    def assert_lyapunov_works(self, L, K, e1, e2):
+    def assert_lyapunov_works(self, G):
         """
         Check that Lyapunov games act the way we expect.
         """
-        game = SymmetricLinearGame(L, K, e1, e2)
-        soln = game.solution()
+        soln = G.solution()
 
         # We only check for positive/negative stability if the game
         # value is not basically zero. If the value is that close to
         # zero, we just won't check any assertions.
-        eigs = eigenvalues_re(L)
-        if soln.game_value() > options.ABS_TOL:
+        #
+        # See :meth:`assert_within_tol` for an explanation of the
+        # fudge factors.
+        eigs = eigenvalues_re(G.L())
+
+        if soln.game_value() > EPSILON:
             # L should be positive stable
             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
             self.assertTrue(positive_stable)
-        elif soln.game_value() < -options.ABS_TOL:
+        elif soln.game_value() < -EPSILON:
             # L should be negative stable
             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
             self.assertTrue(negative_stable)
 
         # The dual game's value should always equal the primal's.
-        dualsoln = game.dual().solution()
-        self.assert_within_tol(dualsoln.game_value(), soln.game_value())
+        dualsoln = G.dual().solution()
+        self.assert_within_tol(dualsoln.game_value(),
+                               soln.game_value(),
+                               G.condition())
 
 
     def test_lyapunov_orthant(self):
         """
         Test that a Lyapunov game on the nonnegative orthant works.
         """
-        (K, e1, e2) = random_orthant_params()[1:]
-        L = random_diagonal_matrix(K.dimension())
-
-        self.assert_lyapunov_works(L, K, e1, e2)
+        G = random_ll_orthant_game()
+        self.assert_lyapunov_works(G)
 
 
     def test_lyapunov_icecream(self):
         """
         Test that a Lyapunov game on the ice-cream cone works.
         """
-        (K, e1, e2) = random_icecream_params()[1:]
-        L = random_lyapunov_like_icecream(K.dimension())
-
-        self.assert_lyapunov_works(L, K, e1, e2)
+        G = random_ll_icecream_game()
+        self.assert_lyapunov_works(G)