A bunch more doc fixes.

[dunshire.git] / dunshire / games.py

diff --git a/dunshire/games.py b/dunshire/games.py
index 75f5329bb973e05d9070609fcb77e5eeba80fdee..ea7a64f6b8e6451a808b464494c11e9be9f0de78 100644 (file)
--- a/dunshire/games.py
+++ b/dunshire/games.py
@@ -179,11 +179,15 @@ class SymmetricLinearGame:
     ----------
 
     L : list of list of float
     ----------
 
     L : list of list of float

-        A matrix represented as a list of ROWS. This representation
-        agrees with (for example) SageMath and NumPy, but not with CVXOPT
-        (whose matrix constructor accepts a list of columns).
-
-    K : :class:`SymmetricCone`
+        A matrix represented as a list of **rows**. This representation
+        agrees with (for example) `SageMath <http://www.sagemath.org/>`_
+        and `NumPy <http://www.numpy.org/>`_, but not with CVXOPT (whose
+        matrix constructor accepts a list of columns). In reality, ``L``
+        can be any iterable type of the correct length; however, you
+        should be extremely wary of the way we interpret anything other
+        than a list of rows.
+
+    K : dunshire.cones.SymmetricCone

         The symmetric cone instance over which the game is played.
 
     e1 : iterable float
         The symmetric cone instance over which the game is played.
 
     e1 : iterable float


@@ -461,8 +465,8 @@ class SymmetricLinearGame:
         The payoff operator takes pairs of strategies to a real
         number. For example, if player one's strategy is :math:`x` and
         player two's strategy is :math:`y`, then the associated payoff
         The payoff operator takes pairs of strategies to a real
         number. For example, if player one's strategy is :math:`x` and
         player two's strategy is :math:`y`, then the associated payoff

-        is :math:`\left\langle L\left(x\right),y \right\rangle` \in
-        \mathbb{R}. Here, :math:`L` denotes the same linear operator as
+        is :math:`\left\langle L\left(x\right),y \right\rangle \in
+        \mathbb{R}`. Here, :math:`L` denotes the same linear operator as

         :meth:`L`. This method computes the payoff given the two
         players' strategies.
 
         :meth:`L`. This method computes the payoff given the two
         players' strategies.
 


@@ -489,7 +493,6 @@ class SymmetricLinearGame:
         strategies::
 
             >>> from dunshire import *
         strategies::
 
             >>> from dunshire import *

-            >>> from dunshire.options import ABS_TOL

             >>> K = NonnegativeOrthant(3)
             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
             >>> e1 = [1,1,1]
             >>> K = NonnegativeOrthant(3)
             >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
             >>> e1 = [1,1,1]


@@ -498,7 +501,7 @@ class SymmetricLinearGame:
             >>> soln = SLG.solution()
             >>> x_bar = soln.player1_optimal()
             >>> y_bar = soln.player2_optimal()
             >>> soln = SLG.solution()
             >>> x_bar = soln.player1_optimal()
             >>> y_bar = soln.player2_optimal()

-            >>> abs(SLG.payoff(x_bar, y_bar) - soln.game_value()) < ABS_TOL
+            >>> SLG.payoff(x_bar, y_bar) == soln.game_value()

             True
 
         """
             True
 
         """


@@ -577,11 +580,12 @@ class SymmetricLinearGame:
 
 
     def A(self):
 
 
     def A(self):

-        """
+        r"""

         Return the matrix ``A`` used in our CVXOPT construction.
 
         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.
+        This matrix :math:`A` appears on the right-hand side of
+        :math:`Ax = b` in the `statement of the CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.

 
         .. warning::
 
 
         .. warning::
 


@@ -593,7 +597,7 @@ class SymmetricLinearGame:
 
         matrix
             A ``1``-by-``(1 + self.dimension())`` row vector. Its first
 
         matrix
             A ``1``-by-``(1 + self.dimension())`` row vector. Its first

-            entry is zero, and the rest are the entries of ``e2``.
+            entry is zero, and the rest are the entries of :meth:`e2`.

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


@@ -617,8 +621,9 @@ class SymmetricLinearGame:
         r"""
         Return the matrix ``G`` used in our CVXOPT construction.
 
         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.
+        Thus matrix :math:`G` appears on the left-hand side of :math:`Gx
+        + s = h` in the `statement of the CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.

 
         .. warning::
 
 
         .. warning::
 


@@ -656,11 +661,13 @@ class SymmetricLinearGame:
 
 
     def c(self):
 
 
     def c(self):

-        """
+        r"""

         Return the vector ``c`` used in our CVXOPT construction.
 
         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.
+        The column vector :math:`c` appears in the objective function
+        value :math:`\left\langle c,x \right\rangle` in the `statement
+        of the CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.

 
         .. warning::
 
 
         .. warning::
 


@@ -671,7 +678,7 @@ class SymmetricLinearGame:
         -------
 
         matrix
         -------
 
         matrix

-            A ``self.dimension()``-by-``1`` column vector.
+            A :meth:`dimension`-by-``1`` column vector.

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


@@ -697,8 +704,9 @@ class SymmetricLinearGame:
         """
         Return the cone ``C`` used in our CVXOPT construction.
 
         """
         Return the cone ``C`` used in our CVXOPT construction.
 

-        The cone ``C`` is the cone over which the conelp program takes
-        place.
+        This is the cone over which the `CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_
+        takes place.

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


@@ -727,8 +735,9 @@ class SymmetricLinearGame:
         r"""
         Return the ``h`` vector used in our CVXOPT construction.
 
         r"""
         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.
+        The :math:`h` vector appears on the right-hand side of :math:`Gx
+        + s = h` in the `statement of the CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.

 
         .. warning::
 
 
         .. warning::
 


@@ -769,8 +778,9 @@ class SymmetricLinearGame:
         r"""
         Return the ``b`` vector used in our CVXOPT construction.
 
         r"""
         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.
+        The vector :math:`b` appears on the right-hand side of :math:`Ax
+        = b` in the `statement of the CVXOPT conelp program
+        <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.

 
         This method is static because the dimensions and entries of
         ``b`` are known beforehand, and don't depend on any other
 
         This method is static because the dimensions and entries of
         ``b`` are known beforehand, and don't depend on any other


@@ -809,11 +819,26 @@ class SymmetricLinearGame:
         Return a feasible starting point for player one.
 
         This starting point is for the CVXOPT formulation and not for
         Return a feasible starting point for player one.
 
         This starting point is for the CVXOPT formulation and not for

-        the original game. The basic premise is that if you normalize
-        :meth:`e2`, then you get a point in :meth:`K` that makes a unit
-        inner product with :meth:`e2`. We then get to choose the primal
-        objective function value such that the constraint involving
-        :meth:`L` is satisfied.
+        the original game. The basic premise is that if you scale
+        :meth:`e2` by the reciprocal of its squared norm, then you get a
+        point in :meth:`K` that makes a unit inner product with
+        :meth:`e2`. We then get to choose the primal objective function
+        value such that the constraint involving :meth:`L` is satisfied.
+
+        Returns
+        -------
+
+        dict
+            A dictionary with two keys, ``'x'`` and ``'s'``, which
+            contain the vectors of the same name in the CVXOPT primal
+            problem formulation.
+
+            The vector ``x`` consists of the primal objective function
+            value concatenated with the strategy (for player one) that
+            achieves it. The vector ``s`` is essentially a dummy
+            variable, and is computed from the equality constraing in
+            the CVXOPT primal problem.
+

         """
         p = self.e2() / (norm(self.e2()) ** 2)
         dist = self.K().ball_radius(self.e1())
         """
         p = self.e2() / (norm(self.e2()) ** 2)
         dist = self.K().ball_radius(self.e1())


@@ -827,6 +852,29 @@ class SymmetricLinearGame:
     def player2_start(self):
         """
         Return a feasible starting point for player two.
     def player2_start(self):
         """
         Return a feasible starting point for player two.

+
+        This starting point is for the CVXOPT formulation and not for
+        the original game. The basic premise is that if you scale
+        :meth:`e1` by the reciprocal of its squared norm, then you get a
+        point in :meth:`K` that makes a unit inner product with
+        :meth:`e1`. We then get to choose the dual objective function
+        value such that the constraint involving :meth:`L` is satisfied.
+
+        Returns
+        -------
+
+        dict
+            A dictionary with two keys, ``'y'`` and ``'z'``, which
+            contain the vectors of the same name in the CVXOPT dual
+            problem formulation.
+
+            The ``1``-by-``1`` vector ``y`` consists of the dual
+            objective function value. The last :meth:`dimension` entries
+            of the vector ``z`` contain the strategy (for player two)
+            that achieves it. The remaining entries of ``z`` are
+            essentially dummy variables, computed from the equality
+            constraint in the CVXOPT dual problem.
+

         """
         q = self.e1() / (norm(self.e1()) ** 2)
         dist = self.K().ball_radius(self.e2())
         """
         q = self.e1() / (norm(self.e1()) ** 2)
         dist = self.K().ball_radius(self.e2())


@@ -855,6 +903,19 @@ class SymmetricLinearGame:
             A nonnegative real number; the largest singular value of
             the matrix :meth:`L`.
 
             A nonnegative real number; the largest singular value of
             the matrix :meth:`L`.
 

+        Examples
+        --------
+
+            >>> from dunshire import *
+            >>> from dunshire.matrices import specnorm
+            >>> L = [[1,2],[3,4]]
+            >>> K = NonnegativeOrthant(2)
+            >>> e1 = [1,1]
+            >>> e2 = e1
+            >>> SLG = SymmetricLinearGame(L,K,e1,e2)
+            >>> specnorm(SLG.L()) == SLG._L_specnorm()
+            True
+

         """
         if self._L_specnorm_value is None:
             self._L_specnorm_value = specnorm(self.L())
         """
         if self._L_specnorm_value is None:
             self._L_specnorm_value = specnorm(self.L())


@@ -863,19 +924,21 @@ class SymmetricLinearGame:
 
     def tolerance_scale(self, solution):
         r"""
 
     def tolerance_scale(self, solution):
         r"""

-        Return a scaling factor that should be applied to ``ABS_TOL``
-        for this game.
-
-        When performing certain comparisons, the default tolernace
-        ``ABS_TOL`` may not be appropriate. For example, if we expect
-        ``x`` and ``y`` to be within ``ABS_TOL`` of each other, than the
-        inner product of ``L*x`` and ``y`` can be as far apart as the
-        spectral norm of ``L`` times the sum of the norms of ``x`` and
+
+        Return a scaling factor that should be applied to
+        :const:`dunshire.options.ABS_TOL` for this game.
+
+        When performing certain comparisons, the default tolerance
+        :const:`dunshire.options.ABS_TOL` may not be appropriate. For
+        example, if we expect ``x`` and ``y`` to be within
+        :const:`dunshire.options.ABS_TOL` of each other, than the inner
+        product of ``L*x`` and ``y`` can be as far apart as the spectral
+        norm of ``L`` times the sum of the norms of ``x`` and

         ``y``. Such a comparison is made in :meth:`solution`, and in
         many of our unit tests.
 
         ``y``. Such a comparison is made in :meth:`solution`, and in
         many of our unit tests.
 

-        The returned scaling factor found from the inner product mentioned
-        above is
+        The returned scaling factor found from the inner product
+        mentioned above is

 
         .. math::
 
 
         .. math::
 


@@ -906,9 +969,27 @@ class SymmetricLinearGame:
         -------
 
         float
         -------
 
         float

-            A scaling factor to be multiplied by ``ABS_TOL`` when
+            A scaling factor to be multiplied by
+            :const:`dunshire.options.ABS_TOL` when

             making comparisons involving solutions of this game.
 
             making comparisons involving solutions of this game.
 

+        Examples
+        --------
+
+        The spectral norm of ``L`` in this case is around ``5.464``, and
+        the optimal strategies both have norm one, so we expect the
+        tolerance scale to be somewhere around ``2 * 5.464``, or
+        ``10.929``::
+
+            >>> from dunshire import *
+            >>> L = [[1,2],[3,4]]
+            >>> K = NonnegativeOrthant(2)
+            >>> e1 = [1,1]
+            >>> e2 = e1
+            >>> SLG = SymmetricLinearGame(L,K,e1,e2)
+            >>> SLG.tolerance_scale(SLG.solution())
+            10.929...
+

         """
         norm_p1_opt = norm(solution.player1_optimal())
         norm_p2_opt = norm(solution.player2_optimal())
         """
         norm_p1_opt = norm(solution.player1_optimal())
         norm_p2_opt = norm(solution.player2_optimal())


@@ -926,7 +1007,7 @@ class SymmetricLinearGame:
         Returns
         -------
 
         Returns
         -------
 

-        :class:`Solution`
+        Solution

             A :class:`Solution` object describing the game's value and
             the optimal strategies of both players.
 
             A :class:`Solution` object describing the game's value and
             the optimal strategies of both players.
 


@@ -1134,12 +1215,14 @@ class SymmetricLinearGame:
         # same. Even if CVXOPT bails out due to numerical difficulty,
         # it will have some candidate points in mind. If those
         # candidates are good enough, we take them. We do the same
         # same. Even if CVXOPT bails out due to numerical difficulty,
         # it will have some candidate points in mind. If those
         # candidates are good enough, we take them. We do the same

-        # check (perhaps pointlessly so) for "optimal" results.
+        # check for "optimal" results.

         #
         # First we check that the primal/dual objective values are
         #
         # First we check that the primal/dual objective values are

-        # close enough (one could be low by ABS_TOL, the other high by
-        # it) because otherwise CVXOPT might return "unknown" and give
-        # us two points in the cone that are nowhere near optimal.
+        # close enough because otherwise CVXOPT might return "unknown"
+        # and give us two points in the cone that are nowhere near
+        # optimal. And in fact, we need to ensure that they're close
+        # for "optimal" results, too, because we need to know how
+        # lenient to be in our testing.

         #
         if abs(p1_value - p2_value) > self.tolerance_scale(soln)*ABS_TOL:
             printing.options['dformat'] = DEBUG_FLOAT_FORMAT
         #
         if abs(p1_value - p2_value) > self.tolerance_scale(soln)*ABS_TOL:
             printing.options['dformat'] = DEBUG_FLOAT_FORMAT


@@ -1163,8 +1246,12 @@ class SymmetricLinearGame:
         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
         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`).
+        high, you can problems like :class:`PoorScalingException`.
+
+        Random testing shows that a condition number of around ``125``
+        is about the best that we can solve reliably. However, the
+        failures are intermittent, and you may get lucky with an
+        ill-conditioned game.

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