]>
gitweb.michael.orlitzky.com - dunshire.git/blob - test/symmetric_linear_game_test.py
2 Unit tests for the :class:`SymmetricLinearGame` class.
6 from random
import randint
, uniform
7 from unittest
import TestCase
9 from cvxopt
import matrix
10 from dunshire
.cones
import NonnegativeOrthant
, IceCream
11 from dunshire
.games
import SymmetricLinearGame
12 from dunshire
.matrices
import (append_col
, append_row
, eigenvalues_re
,
13 identity
, inner_product
)
14 from dunshire
import options
17 def random_matrix(dims
):
19 Generate a random square matrix.
25 The number of rows/columns you want in the returned matrix.
31 A new matrix whose entries are random floats chosen uniformly from
32 the interval [-10, 10].
37 >>> A = random_matrix(3)
42 return matrix([[uniform(-10, 10) for _
in range(dims
)]
43 for _
in range(dims
)])
46 def random_nonnegative_matrix(dims
):
48 Generate a random square matrix with nonnegative entries.
54 The number of rows/columns you want in the returned matrix.
60 A new matrix whose entries are random floats chosen uniformly from
66 >>> A = random_nonnegative_matrix(3)
69 >>> all([entry >= 0 for entry in A])
73 L
= random_matrix(dims
)
74 return matrix([abs(entry
) for entry
in L
], (dims
, dims
))
77 def random_diagonal_matrix(dims
):
79 Generate a random square matrix with zero off-diagonal entries.
81 These matrices are Lyapunov-like on the nonnegative orthant, as is
88 The number of rows/columns you want in the returned matrix.
94 A new matrix whose diagonal entries are random floats chosen
95 uniformly from the interval [-10, 10] and whose off-diagonal
101 >>> A = random_diagonal_matrix(3)
104 >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0
108 return matrix([[uniform(-10, 10)*int(i
== j
) for i
in range(dims
)]
109 for j
in range(dims
)])
112 def random_skew_symmetric_matrix(dims
):
114 Generate a random skew-symmetrix matrix.
120 The number of rows/columns you want in the returned matrix.
126 A new skew-matrix whose strictly above-diagonal entries are
127 random floats chosen uniformly from the interval [-10, 10].
132 >>> A = random_skew_symmetric_matrix(3)
136 >>> from dunshire.matrices import norm
137 >>> A = random_skew_symmetric_matrix(randint(1, 10))
138 >>> norm(A + A.trans()) < options.ABS_TOL
142 strict_ut
= [[uniform(-10, 10)*int(i
< j
) for i
in range(dims
)]
143 for j
in range(dims
)]
145 strict_ut
= matrix(strict_ut
, (dims
, dims
))
146 return strict_ut
- strict_ut
.trans()
149 def random_lyapunov_like_icecream(dims
):
151 Generate a random matrix Lyapunov-like on the ice-cream cone.
153 The form of these matrices is cited in Gowda and Tao
154 [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their
155 notation) are easy to generate. The submatrix ``D`` is a little
156 trickier, but it can be found noticing that :math:`C + C^{T} = 0`
157 for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T}
158 + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an
159 :math:`aI` with each of :math:`C,C^{T}` and let those be our
166 The dimension of the ice-cream cone (not of the matrix you want!)
167 on which the returned matrix should be Lyapunov-like.
173 A new matrix, Lyapunov-like on the ice-cream cone in ``dims``
174 dimensions, whose free entries are random floats chosen uniformly
175 from the interval [-10, 10].
180 .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a
181 proper cone and Lyapunov-like transformations. Mathematical
182 Programming, 147:155-170, 2014.
187 >>> L = random_lyapunov_like_icecream(3)
190 >>> x = matrix([1,1,0])
191 >>> s = matrix([1,-1,0])
192 >>> abs(inner_product(L*x, s)) < options.ABS_TOL
196 a
= matrix([uniform(-10, 10)], (1, 1))
197 b
= matrix([uniform(-10, 10) for _
in range(dims
-1)], (dims
-1, 1))
198 D
= random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
199 row1
= append_col(a
, b
.trans())
200 row2
= append_col(b
, D
)
201 return append_row(row1
, row2
)
204 def random_orthant_params():
206 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
207 random game over the nonnegative orthant.
209 ambient_dim
= randint(1, 10)
210 K
= NonnegativeOrthant(ambient_dim
)
211 e1
= [uniform(0.5, 10) for _
in range(K
.dimension())]
212 e2
= [uniform(0.5, 10) for _
in range(K
.dimension())]
213 L
= random_matrix(K
.dimension())
214 return (L
, K
, matrix(e1
), matrix(e2
))
217 def random_icecream_params():
219 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
220 random game over the ice-cream cone.
222 # Use a minimum dimension of two to avoid divide-by-zero in
223 # the fudge factor we make up later.
224 ambient_dim
= randint(2, 10)
225 K
= IceCream(ambient_dim
)
226 e1
= [1] # Set the "height" of e1 to one
227 e2
= [1] # And the same for e2
229 # If we choose the rest of the components of e1,e2 randomly
230 # between 0 and 1, then the largest the squared norm of the
231 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
232 # need to make it less than one (the height of the cone) so
233 # that the whole thing is in the cone. The norm of the
234 # non-height part is sqrt(dim(K) - 1), and we can divide by
236 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
237 e1
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
238 e2
+= [fudge_factor
*uniform(0, 1) for _
in range(K
.dimension() - 1)]
239 L
= random_matrix(K
.dimension())
241 return (L
, K
, matrix(e1
), matrix(e2
))
244 # Tell pylint to shut up about the large number of methods.
245 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
247 Tests for the SymmetricLinearGame and Solution classes.
249 def assert_within_tol(self
, first
, second
):
251 Test that ``first`` and ``second`` are equal within our default
254 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
257 def assert_solution_exists(self
, L
, K
, e1
, e2
):
259 Given the parameters needed to construct a SymmetricLinearGame,
260 ensure that that game has a solution.
262 # The matrix() constructor assumes that ``L`` is a list of
263 # columns, so we transpose it to agree with what
264 # SymmetricLinearGame() thinks.
265 G
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
268 expected
= inner_product(L
*soln
.player1_optimal(),
269 soln
.player2_optimal())
270 self
.assert_within_tol(soln
.game_value(), expected
)
273 def test_solution_exists_orthant(self
):
275 Every linear game has a solution, so we should be able to solve
276 every symmetric linear game over the NonnegativeOrthant. Pick
277 some parameters randomly and give it a shot. The resulting
278 optimal solutions should give us the optimal game value when we
279 apply the payoff operator to them.
281 (L
, K
, e1
, e2
) = random_orthant_params()
282 self
.assert_solution_exists(L
, K
, e1
, e2
)
285 def test_solution_exists_icecream(self
):
287 Like :meth:`test_solution_exists_nonnegative_orthant`, except
288 over the ice cream cone.
290 (L
, K
, e1
, e2
) = random_icecream_params()
291 self
.assert_solution_exists(L
, K
, e1
, e2
)
294 def test_negative_value_z_operator(self
):
296 Test the example given in Gowda/Ravindran of a Z-matrix with
297 negative game value on the nonnegative orthant.
299 K
= NonnegativeOrthant(2)
302 L
= [[1, -2], [-2, 1]]
303 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
304 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
307 def assert_scaling_works(self
, L
, K
, e1
, e2
):
309 Test that scaling ``L`` by a nonnegative number scales the value
310 of the game by the same number.
312 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
313 value1
= game1
.solution().game_value()
315 alpha
= uniform(0.1, 10)
316 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
317 value2
= game2
.solution().game_value()
318 self
.assert_within_tol(alpha
*value1
, value2
)
321 def test_scaling_orthant(self
):
323 Test that scaling ``L`` by a nonnegative number scales the value
324 of the game by the same number over the nonnegative orthant.
326 (L
, K
, e1
, e2
) = random_orthant_params()
327 self
.assert_scaling_works(L
, K
, e1
, e2
)
330 def test_scaling_icecream(self
):
332 The same test as :meth:`test_nonnegative_scaling_orthant`,
333 except over the ice cream cone.
335 (L
, K
, e1
, e2
) = random_icecream_params()
336 self
.assert_scaling_works(L
, K
, e1
, e2
)
339 def assert_translation_works(self
, L
, K
, e1
, e2
):
341 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
342 the value of the associated game by alpha.
344 # We need to use ``L`` later, so make sure we transpose it
345 # before passing it in as a column-indexed matrix.
346 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
347 soln1
= game1
.solution()
348 value1
= soln1
.game_value()
349 x_bar
= soln1
.player1_optimal()
350 y_bar
= soln1
.player2_optimal()
352 alpha
= uniform(-10, 10)
353 tensor_prod
= e1
*e2
.trans()
355 # This is the "correct" representation of ``M``, but COLUMN
357 M
= L
+ alpha
*tensor_prod
359 # so we have to transpose it when we feed it to the constructor.
360 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
361 value2
= game2
.solution().game_value()
363 self
.assert_within_tol(value1
+ alpha
, value2
)
365 # Make sure the same optimal pair works.
366 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
369 def test_translation_orthant(self
):
371 Test that translation works over the nonnegative orthant.
373 (L
, K
, e1
, e2
) = random_orthant_params()
374 self
.assert_translation_works(L
, K
, e1
, e2
)
377 def test_translation_icecream(self
):
379 The same as :meth:`test_translation_orthant`, except over the
382 (L
, K
, e1
, e2
) = random_icecream_params()
383 self
.assert_translation_works(L
, K
, e1
, e2
)
386 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
388 Check the value of the "opposite" game that gives rise to a
389 value that is the negation of the original game. Comes from
392 # We need to use ``L`` later, so make sure we transpose it
393 # before passing it in as a column-indexed matrix.
394 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
396 # This is the "correct" representation of ``M``, but
400 # so we have to transpose it when we feed it to the constructor.
401 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
403 soln1
= game1
.solution()
404 x_bar
= soln1
.player1_optimal()
405 y_bar
= soln1
.player2_optimal()
406 soln2
= game2
.solution()
408 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
410 # Make sure the switched optimal pair works.
411 self
.assert_within_tol(soln2
.game_value(),
412 inner_product(M
*y_bar
, x_bar
))
415 def test_opposite_game_orthant(self
):
417 Test the value of the "opposite" game over the nonnegative
420 (L
, K
, e1
, e2
) = random_orthant_params()
421 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
424 def test_opposite_game_icecream(self
):
426 Like :meth:`test_opposite_game_orthant`, except over the
429 (L
, K
, e1
, e2
) = random_icecream_params()
430 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
433 def assert_orthogonality(self
, L
, K
, e1
, e2
):
435 Two orthogonality relations hold at an optimal solution, and we
438 # We need to use ``L`` later, so make sure we transpose it
439 # before passing it in as a column-indexed matrix.
440 game
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
441 soln
= game
.solution()
442 x_bar
= soln
.player1_optimal()
443 y_bar
= soln
.player2_optimal()
444 value
= soln
.game_value()
446 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
447 self
.assert_within_tol(ip1
, 0)
449 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
450 self
.assert_within_tol(ip2
, 0)
453 def test_orthogonality_orthant(self
):
455 Check the orthgonality relationships that hold for a solution
456 over the nonnegative orthant.
458 (L
, K
, e1
, e2
) = random_orthant_params()
459 self
.assert_orthogonality(L
, K
, e1
, e2
)
462 def test_orthogonality_icecream(self
):
464 Check the orthgonality relationships that hold for a solution
465 over the ice-cream cone.
467 (L
, K
, e1
, e2
) = random_icecream_params()
468 self
.assert_orthogonality(L
, K
, e1
, e2
)
471 def test_positive_operator_value(self
):
473 Test that a positive operator on the nonnegative orthant gives
474 rise to a a game with a nonnegative value.
476 This test theoretically applies to the ice-cream cone as well,
477 but we don't know how to make positive operators on that cone.
479 (K
, e1
, e2
) = random_orthant_params()[1:]
480 L
= random_nonnegative_matrix(K
.dimension())
482 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
483 self
.assertTrue(game
.solution().game_value() >= -options
.ABS_TOL
)
486 def assert_lyapunov_works(self
, L
, K
, e1
, e2
):
488 Check that Lyapunov games act the way we expect.
490 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
491 soln
= game
.solution()
493 # We only check for positive/negative stability if the game
494 # value is not basically zero. If the value is that close to
495 # zero, we just won't check any assertions.
496 eigs
= eigenvalues_re(L
)
497 if soln
.game_value() > options
.ABS_TOL
:
498 # L should be positive stable
499 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
500 self
.assertTrue(positive_stable
)
501 elif soln
.game_value() < -options
.ABS_TOL
:
502 # L should be negative stable
503 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
504 self
.assertTrue(negative_stable
)
506 # The dual game's value should always equal the primal's.
507 dualsoln
= game
.dual().solution()
508 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
511 def test_lyapunov_orthant(self
):
513 Test that a Lyapunov game on the nonnegative orthant works.
515 (K
, e1
, e2
) = random_orthant_params()[1:]
516 L
= random_diagonal_matrix(K
.dimension())
518 self
.assert_lyapunov_works(L
, K
, e1
, e2
)
521 def test_lyapunov_icecream(self
):
523 Test that a Lyapunov game on the ice-cream cone works.
525 (K
, e1
, e2
) = random_icecream_params()[1:]
526 L
= random_lyapunov_like_icecream(K
.dimension())
528 self
.assert_lyapunov_works(L
, K
, e1
, e2
)