test/symmetric_linear_game_test.py

   1 # These few are used only for tests.
   2 from math import sqrt
   3 from random import randint, uniform
   4 from unittest import TestCase
   5
   6 from cvxopt import matrix
   7 from dunshire.cones import NonnegativeOrthant, IceCream
   8 from dunshire.games import SymmetricLinearGame
   9 from dunshire.matrices import (append_col, append_row, eigenvalues_re,
  10                                identity, inner_product)
  11 from dunshire import options
  12
  13 def _random_matrix(dims):
  14     """
  15     Generate a random square (``dims``-by-``dims``) matrix. This is used
  16     only by the :class:`SymmetricLinearGameTest` class.
  17     """
  18     return matrix([[uniform(-10, 10) for i in range(dims)]
  19                    for j in range(dims)])
  20
  21 def _random_nonnegative_matrix(dims):
  22     """
  23     Generate a random square (``dims``-by-``dims``) matrix with
  24     nonnegative entries. This is used only by the
  25     :class:`SymmetricLinearGameTest` class.
  26     """
  27     L = _random_matrix(dims)
  28     return matrix([abs(entry) for entry in L], (dims, dims))
  29
  30 def _random_diagonal_matrix(dims):
  31     """
  32     Generate a random square (``dims``-by-``dims``) matrix with nonzero
  33     entries only on the diagonal. This is used only by the
  34     :class:`SymmetricLinearGameTest` class.
  35     """
  36     return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)]
  37                    for j in range(dims)])
  38
  39
  40 def _random_skew_symmetric_matrix(dims):
  41     """
  42     Generate a random skew-symmetrix (``dims``-by-``dims``) matrix.
  43
  44     Examples
  45     --------
  46
  47         >>> from dunshire.matrices import norm
  48         >>> A = _random_skew_symmetric_matrix(randint(1, 10))
  49         >>> norm(A + A.trans()) < options.ABS_TOL
  50         True
  51
  52     """
  53     strict_ut = [[uniform(-10, 10)*int(i < j) for i in range(dims)]
  54                  for j in range(dims)]
  55
  56     strict_ut = matrix(strict_ut, (dims, dims))
  57     return strict_ut - strict_ut.trans()
  58
  59
  60 def _random_lyapunov_like_icecream(dims):
  61     """
  62     Generate a random Lyapunov-like matrix over the ice-cream cone in
  63     ``dims`` dimensions.
  64     """
  65     a = matrix([uniform(-10, 10)], (1, 1))
  66     b = matrix([uniform(-10, 10) for idx in range(dims-1)], (dims-1, 1))
  67     D = _random_skew_symmetric_matrix(dims-1) + a*identity(dims-1)
  68     row1 = append_col(a, b.trans())
  69     row2 = append_col(b, D)
  70     return append_row(row1, row2)
  71
  72
  73 def _random_orthant_params():
  74     """
  75     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
  76     random game over the nonnegative orthant. This is only used by
  77     the :class:`SymmetricLinearGameTest` class.
  78     """
  79     ambient_dim = randint(1, 10)
  80     K = NonnegativeOrthant(ambient_dim)
  81     e1 = [uniform(0.5, 10) for idx in range(K.dimension())]
  82     e2 = [uniform(0.5, 10) for idx in range(K.dimension())]
  83     L = _random_matrix(K.dimension())
  84     return (L, K, matrix(e1), matrix(e2))
  85
  86
  87 def _random_icecream_params():
  88     """
  89     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
  90     random game over the ice cream cone. This is only used by
  91     the :class:`SymmetricLinearGameTest` class.
  92     """
  93     # Use a minimum dimension of two to avoid divide-by-zero in
  94     # the fudge factor we make up later.
  95     ambient_dim = randint(2, 10)
  96     K = IceCream(ambient_dim)
  97     e1 = [1] # Set the "height" of e1 to one
  98     e2 = [1] # And the same for e2
  99
 100     # If we choose the rest of the components of e1,e2 randomly
 101     # between 0 and 1, then the largest the squared norm of the
 102     # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
 103     # need to make it less than one (the height of the cone) so
 104     # that the whole thing is in the cone. The norm of the
 105     # non-height part is sqrt(dim(K) - 1), and we can divide by
 106     # twice that.
 107     fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0))
 108     e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 109     e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 110     L = _random_matrix(K.dimension())
 111
 112     return (L, K, matrix(e1), matrix(e2))
 113
 114
 115 # Tell pylint to shut up about the large number of methods.
 116 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
 117     """
 118     Tests for the SymmetricLinearGame and Solution classes.
 119     """
 120     def assert_within_tol(self, first, second):
 121         """
 122         Test that ``first`` and ``second`` are equal within our default
 123         tolerance.
 124         """
 125         self.assertTrue(abs(first - second) < options.ABS_TOL)
 126
 127
 128     def assert_norm_within_tol(self, first, second):
 129         """
 130         Test that ``first`` and ``second`` vectors are equal in the
 131         sense that the norm of their difference is within our default
 132         tolerance.
 133         """
 134         self.assert_within_tol(norm(first - second), 0)
 135
 136
 137     def assert_solution_exists(self, L, K, e1, e2):
 138         """
 139         Given the parameters needed to construct a SymmetricLinearGame,
 140         ensure that that game has a solution.
 141         """
 142         # The matrix() constructor assumes that ``L`` is a list of
 143         # columns, so we transpose it to agree with what
 144         # SymmetricLinearGame() thinks.
 145         G = SymmetricLinearGame(L.trans(), K, e1, e2)
 146         soln = G.solution()
 147
 148         expected = inner_product(L*soln.player1_optimal(),
 149                                  soln.player2_optimal())
 150         self.assert_within_tol(soln.game_value(), expected)
 151
 152
 153     def test_solution_exists_orthant(self):
 154         """
 155         Every linear game has a solution, so we should be able to solve
 156         every symmetric linear game over the NonnegativeOrthant. Pick
 157         some parameters randomly and give it a shot. The resulting
 158         optimal solutions should give us the optimal game value when we
 159         apply the payoff operator to them.
 160         """
 161         (L, K, e1, e2) = _random_orthant_params()
 162         self.assert_solution_exists(L, K, e1, e2)
 163
 164
 165     def test_solution_exists_icecream(self):
 166         """
 167         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 168         over the ice cream cone.
 169         """
 170         (L, K, e1, e2) = _random_icecream_params()
 171         self.assert_solution_exists(L, K, e1, e2)
 172
 173
 174     def test_negative_value_z_operator(self):
 175         """
 176         Test the example given in Gowda/Ravindran of a Z-matrix with
 177         negative game value on the nonnegative orthant.
 178         """
 179         K = NonnegativeOrthant(2)
 180         e1 = [1, 1]
 181         e2 = e1
 182         L = [[1, -2], [-2, 1]]
 183         G = SymmetricLinearGame(L, K, e1, e2)
 184         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 185
 186
 187     def assert_scaling_works(self, L, K, e1, e2):
 188         """
 189         Test that scaling ``L`` by a nonnegative number scales the value
 190         of the game by the same number.
 191         """
 192         game1 = SymmetricLinearGame(L, K, e1, e2)
 193         value1 = game1.solution().game_value()
 194
 195         alpha = uniform(0.1, 10)
 196         game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
 197         value2 = game2.solution().game_value()
 198         self.assert_within_tol(alpha*value1, value2)
 199
 200
 201     def test_scaling_orthant(self):
 202         """
 203         Test that scaling ``L`` by a nonnegative number scales the value
 204         of the game by the same number over the nonnegative orthant.
 205         """
 206         (L, K, e1, e2) = _random_orthant_params()
 207         self.assert_scaling_works(L, K, e1, e2)
 208
 209
 210     def test_scaling_icecream(self):
 211         """
 212         The same test as :meth:`test_nonnegative_scaling_orthant`,
 213         except over the ice cream cone.
 214         """
 215         (L, K, e1, e2) = _random_icecream_params()
 216         self.assert_scaling_works(L, K, e1, e2)
 217
 218
 219     def assert_translation_works(self, L, K, e1, e2):
 220         """
 221         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 222         the value of the associated game by alpha.
 223         """
 224         # We need to use ``L`` later, so make sure we transpose it
 225         # before passing it in as a column-indexed matrix.
 226         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 227         soln1 = game1.solution()
 228         value1 = soln1.game_value()
 229         x_bar = soln1.player1_optimal()
 230         y_bar = soln1.player2_optimal()
 231
 232         alpha = uniform(-10, 10)
 233         tensor_prod = e1*e2.trans()
 234
 235         # This is the "correct" representation of ``M``, but COLUMN
 236         # indexed...
 237         M = L + alpha*tensor_prod
 238
 239         # so we have to transpose it when we feed it to the constructor.
 240         game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
 241         value2 = game2.solution().game_value()
 242
 243         self.assert_within_tol(value1 + alpha, value2)
 244
 245         # Make sure the same optimal pair works.
 246         self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
 247
 248
 249     def test_translation_orthant(self):
 250         """
 251         Test that translation works over the nonnegative orthant.
 252         """
 253         (L, K, e1, e2) = _random_orthant_params()
 254         self.assert_translation_works(L, K, e1, e2)
 255
 256
 257     def test_translation_icecream(self):
 258         """
 259         The same as :meth:`test_translation_orthant`, except over the
 260         ice cream cone.
 261         """
 262         (L, K, e1, e2) = _random_icecream_params()
 263         self.assert_translation_works(L, K, e1, e2)
 264
 265
 266     def assert_opposite_game_works(self, L, K, e1, e2):
 267         """
 268         Check the value of the "opposite" game that gives rise to a
 269         value that is the negation of the original game. Comes from
 270         some corollary.
 271         """
 272         # We need to use ``L`` later, so make sure we transpose it
 273         # before passing it in as a column-indexed matrix.
 274         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 275
 276         # This is the "correct" representation of ``M``, but
 277         # COLUMN indexed...
 278         M = -L.trans()
 279
 280         # so we have to transpose it when we feed it to the constructor.
 281         game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
 282
 283         soln1 = game1.solution()
 284         x_bar = soln1.player1_optimal()
 285         y_bar = soln1.player2_optimal()
 286         soln2 = game2.solution()
 287
 288         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 289
 290         # Make sure the switched optimal pair works.
 291         self.assert_within_tol(soln2.game_value(),
 292                                inner_product(M*y_bar, x_bar))
 293
 294
 295     def test_opposite_game_orthant(self):
 296         """
 297         Test the value of the "opposite" game over the nonnegative
 298         orthant.
 299         """
 300         (L, K, e1, e2) = _random_orthant_params()
 301         self.assert_opposite_game_works(L, K, e1, e2)
 302
 303
 304     def test_opposite_game_icecream(self):
 305         """
 306         Like :meth:`test_opposite_game_orthant`, except over the
 307         ice-cream cone.
 308         """
 309         (L, K, e1, e2) = _random_icecream_params()
 310         self.assert_opposite_game_works(L, K, e1, e2)
 311
 312
 313     def assert_orthogonality(self, L, K, e1, e2):
 314         """
 315         Two orthogonality relations hold at an optimal solution, and we
 316         check them here.
 317         """
 318         # We need to use ``L`` later, so make sure we transpose it
 319         # before passing it in as a column-indexed matrix.
 320         game = SymmetricLinearGame(L.trans(), K, e1, e2)
 321         soln = game.solution()
 322         x_bar = soln.player1_optimal()
 323         y_bar = soln.player2_optimal()
 324         value = soln.game_value()
 325
 326         ip1 = inner_product(y_bar, L*x_bar - value*e1)
 327         self.assert_within_tol(ip1, 0)
 328
 329         ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
 330         self.assert_within_tol(ip2, 0)
 331
 332
 333     def test_orthogonality_orthant(self):
 334         """
 335         Check the orthgonality relationships that hold for a solution
 336         over the nonnegative orthant.
 337         """
 338         (L, K, e1, e2) = _random_orthant_params()
 339         self.assert_orthogonality(L, K, e1, e2)
 340
 341
 342     def test_orthogonality_icecream(self):
 343         """
 344         Check the orthgonality relationships that hold for a solution
 345         over the ice-cream cone.
 346         """
 347         (L, K, e1, e2) = _random_icecream_params()
 348         self.assert_orthogonality(L, K, e1, e2)
 349
 350
 351     def test_positive_operator_value(self):
 352         """
 353         Test that a positive operator on the nonnegative orthant gives
 354         rise to a a game with a nonnegative value.
 355
 356         This test theoretically applies to the ice-cream cone as well,
 357         but we don't know how to make positive operators on that cone.
 358         """
 359         (K, e1, e2) = _random_orthant_params()[1:]
 360         L = _random_nonnegative_matrix(K.dimension())
 361
 362         game = SymmetricLinearGame(L, K, e1, e2)
 363         self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 364
 365
 366     def assert_lyapunov_works(self, L, K, e1, e2):
 367         """
 368         Check that Lyapunov games act the way we expect.
 369         """
 370         game = SymmetricLinearGame(L, K, e1, e2)
 371         soln = game.solution()
 372
 373         # We only check for positive/negative stability if the game
 374         # value is not basically zero. If the value is that close to
 375         # zero, we just won't check any assertions.
 376         eigs = eigenvalues_re(L)
 377         if soln.game_value() > options.ABS_TOL:
 378             # L should be positive stable
 379             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 380             self.assertTrue(positive_stable)
 381         elif soln.game_value() < -options.ABS_TOL:
 382             # L should be negative stable
 383             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 384             self.assertTrue(negative_stable)
 385
 386         # The dual game's value should always equal the primal's.
 387         dualsoln = game.dual().solution()
 388         self.assert_within_tol(dualsoln.game_value(), soln.game_value())
 389
 390
 391     def test_lyapunov_orthant(self):
 392         """
 393         Test that a Lyapunov game on the nonnegative orthant works.
 394         """
 395         (K, e1, e2) = _random_orthant_params()[1:]
 396         L = _random_diagonal_matrix(K.dimension())
 397
 398         self.assert_lyapunov_works(L, K, e1, e2)
 399
 400
 401     def test_lyapunov_icecream(self):
 402         """
 403         Test that a Lyapunov game on the ice-cream cone works.
 404         """
 405         (K, e1, e2) = _random_icecream_params()[1:]
 406         L = _random_lyapunov_like_icecream(K.dimension())
 407
 408         self.assert_lyapunov_works(L, K, e1, e2)