2 Unit tests for the :class:`SymmetricLinearGame` class.
5 from unittest
import TestCase
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
,
16 # Tell pylint to shut up about the large number of methods.
17 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
19 Tests for the SymmetricLinearGame and Solution classes.
21 def assert_within_tol(self
, first
, second
, modifier
=1):
23 Test that ``first`` and ``second`` are equal within a multiple of
24 our default tolerances.
30 The first number to compare.
33 The second number to compare.
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
42 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
*modifier
)
45 def test_solutions_dont_change_orthant(self
):
47 If we solve the same game twice over the nonnegative orthant,
48 then we should get the same solution both times. The solution to
49 a game is not unique, but the process we use is (as far as we
52 G
= random_orthant_game()
53 self
.assert_solutions_dont_change(G
)
55 def test_solutions_dont_change_icecream(self
):
57 If we solve the same game twice over the ice-cream cone, then we
58 should get the same solution both times. The solution to a game
59 is not unique, but the process we use is (as far as we know)
62 G
= random_icecream_game()
63 self
.assert_solutions_dont_change(G
)
65 def assert_solutions_dont_change(self
, G
):
67 Solve ``G`` twice and check that the solutions agree.
71 p1_diff
= norm(soln1
.player1_optimal() - soln2
.player1_optimal())
72 p2_diff
= norm(soln1
.player2_optimal() - soln2
.player2_optimal())
73 gv_diff
= abs(soln1
.game_value() - soln2
.game_value())
75 p1_close
= p1_diff
< options
.ABS_TOL
76 p2_close
= p2_diff
< options
.ABS_TOL
77 gv_close
= gv_diff
< options
.ABS_TOL
79 self
.assertTrue(p1_close
and p2_close
and gv_close
)
82 def assert_player1_start_valid(self
, G
):
84 Ensure that player one's starting point satisfies both the
85 equality and cone inequality in the CVXOPT primal problem.
87 x
= G
.player1_start()['x']
88 s
= G
.player1_start()['s']
89 s1
= s
[0:G
.dimension()]
90 s2
= s
[G
.dimension():]
91 self
.assert_within_tol(norm(G
.A()*x
- G
.b()), 0)
92 self
.assertTrue((s1
, s2
) in G
.C())
95 def test_player1_start_valid_orthant(self
):
97 Ensure that player one's starting point is feasible over the
100 G
= random_orthant_game()
101 self
.assert_player1_start_valid(G
)
104 def test_player1_start_valid_icecream(self
):
106 Ensure that player one's starting point is feasible over the
109 G
= random_icecream_game()
110 self
.assert_player1_start_valid(G
)
113 def assert_player2_start_valid(self
, G
):
115 Check that player two's starting point satisfies both the
116 cone inequality in the CVXOPT dual problem.
118 z
= G
.player2_start()['z']
119 z1
= z
[0:G
.dimension()]
120 z2
= z
[G
.dimension():]
121 self
.assertTrue((z1
, z2
) in G
.C())
124 def test_player2_start_valid_orthant(self
):
126 Ensure that player two's starting point is feasible over the
129 G
= random_orthant_game()
130 self
.assert_player2_start_valid(G
)
133 def test_player2_start_valid_icecream(self
):
135 Ensure that player two's starting point is feasible over the
138 G
= random_icecream_game()
139 self
.assert_player2_start_valid(G
)
142 def test_condition_lower_bound(self
):
144 Ensure that the condition number of a game is greater than or
147 It should be safe to compare these floats directly: we compute
148 the condition number as the ratio of one nonnegative real number
149 to a smaller nonnegative real number.
151 G
= random_orthant_game()
152 self
.assertTrue(G
.condition() >= 1.0)
153 G
= random_icecream_game()
154 self
.assertTrue(G
.condition() >= 1.0)
157 def assert_scaling_works(self
, G
):
159 Test that scaling ``L`` by a nonnegative number scales the value
160 of the game by the same number.
162 (alpha
, H
) = random_nn_scaling(G
)
165 value1
= soln1
.game_value()
166 value2
= soln2
.game_value()
167 modifier1
= G
.tolerance_scale(soln1
)
168 modifier2
= H
.tolerance_scale(soln2
)
169 modifier
= max(modifier1
, modifier2
)
170 self
.assert_within_tol(alpha
*value1
, value2
, modifier
)
173 def test_scaling_orthant(self
):
175 Test that scaling ``L`` by a nonnegative number scales the value
176 of the game by the same number over the nonnegative orthant.
178 G
= random_orthant_game()
179 self
.assert_scaling_works(G
)
182 def test_scaling_icecream(self
):
184 The same test as :meth:`test_nonnegative_scaling_orthant`,
185 except over the ice cream cone.
187 G
= random_icecream_game()
188 self
.assert_scaling_works(G
)
191 def assert_translation_works(self
, G
):
193 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
194 the value of the associated game by alpha.
196 # We need to use ``L`` later, so make sure we transpose it
197 # before passing it in as a column-indexed matrix.
199 value1
= soln1
.game_value()
200 x_bar
= soln1
.player1_optimal()
201 y_bar
= soln1
.player2_optimal()
203 # This is the "correct" representation of ``M``, but COLUMN
205 (alpha
, H
) = random_translation(G
)
206 value2
= H
.solution().game_value()
208 modifier
= G
.tolerance_scale(soln1
)
209 self
.assert_within_tol(value1
+ alpha
, value2
, modifier
)
211 # Make sure the same optimal pair works.
212 self
.assert_within_tol(value2
, H
.payoff(x_bar
, y_bar
), modifier
)
215 def test_translation_orthant(self
):
217 Test that translation works over the nonnegative orthant.
219 G
= random_orthant_game()
220 self
.assert_translation_works(G
)
223 def test_translation_icecream(self
):
225 The same as :meth:`test_translation_orthant`, except over the
228 G
= random_icecream_game()
229 self
.assert_translation_works(G
)
232 def assert_opposite_game_works(self
, G
):
234 Check the value of the "opposite" game that gives rise to a
235 value that is the negation of the original game. Comes from
238 # This is the "correct" representation of ``M``, but
242 # so we have to transpose it when we feed it to the constructor.
243 # Note: the condition number of ``H`` should be comparable to ``G``.
244 H
= SymmetricLinearGame(M
.trans(), G
.K(), G
.e2(), G
.e1())
247 x_bar
= soln1
.player1_optimal()
248 y_bar
= soln1
.player2_optimal()
251 modifier
= G
.tolerance_scale(soln1
)
252 self
.assert_within_tol(-soln1
.game_value(),
256 # Make sure the switched optimal pair works. Since x_bar and
257 # y_bar come from G, we use the same modifier.
258 self
.assert_within_tol(soln2
.game_value(),
259 H
.payoff(y_bar
, x_bar
),
264 def test_opposite_game_orthant(self
):
266 Test the value of the "opposite" game over the nonnegative
269 G
= random_orthant_game()
270 self
.assert_opposite_game_works(G
)
273 def test_opposite_game_icecream(self
):
275 Like :meth:`test_opposite_game_orthant`, except over the
278 G
= random_icecream_game()
279 self
.assert_opposite_game_works(G
)
282 def assert_orthogonality(self
, G
):
284 Two orthogonality relations hold at an optimal solution, and we
288 x_bar
= soln
.player1_optimal()
289 y_bar
= soln
.player2_optimal()
290 value
= soln
.game_value()
292 ip1
= inner_product(y_bar
, G
.L()*x_bar
- value
*G
.e1())
293 ip2
= inner_product(value
*G
.e2() - G
.L().trans()*y_bar
, x_bar
)
295 modifier
= G
.tolerance_scale(soln
)
296 self
.assert_within_tol(ip1
, 0, modifier
)
297 self
.assert_within_tol(ip2
, 0, modifier
)
300 def test_orthogonality_orthant(self
):
302 Check the orthgonality relationships that hold for a solution
303 over the nonnegative orthant.
305 G
= random_orthant_game()
306 self
.assert_orthogonality(G
)
309 def test_orthogonality_icecream(self
):
311 Check the orthgonality relationships that hold for a solution
312 over the ice-cream cone.
314 G
= random_icecream_game()
315 self
.assert_orthogonality(G
)
318 def test_positive_operator_value(self
):
320 Test that a positive operator on the nonnegative orthant gives
321 rise to a a game with a nonnegative value.
323 This test theoretically applies to the ice-cream cone as well,
324 but we don't know how to make positive operators on that cone.
326 G
= random_positive_orthant_game()
327 self
.assertTrue(G
.solution().game_value() >= -options
.ABS_TOL
)
330 def assert_lyapunov_works(self
, G
):
332 Check that Lyapunov games act the way we expect.
336 # We only check for positive/negative stability if the game
337 # value is not basically zero. If the value is that close to
338 # zero, we just won't check any assertions.
340 # See :meth:`assert_within_tol` for an explanation of the
342 eigs
= eigenvalues_re(G
.L())
344 if soln
.game_value() > options
.ABS_TOL
:
345 # L should be positive stable
346 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
347 self
.assertTrue(positive_stable
)
348 elif soln
.game_value() < -options
.ABS_TOL
:
349 # L should be negative stable
350 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
351 self
.assertTrue(negative_stable
)
353 dualsoln
= G
.dual().solution()
354 mod
= G
.tolerance_scale(soln
)
355 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value(), mod
)
358 def test_lyapunov_orthant(self
):
360 Test that a Lyapunov game on the nonnegative orthant works.
362 G
= random_ll_orthant_game()
363 self
.assert_lyapunov_works(G
)
366 def test_lyapunov_icecream(self
):
368 Test that a Lyapunov game on the ice-cream cone works.
370 G
= random_ll_icecream_game()
371 self
.assert_lyapunov_works(G
)