From 21a2eb9a647a48c0e94d02c60ef8785c4ea35f7b Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Wed, 26 Oct 2016 14:05:00 -0400 Subject: [PATCH] Remove a unicode hyphen from a reference. --- test/symmetric_linear_game_test.py | 528 +++++++++++++++++++++++++++++ 1 file changed, 528 insertions(+) create mode 100644 test/symmetric_linear_game_test.py diff --git a/test/symmetric_linear_game_test.py b/test/symmetric_linear_game_test.py new file mode 100644 index 0000000..f61356d --- /dev/null +++ b/test/symmetric_linear_game_test.py @@ -0,0 +1,528 @@ +""" +Unit tests for the :class:`SymmetricLinearGame` class. +""" + +from math import sqrt +from random import randint, uniform +from unittest import TestCase + +from cvxopt import matrix +from dunshire.cones import NonnegativeOrthant, IceCream +from dunshire.games import SymmetricLinearGame +from dunshire.matrices import (append_col, append_row, eigenvalues_re, + identity, inner_product) +from dunshire import options + + +def random_matrix(dims): + """ + Generate a random square matrix. + + Parameters + ---------- + + dims : int + The number of rows/columns you want in the returned matrix. + + Returns + ------- + + matrix + A new matrix whose entries are random floats chosen uniformly from + the interval [-10, 10]. + + Examples + -------- + + >>> A = random_matrix(3) + >>> A.size + (3, 3) + + """ + return matrix([[uniform(-10, 10) for i in range(dims)] + for j in range(dims)]) + + +def random_nonnegative_matrix(dims): + """ + Generate a random square matrix with nonnegative entries. + + Parameters + ---------- + + dims : int + The number of rows/columns you want in the returned matrix. + + Returns + ------- + + matrix + A new matrix whose entries are random floats chosen uniformly from + the interval [0, 10]. + + Examples + -------- + + >>> A = random_nonnegative_matrix(3) + >>> A.size + (3, 3) + >>> all([entry >= 0 for entry in A]) + True + + """ + L = random_matrix(dims) + return matrix([abs(entry) for entry in L], (dims, dims)) + + +def random_diagonal_matrix(dims): + """ + Generate a random square matrix with zero off-diagonal entries. + + These matrices are Lyapunov-like on the nonnegative orthant, as is + fairly easy to see. + + Parameters + ---------- + + dims : int + The number of rows/columns you want in the returned matrix. + + Returns + ------- + + matrix + A new matrix whose diagonal entries are random floats chosen + uniformly from the interval [-10, 10] and whose off-diagonal + entries are zero. + + Examples + -------- + + >>> A = random_diagonal_matrix(3) + >>> A.size + (3, 3) + >>> A[0,1] == A[0,2] == A[1,0] == A[2,0] == A[1,2] == A[2,1] == 0 + True + + """ + return matrix([[uniform(-10, 10)*int(i == j) for i in range(dims)] + for j in range(dims)]) + + +def random_skew_symmetric_matrix(dims): + """ + Generate a random skew-symmetrix matrix. + + Parameters + ---------- + + dims : int + The number of rows/columns you want in the returned matrix. + + Returns + ------- + + matrix + A new skew-matrix whose strictly above-diagonal entries are + random floats chosen uniformly from the interval [-10, 10]. + + Examples + -------- + + >>> A = random_skew_symmetric_matrix(3) + >>> A.size + (3, 3) + + >>> from dunshire.matrices import norm + >>> A = random_skew_symmetric_matrix(randint(1, 10)) + >>> norm(A + A.trans()) < options.ABS_TOL + True + + """ + strict_ut = [[uniform(-10, 10)*int(i < j) for i in range(dims)] + for j in range(dims)] + + strict_ut = matrix(strict_ut, (dims, dims)) + return strict_ut - strict_ut.trans() + + +def random_lyapunov_like_icecream(dims): + r""" + Generate a random matrix Lyapunov-like on the ice-cream cone. + + The form of these matrices is cited in Gowda and Tao + [GowdaTao]_. The scalar ``a`` and the vector ``b`` (using their + notation) are easy to generate. The submatrix ``D`` is a little + trickier, but it can be found noticing that :math:`C + C^{T} = 0` + for a skew-symmetric matrix :math:`C` implying that :math:`C + C^{T} + + \left(2a\right)I = \left(2a\right)I`. Thus we can stick an + :math:`aI` with each of :math:`C,C^{T}` and let those be our + :math:`D,D^{T}`. + + Parameters + ---------- + + dims : int + The dimension of the ice-cream cone (not of the matrix you want!) + on which the returned matrix should be Lyapunov-like. + + Returns + ------- + + matrix + A new matrix, Lyapunov-like on the ice-cream cone in ``dims`` + dimensions, whose free entries are random floats chosen uniformly + from the interval [-10, 10]. + + References + ---------- + + .. [GowdaTao] M. S. Gowda and J. Tao. On the bilinearity rank of a + proper cone and Lyapunov-like transformations. Mathematical + Programming, 147:155-170, 2014. + + Examples + -------- + + >>> L = random_lyapunov_like_icecream(3) + >>> L.size + (3, 3) + >>> x = matrix([1,1,0]) + >>> s = matrix([1,-1,0]) + >>> abs(inner_product(L*x, s)) < options.ABS_TOL + True + + """ + a = matrix([uniform(-10, 10)], (1, 1)) + b = matrix([uniform(-10, 10) for idx in range(dims-1)], (dims-1, 1)) + D = random_skew_symmetric_matrix(dims-1) + a*identity(dims-1) + row1 = append_col(a, b.trans()) + row2 = append_col(b, D) + return append_row(row1, row2) + + +def random_orthant_params(): + """ + Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a + random game over the nonnegative orthant. + """ + ambient_dim = randint(1, 10) + K = NonnegativeOrthant(ambient_dim) + e1 = [uniform(0.5, 10) for idx in range(K.dimension())] + e2 = [uniform(0.5, 10) for idx in range(K.dimension())] + L = random_matrix(K.dimension()) + return (L, K, matrix(e1), matrix(e2)) + + +def random_icecream_params(): + """ + Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a + random game over the ice-cream cone. + """ + # Use a minimum dimension of two to avoid divide-by-zero in + # the fudge factor we make up later. + ambient_dim = randint(2, 10) + K = IceCream(ambient_dim) + e1 = [1] # Set the "height" of e1 to one + e2 = [1] # And the same for e2 + + # If we choose the rest of the components of e1,e2 randomly + # between 0 and 1, then the largest the squared norm of the + # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We + # need to make it less than one (the height of the cone) so + # that the whole thing is in the cone. The norm of the + # non-height part is sqrt(dim(K) - 1), and we can divide by + # twice that. + fudge_factor = 1.0 / (2.0*sqrt(K.dimension() - 1.0)) + e1 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)] + e2 += [fudge_factor*uniform(0, 1) for idx in range(K.dimension() - 1)] + L = random_matrix(K.dimension()) + + return (L, K, matrix(e1), matrix(e2)) + + +# 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 our default + tolerance. + """ + self.assertTrue(abs(first - second) < options.ABS_TOL) + + + def assert_solution_exists(self, L, K, e1, e2): + """ + Given the parameters needed to construct a SymmetricLinearGame, + ensure that that game has a solution. + """ + # The matrix() constructor assumes that ``L`` is a list of + # columns, so we transpose it to agree with what + # SymmetricLinearGame() thinks. + G = SymmetricLinearGame(L.trans(), K, e1, e2) + soln = G.solution() + + expected = inner_product(L*soln.player1_optimal(), + soln.player2_optimal()) + self.assert_within_tol(soln.game_value(), expected) + + + 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. + """ + (L, K, e1, e2) = random_orthant_params() + self.assert_solution_exists(L, K, e1, e2) + + + def test_solution_exists_icecream(self): + """ + Like :meth:`test_solution_exists_nonnegative_orthant`, except + over the ice cream cone. + """ + (L, K, e1, e2) = random_icecream_params() + self.assert_solution_exists(L, K, e1, e2) + + + 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, L, K, e1, e2): + """ + Test that scaling ``L`` by a nonnegative number scales the value + of the game by the same number. + """ + game1 = SymmetricLinearGame(L, K, e1, e2) + value1 = game1.solution().game_value() + + alpha = uniform(0.1, 10) + game2 = SymmetricLinearGame(alpha*L, K, e1, e2) + value2 = game2.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. + """ + (L, K, e1, e2) = random_orthant_params() + self.assert_scaling_works(L, K, e1, e2) + + + def test_scaling_icecream(self): + """ + The same test as :meth:`test_nonnegative_scaling_orthant`, + except over the ice cream cone. + """ + (L, K, e1, e2) = random_icecream_params() + self.assert_scaling_works(L, K, e1, e2) + + + def assert_translation_works(self, L, K, e1, e2): + """ + 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. + game1 = SymmetricLinearGame(L.trans(), K, e1, e2) + soln1 = game1.solution() + value1 = soln1.game_value() + x_bar = soln1.player1_optimal() + y_bar = soln1.player2_optimal() + + alpha = uniform(-10, 10) + tensor_prod = e1*e2.trans() + + # This is the "correct" representation of ``M``, but COLUMN + # indexed... + M = L + alpha*tensor_prod + + # so we have to transpose it when we feed it to the constructor. + game2 = SymmetricLinearGame(M.trans(), K, e1, e2) + value2 = game2.solution().game_value() + + self.assert_within_tol(value1 + alpha, value2) + + # Make sure the same optimal pair works. + self.assert_within_tol(value2, inner_product(M*x_bar, y_bar)) + + + def test_translation_orthant(self): + """ + Test that translation works over the nonnegative orthant. + """ + (L, K, e1, e2) = random_orthant_params() + self.assert_translation_works(L, K, e1, e2) + + + def test_translation_icecream(self): + """ + The same as :meth:`test_translation_orthant`, except over the + ice cream cone. + """ + (L, K, e1, e2) = random_icecream_params() + self.assert_translation_works(L, K, e1, e2) + + + def assert_opposite_game_works(self, L, K, e1, e2): + """ + 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. + """ + # We need to use ``L`` later, so make sure we transpose it + # before passing it in as a column-indexed matrix. + game1 = SymmetricLinearGame(L.trans(), K, e1, e2) + + # This is the "correct" representation of ``M``, but + # COLUMN indexed... + M = -L.trans() + + # so we have to transpose it when we feed it to the constructor. + game2 = SymmetricLinearGame(M.trans(), K, e2, e1) + + soln1 = game1.solution() + x_bar = soln1.player1_optimal() + y_bar = soln1.player2_optimal() + soln2 = game2.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. + """ + (L, K, e1, e2) = random_orthant_params() + self.assert_opposite_game_works(L, K, e1, e2) + + + def test_opposite_game_icecream(self): + """ + Like :meth:`test_opposite_game_orthant`, except over the + ice-cream cone. + """ + (L, K, e1, e2) = random_icecream_params() + self.assert_opposite_game_works(L, K, e1, e2) + + + def assert_orthogonality(self, L, K, e1, e2): + """ + Two orthogonality relations hold at an optimal solution, and we + check them here. + """ + # We need to use ``L`` later, so make sure we transpose it + # before passing it in as a column-indexed matrix. + game = SymmetricLinearGame(L.trans(), K, e1, e2) + soln = game.solution() + x_bar = soln.player1_optimal() + y_bar = soln.player2_optimal() + value = soln.game_value() + + ip1 = inner_product(y_bar, L*x_bar - value*e1) + self.assert_within_tol(ip1, 0) + + ip2 = inner_product(value*e2 - 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. + """ + (L, K, e1, e2) = random_orthant_params() + self.assert_orthogonality(L, K, e1, e2) + + + def test_orthogonality_icecream(self): + """ + Check the orthgonality relationships that hold for a solution + over the ice-cream cone. + """ + (L, K, e1, e2) = random_icecream_params() + self.assert_orthogonality(L, K, e1, e2) + + + 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. + """ + (K, e1, e2) = random_orthant_params()[1:] + L = random_nonnegative_matrix(K.dimension()) + + game = SymmetricLinearGame(L, K, e1, e2) + self.assertTrue(game.solution().game_value() >= -options.ABS_TOL) + + + def assert_lyapunov_works(self, L, K, e1, e2): + """ + Check that Lyapunov games act the way we expect. + """ + game = SymmetricLinearGame(L, K, e1, e2) + soln = game.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. + eigs = eigenvalues_re(L) + if soln.game_value() > options.ABS_TOL: + # L should be positive stable + positive_stable = all([eig > -options.ABS_TOL for eig in eigs]) + self.assertTrue(positive_stable) + elif soln.game_value() < -options.ABS_TOL: + # 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 = game.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. + """ + (K, e1, e2) = random_orthant_params()[1:] + L = random_diagonal_matrix(K.dimension()) + + self.assert_lyapunov_works(L, K, e1, e2) + + + def test_lyapunov_icecream(self): + """ + Test that a Lyapunov game on the ice-cream cone works. + """ + (K, e1, e2) = random_icecream_params()[1:] + L = random_lyapunov_like_icecream(K.dimension()) + + self.assert_lyapunov_works(L, K, e1, e2) -- 2.44.2