[dunshire.git] / test / symmetric_linear_game_test.py

"""
Unit tests for the :class:`SymmetricLinearGame` class.
"""

MAX_COND = 250
"""
The maximum condition number of a randomly-generated game.
"""

RANDOM_MAX = 10
"""
When generating uniform random real numbers, this will be used as the
largest allowed magnitude. It keeps our condition numbers down and other
properties within reason.
"""

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 [-RANDOM_MAX, RANDOM_MAX].

    Examples
    --------

        >>> A = random_matrix(3)
        >>> A.size
        (3, 3)

    """
    return matrix([[uniform(-RANDOM_MAX, RANDOM_MAX) for _ in range(dims)]
                   for _ 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, RANDOM_MAX].

    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 [-RANDOM_MAX, RANDOM_MAX] 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(-RANDOM_MAX, RANDOM_MAX)*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
        [-RANDOM_MAX, RANDOM_MAX].

    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 _ 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_game():
    """
    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
    random game over the nonnegative orthant, and return the
    corresponding :class:`SymmetricLinearGame`.

    We keep going until we generate a game with a condition number under
    5000.
    """
    ambient_dim = randint(1, 10)
    K = NonnegativeOrthant(ambient_dim)
    e1 = [uniform(0.5, 10) for _ in range(K.dimension())]
    e2 = [uniform(0.5, 10) for _ in range(K.dimension())]
    L = random_matrix(K.dimension())
    G = SymmetricLinearGame(L, K, e1, e2)

    if G._condition() <= MAX_COND:
        return G
    else:
        return random_orthant_game()


def random_icecream_game():
    """
    Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
    random game over the ice-cream cone, and return the corresponding
    :class:`SymmetricLinearGame`.
    """
    # 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 _ in range(K.dimension() - 1)]
    e2 += [fudge_factor*uniform(0, 1) for _ in range(K.dimension() - 1)]
    L = random_matrix(K.dimension())
    G = SymmetricLinearGame(L, K, e1, e2)

    if G._condition() <= MAX_COND:
        return G
    else:
        return random_icecream_game()


# 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.

        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.
        """
        self.assertTrue(abs(first - second) < 2*2*RANDOM_MAX*options.ABS_TOL)


    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, game1):
        """
        Test that scaling ``L`` by a nonnegative number scales the value
        of the game by the same number.
        """
        value1 = game1.solution().game_value()

        alpha = uniform(0.1, 10)
        game2 = SymmetricLinearGame(alpha*game1._L.trans(),
                                    game1._K,
                                    game1._e1,
                                    game1._e2)

        while game2._condition() > MAX_COND:
            # Loop until the condition number of game2 doesn't suck.
            alpha = uniform(0.1, 10)
            game2 = SymmetricLinearGame(alpha*game1._L.trans(),
                                        game1._K,
                                        game1._e1,
                                        game1._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.
        """
        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, game1):
        """
        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 = game1.solution()
        value1 = soln1.game_value()
        x_bar = soln1.player1_optimal()
        y_bar = soln1.player2_optimal()
        tensor_prod = game1._e1*game1._e2.trans()

        # This is the "correct" representation of ``M``, but COLUMN
        # indexed...
        alpha = uniform(-10, 10)
        M = game1._L + alpha*tensor_prod

        # so we have to transpose it when we feed it to the constructor.
        game2 = SymmetricLinearGame(M.trans(), game1._K, game1._e1, game1._e2)
        while game2._condition() > MAX_COND:
            # Loop until the condition number of game2 doesn't suck.
            alpha = uniform(-10, 10)
            M = game1._L + alpha*tensor_prod
            game2 = SymmetricLinearGame(M.trans(),
                                        game1._K,
                                        game1._e1,
                                        game1._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.
        """
        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, game1):
        """
        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 = -game1._L.trans()

        # so we have to transpose it when we feed it to the constructor.
        # Note: the condition number of game2 should be comparable to game1.
        game2 = SymmetricLinearGame(M.trans(), game1._K, game1._e2, game1._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.
        """
        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_orthant_game()
        L = random_nonnegative_matrix(G._K.dimension())

        # Replace the totally-random ``L`` with the random nonnegative one.
        G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        while G._condition() > MAX_COND:
            # Try again until the condition number is satisfactory.
            G = random_orthant_game()
            L = random_nonnegative_matrix(G._K.dimension())
            G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        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)
        epsilon = 2*2*RANDOM_MAX*options.ABS_TOL
        if soln.game_value() > epsilon:
            # L should be positive stable
            positive_stable = all([eig > -options.ABS_TOL for eig in eigs])
            if not positive_stable:
                print(str(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])
            if not negative_stable:
                print(str(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_orthant_game()
        L = random_diagonal_matrix(G._K.dimension())

        # Replace the totally-random ``L`` with random Lyapunov-like one.
        G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        while G._condition() > MAX_COND:
            # Try again until the condition number is satisfactory.
            G = random_orthant_game()
            L = random_diagonal_matrix(G._K.dimension())
            G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        self.assert_lyapunov_works(G)


    def test_lyapunov_icecream(self):
        """
        Test that a Lyapunov game on the ice-cream cone works.
        """
        G = random_icecream_game()
        L = random_lyapunov_like_icecream(G._K.dimension())

        # Replace the totally-random ``L`` with random Lyapunov-like one.
        G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        while G._condition() > MAX_COND:
            # Try again until the condition number is satisfactory.
            G = random_orthant_game()
            L = random_lyapunov_like_icecream(G._K.dimension())
            G = SymmetricLinearGame(L, G._K, G._e1, G._e2)

        self.assert_lyapunov_works(G)