test/symmetric_linear_game_test.py

   1 """
   2 Unit tests for the :class:`SymmetricLinearGame` class.
   3 """
   4
   5 from unittest import TestCase
   6
   7 from dunshire.games import SymmetricLinearGame
   8 from dunshire.matrices import eigenvalues_re, inner_product
   9 from dunshire import options
  10 from .randomgen import (random_icecream_game, random_ll_icecream_game,
  11                         random_ll_orthant_game, random_nn_scaling,
  12                         random_orthant_game, random_positive_orthant_game,
  13                         random_translation)
  14
  15
  16 # Tell pylint to shut up about the large number of methods.
  17 class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904
  18     """
  19     Tests for the SymmetricLinearGame and Solution classes.
  20     """
  21     def assert_within_tol(self, first, second, modifier=1):
  22         """
  23         Test that ``first`` and ``second`` are equal within a multiple of
  24         our default tolerances.
  25
  26         Parameters
  27         ----------
  28
  29         first : float
  30             The first number to compare.
  31
  32         second : float
  33             The second number to compare.
  34
  35         modifier : float
  36             A scaling factor (default: 1) applied to the default
  37             tolerance for this comparison. If you have a poorly-
  38             conditioned matrix, for example, you may want to set this
  39             greater than one.
  40
  41         """
  42         self.assertTrue(abs(first - second) < options.ABS_TOL*modifier)
  43
  44
  45
  46     def test_condition_lower_bound(self):
  47         """
  48         Ensure that the condition number of a game is greater than or
  49         equal to one.
  50
  51         It should be safe to compare these floats directly: we compute
  52         the condition number as the ratio of one nonnegative real number
  53         to a smaller nonnegative real number.
  54         """
  55         G = random_orthant_game()
  56         self.assertTrue(G.condition() >= 1.0)
  57         G = random_icecream_game()
  58         self.assertTrue(G.condition() >= 1.0)
  59
  60
  61     def assert_scaling_works(self, G):
  62         """
  63         Test that scaling ``L`` by a nonnegative number scales the value
  64         of the game by the same number.
  65         """
  66         (alpha, H) = random_nn_scaling(G)
  67         value1 = G.solution().game_value()
  68         value2 = H.solution().game_value()
  69         modifier = 4*max(abs(alpha), 1)
  70         self.assert_within_tol(alpha*value1, value2, modifier)
  71
  72
  73     def test_scaling_orthant(self):
  74         """
  75         Test that scaling ``L`` by a nonnegative number scales the value
  76         of the game by the same number over the nonnegative orthant.
  77         """
  78         G = random_orthant_game()
  79         self.assert_scaling_works(G)
  80
  81
  82     def test_scaling_icecream(self):
  83         """
  84         The same test as :meth:`test_nonnegative_scaling_orthant`,
  85         except over the ice cream cone.
  86         """
  87         G = random_icecream_game()
  88         self.assert_scaling_works(G)
  89
  90
  91     def assert_translation_works(self, G):
  92         """
  93         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
  94         the value of the associated game by alpha.
  95         """
  96         # We need to use ``L`` later, so make sure we transpose it
  97         # before passing it in as a column-indexed matrix.
  98         soln1 = G.solution()
  99         value1 = soln1.game_value()
 100         x_bar = soln1.player1_optimal()
 101         y_bar = soln1.player2_optimal()
 102
 103         # This is the "correct" representation of ``M``, but COLUMN
 104         # indexed...
 105         (alpha, H) = random_translation(G)
 106         value2 = H.solution().game_value()
 107
 108         modifier = 4*max(abs(alpha), 1)
 109         self.assert_within_tol(value1 + alpha, value2, modifier)
 110
 111         # Make sure the same optimal pair works.
 112         self.assert_within_tol(value2, H.payoff(x_bar, y_bar), modifier)
 113
 114
 115     def test_translation_orthant(self):
 116         """
 117         Test that translation works over the nonnegative orthant.
 118         """
 119         G = random_orthant_game()
 120         self.assert_translation_works(G)
 121
 122
 123     def test_translation_icecream(self):
 124         """
 125         The same as :meth:`test_translation_orthant`, except over the
 126         ice cream cone.
 127         """
 128         G = random_icecream_game()
 129         self.assert_translation_works(G)
 130
 131
 132     def assert_opposite_game_works(self, G):
 133         """
 134         Check the value of the "opposite" game that gives rise to a
 135         value that is the negation of the original game. Comes from
 136         some corollary.
 137         """
 138         # This is the "correct" representation of ``M``, but
 139         # COLUMN indexed...
 140         M = -G.L().trans()
 141
 142         # so we have to transpose it when we feed it to the constructor.
 143         # Note: the condition number of ``H`` should be comparable to ``G``.
 144         H = SymmetricLinearGame(M.trans(), G.K(), G.e2(), G.e1())
 145
 146         soln1 = G.solution()
 147         x_bar = soln1.player1_optimal()
 148         y_bar = soln1.player2_optimal()
 149         soln2 = H.solution()
 150
 151         # The modifier of 4 is because each could be off by 2*ABS_TOL,
 152         # which is how far apart the primal/dual objectives have been
 153         # observed being.
 154         self.assert_within_tol(-soln1.game_value(), soln2.game_value(), 4)
 155
 156         # Make sure the switched optimal pair works. Since x_bar and
 157         # y_bar come from G, we use the same modifier.
 158         self.assert_within_tol(soln2.game_value(), H.payoff(y_bar, x_bar), 4)
 159
 160
 161
 162     def test_opposite_game_orthant(self):
 163         """
 164         Test the value of the "opposite" game over the nonnegative
 165         orthant.
 166         """
 167         G = random_orthant_game()
 168         self.assert_opposite_game_works(G)
 169
 170
 171     def test_opposite_game_icecream(self):
 172         """
 173         Like :meth:`test_opposite_game_orthant`, except over the
 174         ice-cream cone.
 175         """
 176         G = random_icecream_game()
 177         self.assert_opposite_game_works(G)
 178
 179
 180     def assert_orthogonality(self, G):
 181         """
 182         Two orthogonality relations hold at an optimal solution, and we
 183         check them here.
 184         """
 185         soln = G.solution()
 186         x_bar = soln.player1_optimal()
 187         y_bar = soln.player2_optimal()
 188         value = soln.game_value()
 189
 190         ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1())
 191         ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar)
 192
 193         # Huh.. well, y_bar and x_bar can each be epsilon away, but
 194         # x_bar is scaled by L, so that's (norm(L) + 1), and then
 195         # value could be off by epsilon, so that's another norm(e1) or
 196         # norm(e2). On the other hand, this test seems to pass most of
 197         # the time even with a modifier of one. How about.. four?
 198         self.assert_within_tol(ip1, 0, 4)
 199         self.assert_within_tol(ip2, 0, 4)
 200
 201
 202     def test_orthogonality_orthant(self):
 203         """
 204         Check the orthgonality relationships that hold for a solution
 205         over the nonnegative orthant.
 206         """
 207         G = random_orthant_game()
 208         self.assert_orthogonality(G)
 209
 210
 211     def test_orthogonality_icecream(self):
 212         """
 213         Check the orthgonality relationships that hold for a solution
 214         over the ice-cream cone.
 215         """
 216         G = random_icecream_game()
 217         self.assert_orthogonality(G)
 218
 219
 220     def test_positive_operator_value(self):
 221         """
 222         Test that a positive operator on the nonnegative orthant gives
 223         rise to a a game with a nonnegative value.
 224
 225         This test theoretically applies to the ice-cream cone as well,
 226         but we don't know how to make positive operators on that cone.
 227         """
 228         G = random_positive_orthant_game()
 229         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 230
 231
 232     def assert_lyapunov_works(self, G):
 233         """
 234         Check that Lyapunov games act the way we expect.
 235         """
 236         soln = G.solution()
 237
 238         # We only check for positive/negative stability if the game
 239         # value is not basically zero. If the value is that close to
 240         # zero, we just won't check any assertions.
 241         #
 242         # See :meth:`assert_within_tol` for an explanation of the
 243         # fudge factors.
 244         eigs = eigenvalues_re(G.L())
 245
 246         if soln.game_value() > options.ABS_TOL:
 247             # L should be positive stable
 248             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 249             self.assertTrue(positive_stable)
 250         elif soln.game_value() < -options.ABS_TOL:
 251             # L should be negative stable
 252             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 253             self.assertTrue(negative_stable)
 254
 255         # The dual game's value should always equal the primal's.
 256         # The modifier of 4 is because even though the games are dual,
 257         # CVXOPT doesn't know that, and each could be off by 2*ABS_TOL.
 258         dualsoln = G.dual().solution()
 259         self.assert_within_tol(dualsoln.game_value(), soln.game_value(), 4)
 260
 261
 262     def test_lyapunov_orthant(self):
 263         """
 264         Test that a Lyapunov game on the nonnegative orthant works.
 265         """
 266         G = random_ll_orthant_game()
 267         self.assert_lyapunov_works(G)
 268
 269
 270     def test_lyapunov_icecream(self):
 271         """
 272         Test that a Lyapunov game on the ice-cream cone works.
 273         """
 274         G = random_ll_icecream_game()
 275         self.assert_lyapunov_works(G)