""" Unit tests for the :class:`SymmetricLinearGame` class. """ from unittest import TestCase from dunshire.cones import NonnegativeOrthant from dunshire.games import SymmetricLinearGame from dunshire.matrices import eigenvalues_re, inner_product from dunshire import options from .randomgen import (RANDOM_MAX, random_icecream_game, random_ll_icecream_game, random_ll_orthant_game, random_nn_scaling, random_orthant_game, random_positive_orthant_game, random_translation) EPSILON = 2*2*RANDOM_MAX*options.ABS_TOL """ This is the tolerance constant including fudge factors that we use to determine whether or not two numbers are equal in tests. The factor of two is because if we compare two solutions, both of which may be off by ``ABS_TOL``, then the result could be off by ``2*ABS_TOL``. The factor of ``RANDOM_MAX`` allows for scaling a result (by ``RANDOM_MAX``) that may be off by ``ABS_TOL``. The final factor of two is to allow for the edge cases where we get an "unknown" result and need to lower the CVXOPT tolerance by a factor of two. """ # Tell pylint to shut up about the large number of methods. class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ Tests for the SymmetricLinearGame and Solution classes. """ def assert_within_tol(self, first, second): """ Test that ``first`` and ``second`` are equal within a multiple of our default tolerances. """ self.assertTrue(abs(first - second) < EPSILON) def assert_solution_exists(self, G): """ Given a SymmetricLinearGame, ensure that it has a solution. """ soln = G.solution() expected = inner_product(G._L*soln.player1_optimal(), soln.player2_optimal()) self.assert_within_tol(soln.game_value(), expected) def test_condition_lower_bound(self): """ Ensure that the condition number of a game is greater than or equal to one. It should be safe to compare these floats directly: we compute the condition number as the ratio of one nonnegative real number to a smaller nonnegative real number. """ G = random_orthant_game() self.assertTrue(G.condition() >= 1.0) G = random_icecream_game() self.assertTrue(G.condition() >= 1.0) def test_solution_exists_orthant(self): """ Every linear game has a solution, so we should be able to solve every symmetric linear game over the NonnegativeOrthant. Pick some parameters randomly and give it a shot. The resulting optimal solutions should give us the optimal game value when we apply the payoff operator to them. """ G = random_orthant_game() self.assert_solution_exists(G) def test_solution_exists_icecream(self): """ Like :meth:`test_solution_exists_nonnegative_orthant`, except over the ice cream cone. """ G = random_icecream_game() self.assert_solution_exists(G) def test_negative_value_z_operator(self): """ Test the example given in Gowda/Ravindran of a Z-matrix with negative game value on the nonnegative orthant. """ K = NonnegativeOrthant(2) e1 = [1, 1] e2 = e1 L = [[1, -2], [-2, 1]] G = SymmetricLinearGame(L, K, e1, e2) self.assertTrue(G.solution().game_value() < -options.ABS_TOL) def assert_scaling_works(self, G): """ Test that scaling ``L`` by a nonnegative number scales the value of the game by the same number. """ (alpha, H) = random_nn_scaling(G) value1 = G.solution().game_value() value2 = H.solution().game_value() self.assert_within_tol(alpha*value1, value2) def test_scaling_orthant(self): """ Test that scaling ``L`` by a nonnegative number scales the value of the game by the same number over the nonnegative orthant. """ G = random_orthant_game() self.assert_scaling_works(G) def test_scaling_icecream(self): """ The same test as :meth:`test_nonnegative_scaling_orthant`, except over the ice cream cone. """ G = random_icecream_game() self.assert_scaling_works(G) def assert_translation_works(self, G): """ Check that translating ``L`` by alpha*(e1*e2.trans()) increases the value of the associated game by alpha. """ # We need to use ``L`` later, so make sure we transpose it # before passing it in as a column-indexed matrix. soln1 = G.solution() value1 = soln1.game_value() x_bar = soln1.player1_optimal() y_bar = soln1.player2_optimal() # This is the "correct" representation of ``M``, but COLUMN # indexed... (alpha, H) = random_translation(G) value2 = H.solution().game_value() self.assert_within_tol(value1 + alpha, value2) # Make sure the same optimal pair works. self.assert_within_tol(value2, inner_product(H._L*x_bar, y_bar)) def test_translation_orthant(self): """ Test that translation works over the nonnegative orthant. """ G = random_orthant_game() self.assert_translation_works(G) def test_translation_icecream(self): """ The same as :meth:`test_translation_orthant`, except over the ice cream cone. """ G = random_icecream_game() self.assert_translation_works(G) def assert_opposite_game_works(self, G): """ Check the value of the "opposite" game that gives rise to a value that is the negation of the original game. Comes from some corollary. """ # This is the "correct" representation of ``M``, but # COLUMN indexed... M = -G._L.trans() # so we have to transpose it when we feed it to the constructor. # Note: the condition number of ``H`` should be comparable to ``G``. H = SymmetricLinearGame(M.trans(), G._K, G._e2, G._e1) soln1 = G.solution() x_bar = soln1.player1_optimal() y_bar = soln1.player2_optimal() soln2 = H.solution() self.assert_within_tol(-soln1.game_value(), soln2.game_value()) # Make sure the switched optimal pair works. self.assert_within_tol(soln2.game_value(), inner_product(M*y_bar, x_bar)) def test_opposite_game_orthant(self): """ Test the value of the "opposite" game over the nonnegative orthant. """ G = random_orthant_game() self.assert_opposite_game_works(G) def test_opposite_game_icecream(self): """ Like :meth:`test_opposite_game_orthant`, except over the ice-cream cone. """ G = random_icecream_game() self.assert_opposite_game_works(G) def assert_orthogonality(self, G): """ Two orthogonality relations hold at an optimal solution, and we check them here. """ soln = G.solution() x_bar = soln.player1_optimal() y_bar = soln.player2_optimal() value = soln.game_value() ip1 = inner_product(y_bar, G._L*x_bar - value*G._e1) self.assert_within_tol(ip1, 0) ip2 = inner_product(value*G._e2 - G._L.trans()*y_bar, x_bar) self.assert_within_tol(ip2, 0) def test_orthogonality_orthant(self): """ Check the orthgonality relationships that hold for a solution over the nonnegative orthant. """ G = random_orthant_game() self.assert_orthogonality(G) def test_orthogonality_icecream(self): """ Check the orthgonality relationships that hold for a solution over the ice-cream cone. """ G = random_icecream_game() self.assert_orthogonality(G) def test_positive_operator_value(self): """ Test that a positive operator on the nonnegative orthant gives rise to a a game with a nonnegative value. This test theoretically applies to the ice-cream cone as well, but we don't know how to make positive operators on that cone. """ G = random_positive_orthant_game() self.assertTrue(G.solution().game_value() >= -options.ABS_TOL) def assert_lyapunov_works(self, G): """ Check that Lyapunov games act the way we expect. """ soln = G.solution() # We only check for positive/negative stability if the game # value is not basically zero. If the value is that close to # zero, we just won't check any assertions. # # See :meth:`assert_within_tol` for an explanation of the # fudge factors. eigs = eigenvalues_re(G._L) if soln.game_value() > EPSILON: # L should be positive stable positive_stable = all([eig > -options.ABS_TOL for eig in eigs]) self.assertTrue(positive_stable) elif soln.game_value() < -EPSILON: # L should be negative stable negative_stable = all([eig < options.ABS_TOL for eig in eigs]) self.assertTrue(negative_stable) # The dual game's value should always equal the primal's. dualsoln = G.dual().solution() self.assert_within_tol(dualsoln.game_value(), soln.game_value()) def test_lyapunov_orthant(self): """ Test that a Lyapunov game on the nonnegative orthant works. """ G = random_ll_orthant_game() self.assert_lyapunov_works(G) def test_lyapunov_icecream(self): """ Test that a Lyapunov game on the ice-cream cone works. """ G = random_ll_icecream_game() self.assert_lyapunov_works(G)