This module contains the main :class:`SymmetricLinearGame` class that
knows how to solve a linear game.
"""
-
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,
+ inner_product, norm, specnorm)
from . import options
printing.options['dformat'] = options.FLOAT_FORMAT
-solvers.options['show_progress'] = options.VERBOSE
class Solution:
--------
>>> print(Solution(10, matrix([1,2]), matrix([3,4])))
- Game value: 10.0000000
+ Game value: 10.000...
Player 1 optimal:
[ 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::
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
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
e1 = [ 1]
[ 1],
e2 = [ 1]
- [ 1].
+ [ 1],
+ Condition((L, K, e1, e2)) = 6.073...
>>> L = cvxopt.matrix(L)
>>> print(L)
[ 1 3]
e1 = [ 1]
[ 1],
e2 = [ 1]
- [ 1].
+ [ 1],
+ Condition((L, K, e1, e2)) = 6.073...
"""
def __init__(self, L, K, e1, e2):
if not self._e2 in K:
raise ValueError('the point e2 must lie in the interior of K')
+ # Initial value of cached method.
+ self._L_specnorm_value = None
+
+
def __str__(self):
"""
Return a string representation of this game.
' L = {:s},\n' \
' K = {!s},\n' \
' e1 = {:s},\n' \
- ' e2 = {:s}.'
- 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)
+ ' 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())
+
+ return tpl.format(indented_L,
+ str(self.K()),
+ indented_e1,
+ indented_e2,
+ self.condition())
+
+
+ def L(self):
+ """
+ Return the matrix ``L`` passed to the constructor.
+
+ Returns
+ -------
+
+ matrix
+ The matrix that defines this game's :meth:`payoff` operator.
+
+ Examples
+ --------
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(3)
+ >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+ >>> e1 = [1,1,1]
+ >>> e2 = [1,2,3]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.L())
+ [ 1 -5 -15]
+ [ -1 2 -3]
+ [-12 -15 1]
+ <BLANKLINE>
+
+ """
+ return self._L
+
+
+ def K(self):
+ """
+ Return the cone over which this game is played.
+
+ Returns
+ -------
+
+ SymmetricCone
+ The :class:`SymmetricCone` over which this game is played.
+
+ Examples
+ --------
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(3)
+ >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+ >>> e1 = [1,1,1]
+ >>> e2 = [1,2,3]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.K())
+ Nonnegative orthant in the real 3-space
+
+ """
+ return self._K
+
+
+ def e1(self):
+ """
+ Return player one's interior point.
+
+ Returns
+ -------
+
+ matrix
+ The point interior to :meth:`K` affiliated with player one.
+
+ Examples
+ --------
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(3)
+ >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+ >>> e1 = [1,1,1]
+ >>> e2 = [1,2,3]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.e1())
+ [ 1]
+ [ 1]
+ [ 1]
+ <BLANKLINE>
+
+ """
+ return self._e1
+
+
+ def e2(self):
+ """
+ Return player two's interior point.
+
+ Returns
+ -------
+
+ matrix
+ The point interior to :meth:`K` affiliated with player one.
+
+ Examples
+ --------
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(3)
+ >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
+ >>> e1 = [1,1,1]
+ >>> e2 = [1,2,3]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.e2())
+ [ 1]
+ [ 2]
+ [ 3]
+ <BLANKLINE>
+
+ """
+ return self._e2
+
+
+ def payoff(self, strategy1, strategy2):
+ r"""
+ Return the payoff associated with ``strategy1`` and ``strategy2``.
+
+ 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
+ :meth:`L`. This method computes the payoff given the two
+ players' strategies.
+
+ Parameters
+ ----------
+
+ strategy1 : matrix
+ Player one's strategy.
+
+ strategy2 : matrix
+ Player two's strategy.
+
+ Returns
+ -------
+
+ float
+ The payoff for the game when player one plays ``strategy1``
+ and player two plays ``strategy2``.
+
+ Examples
+ --------
+
+ The value of the game should be the payoff at the optimal
+ 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]
+ >>> e2 = [1,1,1]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> 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
+ True
+
+ """
+ return inner_product(self.L()*strategy1, strategy2)
+
+
+ def dimension(self):
+ """
+ Return the dimension of this game.
+
+ The dimension of a game is not needed for the theory, but it is
+ useful for the implementation. We define the dimension of a game
+ to be the dimension of its underlying cone. Or what is the same,
+ the dimension of the space from which the strategies are chosen.
+
+ Returns
+ -------
+
+ int
+ The dimension of the cone :meth:`K`, or of the space where
+ this game is played.
+
+ Examples
+ --------
+
+ The dimension of a game over the nonnegative quadrant in the
+ plane should be two (the dimension of the plane)::
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(2)
+ >>> L = [[1,-5],[-1,2]]
+ >>> e1 = [1,1]
+ >>> e2 = [1,4]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> SLG.dimension()
+ 2
+
+ """
+ return self.K().dimension()
+
+
+ def _zero(self):
+ """
+ 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
+ -------
+
+ matrix
+ A ``self.dimension()``-by-``1`` column vector of zeros.
+
+ 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.dimension(), 1), tc='d')
+
+
+ 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 + self.dimension())`` row vector. Its first
+ entry is zero, and the rest are the entries of ``e2``.
+
+ Examples
+ --------
+
+ >>> from dunshire import *
+ >>> K = NonnegativeOrthant(3)
+ >>> L = [[1,1,1],[1,1,1],[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.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*self.dimension()``-by-``(1 + self.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)
+ >>> 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>
+
+ """
+ identity_matrix = identity(self.dimension())
+ return append_row(append_col(self._zero(), -identity_matrix),
+ 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 ``self.dimension()``-by-``1`` column vector.
+
+ 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())
+ [-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*self.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()])
+
+
+ @staticmethod
+ def b():
+ """
+ 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.
+
+ This method is static because the dimensions and entries of
+ ``b`` are known beforehand, and don't depend on any other
+ properties of the game.
+
+ .. 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 player1_start(self):
+ """
+ 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.
+ """
+ p = self.e2() / (norm(self.e2()) ** 2)
+ dist = self.K().ball_radius(self.e1())
+ nu = - self._L_specnorm()/(dist*norm(self.e2()))
+ x = matrix([nu, p], (self.dimension() + 1, 1))
+ s = - self._G()*x
+
+ return {'x': x, 's': s}
+
+
+ def player2_start(self):
+ """
+ Return a feasible starting point for player two.
+ """
+ q = self.e1() / (norm(self.e1()) ** 2)
+ dist = self.K().ball_radius(self.e2())
+ omega = self._L_specnorm()/(dist*norm(self.e1()))
+ y = matrix([omega])
+ z2 = q
+ z1 = y*self.e2() - self.L().trans()*z2
+ z = matrix([z1, z2], (self.dimension()*2, 1))
+
+ return {'y': y, 'z': z}
+
+
+ def _L_specnorm(self):
+ """
+ Compute the spectral norm of ``L`` and cache it.
+ """
+ if self._L_specnorm_value is None:
+ self._L_specnorm_value = specnorm(self.L())
+ return self._L_specnorm_value
+
+ def epsilon_scale(self, solution):
+ # Don't return anything smaller than 1... we can't go below
+ # out "minimum tolerance."
+ norm_p1_opt = norm(solution.player1_optimal())
+ norm_p2_opt = norm(solution.player2_optimal())
+ scale = self._L_specnorm()*(norm_p1_opt + norm_p2_opt)
+ return max(1, scale)
def solution(self):
>>> e2 = [1,1,1]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
- Game value: -6.1724138
+ Game value: -6.172...
Player 1 optimal:
- [ 0.5517241]
- [-0.0000000]
- [ 0.4482759]
+ [0.551...]
+ [0.000...]
+ [0.448...]
Player 2 optimal:
- [0.4482759]
- [0.0000000]
- [0.5517241]
+ [0.448...]
+ [0.000...]
+ [0.551...]
The value of the following game can be computed using the fact
that the identity is invertible::
>>> e2 = [4,5,6]
>>> SLG = SymmetricLinearGame(L, K, e1, e2)
>>> print(SLG.solution())
- Game value: 0.0312500
+ Game value: 0.031...
Player 1 optimal:
- [0.0312500]
- [0.0625000]
- [0.0937500]
+ [0.031...]
+ [0.062...]
+ [0.093...]
Player 2 optimal:
- [0.1250000]
- [0.1562500]
- [0.1875000]
+ [0.125...]
+ [0.156...]
+ [0.187...]
- """
- # The cone "C" that appears in the statement of the CVXOPT
- # conelp program.
- C = CartesianProduct(self._K, self._K)
+ This is another Gowda/Ravindran example that is supposed to have
+ a negative game value::
- # 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')
-
- # A column of zeros that fits K.
- zero = matrix(0, (self._K.dimension(), 1), tc='d')
+ >>> from dunshire import *
+ >>> from dunshire.options import ABS_TOL
+ >>> L = [[1, -2], [-2, 1]]
+ >>> K = NonnegativeOrthant(2)
+ >>> e1 = [1, 1]
+ >>> e2 = e1
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> SLG.solution().game_value() < -ABS_TOL
+ True
- # 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])
+ The following two games are problematic numerically, but we
+ should be able to solve them::
- # 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])
+ >>> from dunshire import *
+ >>> L = [[-0.95237953890954685221, 1.83474556206462535712],
+ ... [ 1.30481749924621448500, 1.65278664543326403447]]
+ >>> K = NonnegativeOrthant(2)
+ >>> e1 = [0.95477167524644313001, 0.63270781756540095397]
+ >>> e2 = [0.39633793037154141370, 0.10239281495640320530]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.solution())
+ Game value: 18.767...
+ Player 1 optimal:
+ [0.000...]
+ [9.766...]
+ Player 2 optimal:
+ [1.047...]
+ [0.000...]
- # 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))
+ ::
- # 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')
+ >>> from dunshire import *
+ >>> L = [[1.54159395026049472754, 2.21344728574316684799],
+ ... [1.33147433507846657541, 1.17913616272988108769]]
+ >>> K = NonnegativeOrthant(2)
+ >>> e1 = [0.39903040089404784307, 0.12377403622479113410]
+ >>> e2 = [0.15695181142215544612, 0.85527381344651265405]
+ >>> SLG = SymmetricLinearGame(L, K, e1, e2)
+ >>> print(SLG.solution())
+ Game value: 24.614...
+ Player 1 optimal:
+ [6.371...]
+ [0.000...]
+ Player 2 optimal:
+ [2.506...]
+ [0.000...]
- # Actually solve the thing and obtain a dictionary describing
- # what happened.
+ """
try:
- soln_dict = solvers.conelp(c, G, h, C.cvxopt_dims(), A, b)
- except ValueError as e:
- if str(e) == 'math domain error':
+ opts = {'show_progress': False}
+ soln_dict = solvers.conelp(self._c(),
+ self._G(),
+ self._h(),
+ self.C().cvxopt_dims(),
+ self.A(),
+ self.b(),
+ primalstart=self.player1_start(),
+ dualstart=self.player2_start(),
+ options=opts)
+ except ValueError as error:
+ if str(error) == 'math domain error':
# Oops, CVXOPT tried to take the square root of a
# negative number. Report some details about the game
# rather than just the underlying CVXOPT crash.
+ printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
raise PoorScalingException(self)
else:
- raise e
+ raise error
# The optimal strategies are named ``p`` and ``q`` in the
# background documentation, and we need to extract them from
p1_value = -soln_dict['primal objective']
p2_value = -soln_dict['dual objective']
p1_optimal = soln_dict['x'][1:]
- p2_optimal = soln_dict['z'][self._K.dimension():]
+ p2_optimal = soln_dict['z'][self.dimension():]
# The "status" field contains "optimal" if everything went
# according to plan. Other possible values are "primal
# infeasible", "dual infeasible", "unknown", all of which mean
- # we didn't get a solution. The "infeasible" ones are the
- # worst, since they indicate that CVXOPT is convinced the
- # problem is infeasible (and that cannot happen).
+ # we didn't get a solution.
+ #
+ # The "infeasible" ones are the worst, since they indicate
+ # that CVXOPT is convinced the problem is infeasible (and that
+ # cannot happen).
if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
+ printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
+ raise GameUnsolvableException(self, soln_dict)
+
+ # For the game value, we could use any of:
+ #
+ # * p1_value
+ # * p2_value
+ # * (p1_value + p2_value)/2
+ # * the game payoff
+ #
+ # We want the game value to be the payoff, however, so it
+ # makes the most sense to just use that, even if it means we
+ # can't test the fact that p1_value/p2_value are close to the
+ # payoff.
+ payoff = self.payoff(p1_optimal, p2_optimal)
+ soln = Solution(payoff, p1_optimal, p2_optimal)
+
+ # The "optimal" and "unknown" results, we actually treat the
+ # 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.
+ #
+ # 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.
+ #
+ if abs(p1_value - p2_value) > self.epsilon_scale(soln)*options.ABS_TOL:
+ printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
+ raise GameUnsolvableException(self, soln_dict)
+
+ # And we also check that the points it gave us belong to the
+ # cone, just in case...
+ if (p1_optimal not in self._K) or (p2_optimal not in self._K):
+ printing.options['dformat'] = options.DEBUG_FLOAT_FORMAT
raise GameUnsolvableException(self, soln_dict)
- elif soln_dict['status'] == 'unknown':
- # When we get a status of "unknown", we may still be able
- # to salvage a solution out of the returned
- # dictionary. Often this is the result of numerical
- # difficulty and we can simply check that the primal/dual
- # 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:
- raise GameUnsolvableException(self, soln_dict)
- if (p1_optimal not in self._K) or (p2_optimal not in self._K):
- raise GameUnsolvableException(self, soln_dict)
-
- return Solution(p1_value, p1_optimal, p2_optimal)
+
+ return soln
+
+
+ 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):
[ 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
# it will be transposed there. And keep in mind that ``self._K``
# is its own dual.
- return SymmetricLinearGame(self._L,
- self._K,
- self._e2,
- self._e1)
+ return SymmetricLinearGame(self.L(),
+ self.K(),
+ self.e2(),
+ self.e1())