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