X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=test%2Fsymmetric_linear_game_test.py;h=bba2f7ccfcb48c38312e5d5849aae892d40eac31;hb=2b44481f8a79cbab75ddc0f73eea813b66e17d62;hp=2978f11b627feeefe5edc82d89bec466eaae455b;hpb=80a45eb7673f79a55ee638fb921b8f501ae381c7;p=dunshire.git diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py index 2978f11..bba2f7c 100644 --- a/test/symmetric_linear_game_test.py +++ b/test/symmetric_linear_game_test.py @@ -2,292 +2,62 @@ 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 -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) - -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 [-RANDOM_MAX, RANDOM_MAX]. - - Examples - -------- - - >>> A = random_matrix(3) - >>> A.size - (3, 3) - - """ - return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX) 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, RANDOM_MAX]. - - 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 [-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(-RANDOM_MAX, RANDOM_MAX)*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 - [-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)) - >>> 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 _ 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_game(): - """ - Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a - 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()) - G = SymmetricLinearGame(L, K, e1, e2) - - if G._condition() <= MAX_COND: - return G - else: - return random_orthant_game() - - -def random_icecream_game(): - """ - Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a - 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. - 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()) - G = SymmetricLinearGame(L, K, e1, e2) - - if G._condition() <= MAX_COND: - return G - else: - return random_icecream_game() - +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). +""" # 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_within_tol(self, first, second, modifier=1): """ 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. + Parameters + ---------- + + first : float + The first number to compare. + + 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. + """ - self.assertTrue(abs(first - second) < 2*2*RANDOM_MAX*options.ABS_TOL) + self.assertTrue(abs(first - second) < EPSILON*modifier) def assert_solution_exists(self, G): @@ -296,9 +66,8 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ soln = G.solution() - expected = inner_product(G._L*soln.player1_optimal(), - soln.player2_optimal()) - self.assert_within_tol(soln.game_value(), expected) + expected = G.payoff(soln.player1_optimal(), soln.player2_optimal()) + self.assert_within_tol(soln.game_value(), expected, G.condition()) @@ -312,9 +81,9 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 to a smaller nonnegative real number. """ G = random_orthant_game() - self.assertTrue(G._condition() >= 1.0) + self.assertTrue(G.condition() >= 1.0) G = random_icecream_game() - self.assertTrue(G._condition() >= 1.0) + self.assertTrue(G.condition() >= 1.0) def test_solution_exists_orthant(self): @@ -351,29 +120,15 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 self.assertTrue(G.solution().game_value() < -options.ABS_TOL) - def assert_scaling_works(self, game1): + def assert_scaling_works(self, G): """ Test that scaling ``L`` by a nonnegative number scales the value of the game by the same number. """ - value1 = game1.solution().game_value() - - alpha = uniform(0.1, 10) - 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) + (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): @@ -394,41 +149,29 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 self.assert_scaling_works(G) - def assert_translation_works(self, game1): + 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. - soln1 = game1.solution() + soln1 = G.solution() value1 = soln1.game_value() x_bar = soln1.player1_optimal() y_bar = soln1.player2_optimal() - tensor_prod = game1._e1*game1._e2.trans() # This is the "correct" representation of ``M``, but COLUMN # indexed... - 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(), 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() + (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): @@ -448,7 +191,7 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 self.assert_translation_works(G) - def assert_opposite_game_works(self, game1): + 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 @@ -456,22 +199,25 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ # This is the "correct" representation of ``M``, but # COLUMN indexed... - M = -game1._L.trans() + M = -G.L().trans() # so we have to transpose it when we feed it to the constructor. - # Note: the condition number of game2 should be comparable to game1. - game2 = SymmetricLinearGame(M.trans(), game1._K, game1._e2, game1._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): @@ -502,11 +248,11 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 y_bar = soln.player2_optimal() value = soln.game_value() - ip1 = inner_product(y_bar, G._L*x_bar - value*G._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*G._e2 - G._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): @@ -535,18 +281,7 @@ 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. """ - 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) - + G = random_positive_orthant_game() self.assertTrue(G.solution().game_value() >= -options.ABS_TOL) @@ -562,42 +297,29 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 # # 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: + 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]) - if not positive_stable: - print(str(eigs)) self.assertTrue(positive_stable) - elif soln.game_value() < -epsilon: + 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 = G.dual().solution() - self.assert_within_tol(dualsoln.game_value(), soln.game_value()) + 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. """ - 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) - + G = random_ll_orthant_game() self.assert_lyapunov_works(G) @@ -605,16 +327,5 @@ class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ Test that a Lyapunov game on the ice-cream cone works. """ - 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) - + G = random_ll_icecream_game() self.assert_lyapunov_works(G)