X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=test%2Fsymmetric_linear_game_test.py;h=936a7e869283b4fd9ee2e82ddccefa5ef7253658;hb=96a9491fcc4c7df4c73f9617f2185586b0226b78;hp=5adbb2ddd11942faf3c31354513b62ab6877e853;hpb=e56739b9f432a5f2dce0223158de946b3db6c0e5;p=dunshire.git

diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py
index 5adbb2d..936a7e8 100644
--- a/test/symmetric_linear_game_test.py
+++ b/test/symmetric_linear_game_test.py
@@ -1,153 +1,90 @@
-# These few are used only for tests.
-from math import sqrt
-from random import randint, uniform
+"""
+Unit tests for the :class:`SymmetricLinearGame` class.
+"""
+
 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 (``dims``-by-``dims``) matrix. This is used
-    only by the :class:`SymmetricLinearGameTest` class.
-    """
-    return matrix([[uniform(-10, 10) for i in range(dims)]
-                   for j in range(dims)])
-
-def _random_nonnegative_matrix(dims):
-    """
-    Generate a random square (``dims``-by-``dims``) matrix with
-    nonnegative entries. This is used only by the
-    :class:`SymmetricLinearGameTest` class.
-    """
-    L = _random_matrix(dims)
-    return matrix([abs(entry) for entry in L], (dims, dims))
-
-def _random_diagonal_matrix(dims):
-    """
-    Generate a random square (``dims``-by-``dims``) matrix with nonzero
-    entries only on the diagonal. This is used only by the
-    :class:`SymmetricLinearGameTest` class.
-    """
-    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 (``dims``-by-``dims``) matrix.
-
-    Examples
-    --------
-
-        >>> 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 assert_within_tol(self, first, second, modifier=1):
+        """
+        Test that ``first`` and ``second`` are equal within a multiple of
+        our default tolerances.
 
-def _random_lyapunov_like_icecream(dims):
-    """
-    Generate a random Lyapunov-like matrix over the ice-cream cone in
-    ``dims`` dimensions.
-    """
-    a = matrix([uniform(-10, 10)], (1, 1))
-    b = matrix([uniform(-10, 10) for idx 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)
+        Parameters
+        ----------
 
+        first : float
+            The first number to compare.
 
-def _random_orthant_params():
-    """
-    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
-    random game over the nonnegative orthant. This is only used by
-    the :class:`SymmetricLinearGameTest` class.
-    """
-    ambient_dim = randint(1, 10)
-    K = NonnegativeOrthant(ambient_dim)
-    e1 = [uniform(0.5, 10) for idx in range(K.dimension())]
-    e2 = [uniform(0.5, 10) for idx in range(K.dimension())]
-    L = _random_matrix(K.dimension())
-    return (L, K, matrix(e1), matrix(e2))
+        second : float
+            The second number to compare.
 
+        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.
 
-def _random_icecream_params():
-    """
-    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
-    random game over the ice cream cone. This is only used by
-    the :class:`SymmetricLinearGameTest` class.
-    """
-    # 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 idx in range(K.dimension() - 1)]
-    e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
-    L = _random_matrix(K.dimension())
-
-    return (L, K, matrix(e1), matrix(e2))
+        """
+        self.assertTrue(abs(first - second) < EPSILON*modifier)
 
 
-# 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):
+    def assert_solution_exists(self, G):
         """
-        Test that ``first`` and ``second`` are equal within our default
-        tolerance.
+        Given  a SymmetricLinearGame, ensure that it has a solution.
         """
-        self.assertTrue(abs(first - second) < options.ABS_TOL)
+        soln = G.solution()
 
+        expected = inner_product(G._L*soln.player1_optimal(),
+                                 soln.player2_optimal())
+        self.assert_within_tol(soln.game_value(), expected, G.condition())
 
-    def assert_norm_within_tol(self, first, second):
-        """
-        Test that ``first`` and ``second`` vectors are equal in the
-        sense that the norm of their difference is within our default
-        tolerance.
-        """
-        self.assert_within_tol(norm(first - second), 0)
 
 
-    def assert_solution_exists(self, L, K, e1, e2):
-        """
-        Given the parameters needed to construct a SymmetricLinearGame,
-        ensure that that game has a solution.
+    def test_condition_lower_bound(self):
         """
-        # 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()
+        Ensure that the condition number of a game is greater than or
+        equal to one.
 
-        expected = inner_product(L*soln.player1_optimal(),
-                                 soln.player2_optimal())
-        self.assert_within_tol(soln.game_value(), expected)
+        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.
+        """
+        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):
@@ -158,8 +95,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):
@@ -167,8 +104,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):
@@ -184,18 +121,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):
@@ -203,8 +137,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):
@@ -212,46 +146,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
+        (alpha, H) = random_translation(G)
+        value2 = H.solution().game_value()
 
-        # 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()
-
-        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,
+                               inner_product(H._L*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):
@@ -259,37 +188,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))
+                               inner_product(M*y_bar, x_bar),
+                               H.condition())
 
 
     def test_opposite_game_orthant(self):
@@ -297,8 +226,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):
@@ -306,28 +235,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):
@@ -335,8 +261,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):
@@ -344,8 +270,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):
@@ -356,53 +282,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())
-
-        game = SymmetricLinearGame(L, K, e1, e2)
-        self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
+        G = random_positive_orthant_game()
+        self.assertTrue(G.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)