2 Unit tests for the :class:`SymmetricLinearGame` class.
5 from unittest
import TestCase
7 from dunshire
.cones
import NonnegativeOrthant
8 from dunshire
.games
import SymmetricLinearGame
9 from dunshire
.matrices
import eigenvalues_re
, inner_product
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
)
16 EPSILON
= 2*2*RANDOM_MAX
*options
.ABS_TOL
18 This is the tolerance constant including fudge factors that we use to
19 determine whether or not two numbers are equal in tests.
21 The factor of two is because if we compare two solutions, both
22 of which may be off by ``ABS_TOL``, then the result could be off
23 by ``2*ABS_TOL``. The factor of ``RANDOM_MAX`` allows for
24 scaling a result (by ``RANDOM_MAX``) that may be off by
25 ``ABS_TOL``. The final factor of two is to allow for the edge
26 cases where we get an "unknown" result and need to lower the
27 CVXOPT tolerance by a factor of two.
30 # Tell pylint to shut up about the large number of methods.
31 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
33 Tests for the SymmetricLinearGame and Solution classes.
35 def assert_within_tol(self
, first
, second
):
37 Test that ``first`` and ``second`` are equal within a multiple of
38 our default tolerances.
40 self
.assertTrue(abs(first
- second
) < EPSILON
)
43 def assert_solution_exists(self
, G
):
45 Given a SymmetricLinearGame, ensure that it has a solution.
49 expected
= inner_product(G
._L*soln
.player1_optimal(),
50 soln
.player2_optimal())
51 self
.assert_within_tol(soln
.game_value(), expected
)
55 def test_condition_lower_bound(self
):
57 Ensure that the condition number of a game is greater than or
60 It should be safe to compare these floats directly: we compute
61 the condition number as the ratio of one nonnegative real number
62 to a smaller nonnegative real number.
64 G
= random_orthant_game()
65 self
.assertTrue(G
.condition() >= 1.0)
66 G
= random_icecream_game()
67 self
.assertTrue(G
.condition() >= 1.0)
70 def test_solution_exists_orthant(self
):
72 Every linear game has a solution, so we should be able to solve
73 every symmetric linear game over the NonnegativeOrthant. Pick
74 some parameters randomly and give it a shot. The resulting
75 optimal solutions should give us the optimal game value when we
76 apply the payoff operator to them.
78 G
= random_orthant_game()
79 self
.assert_solution_exists(G
)
82 def test_solution_exists_icecream(self
):
84 Like :meth:`test_solution_exists_nonnegative_orthant`, except
85 over the ice cream cone.
87 G
= random_icecream_game()
88 self
.assert_solution_exists(G
)
91 def test_negative_value_z_operator(self
):
93 Test the example given in Gowda/Ravindran of a Z-matrix with
94 negative game value on the nonnegative orthant.
96 K
= NonnegativeOrthant(2)
99 L
= [[1, -2], [-2, 1]]
100 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
101 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
104 def assert_scaling_works(self
, G
):
106 Test that scaling ``L`` by a nonnegative number scales the value
107 of the game by the same number.
109 (alpha
, H
) = random_nn_scaling(G
)
110 value1
= G
.solution().game_value()
111 value2
= H
.solution().game_value()
112 self
.assert_within_tol(alpha
*value1
, value2
)
115 def test_scaling_orthant(self
):
117 Test that scaling ``L`` by a nonnegative number scales the value
118 of the game by the same number over the nonnegative orthant.
120 G
= random_orthant_game()
121 self
.assert_scaling_works(G
)
124 def test_scaling_icecream(self
):
126 The same test as :meth:`test_nonnegative_scaling_orthant`,
127 except over the ice cream cone.
129 G
= random_icecream_game()
130 self
.assert_scaling_works(G
)
133 def assert_translation_works(self
, G
):
135 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
136 the value of the associated game by alpha.
138 # We need to use ``L`` later, so make sure we transpose it
139 # before passing it in as a column-indexed matrix.
141 value1
= soln1
.game_value()
142 x_bar
= soln1
.player1_optimal()
143 y_bar
= soln1
.player2_optimal()
145 # This is the "correct" representation of ``M``, but COLUMN
147 (alpha
, H
) = random_translation(G
)
148 value2
= H
.solution().game_value()
150 self
.assert_within_tol(value1
+ alpha
, value2
)
152 # Make sure the same optimal pair works.
153 self
.assert_within_tol(value2
, inner_product(H
._L*x_bar
, y_bar
))
156 def test_translation_orthant(self
):
158 Test that translation works over the nonnegative orthant.
160 G
= random_orthant_game()
161 self
.assert_translation_works(G
)
164 def test_translation_icecream(self
):
166 The same as :meth:`test_translation_orthant`, except over the
169 G
= random_icecream_game()
170 self
.assert_translation_works(G
)
173 def assert_opposite_game_works(self
, G
):
175 Check the value of the "opposite" game that gives rise to a
176 value that is the negation of the original game. Comes from
179 # This is the "correct" representation of ``M``, but
183 # so we have to transpose it when we feed it to the constructor.
184 # Note: the condition number of ``H`` should be comparable to ``G``.
185 H
= SymmetricLinearGame(M
.trans(), G
._K
, G
._e
2, G
._e
1)
188 x_bar
= soln1
.player1_optimal()
189 y_bar
= soln1
.player2_optimal()
192 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
194 # Make sure the switched optimal pair works.
195 self
.assert_within_tol(soln2
.game_value(),
196 inner_product(M
*y_bar
, x_bar
))
199 def test_opposite_game_orthant(self
):
201 Test the value of the "opposite" game over the nonnegative
204 G
= random_orthant_game()
205 self
.assert_opposite_game_works(G
)
208 def test_opposite_game_icecream(self
):
210 Like :meth:`test_opposite_game_orthant`, except over the
213 G
= random_icecream_game()
214 self
.assert_opposite_game_works(G
)
217 def assert_orthogonality(self
, G
):
219 Two orthogonality relations hold at an optimal solution, and we
223 x_bar
= soln
.player1_optimal()
224 y_bar
= soln
.player2_optimal()
225 value
= soln
.game_value()
227 ip1
= inner_product(y_bar
, G
._L*x_bar
- value
*G
._e
1)
228 self
.assert_within_tol(ip1
, 0)
230 ip2
= inner_product(value
*G
._e
2 - G
._L.trans()*y_bar
, x_bar
)
231 self
.assert_within_tol(ip2
, 0)
234 def test_orthogonality_orthant(self
):
236 Check the orthgonality relationships that hold for a solution
237 over the nonnegative orthant.
239 G
= random_orthant_game()
240 self
.assert_orthogonality(G
)
243 def test_orthogonality_icecream(self
):
245 Check the orthgonality relationships that hold for a solution
246 over the ice-cream cone.
248 G
= random_icecream_game()
249 self
.assert_orthogonality(G
)
252 def test_positive_operator_value(self
):
254 Test that a positive operator on the nonnegative orthant gives
255 rise to a a game with a nonnegative value.
257 This test theoretically applies to the ice-cream cone as well,
258 but we don't know how to make positive operators on that cone.
260 G
= random_positive_orthant_game()
261 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
264 def assert_lyapunov_works(self
, G
):
266 Check that Lyapunov games act the way we expect.
270 # We only check for positive/negative stability if the game
271 # value is not basically zero. If the value is that close to
272 # zero, we just won't check any assertions.
274 # See :meth:`assert_within_tol` for an explanation of the
276 eigs
= eigenvalues_re(G
._L)
278 if soln
.game_value() > EPSILON
:
279 # L should be positive stable
280 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
281 self
.assertTrue(positive_stable
)
282 elif soln
.game_value() < -EPSILON
:
283 # L should be negative stable
284 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
285 self
.assertTrue(negative_stable
)
287 # The dual game's value should always equal the primal's.
288 dualsoln
= G
.dual().solution()
289 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
292 def test_lyapunov_orthant(self
):
294 Test that a Lyapunov game on the nonnegative orthant works.
296 G
= random_ll_orthant_game()
297 self
.assert_lyapunov_works(G
)
300 def test_lyapunov_icecream(self
):
302 Test that a Lyapunov game on the ice-cream cone works.
304 G
= random_ll_icecream_game()
305 self
.assert_lyapunov_works(G
)