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, norm
   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     def test_solutions_dont_change_orthant(self):
  46         G = random_orthant_game()
  47         self.assert_solutions_dont_change(G)
  48
  49     def test_solutions_dont_change_icecream(self):
  50         G = random_icecream_game()
  51         self.assert_solutions_dont_change(G)
  52
  53     def assert_solutions_dont_change(self, G):
  54         """
  55         If we solve the same problem twice, we should get
  56         the same answer both times.
  57         """
  58         soln1 = G.solution()
  59         soln2 = G.solution()
  60         p1_diff = norm(soln1.player1_optimal() - soln2.player1_optimal())
  61         p2_diff = norm(soln1.player2_optimal() - soln2.player2_optimal())
  62         gv_diff = abs(soln1.game_value() - soln2.game_value())
  63
  64         p1_close = p1_diff < options.ABS_TOL
  65         p2_close = p2_diff < options.ABS_TOL
  66         gv_close = gv_diff < options.ABS_TOL
  67
  68         self.assertTrue(p1_close and p2_close and gv_close)
  69
  70
  71     def test_condition_lower_bound(self):
  72         """
  73         Ensure that the condition number of a game is greater than or
  74         equal to one.
  75
  76         It should be safe to compare these floats directly: we compute
  77         the condition number as the ratio of one nonnegative real number
  78         to a smaller nonnegative real number.
  79         """
  80         G = random_orthant_game()
  81         self.assertTrue(G.condition() >= 1.0)
  82         G = random_icecream_game()
  83         self.assertTrue(G.condition() >= 1.0)
  84
  85
  86     def assert_scaling_works(self, G):
  87         """
  88         Test that scaling ``L`` by a nonnegative number scales the value
  89         of the game by the same number.
  90         """
  91         (alpha, H) = random_nn_scaling(G)
  92         value1 = G.solution().game_value()
  93         value2 = H.solution().game_value()
  94         modifier = 4*max(abs(alpha), 1)
  95         self.assert_within_tol(alpha*value1, value2, modifier)
  96
  97
  98     def test_scaling_orthant(self):
  99         """
 100         Test that scaling ``L`` by a nonnegative number scales the value
 101         of the game by the same number over the nonnegative orthant.
 102         """
 103         G = random_orthant_game()
 104         self.assert_scaling_works(G)
 105
 106
 107     def test_scaling_icecream(self):
 108         """
 109         The same test as :meth:`test_nonnegative_scaling_orthant`,
 110         except over the ice cream cone.
 111         """
 112         G = random_icecream_game()
 113         self.assert_scaling_works(G)
 114
 115
 116     def assert_translation_works(self, G):
 117         """
 118         Check that translating ``L`` by alpha*(e1*e2.trans()) increases
 119         the value of the associated game by alpha.
 120         """
 121         # We need to use ``L`` later, so make sure we transpose it
 122         # before passing it in as a column-indexed matrix.
 123         soln1 = G.solution()
 124         value1 = soln1.game_value()
 125         x_bar = soln1.player1_optimal()
 126         y_bar = soln1.player2_optimal()
 127
 128         # This is the "correct" representation of ``M``, but COLUMN
 129         # indexed...
 130         (alpha, H) = random_translation(G)
 131         value2 = H.solution().game_value()
 132
 133         modifier = 4*max(abs(alpha), 1)
 134         self.assert_within_tol(value1 + alpha, value2, modifier)
 135
 136         # Make sure the same optimal pair works.
 137         self.assert_within_tol(value2, H.payoff(x_bar, y_bar), modifier)
 138
 139
 140     def test_translation_orthant(self):
 141         """
 142         Test that translation works over the nonnegative orthant.
 143         """
 144         G = random_orthant_game()
 145         self.assert_translation_works(G)
 146
 147
 148     def test_translation_icecream(self):
 149         """
 150         The same as :meth:`test_translation_orthant`, except over the
 151         ice cream cone.
 152         """
 153         G = random_icecream_game()
 154         self.assert_translation_works(G)
 155
 156
 157     def assert_opposite_game_works(self, G):
 158         """
 159         Check the value of the "opposite" game that gives rise to a
 160         value that is the negation of the original game. Comes from
 161         some corollary.
 162         """
 163         # This is the "correct" representation of ``M``, but
 164         # COLUMN indexed...
 165         M = -G.L().trans()
 166
 167         # so we have to transpose it when we feed it to the constructor.
 168         # Note: the condition number of ``H`` should be comparable to ``G``.
 169         H = SymmetricLinearGame(M.trans(), G.K(), G.e2(), G.e1())
 170
 171         soln1 = G.solution()
 172         x_bar = soln1.player1_optimal()
 173         y_bar = soln1.player2_optimal()
 174         soln2 = H.solution()
 175
 176         # The modifier of 4 is because each could be off by 2*ABS_TOL,
 177         # which is how far apart the primal/dual objectives have been
 178         # observed being.
 179         self.assert_within_tol(-soln1.game_value(), soln2.game_value(), 4)
 180
 181         # Make sure the switched optimal pair works. Since x_bar and
 182         # y_bar come from G, we use the same modifier.
 183         self.assert_within_tol(soln2.game_value(), H.payoff(y_bar, x_bar), 4)
 184
 185
 186
 187     def test_opposite_game_orthant(self):
 188         """
 189         Test the value of the "opposite" game over the nonnegative
 190         orthant.
 191         """
 192         G = random_orthant_game()
 193         self.assert_opposite_game_works(G)
 194
 195
 196     def test_opposite_game_icecream(self):
 197         """
 198         Like :meth:`test_opposite_game_orthant`, except over the
 199         ice-cream cone.
 200         """
 201         G = random_icecream_game()
 202         self.assert_opposite_game_works(G)
 203
 204
 205     def assert_orthogonality(self, G):
 206         """
 207         Two orthogonality relations hold at an optimal solution, and we
 208         check them here.
 209         """
 210         soln = G.solution()
 211         x_bar = soln.player1_optimal()
 212         y_bar = soln.player2_optimal()
 213         value = soln.game_value()
 214
 215         ip1 = inner_product(y_bar, G.L()*x_bar - value*G.e1())
 216         ip2 = inner_product(value*G.e2() - G.L().trans()*y_bar, x_bar)
 217
 218         # Huh.. well, y_bar and x_bar can each be epsilon away, but
 219         # x_bar is scaled by L, so that's (norm(L) + 1), and then
 220         # value could be off by epsilon, so that's another norm(e1) or
 221         # norm(e2). On the other hand, this test seems to pass most of
 222         # the time even with a modifier of one. How about.. four?
 223         self.assert_within_tol(ip1, 0, 4)
 224         self.assert_within_tol(ip2, 0, 4)
 225
 226
 227     def test_orthogonality_orthant(self):
 228         """
 229         Check the orthgonality relationships that hold for a solution
 230         over the nonnegative orthant.
 231         """
 232         G = random_orthant_game()
 233         self.assert_orthogonality(G)
 234
 235
 236     def test_orthogonality_icecream(self):
 237         """
 238         Check the orthgonality relationships that hold for a solution
 239         over the ice-cream cone.
 240         """
 241         G = random_icecream_game()
 242         self.assert_orthogonality(G)
 243
 244
 245     def test_positive_operator_value(self):
 246         """
 247         Test that a positive operator on the nonnegative orthant gives
 248         rise to a a game with a nonnegative value.
 249
 250         This test theoretically applies to the ice-cream cone as well,
 251         but we don't know how to make positive operators on that cone.
 252         """
 253         G = random_positive_orthant_game()
 254         self.assertTrue(G.solution().game_value() >= -options.ABS_TOL)
 255
 256
 257     def assert_lyapunov_works(self, G):
 258         """
 259         Check that Lyapunov games act the way we expect.
 260         """
 261         soln = G.solution()
 262
 263         # We only check for positive/negative stability if the game
 264         # value is not basically zero. If the value is that close to
 265         # zero, we just won't check any assertions.
 266         #
 267         # See :meth:`assert_within_tol` for an explanation of the
 268         # fudge factors.
 269         eigs = eigenvalues_re(G.L())
 270
 271         if soln.game_value() > options.ABS_TOL:
 272             # L should be positive stable
 273             positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
 274             self.assertTrue(positive_stable)
 275         elif soln.game_value() < -options.ABS_TOL:
 276             # L should be negative stable
 277             negative_stable = all([eig < options.ABS_TOL for eig in eigs])
 278             self.assertTrue(negative_stable)
 279
 280         # The dual game's value should always equal the primal's.
 281         # The modifier of 4 is because even though the games are dual,
 282         # CVXOPT doesn't know that, and each could be off by 2*ABS_TOL.
 283         dualsoln = G.dual().solution()
 284         self.assert_within_tol(dualsoln.game_value(), soln.game_value(), 4)
 285
 286
 287     def test_lyapunov_orthant(self):
 288         """
 289         Test that a Lyapunov game on the nonnegative orthant works.
 290         """
 291         G = random_ll_orthant_game()
 292         self.assert_lyapunov_works(G)
 293
 294
 295     def test_lyapunov_icecream(self):
 296         """
 297         Test that a Lyapunov game on the ice-cream cone works.
 298         """
 299         G = random_ll_icecream_game()
 300         self.assert_lyapunov_works(G)