From 80a45eb7673f79a55ee638fb921b8f501ae381c7 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Mon, 31 Oct 2016 20:15:50 -0400 Subject: [PATCH] Overhaul the tests to get more predictable behavior. The most important change to the SymmetricLinearGame tests is that we now check the condition numbers of the generated games. That prevents most of the numerical trouble experienced before, and solves a few open TODO items. A RANDOM_MAX constant was introduced, and incorporated into the fudge factor for the absolute tolerance used in tests. That contributes to fixing the open TODO items as well. The test code itself is pretty ugly now, but it can be fixed once they all pass reliably (there's still a Lyapunov-like test failing). --- test/symmetric_linear_game_test.py | 262 +++++++++++++++++++---------- 1 file changed, 177 insertions(+), 85 deletions(-) diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py index 69c352a..2978f11 100644 --- a/test/symmetric_linear_game_test.py +++ b/test/symmetric_linear_game_test.py @@ -2,6 +2,18 @@ Unit tests for the :class:`SymmetricLinearGame` class. """ +MAX_COND = 250 +""" +The maximum condition number of a randomly-generated game. +""" + +RANDOM_MAX = 10 +""" +When generating uniform random real numbers, this will be used as the +largest allowed magnitude. It keeps our condition numbers down and other +properties within reason. +""" + from math import sqrt from random import randint, uniform from unittest import TestCase @@ -29,7 +41,7 @@ def random_matrix(dims): matrix A new matrix whose entries are random floats chosen uniformly from - the interval [-10, 10]. + the interval [-RANDOM_MAX, RANDOM_MAX]. Examples -------- @@ -39,7 +51,7 @@ def random_matrix(dims): (3, 3) """ - return matrix([[uniform(-10, 10) for _ in range(dims)] + return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX) for _ in range(dims)] for _ in range(dims)]) @@ -58,7 +70,7 @@ def random_nonnegative_matrix(dims): matrix A new matrix whose entries are random floats chosen uniformly from - the interval [0, 10]. + the interval [0, RANDOM_MAX]. Examples -------- @@ -92,8 +104,8 @@ def random_diagonal_matrix(dims): matrix A new matrix whose diagonal entries are random floats chosen - uniformly from the interval [-10, 10] and whose off-diagonal - entries are zero. + uniformly from the interval [-RANDOM_MAX, RANDOM_MAX] and whose + off-diagonal entries are zero. Examples -------- @@ -105,7 +117,8 @@ def random_diagonal_matrix(dims): True """ - return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)] + return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX)*int(i == j) + for i in range(dims)] for j in range(dims)]) @@ -124,7 +137,8 @@ def random_skew_symmetric_matrix(dims): matrix A new skew-matrix whose strictly above-diagonal entries are - random floats chosen uniformly from the interval [-10, 10]. + random floats chosen uniformly from the interval + [-RANDOM_MAX, RANDOM_MAX]. Examples -------- @@ -201,23 +215,33 @@ def random_lyapunov_like_icecream(dims): return append_row(row1, row2) -def random_orthant_params(): +def random_orthant_game(): """ Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a - random game over the nonnegative orthant. + random game over the nonnegative orthant, and return the + corresponding :class:`SymmetricLinearGame`. + + We keep going until we generate a game with a condition number under + 5000. """ 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)) + G = SymmetricLinearGame(L, K, e1, e2) + if G._condition() <= MAX_COND: + return G + else: + return random_orthant_game() -def random_icecream_params(): + +def random_icecream_game(): """ Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a - random game over the ice-cream cone. + random game over the ice-cream cone, and return the corresponding + :class:`SymmetricLinearGame`. """ # Use a minimum dimension of two to avoid divide-by-zero in # the fudge factor we make up later. @@ -237,8 +261,12 @@ def random_icecream_params(): 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()) + G = SymmetricLinearGame(L, K, e1, e2) - return (L, K, matrix(e1), matrix(e2)) + if G._condition() <= MAX_COND: + return G + else: + return random_icecream_game() # Tell pylint to shut up about the large number of methods. @@ -248,28 +276,47 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ def assert_within_tol(self, first, second): """ - Test that ``first`` and ``second`` are equal within our default - tolerance. + Test that ``first`` and ``second`` are equal within a multiple of + our default tolerances. + + The factor of two is because if we compare two solutions, both + of which may be off by ``ABS_TOL``, then the result could be off + by ``2*ABS_TOL``. The factor of ``RANDOM_MAX`` allows for + scaling a result (by ``RANDOM_MAX``) that may be off by + ``ABS_TOL``. The final factor of two is to allow for the edge + cases where we get an "unknown" result and need to lower the + CVXOPT tolerance by a factor of two. """ - self.assertTrue(abs(first - second) < options.ABS_TOL) + self.assertTrue(abs(first - second) < 2*2*RANDOM_MAX*options.ABS_TOL) - def assert_solution_exists(self, L, K, e1, e2): + def assert_solution_exists(self, G): """ - Given the parameters needed to construct a SymmetricLinearGame, - ensure that that game has a solution. + Given a SymmetricLinearGame, ensure that it has a solution. """ - # 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(), + expected = inner_product(G._L*soln.player1_optimal(), soln.player2_optimal()) self.assert_within_tol(soln.game_value(), expected) + + def test_condition_lower_bound(self): + """ + Ensure that the condition number of a game is greater than or + equal to one. + + 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): """ Every linear game has a solution, so we should be able to solve @@ -278,8 +325,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 +334,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,16 +351,27 @@ 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, game1): """ 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) + game2 = SymmetricLinearGame(alpha*game1._L.trans(), + game1._K, + game1._e1, + game1._e2) + + while game2._condition() > MAX_COND: + # Loop until the condition number of game2 doesn't suck. + alpha = uniform(0.1, 10) + game2 = SymmetricLinearGame(alpha*game1._L.trans(), + game1._K, + game1._e1, + game1._e2) + value2 = game2.solution().game_value() self.assert_within_tol(alpha*value1, value2) @@ -323,8 +381,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,32 +390,39 @@ 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, game1): """ 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() value1 = soln1.game_value() x_bar = soln1.player1_optimal() y_bar = soln1.player2_optimal() - - alpha = uniform(-10, 10) - tensor_prod = e1*e2.trans() + tensor_prod = game1._e1*game1._e2.trans() # This is the "correct" representation of ``M``, but COLUMN # indexed... - M = L + alpha*tensor_prod + alpha = uniform(-10, 10) + M = game1._L + alpha*tensor_prod # so we have to transpose it when we feed it to the constructor. - game2 = SymmetricLinearGame(M.trans(), K, e1, e2) + game2 = SymmetricLinearGame(M.trans(), game1._K, game1._e1, game1._e2) + while game2._condition() > MAX_COND: + # Loop until the condition number of game2 doesn't suck. + alpha = uniform(-10, 10) + M = game1._L + alpha*tensor_prod + game2 = SymmetricLinearGame(M.trans(), + game1._K, + game1._e1, + game1._e2) + value2 = game2.solution().game_value() self.assert_within_tol(value1 + alpha, value2) @@ -370,8 +435,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ 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,26 +444,23 @@ 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, game1): """ 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 = -game1._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 game2 should be comparable to game1. + game2 = SymmetricLinearGame(M.trans(), game1._K, game1._e2, game1._e1) soln1 = game1.solution() x_bar = soln1.player1_optimal() @@ -417,8 +479,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,27 +488,24 @@ 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) + ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1) self.assert_within_tol(ip1, 0) - ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar) + ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar) self.assert_within_tol(ip2, 0) @@ -455,8 +514,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 +523,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,35 +535,50 @@ 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_orthant_game() + L = random_nonnegative_matrix(G._K.dimension()) + + # Replace the totally-random ``L`` with the random nonnegative one. + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) - game = SymmetricLinearGame(L, K, e1, e2) - self.assertTrue(game.solution().game_value() >= -options.ABS_TOL) + while G._condition() > MAX_COND: + # Try again until the condition number is satisfactory. + G = random_orthant_game() + L = random_nonnegative_matrix(G._K.dimension()) + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + 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) + epsilon = 2*2*RANDOM_MAX*options.ABS_TOL + if soln.game_value() > epsilon: # L should be positive stable positive_stable = all([eig > -options.ABS_TOL for eig in eigs]) + if not positive_stable: + print(str(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]) + if not negative_stable: + print(str(eigs)) self.assertTrue(negative_stable) # The dual game's value should always equal the primal's. - dualsoln = game.dual().solution() + dualsoln = G.dual().solution() self.assert_within_tol(dualsoln.game_value(), soln.game_value()) @@ -512,17 +586,35 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ Test that a Lyapunov game on the nonnegative orthant works. """ - (K, e1, e2) = random_orthant_params()[1:] - L = random_diagonal_matrix(K.dimension()) + G = random_orthant_game() + L = random_diagonal_matrix(G._K.dimension()) - self.assert_lyapunov_works(L, K, e1, e2) + # Replace the totally-random ``L`` with random Lyapunov-like one. + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + + while G._condition() > MAX_COND: + # Try again until the condition number is satisfactory. + G = random_orthant_game() + L = random_diagonal_matrix(G._K.dimension()) + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + + 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()) + G = random_icecream_game() + L = random_lyapunov_like_icecream(G._K.dimension()) + + # Replace the totally-random ``L`` with random Lyapunov-like one. + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) + + while G._condition() > MAX_COND: + # Try again until the condition number is satisfactory. + G = random_orthant_game() + L = random_lyapunov_like_icecream(G._K.dimension()) + G = SymmetricLinearGame(L, G._K, G._e1, G._e2) - self.assert_lyapunov_works(L, K, e1, e2) + self.assert_lyapunov_works(G) -- 2.44.2