X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=test%2Fsymmetric_linear_game_test.py;h=1e7194b6bf08e50c1739539469a36279d866f8c1;hb=e22adb2af08288282c3f085eb7a43ab131577bfe;hp=f61356d7ece50cf6df2807181587920175123264;hpb=21a2eb9a647a48c0e94d02c60ef8785c4ea35f7b;p=dunshire.git diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py index f61356d..1e7194b 100644 --- a/test/symmetric_linear_game_test.py +++ b/test/symmetric_linear_game_test.py @@ -2,243 +2,15 @@ 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.games import SymmetricLinearGame -from dunshire.matrices import (append_col, append_row, eigenvalues_re, - identity, inner_product) +from dunshire.matrices import eigenvalues_re, inner_product, norm from dunshire import options - - -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 i in range(dims)] - for j 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): - """ - 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 - - """ - 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]. - - 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) - row1 = append_col(a, b.trans()) - row2 = append_col(b, D) - return append_row(row1, row2) - - -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 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)) - - -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 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)) +from .randomgen import (random_icecream_game, random_ll_icecream_game, + random_ll_orthant_game, random_nn_scaling, + random_orthant_game, random_positive_orthant_game, + random_translation) # Tell pylint to shut up about the large number of methods. @@ -246,76 +18,81 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ Tests for the SymmetricLinearGame and Solution classes. """ - def assert_within_tol(self, first, second): + def assert_within_tol(self, first, second, modifier=1): """ - 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. + Parameters + ---------- - def assert_solution_exists(self, L, K, e1, e2): - """ - Given the parameters needed to construct a SymmetricLinearGame, - ensure that that game 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() + first : float + The first number to compare. - expected = inner_product(L*soln.player1_optimal(), - soln.player2_optimal()) - self.assert_within_tol(soln.game_value(), expected) + second : float + The second number to compare. + modifier : float + A scaling factor (default: 1) applied to the default + tolerance for this comparison. If you have a poorly- + conditioned matrix, for example, you may want to set this + greater than one. - def test_solution_exists_orthant(self): - """ - Every linear game has a solution, so we should be able to solve - every symmetric linear game over the NonnegativeOrthant. Pick - some parameters randomly and give it a shot. The resulting - 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) + self.assertTrue(abs(first - second) < options.ABS_TOL*modifier) + + def test_solutions_dont_change_orthant(self): + G = random_orthant_game() + self.assert_solutions_dont_change(G) - def test_solution_exists_icecream(self): + def test_solutions_dont_change_icecream(self): + G = random_icecream_game() + self.assert_solutions_dont_change(G) + + def assert_solutions_dont_change(self, G): """ - Like :meth:`test_solution_exists_nonnegative_orthant`, except - over the ice cream cone. + If we solve the same problem twice, we should get + the same answer both times. """ - (L, K, e1, e2) = random_icecream_params() - self.assert_solution_exists(L, K, e1, e2) + soln1 = G.solution() + soln2 = G.solution() + p1_diff = norm(soln1.player1_optimal() - soln2.player1_optimal()) + p2_diff = norm(soln1.player2_optimal() - soln2.player2_optimal()) + gv_diff = abs(soln1.game_value() - soln2.game_value()) + + p1_close = p1_diff < options.ABS_TOL + p2_close = p2_diff < options.ABS_TOL + gv_close = gv_diff < options.ABS_TOL + + self.assertTrue(p1_close and p2_close and gv_close) - def test_negative_value_z_operator(self): + def test_condition_lower_bound(self): """ - Test the example given in Gowda/Ravindran of a Z-matrix with - negative game value on the nonnegative orthant. + 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. """ - K = NonnegativeOrthant(2) - e1 = [1, 1] - e2 = e1 - L = [[1, -2], [-2, 1]] - G = SymmetricLinearGame(L, K, e1, e2) - self.assertTrue(G.solution().game_value() < -options.ABS_TOL) + G = random_orthant_game() + self.assertTrue(G.condition() >= 1.0) + G = random_icecream_game() + self.assertTrue(G.condition() >= 1.0) - 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() + modifier = 4*max(abs(alpha), 1) + self.assert_within_tol(alpha*value1, value2, modifier) def test_scaling_orthant(self): @@ -323,8 +100,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 +109,40 @@ 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) + modifier = 4*max(abs(alpha), 1) + self.assert_within_tol(value1 + alpha, value2, modifier) # 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), modifier) 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 +150,38 @@ 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() + + # The modifier of 4 is because each could be off by 2*ABS_TOL, + # which is how far apart the primal/dual objectives have been + # observed being. + self.assert_within_tol(-soln1.game_value(), soln2.game_value(), 4) - self.assert_within_tol(-soln1.game_value(), soln2.game_value()) + # Make sure the switched optimal pair works. Since x_bar and + # y_bar come from G, we use the same modifier. + self.assert_within_tol(soln2.game_value(), H.payoff(y_bar, x_bar), 4) - # Make sure the switched optimal pair works. - self.assert_within_tol(soln2.game_value(), - inner_product(M*y_bar, x_bar)) def test_opposite_game_orthant(self): @@ -417,8 +189,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 +198,30 @@ 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()) + ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar) - ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar) - self.assert_within_tol(ip2, 0) + # Huh.. well, y_bar and x_bar can each be epsilon away, but + # x_bar is scaled by L, so that's (norm(L) + 1), and then + # value could be off by epsilon, so that's another norm(e1) or + # norm(e2). On the other hand, this test seems to pass most of + # the time even with a modifier of one. How about.. four? + self.assert_within_tol(ip1, 0, 4) + self.assert_within_tol(ip2, 0, 4) def test_orthogonality_orthant(self): @@ -455,8 +229,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 +238,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,24 +250,24 @@ 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) + # + # See :meth:`assert_within_tol` for an explanation of the + # fudge factors. + eigs = eigenvalues_re(G.L()) + if soln.game_value() > options.ABS_TOL: # L should be positive stable positive_stable = all([eig > -options.ABS_TOL for eig in eigs]) @@ -504,25 +278,23 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 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()) + # The modifier of 4 is because even though the games are dual, + # CVXOPT doesn't know that, and each could be off by 2*ABS_TOL. + dualsoln = G.dual().solution() + self.assert_within_tol(dualsoln.game_value(), soln.game_value(), 4) 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)