Use private methods for the rest of the CVXOPT vectors/matrices.

[dunshire.git] / dunshire / games.py

diff --git a/dunshire/games.py b/dunshire/games.py
index 9610802e4ffd4108d2c244b2c36a9e44084427cd..13c84f88b55824ca1f75630645f732a0e60f74a6 100644 (file)
--- a/dunshire/games.py
+++ b/dunshire/games.py
@@ -8,12 +8,10 @@ knows how to solve a linear game.
 from cvxopt import matrix, printing, solvers
 from .cones import CartesianProduct
 from .errors import GameUnsolvableException, PoorScalingException
 from cvxopt import matrix, printing, solvers
 from .cones import CartesianProduct
 from .errors import GameUnsolvableException, PoorScalingException

-from .matrices import append_col, append_row, identity
+from .matrices import append_col, append_row, condition_number, identity

 from . import options
 
 printing.options['dformat'] = options.FLOAT_FORMAT
 from . import options
 
 printing.options['dformat'] = options.FLOAT_FORMAT

-solvers.options['show_progress'] = options.VERBOSE
-

 
 class Solution:
     """
 
 class Solution:
     """


@@ -221,7 +219,8 @@ class SymmetricLinearGame:
                [ 1],
           e2 = [ 1]
                [ 2]
                [ 1],
           e2 = [ 1]
                [ 2]

-               [ 3].
+               [ 3],
+          Condition((L, K, e1, e2)) = 31.834...

 
     Lists can (and probably should) be used for every argument::
 
 
     Lists can (and probably should) be used for every argument::
 


@@ -239,7 +238,8 @@ class SymmetricLinearGame:
           e1 = [ 1]
                [ 1],
           e2 = [ 1]
           e1 = [ 1]
                [ 1],
           e2 = [ 1]

-               [ 1].
+               [ 1],
+          Condition((L, K, e1, e2)) = 1.707...

 
     The points ``e1`` and ``e2`` can also be passed as some other
     enumerable type (of the correct length) without much harm, since
 
     The points ``e1`` and ``e2`` can also be passed as some other
     enumerable type (of the correct length) without much harm, since


@@ -261,7 +261,8 @@ class SymmetricLinearGame:
           e1 = [ 1]
                [ 1],
           e2 = [ 1]
           e1 = [ 1]
                [ 1],
           e2 = [ 1]

-               [ 1].
+               [ 1],
+          Condition((L, K, e1, e2)) = 1.707...

 
     However, ``L`` will always be intepreted as a list of rows, even
     if it is passed as a :class:`cvxopt.base.matrix` which is
 
     However, ``L`` will always be intepreted as a list of rows, even
     if it is passed as a :class:`cvxopt.base.matrix` which is


@@ -282,7 +283,8 @@ class SymmetricLinearGame:
           e1 = [ 1]
                [ 1],
           e2 = [ 1]
           e1 = [ 1]
                [ 1],
           e2 = [ 1]

-               [ 1].
+               [ 1],
+          Condition((L, K, e1, e2)) = 6.073...

         >>> L = cvxopt.matrix(L)
         >>> print(L)
         [ 1  3]
         >>> L = cvxopt.matrix(L)
         >>> print(L)
         [ 1  3]


@@ -297,7 +299,8 @@ class SymmetricLinearGame:
           e1 = [ 1]
                [ 1],
           e2 = [ 1]
           e1 = [ 1]
                [ 1],
           e2 = [ 1]

-               [ 1].
+               [ 1],
+          Condition((L, K, e1, e2)) = 6.073...

 
     """
     def __init__(self, L, K, e1, e2):
 
     """
     def __init__(self, L, K, e1, e2):


@@ -319,6 +322,8 @@ class SymmetricLinearGame:
         if not self._e2 in K:
             raise ValueError('the point e2 must lie in the interior of K')
 
         if not self._e2 in K:
             raise ValueError('the point e2 must lie in the interior of K')
 

+
+

     def __str__(self):
         """
         Return a string representation of this game.
     def __str__(self):
         """
         Return a string representation of this game.


@@ -327,110 +332,351 @@ class SymmetricLinearGame:
               '  L = {:s},\n' \
               '  K = {!s},\n' \
               '  e1 = {:s},\n' \
               '  L = {:s},\n' \
               '  K = {!s},\n' \
               '  e1 = {:s},\n' \

-              '  e2 = {:s}.'
+              '  e2 = {:s},\n' \
+              '  Condition((L, K, e1, e2)) = {:f}.'

         indented_L = '\n      '.join(str(self._L).splitlines())
         indented_e1 = '\n       '.join(str(self._e1).splitlines())
         indented_e2 = '\n       '.join(str(self._e2).splitlines())
         indented_L = '\n      '.join(str(self._L).splitlines())
         indented_e1 = '\n       '.join(str(self._e1).splitlines())
         indented_e2 = '\n       '.join(str(self._e2).splitlines())

-        return tpl.format(indented_L, str(self._K), indented_e1, indented_e2)

 
 

+        return tpl.format(indented_L,
+                          str(self._K),
+                          indented_e1,
+                          indented_e2,
+                          self.condition())

 
 

-    def solution(self):
+
+    def _zero(self):

         """
         """

-        Solve this linear game and return a :class:`Solution`.
+        Return a column of zeros that fits ``K``.
+
+        This is used in our CVXOPT construction.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.

 
         Returns
         -------
 
 
         Returns
         -------
 

-        :class:`Solution`
-            A :class:`Solution` object describing the game's value and
-            the optimal strategies of both players.
+        matrix
+            A ``K.dimension()``-by-``1`` column vector of zeros.

 
 

-        Raises
-        ------
-        GameUnsolvableException
-            If the game could not be solved (if an optimal solution to its
-            associated cone program was not found).
+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = identity(3)
+            >>> e1 = [1,1,1]
+            >>> e2 = e1
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG._zero())
+            [0.0000000]
+            [0.0000000]
+            [0.0000000]
+            <BLANKLINE>
+
+        """
+        return matrix(0, (self._K.dimension(), 1), tc='d')

 
 

-        PoorScalingException
-            If the game could not be solved because CVXOPT crashed while
-            trying to take the square root of a negative number.
+
+    def _A(self):
+        """
+        Return the matrix ``A`` used in our CVXOPT construction.
+
+        This matrix ``A``  appears on the right-hand side of ``Ax = b``
+        in the statement of the CVXOPT conelp program.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.
+
+        Returns
+        -------
+
+        matrix
+            A ``1``-by-``(1 + K.dimension())`` row vector. Its first
+            entry is zero, and the rest are the entries of ``e2``.

 
         Examples
         --------
 
 
         Examples
         --------
 

-        This example is computed in Gowda and Ravindran in the section
-        "The value of a Z-transformation"::
-

             >>> from dunshire import *
             >>> K = NonnegativeOrthant(3)
             >>> from dunshire import *
             >>> K = NonnegativeOrthant(3)

-            >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+            >>> L = [[1,1,1],[1,1,1],[1,1,1]]

             >>> e1 = [1,1,1]
             >>> e1 = [1,1,1]

+            >>> e2 = [1,2,3]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG._A())
+            [0.0000000 1.0000000 2.0000000 3.0000000]
+            <BLANKLINE>
+
+        """
+        return matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
+
+
+
+    def _G(self):
+        r"""
+        Return the matrix ``G`` used in our CVXOPT construction.
+
+        Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h``
+        in the statement of the CVXOPT conelp program.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.
+
+        Returns
+        -------
+
+        matrix
+            A ``2*K.dimension()``-by-``1 + K.dimension()`` matrix.
+
+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[4,5,6],[7,8,9],[10,11,12]]
+            >>> e1 = [1,2,3]

             >>> e2 = [1,1,1]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> e2 = [1,1,1]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)

-            >>> print(SLG.solution())
-            Game value: -6.1724138
-            Player 1 optimal:
-              [ 0.5517241]
-              [-0.0000000]
-              [ 0.4482759]
-            Player 2 optimal:
-              [0.4482759]
-              [0.0000000]
-              [0.5517241]
+            >>> print(SLG._G())
+            [  0.0000000  -1.0000000   0.0000000   0.0000000]
+            [  0.0000000   0.0000000  -1.0000000   0.0000000]
+            [  0.0000000   0.0000000   0.0000000  -1.0000000]
+            [  1.0000000  -4.0000000  -5.0000000  -6.0000000]
+            [  2.0000000  -7.0000000  -8.0000000  -9.0000000]
+            [  3.0000000 -10.0000000 -11.0000000 -12.0000000]
+            <BLANKLINE>

 
 

-        The value of the following game can be computed using the fact
-        that the identity is invertible::
+        """
+        I = identity(self._K.dimension())
+        return append_row(append_col(self._zero(), -I),
+                          append_col(self._e1, -self._L))
+
+
+    def _c(self):
+        """
+        Return the vector ``c`` used in our CVXOPT construction.
+
+        The column vector ``c``  appears in the objective function
+        value ``<c,x>`` in the statement of the CVXOPT conelp program.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.
+
+        Returns
+        -------
+
+        matrix
+            A ``K.dimension()``-by-``1`` column vector.
+
+        Examples
+        --------

 
             >>> from dunshire import *
             >>> K = NonnegativeOrthant(3)
 
             >>> from dunshire import *
             >>> K = NonnegativeOrthant(3)

-            >>> L = [[1,0,0],[0,1,0],[0,0,1]]
+            >>> L = [[4,5,6],[7,8,9],[10,11,12]]

             >>> e1 = [1,2,3]
             >>> e1 = [1,2,3]

-            >>> e2 = [4,5,6]
+            >>> e2 = [1,1,1]

             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)

-            >>> print(SLG.solution())
-            Game value: 0.0312500
-            Player 1 optimal:
-              [0.0312500]
-              [0.0625000]
-              [0.0937500]
-            Player 2 optimal:
-              [0.1250000]
-              [0.1562500]
-              [0.1875000]
+            >>> print(SLG._c())
+            [-1.0000000]
+            [ 0.0000000]
+            [ 0.0000000]
+            [ 0.0000000]
+            <BLANKLINE>
+
+        """
+        return matrix([-1, self._zero()])
+
+
+    def _C(self):
+        """
+        Return the cone ``C`` used in our CVXOPT construction.
+
+        The cone ``C`` is the cone over which the conelp program takes
+        place.
+
+        Returns
+        -------
+
+        CartesianProduct
+            The cartesian product of ``K`` with itself.
+
+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[4,5,6],[7,8,9],[10,11,12]]
+            >>> e1 = [1,2,3]
+            >>> e2 = [1,1,1]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG._C())
+            Cartesian product of dimension 6 with 2 factors:
+              * Nonnegative orthant in the real 3-space
+              * Nonnegative orthant in the real 3-space
+
+        """
+        return CartesianProduct(self._K, self._K)
+
+    def _h(self):
+        """
+        Return the ``h`` vector used in our CVXOPT construction.
+
+        The ``h`` vector appears on the right-hand side of :math:`Gx + s
+        = h` in the statement of the CVXOPT conelp program.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.
+
+        Returns
+        -------
+
+        matrix
+            A ``2*K.dimension()``-by-``1`` column vector of zeros.
+
+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[4,5,6],[7,8,9],[10,11,12]]
+            >>> e1 = [1,2,3]
+            >>> e2 = [1,1,1]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG._h())
+            [0.0000000]
+            [0.0000000]
+            [0.0000000]
+            [0.0000000]
+            [0.0000000]
+            [0.0000000]
+            <BLANKLINE>
+
+        """
+
+        return matrix([self._zero(), self._zero()])
+
+    def _b(self):
+        """
+        Return the ``b`` vector used in our CVXOPT construction.
+
+        The vector ``b`` appears on the right-hand side of :math:`Ax =
+        b` in the statement of the CVXOPT conelp program.
+
+        .. warning::
+
+            It is not safe to cache any of the matrices passed to
+            CVXOPT, because it can clobber them.
+
+        Returns
+        -------

 
 

+        matrix
+            A ``1``-by-``1`` matrix containing a single entry ``1``.
+
+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[4,5,6],[7,8,9],[10,11,12]]
+            >>> e1 = [1,2,3]
+            >>> e2 = [1,1,1]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG._b())
+            [1.0000000]
+            <BLANKLINE>
+
+        """
+        return matrix([1], tc='d')
+
+
+    def _try_solution(self, tolerance):

         """
         """

-        # The cone "C" that appears in the statement of the CVXOPT
-        # conelp program.
-        C = CartesianProduct(self._K, self._K)
+        Solve this linear game within ``tolerance``, if possible.

 
 

-        # The column vector "b" that appears on the right-hand side of
-        # Ax = b in the statement of the CVXOPT conelp program.
-        b = matrix([1], tc='d')
+        This private function is the one that does all of the actual
+        work for :meth:`solution`. This method accepts a ``tolerance``,
+        and what :meth:`solution` does is call this method twice with
+        two different tolerances. First it tries a strict tolerance, and
+        then it tries a looser one.

 
 

-        # A column of zeros that fits K.
-        zero = matrix(0, (self._K.dimension(), 1), tc='d')
+        .. warning::

 
 

-        # The column vector "h" that appears on the right-hand side of
-        # Gx + s = h in the statement of the CVXOPT conelp program.
-        h = matrix([zero, zero])
+            If you try to be smart and precompute the matrices used by
+            this function (the ones passed to ``conelp``), then you're
+            going to shoot yourself in the foot. CVXOPT can and will
+            clobber some (but not all) of its input matrices. This isn't
+            performance sensitive, so play it safe.

 
 

-        # The column vector "c" that appears in the objective function
-        # value <c,x> in the statement of the CVXOPT conelp program.
-        c = matrix([-1, zero])
+        Parameters
+        ----------

 
 

-        # The matrix "G" that appears on the left-hand side of Gx + s = h
-        # in the statement of the CVXOPT conelp program.
-        G = append_row(append_col(zero, -identity(self._K.dimension())),
-                       append_col(self._e1, -self._L))
+        tolerance : float
+            The absolute tolerance to pass to the CVXOPT solver.

 
 

-        # The matrix "A" that appears on the right-hand side of Ax = b
-        # in the statement of the CVXOPT conelp program.
-        A = matrix([0, self._e2], (1, self._K.dimension() + 1), 'd')
+        Returns
+        -------

 
 

-        # Actually solve the thing and obtain a dictionary describing
-        # what happened.
+        :class:`Solution`
+            A :class:`Solution` object describing the game's value and
+            the optimal strategies of both players.
+
+        Raises
+        ------
+        GameUnsolvableException
+            If the game could not be solved (if an optimal solution to its
+            associated cone program was not found).
+
+        PoorScalingException
+            If the game could not be solved because CVXOPT crashed while
+            trying to take the square root of a negative number.
+
+        Examples
+        --------
+
+        This game can be solved easily, so the first attempt in
+        :meth:`solution` should succeed::
+
+            >>> from dunshire import *
+            >>> from dunshire.matrices import norm
+            >>> from dunshire.options import ABS_TOL
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+            >>> e1 = [1,1,1]
+            >>> e2 = [1,1,1]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> s1 = SLG.solution()
+            >>> s2 = SLG._try_solution(options.ABS_TOL)
+            >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL
+            True
+            >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL
+            True
+            >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL
+            True
+
+        """

         try:
         try:

-            soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
+            solvers.options['show_progress'] = options.VERBOSE
+            solvers.options['abs_tol'] = tolerance
+            soln_dict = solvers.conelp(self._c(),
+                                       self._G(),
+                                       self._h(),
+                                       self._C().cvxopt_dims(),
+                                       self._A(),
+                                       self._b())

         except ValueError as e:
             if str(e) == 'math domain error':
                 # Oops, CVXOPT tried to take the square root of a
         except ValueError as e:
             if str(e) == 'math domain error':
                 # Oops, CVXOPT tried to take the square root of a


@@ -467,7 +713,13 @@ class SymmetricLinearGame:
             # objectives match (within a tolerance) and that the
             # primal/dual optimal solutions are within the cone (to a
             # tolerance as well).
             # objectives match (within a tolerance) and that the
             # primal/dual optimal solutions are within the cone (to a
             # tolerance as well).

-            if abs(p1_value - p2_value) > options.ABS_TOL:
+            #
+            # The fudge factor of two is basically unjustified, but
+            # makes intuitive sense when you imagine that the primal
+            # value could be under the true optimal by ``ABS_TOL``
+            # and the dual value could be over by the same amount.
+            #
+            if abs(p1_value - p2_value) > tolerance:

                 raise GameUnsolvableException(self, soln_dict)
             if (p1_optimal not in self._K) or (p2_optimal not in self._K):
                 raise GameUnsolvableException(self, soln_dict)
                 raise GameUnsolvableException(self, soln_dict)
             if (p1_optimal not in self._K) or (p2_optimal not in self._K):
                 raise GameUnsolvableException(self, soln_dict)


@@ -475,6 +727,119 @@ class SymmetricLinearGame:
         return Solution(p1_value, p1_optimal, p2_optimal)
 
 
         return Solution(p1_value, p1_optimal, p2_optimal)
 
 

+    def solution(self):
+        """
+        Solve this linear game and return a :class:`Solution`.
+
+        Returns
+        -------
+
+        :class:`Solution`
+            A :class:`Solution` object describing the game's value and
+            the optimal strategies of both players.
+
+        Raises
+        ------
+        GameUnsolvableException
+            If the game could not be solved (if an optimal solution to its
+            associated cone program was not found).
+
+        PoorScalingException
+            If the game could not be solved because CVXOPT crashed while
+            trying to take the square root of a negative number.
+
+        Examples
+        --------
+
+        This example is computed in Gowda and Ravindran in the section
+        "The value of a Z-transformation"::
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+            >>> e1 = [1,1,1]
+            >>> e2 = [1,1,1]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG.solution())
+            Game value: -6.1724138
+            Player 1 optimal:
+              [ 0.551...]
+              [-0.000...]
+              [ 0.448...]
+            Player 2 optimal:
+              [0.448...]
+              [0.000...]
+              [0.551...]
+
+        The value of the following game can be computed using the fact
+        that the identity is invertible::
+
+            >>> from dunshire import *
+            >>> K = NonnegativeOrthant(3)
+            >>> L = [[1,0,0],[0,1,0],[0,0,1]]
+            >>> e1 = [1,2,3]
+            >>> e2 = [4,5,6]
+            >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+            >>> print(SLG.solution())
+            Game value: 0.0312500
+            Player 1 optimal:
+              [0.031...]
+              [0.062...]
+              [0.093...]
+            Player 2 optimal:
+              [0.125...]
+              [0.156...]
+              [0.187...]
+
+        """
+        try:
+            # First try with a stricter tolerance. Who knows, it might
+            # work. If it does, we prefer that solution.
+            return self._try_solution(options.ABS_TOL / 10)
+
+        except (PoorScalingException, GameUnsolvableException):
+            # Ok, that didn't work. Let's try it with the default
+            # tolerance, and whatever happens, happens.
+            return self._try_solution(tolerance = options.ABS_TOL)
+
+
+    def condition(self):
+        r"""
+        Return the condition number of this game.
+
+        In the CVXOPT construction of this game, two matrices ``G`` and
+        ``A`` appear. When those matrices are nasty, numerical problems
+        can show up. We define the condition number of this game to be
+        the average of the condition numbers of ``G`` and ``A`` in the
+        CVXOPT construction. If the condition number of this game is
+        high, then you can expect numerical difficulty (such as
+        :class:`PoorScalingException`).
+
+        Returns
+        -------
+
+        float
+            A real number greater than or equal to one that measures how
+            bad this game is numerically.
+
+        Examples
+        --------
+
+        >>> from dunshire import *
+        >>> K = NonnegativeOrthant(1)
+        >>> L = [[1]]
+        >>> e1 = [1]
+        >>> e2 = e1
+        >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+        >>> actual = SLG.condition()
+        >>> expected = 1.8090169943749477
+        >>> abs(actual - expected) < options.ABS_TOL
+        True
+
+        """
+        return (condition_number(self._G()) + condition_number(self._A()))/2
+
+

     def dual(self):
         r"""
         Return the dual game to this game.
     def dual(self):
         r"""
         Return the dual game to this game.


@@ -504,7 +869,8 @@ class SymmetricLinearGame:
                    [ 3],
               e2 = [ 1]
                    [ 1]
                    [ 3],
               e2 = [ 1]
                    [ 1]

-                   [ 1].
+                   [ 1],
+              Condition((L, K, e1, e2)) = 44.476...

 
         """
         # We pass ``self._L`` right back into the constructor, because
 
         """
         # We pass ``self._L`` right back into the constructor, because