From 2c440d0cb6dfaacbaa0a8de725ac73d73893aace Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sun, 9 Oct 2016 22:35:14 -0400 Subject: [PATCH] Add a unit test for the ice cream cone solution. --- makefile | 2 +- src/dunshire/symmetric_linear_game.py | 72 +++++++++++++++++++++------ 2 files changed, 57 insertions(+), 17 deletions(-) diff --git a/makefile b/makefile index 95eb207..fa29cf8 100644 --- a/makefile +++ b/makefile @@ -8,7 +8,7 @@ check: lint: PYTHONPATH="$(SRCDIR)" pylint \ --reports=n \ - --good-names='b,c,h,A,C,G,_K,_L,indented_L' \ + --good-names='b,c,e1,e2,h,A,C,G,K,_K,L,L_matrix,_L,indented_L' \ $(SRCDIR)/*.py .PHONY: clean diff --git a/src/dunshire/symmetric_linear_game.py b/src/dunshire/symmetric_linear_game.py index b6489ba..7be55d7 100644 --- a/src/dunshire/symmetric_linear_game.py +++ b/src/dunshire/symmetric_linear_game.py @@ -5,10 +5,14 @@ This module contains the main SymmetricLinearGame class that knows how to solve a linear game. """ -from cvxopt import matrix, printing, solvers +# These few are used only for tests. +from math import sqrt +from random import randint, uniform from unittest import TestCase -from cones import CartesianProduct +# These are mostly actually needed. +from cvxopt import matrix, printing, solvers +from cones import CartesianProduct, IceCream, NonnegativeOrthant from errors import GameUnsolvableException from matrices import append_col, append_row, identity, inner_product import options @@ -388,8 +392,11 @@ class SymmetricLinearGame: class SymmetricLinearGameTest(TestCase): + """ + Tests for the SymmetricLinearGame and Solution classes. + """ - def assertEqualWithinTol(self, first, second): + def assert_within_tol(self, first, second): """ Test that ``first`` and ``second`` are equal within our default tolerance. @@ -397,23 +404,56 @@ class SymmetricLinearGameTest(TestCase): self.assertTrue(abs(first - second) < options.ABS_TOL) - def test_solution_exists(self): + def assert_solution_exists(self, L, K, e1, e2): """ - Every linear game has a solution, so we should be able to solve - every symmetric linear game. Pick some parameters randomly and - give it a shot. + Given the parameters needed to construct a SymmetricLinearGame, + ensure that that game has a solution. """ - from cones import NonnegativeOrthant - from random import randint, uniform - ambient_dim = randint(1,10) - K = NonnegativeOrthant(ambient_dim) - e1 = [uniform(0.1, 10) for idx in range(ambient_dim)] - e2 = [uniform(0.1, 10) for idx in range(ambient_dim)] - L = [[uniform(-10, 10) for i in range(ambient_dim)] - for j in range(ambient_dim)] G = SymmetricLinearGame(L, K, e1, e2) soln = G.solution() L_matrix = matrix(L).trans() expected = inner_product(L_matrix*soln.player1_optimal(), soln.player2_optimal()) - self.assertEqualWithinTol(soln.game_value(), expected) + self.assert_within_tol(soln.game_value(), expected) + + def test_solution_exists_nonnegative_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. + """ + ambient_dim = randint(1, 10) + K = NonnegativeOrthant(ambient_dim) + e1 = [uniform(0.1, 10) for idx in range(K.dimension())] + e2 = [uniform(0.1, 10) for idx in range(K.dimension())] + L = [[uniform(-10, 10) for i in range(K.dimension())] + for j in range(K.dimension())] + self.assert_solution_exists(L, K, e1, e2) + + def test_solution_exists_ice_cream(self): + """ + Like :meth:`test_solution_exists_nonnegative_orthant`, except + 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] + e2 = [1] + # 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 = [[uniform(-10, 10) for i in range(K.dimension())] + for j in range(K.dimension())] + self.assert_solution_exists(L, K, e1, e2) + -- 2.44.2