----------
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 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.
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]
>>> 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
"""
def A(self):
- """
+ r"""
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::
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
--------
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::
def c(self):
- """
+ r"""
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::
-------
matrix
- A ``self.dimension()``-by-``1`` column vector.
+ A :meth:`dimension`-by-``1`` column vector.
Examples
--------
"""
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
-------
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::
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
-------
dict
- A dictionary with two keys, 'x' and 's', which contain the
- vectors of the same name in the CVXOPT primal problem
- formulation.
+ 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
-------
dict
- A dictionary with two keys, 'y' and 'z', which contain the
- vectors of the same name in the CVXOPT dual problem
- formulation.
+ 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
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())
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.
- 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::
-------
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.
+ 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())
Returns
-------
- :class:`Solution`
+ Solution
A :class:`Solution` object describing the game's value and
the optimal strategies of both players.
# 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
- # 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
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
-------