X-Git-Url: https://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=test%2Fsymmetric_linear_game_test.py;h=2978f11b627feeefe5edc82d89bec466eaae455b;hb=c987962fdd4caab7db3801935bc57b744e5fe994;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..2978f11 100644 --- a/test/symmetric_linear_game_test.py +++ b/test/symmetric_linear_game_test.py @@ -1,4 +1,19 @@ -# These few are used only for tests. +""" +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 @@ -10,42 +25,130 @@ from dunshire.matrices import (append_col, append_row, eigenvalues_re, identity, inner_product) from dunshire import options -def _random_matrix(dims): + +def random_matrix(dims): """ - Generate a random square (``dims``-by-``dims``) matrix. This is used - only by the :class:`SymmetricLinearGameTest` class. + 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 [-RANDOM_MAX, RANDOM_MAX]. + + Examples + -------- + + >>> A = random_matrix(3) + >>> A.size + (3, 3) + """ - return matrix([[uniform(-10, 10) for i in range(dims)] - for j in range(dims)]) + return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX) for _ in range(dims)] + for _ in range(dims)]) + -def _random_nonnegative_matrix(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. + 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, RANDOM_MAX]. + + Examples + -------- + + >>> A = random_nonnegative_matrix(3) + >>> A.size + (3, 3) + >>> all([entry >= 0 for entry in A]) + True + """ - L = _random_matrix(dims) + L = random_matrix(dims) return matrix([abs(entry) for entry in L], (dims, dims)) -def _random_diagonal_matrix(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. + 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 [-RANDOM_MAX, RANDOM_MAX] 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)] + return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX)*int(i == j) + for i in range(dims)] for j in range(dims)]) -def _random_skew_symmetric_matrix(dims): +def random_skew_symmetric_matrix(dims): """ - Generate a random skew-symmetrix (``dims``-by-``dims``) matrix. + 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 + [-RANDOM_MAX, RANDOM_MAX]. Examples -------- + >>> A = random_skew_symmetric_matrix(3) + >>> A.size + (3, 3) + >>> from dunshire.matrices import norm - >>> A = _random_skew_symmetric_matrix(randint(1, 10)) + >>> A = random_skew_symmetric_matrix(randint(1, 10)) >>> norm(A + A.trans()) < options.ABS_TOL True @@ -57,38 +160,88 @@ def _random_skew_symmetric_matrix(dims): return strict_ut - strict_ut.trans() -def _random_lyapunov_like_icecream(dims): - """ - Generate a random Lyapunov-like matrix over the ice-cream cone in - ``dims`` dimensions. +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]. + + References + ---------- + + .. [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. + + Examples + -------- + + >>> 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 + """ 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) + 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) -def _random_orthant_params(): +def random_orthant_game(): """ 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. + 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 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)) + 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()) + 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. This is only used by - the :class:`SymmetricLinearGameTest` class. + 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. @@ -105,11 +258,15 @@ def _random_icecream_params(): # 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()) + 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. @@ -119,37 +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. - """ - self.assertTrue(abs(first - second) < options.ABS_TOL) - + Test that ``first`` and ``second`` are equal within a multiple of + our default tolerances. - def assert_norm_within_tol(self, first, second): + 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. """ - 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) + 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 @@ -158,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): @@ -167,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): @@ -184,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) @@ -203,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): @@ -212,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) @@ -250,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): @@ -259,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() @@ -297,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): @@ -306,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) @@ -335,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): @@ -344,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): @@ -356,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) + + 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) - game = SymmetricLinearGame(L, K, e1, e2) - self.assertTrue(game.solution().game_value() >= -options.ABS_TOL) + 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()) @@ -392,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()) + + # 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(L, K, e1, 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)