X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2Fdunshire%2Fgames.py;h=05ab58cd702c5570221184ed47f5bb16289627c0;hb=769e1c7d09936a617f33d1496782fbbd4299851d;hp=76fbf7deedfec733bf4213bec000bdf449087e75;hpb=9da611019b85e58ecab8450f9a9043c6f4a184d1;p=dunshire.git diff --git a/src/dunshire/games.py b/src/dunshire/games.py index 76fbf7d..05ab58c 100644 --- a/src/dunshire/games.py +++ b/src/dunshire/games.py @@ -12,10 +12,11 @@ from unittest import TestCase # 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, norm -import options +from .cones import CartesianProduct, IceCream, NonnegativeOrthant +from .errors import GameUnsolvableException +from .matrices import (append_col, append_row, eigenvalues_re, identity, + inner_product, norm) +from . import options printing.options['dformat'] = options.FLOAT_FORMAT solvers.options['show_progress'] = options.VERBOSE @@ -210,7 +211,6 @@ class SymmetricLinearGame: Examples -------- - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] >>> e1 = [1,1,1] @@ -231,7 +231,6 @@ class SymmetricLinearGame: Lists can (and probably should) be used for every argument:: - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(2) >>> L = [[1,0],[0,1]] >>> e1 = [1,1] @@ -253,7 +252,6 @@ class SymmetricLinearGame: >>> import cvxopt >>> import numpy - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(2) >>> L = [[1,0],[0,1]] >>> e1 = cvxopt.matrix([1,1]) @@ -274,7 +272,6 @@ class SymmetricLinearGame: otherwise indexed by columns:: >>> import cvxopt - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(2) >>> L = [[1,2],[3,4]] >>> e1 = [1,1] @@ -363,7 +360,6 @@ class SymmetricLinearGame: This example is computed in Gowda and Ravindran in the section "The value of a Z-transformation":: - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] >>> e1 = [1,1,1] @@ -383,7 +379,6 @@ class SymmetricLinearGame: The value of the following game can be computed using the fact that the identity is invertible:: - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) >>> L = [[1,0,0],[0,1,0],[0,0,1]] >>> e1 = [1,2,3] @@ -474,7 +469,6 @@ class SymmetricLinearGame: Examples -------- - >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] >>> e1 = [1,1,1] @@ -504,13 +498,63 @@ class SymmetricLinearGame: -def _random_square_matrix(dims): +def _random_matrix(dims): """ - Generate a random square (``dims``-by-``dims``) matrix, - represented as a list of rows. This is used only by the + Generate a random square (``dims``-by-``dims``) matrix. This is used + only by the :class:`SymmetricLinearGameTest` class. + """ + return matrix([[uniform(-10, 10) for i in range(dims)] + for j in range(dims)]) + +def _random_nonnegative_matrix(dims): + """ + Generate a random square (``dims``-by-``dims``) matrix with + nonnegative entries. This is used only by the + :class:`SymmetricLinearGameTest` class. + """ + L = _random_matrix(dims) + return matrix([abs(entry) for entry in L], (dims, dims)) + +def _random_diagonal_matrix(dims): + """ + Generate a random square (``dims``-by-``dims``) matrix with nonzero + entries only on the diagonal. This is used only by the :class:`SymmetricLinearGameTest` class. """ - return [[uniform(-10, 10) for i in range(dims)] for j in range(dims)] + 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 (``dims``-by-``dims``) matrix. + + Examples + -------- + + >>> 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): + """ + Generate a random Lyapunov-like matrix over the ice-cream cone in + ``dims`` dimensions. + """ + 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(): @@ -523,8 +567,8 @@ def _random_orthant_params(): 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_square_matrix(K.dimension()) - return (L, K, e1, e2) + L = _random_matrix(K.dimension()) + return (L, K, matrix(e1), matrix(e2)) def _random_icecream_params(): @@ -550,12 +594,13 @@ def _random_icecream_params(): 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_square_matrix(K.dimension()) + L = _random_matrix(K.dimension()) - return (L, K, e1, e2) + return (L, K, matrix(e1), matrix(e2)) -class SymmetricLinearGameTest(TestCase): +# Tell pylint to shut up about the large number of methods. +class SymmetricLinearGameTest(TestCase): # pylint: disable=R0904 """ Tests for the SymmetricLinearGame and Solution classes. """ @@ -581,14 +626,13 @@ class SymmetricLinearGameTest(TestCase): Given the parameters needed to construct a SymmetricLinearGame, ensure that that game has a solution. """ - G = SymmetricLinearGame(L, K, e1, e2) - soln = G.solution() - # The matrix() constructor assumes that ``L`` is a list of # columns, so we transpose it to agree with what # SymmetricLinearGame() thinks. - L_matrix = matrix(L).trans() - expected = inner_product(L_matrix*soln.player1_optimal(), + 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) @@ -632,9 +676,6 @@ class SymmetricLinearGameTest(TestCase): Test that scaling ``L`` by a nonnegative number scales the value of the game by the same number. """ - # Make ``L`` a matrix so that we can scale it by alpha. Its - # random, so who cares if it gets transposed. - L = matrix(L) game1 = SymmetricLinearGame(L, K, e1, e2) value1 = game1.solution().game_value() @@ -667,23 +708,19 @@ class SymmetricLinearGameTest(TestCase): Check that translating ``L`` by alpha*(e1*e2.trans()) increases the value of the associated game by alpha. """ - e1 = matrix(e1, (K.dimension(), 1)) - e2 = matrix(e2, (K.dimension(), 1)) - game1 = SymmetricLinearGame(L, K, e1, e2) + # 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() - # Make ``L`` a CVXOPT matrix so that we can do math with - # it. Note that this gives us the "correct" representation of - # ``L`` (in agreement with what G has), but COLUMN indexed. alpha = uniform(-10, 10) - L = matrix(L).trans() tensor_prod = e1*e2.trans() - # Likewise, this is the "correct" representation of ``M``, but - # COLUMN indexed... + # 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. @@ -719,16 +756,11 @@ class SymmetricLinearGameTest(TestCase): value that is the negation of the original game. Comes from some corollary. """ - e1 = matrix(e1, (K.dimension(), 1)) - e2 = matrix(e2, (K.dimension(), 1)) - game1 = SymmetricLinearGame(L, K, e1, e2) + # 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) - # Make ``L`` a CVXOPT matrix so that we can do math with - # it. Note that this gives us the "correct" representation of - # ``L`` (in agreement with what G has), but COLUMN indexed. - L = matrix(L).trans() - - # Likewise, this is the "correct" representation of ``M``, but + # This is the "correct" representation of ``M``, but # COLUMN indexed... M = -L.trans() @@ -770,17 +802,14 @@ class SymmetricLinearGameTest(TestCase): Two orthogonality relations hold at an optimal solution, and we check them here. """ - game = SymmetricLinearGame(L, K, e1, e2) + # 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() - # Make these matrices so that we can compute with them. - L = matrix(L).trans() - e1 = matrix(e1, (K.dimension(), 1)) - e2 = matrix(e2, (K.dimension(), 1)) - ip1 = inner_product(y_bar, L*x_bar - value*e1) self.assert_within_tol(ip1, 0) @@ -804,3 +833,63 @@ class SymmetricLinearGameTest(TestCase): """ (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)