test/symmetric_linear_game_test.py

   1 """
   2 Unit tests for the :class:`SymmetricLinearGame` class.
   3 """
   4
   5 from math import sqrt
   6 from random import randint, uniform
   7 from unittest import TestCase
   8
   9 from cvxopt import matrix
  10 from dunshire.cones import NonnegativeOrthant, IceCream
  11 from dunshire.games import SymmetricLinearGame
  12 from dunshire.matrices import (append_col, append_row, eigenvalues_re,
  13                                identity, inner_product)
  14 from dunshire import options
  15
  16
  17 def random_matrix(dims):
  18     """
  19     Generate a random square matrix.
  20
  21     Parameters
  22     ----------
  23
  24     dims : int
  25         The number of rows/columns you want in the returned matrix.
  26
  27     Returns
  28     -------
  29
  30     matrix
  31         A new matrix whose entries are random floats chosen uniformly from
  32         the interval [-10, 10].
  33
  34     Examples
  35     --------
  36
  37         >>> A = random_matrix(3)
  38         >>> A.size
  39         (3, 3)
  40
  41     """
  42     return matrix([[uniform(-10, 10) for i in range(dims)]
  43                    for j in range(dims)])
  44
  45
  46 def random_nonnegative_matrix(dims):
  47     """
  48     Generate a random square matrix with nonnegative entries.
  49
  50     Parameters
  51     ----------
  52
  53     dims : int
  54         The number of rows/columns you want in the returned matrix.
  55
  56     Returns
  57     -------
  58
  59     matrix
  60         A new matrix whose entries are random floats chosen uniformly from
  61         the interval [0, 10].
  62
  63     Examples
  64     --------
  65
  66         >>> A = random_nonnegative_matrix(3)
  67         >>> A.size
  68         (3, 3)
  69         >>> all([entry >= 0 for entry in A])
  70         True
  71
  72     """
  73     L = random_matrix(dims)
  74     return matrix([abs(entry) for entry in L], (dims, dims))
  75
  76
  77 def random_diagonal_matrix(dims):
  78     """
  79     Generate a random square matrix with zero off-diagonal entries.
  80
  81     These matrices are Lyapunov-like on the nonnegative orthant, as is
  82     fairly easy to see.
  83
  84     Parameters
  85     ----------
  86
  87     dims : int
  88         The number of rows/columns you want in the returned matrix.
  89
  90     Returns
  91     -------
  92
  93     matrix
  94         A new matrix whose diagonal entries are random floats chosen
  95         uniformly from the interval [-10, 10] and whose off-diagonal
  96         entries are zero.
  97
  98     Examples
  99     --------
 100
 101         >>> A = random_diagonal_matrix(3)
 102         >>> A.size
 103         (3, 3)
 104         >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
 105         True
 106
 107     """
 108     return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)]
 109                    for j in range(dims)])
 110
 111
 112 def random_skew_symmetric_matrix(dims):
 113     """
 114     Generate a random skew-symmetrix matrix.
 115
 116     Parameters
 117     ----------
 118
 119     dims : int
 120         The number of rows/columns you want in the returned matrix.
 121
 122     Returns
 123     -------
 124
 125     matrix
 126         A new skew-matrix whose strictly above-diagonal entries are
 127         random floats chosen uniformly from the interval [-10, 10].
 128
 129     Examples
 130     --------
 131
 132         >>> A = random_skew_symmetric_matrix(3)
 133         >>> A.size
 134         (3, 3)
 135
 136         >>> from dunshire.matrices import norm
 137         >>> A = random_skew_symmetric_matrix(randint(1, 10))
 138         >>> norm(A + A.trans()) < options.ABS_TOL
 139         True
 140
 141     """
 142     strict_ut = [[uniform(-10, 10)*int(i < j) for i in range(dims)]
 143                  for j in range(dims)]
 144
 145     strict_ut = matrix(strict_ut, (dims, dims))
 146     return strict_ut - strict_ut.trans()
 147
 148
 149 def random_lyapunov_like_icecream(dims):
 150     r"""
 151     Generate a random matrix Lyapunov-like on the ice-cream cone.
 152
 153     The form of these matrices is cited in Gowda and Tao
 154     [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
 155     notation) are easy to generate. The submatrix ``D`` is a little
 156     trickier, but it can be found noticing that :math:`C + C^{T} = 0`
 157     for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
 158     + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
 159     :math:`aI` with each of :math:`C,C^{T}` and let those be our
 160     :math:`D,D^{T}`.
 161
 162     Parameters
 163     ----------
 164
 165     dims : int
 166         The dimension of the ice-cream cone (not of the matrix you want!)
 167         on which the returned matrix should be Lyapunov-like.
 168
 169     Returns
 170     -------
 171
 172     matrix
 173         A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
 174         dimensions, whose free entries are random floats chosen uniformly
 175         from the interval [-10, 10].
 176
 177     References
 178     ----------
 179
 180     .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
 181        proper cone and Lyapunov-like transformations. Mathematical
 182        Programming, 147:155-170, 2014.
 183
 184     Examples
 185     --------
 186
 187         >>> L = random_lyapunov_like_icecream(3)
 188         >>> L.size
 189         (3, 3)
 190         >>> x = matrix([1,1,0])
 191         >>> s = matrix([1,-1,0])
 192         >>> abs(inner_product(L*x, s)) < options.ABS_TOL
 193         True
 194
 195     """
 196     a = matrix([uniform(-10, 10)], (1, 1))
 197     b = matrix([uniform(-10, 10) for idx in range(dims-1)], (dims-1, 1))
 198     D = random_skew_symmetric_matrix(dims-1) + a*identity(dims-1)
 199     row1 = append_col(a, b.trans())
 200     row2 = append_col(b, D)
 201     return append_row(row1, row2)
 202
 203
 204 def random_orthant_params():
 205     """
 206     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 207     random game over the nonnegative orthant.
 208     """
 209     ambient_dim = randint(1, 10)
 210     K = NonnegativeOrthant(ambient_dim)
 211     e1 = [uniform(0.5, 10) for idx in range(K.dimension())]
 212     e2 = [uniform(0.5, 10) for idx in range(K.dimension())]
 213     L = random_matrix(K.dimension())
 214     return (L, K, matrix(e1), matrix(e2))
 215
 216
 217 def random_icecream_params():
 218     """
 219     Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
 220     random game over the ice-cream cone.
 221     """
 222     # Use a minimum dimension of two to avoid divide-by-zero in
 223     # the fudge factor we make up later.
 224     ambient_dim = randint(2, 10)
 225     K = IceCream(ambient_dim)
 226     e1 = [1] # Set the "height" of e1 to one
 227     e2 = [1] # And the same for e2
 228
 229     # If we choose the rest of the components of e1,e2 randomly
 230     # between 0 and 1, then the largest the squared norm of the
 231     # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
 232     # need to make it less than one (the height of the cone) so
 233     # that the whole thing is in the cone. The norm of the
 234     # non-height part is sqrt(dim(K) - 1), and we can divide by
 235     # twice that.
 236     fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0))
 237     e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 238     e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)]
 239     L = random_matrix(K.dimension())
 240
 241     return (L, K, matrix(e1), matrix(e2))
 242
 243
 244 # Tell pylint to shut up about the large number of methods.
 245 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
 246     """
 247     Tests for the SymmetricLinearGame and Solution classes.
 248     """
 249     def assert_within_tol(self, first, second):
 250         """
 251         Test that ``first`` and ``second`` are equal within our default
 252         tolerance.
 253         """
 254         self.assertTrue(abs(first - second) < options.ABS_TOL)
 255
 256
 257     def assert_solution_exists(self, L, K, e1, e2):
 258         """
 259         Given the parameters needed to construct a SymmetricLinearGame,
 260         ensure that that game has a solution.
 261         """
 262         # The matrix() constructor assumes that ``L`` is a list of
 263         # columns, so we transpose it to agree with what
 264         # SymmetricLinearGame() thinks.
 265         G = SymmetricLinearGame(L.trans(), K, e1, e2)
 266         soln = G.solution()
 267
 268         expected = inner_product(L*soln.player1_optimal(),
 269                                  soln.player2_optimal())
 270         self.assert_within_tol(soln.game_value(), expected)
 271
 272
 273     def test_solution_exists_orthant(self):
 274         """
 275         Every linear game has a solution, so we should be able to solve
 276         every symmetric linear game over the NonnegativeOrthant. Pick
 277         some parameters randomly and give it a shot. The resulting
 278         optimal solutions should give us the optimal game value when we
 279         apply the payoff operator to them.
 280         """
 281         (L, K, e1, e2) = random_orthant_params()
 282         self.assert_solution_exists(L, K, e1, e2)
 283
 284
 285     def test_solution_exists_icecream(self):
 286         """
 287         Like :meth:`test_solution_exists_nonnegative_orthant`, except
 288         over the ice cream cone.
 289         """
 290         (L, K, e1, e2) = random_icecream_params()
 291         self.assert_solution_exists(L, K, e1, e2)
 292
 293
 294     def test_negative_value_z_operator(self):
 295         """
 296         Test the example given in Gowda/Ravindran of a Z-matrix with
 297         negative game value on the nonnegative orthant.
 298         """
 299         K = NonnegativeOrthant(2)
 300         e1 = [1, 1]
 301         e2 = e1
 302         L = [[1, -2], [-2, 1]]
 303         G = SymmetricLinearGame(L, K, e1, e2)
 304         self.assertTrue(G.solution().game_value() < -options.ABS_TOL)
 305
 306
 307     def assert_scaling_works(self, L, K, e1, e2):
 308         """
 309         Test that scaling ``L`` by a nonnegative number scales the value
 310         of the game by the same number.
 311         """
 312         game1 = SymmetricLinearGame(L, K, e1, e2)
 313         value1 = game1.solution().game_value()
 314
 315         alpha = uniform(0.1, 10)
 316         game2 = SymmetricLinearGame(alpha*L, K, e1, e2)
 317         value2 = game2.solution().game_value()
 318         self.assert_within_tol(alpha*value1, value2)
 319
 320
 321     def test_scaling_orthant(self):
 322         """
 323         Test that scaling ``L`` by a nonnegative number scales the value
 324         of the game by the same number over the nonnegative orthant.
 325         """
 326         (L, K, e1, e2) = random_orthant_params()
 327         self.assert_scaling_works(L, K, e1, e2)
 328
 329
 330     def test_scaling_icecream(self):
 331         """
 332         The same test as :meth:`test_nonnegative_scaling_orthant`,
 333         except over the ice cream cone.
 334         """
 335         (L, K, e1, e2) = random_icecream_params()
 336         self.assert_scaling_works(L, K, e1, e2)
 337
 338
 339     def assert_translation_works(self, L, K, e1, e2):
 340         """
 341         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 342         the value of the associated game by alpha.
 343         """
 344         # We need to use ``L`` later, so make sure we transpose it
 345         # before passing it in as a column-indexed matrix.
 346         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 347         soln1 = game1.solution()
 348         value1 = soln1.game_value()
 349         x_bar = soln1.player1_optimal()
 350         y_bar = soln1.player2_optimal()
 351
 352         alpha = uniform(-10, 10)
 353         tensor_prod = e1*e2.trans()
 354
 355         # This is the "correct" representation of ``M``, but COLUMN
 356         # indexed...
 357         M = L + alpha*tensor_prod
 358
 359         # so we have to transpose it when we feed it to the constructor.
 360         game2 = SymmetricLinearGame(M.trans(), K, e1, e2)
 361         value2 = game2.solution().game_value()
 362
 363         self.assert_within_tol(value1 + alpha, value2)
 364
 365         # Make sure the same optimal pair works.
 366         self.assert_within_tol(value2, inner_product(M*x_bar, y_bar))
 367
 368
 369     def test_translation_orthant(self):
 370         """
 371         Test that translation works over the nonnegative orthant.
 372         """
 373         (L, K, e1, e2) = random_orthant_params()
 374         self.assert_translation_works(L, K, e1, e2)
 375
 376
 377     def test_translation_icecream(self):
 378         """
 379         The same as :meth:`test_translation_orthant`, except over the
 380         ice cream cone.
 381         """
 382         (L, K, e1, e2) = random_icecream_params()
 383         self.assert_translation_works(L, K, e1, e2)
 384
 385
 386     def assert_opposite_game_works(self, L, K, e1, e2):
 387         """
 388         Check the value of the "opposite" game that gives rise to a
 389         value that is the negation of the original game. Comes from
 390         some corollary.
 391         """
 392         # We need to use ``L`` later, so make sure we transpose it
 393         # before passing it in as a column-indexed matrix.
 394         game1 = SymmetricLinearGame(L.trans(), K, e1, e2)
 395
 396         # This is the "correct" representation of ``M``, but
 397         # COLUMN indexed...
 398         M = -L.trans()
 399
 400         # so we have to transpose it when we feed it to the constructor.
 401         game2 = SymmetricLinearGame(M.trans(), K, e2, e1)
 402
 403         soln1 = game1.solution()
 404         x_bar = soln1.player1_optimal()
 405         y_bar = soln1.player2_optimal()
 406         soln2 = game2.solution()
 407
 408         self.assert_within_tol(-soln1.game_value(), soln2.game_value())
 409
 410         # Make sure the switched optimal pair works.
 411         self.assert_within_tol(soln2.game_value(),
 412                                inner_product(M*y_bar, x_bar))
 413
 414
 415     def test_opposite_game_orthant(self):
 416         """
 417         Test the value of the "opposite" game over the nonnegative
 418         orthant.
 419         """
 420         (L, K, e1, e2) = random_orthant_params()
 421         self.assert_opposite_game_works(L, K, e1, e2)
 422
 423
 424     def test_opposite_game_icecream(self):
 425         """
 426         Like :meth:`test_opposite_game_orthant`, except over the
 427         ice-cream cone.
 428         """
 429         (L, K, e1, e2) = random_icecream_params()
 430         self.assert_opposite_game_works(L, K, e1, e2)
 431
 432
 433     def assert_orthogonality(self, L, K, e1, e2):
 434         """
 435         Two orthogonality relations hold at an optimal solution, and we
 436         check them here.
 437         """
 438         # We need to use ``L`` later, so make sure we transpose it
 439         # before passing it in as a column-indexed matrix.
 440         game = SymmetricLinearGame(L.trans(), K, e1, e2)
 441         soln = game.solution()
 442         x_bar = soln.player1_optimal()
 443         y_bar = soln.player2_optimal()
 444         value = soln.game_value()
 445
 446         ip1 = inner_product(y_bar, L*x_bar - value*e1)
 447         self.assert_within_tol(ip1, 0)
 448
 449         ip2 = inner_product(value*e2 - L.trans()*y_bar, x_bar)
 450         self.assert_within_tol(ip2, 0)
 451
 452
 453     def test_orthogonality_orthant(self):
 454         """
 455         Check the orthgonality relationships that hold for a solution
 456         over the nonnegative orthant.
 457         """
 458         (L, K, e1, e2) = random_orthant_params()
 459         self.assert_orthogonality(L, K, e1, e2)
 460
 461
 462     def test_orthogonality_icecream(self):
 463         """
 464         Check the orthgonality relationships that hold for a solution
 465         over the ice-cream cone.
 466         """
 467         (L, K, e1, e2) = random_icecream_params()
 468         self.assert_orthogonality(L, K, e1, e2)
 469
 470
 471     def test_positive_operator_value(self):
 472         """
 473         Test that a positive operator on the nonnegative orthant gives
 474         rise to a a game with a nonnegative value.
 475
 476         This test theoretically applies to the ice-cream cone as well,
 477         but we don't know how to make positive operators on that cone.
 478         """
 479         (K, e1, e2) = random_orthant_params()[1:]
 480         L = random_nonnegative_matrix(K.dimension())
 481
 482         game = SymmetricLinearGame(L, K, e1, e2)
 483         self.assertTrue(game.solution().game_value() >= -options.ABS_TOL)
 484
 485
 486     def assert_lyapunov_works(self, L, K, e1, e2):
 487         """
 488         Check that Lyapunov games act the way we expect.
 489         """
 490         game = SymmetricLinearGame(L, K, e1, e2)
 491         soln = game.solution()
 492
 493         # We only check for positive/negative stability if the game
 494         # value is not basically zero. If the value is that close to
 495         # zero, we just won't check any assertions.
 496         eigs = eigenvalues_re(L)
 497         if soln.game_value() > options.ABS_TOL:
 498             # L should be positive stable
 499             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 500             self.assertTrue(positive_stable)
 501         elif soln.game_value() < -options.ABS_TOL:
 502             # L should be negative stable
 503             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 504             self.assertTrue(negative_stable)
 505
 506         # The dual game's value should always equal the primal's.
 507         dualsoln = game.dual().solution()
 508         self.assert_within_tol(dualsoln.game_value(), soln.game_value())
 509
 510
 511     def test_lyapunov_orthant(self):
 512         """
 513         Test that a Lyapunov game on the nonnegative orthant works.
 514         """
 515         (K, e1, e2) = random_orthant_params()[1:]
 516         L = random_diagonal_matrix(K.dimension())
 517
 518         self.assert_lyapunov_works(L, K, e1, e2)
 519
 520
 521     def test_lyapunov_icecream(self):
 522         """
 523         Test that a Lyapunov game on the ice-cream cone works.
 524         """
 525         (K, e1, e2) = random_icecream_params()[1:]
 526         L = random_lyapunov_like_icecream(K.dimension())
 527
 528         self.assert_lyapunov_works(L, K, e1, e2)