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
-solvers.options['show_progress'] = options.VERBOSE
-
class Solution:
"""
[ 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')
+
+
def __str__(self):
"""
Return a string representation of this game.
' 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())
- 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 _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 ``K.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._K.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 + K.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._K.dimension() + 1), 'd')
+
+
+
+ def _G(self):
+ r"""
+ Return the matrix ``G`` used in our CVXOPT construction.
+
+ Thus matrix ``G``that 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)
+ >>> 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>
+
+ """
+ I = identity(self._K.dimension())
+ return append_row(append_col(self._zero(), -I),
+ append_col(self._e1, -self._L))
+
+
+ def _try_solution(self, c, h, C, b, tolerance):
+ # Actually solve the thing and obtain a dictionary describing
+ # what happened.
+ try:
+ solvers.options['show_progress'] = options.VERBOSE
+ solvers.options['abs_tol'] = tolerance
+ soln_dict = solvers.conelp(c,self._G(),h,C,self._A(),b)
+ except ValueError as e:
+ if str(e) == '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.
+ raise PoorScalingException(self)
+ else:
+ raise e
+
+ # The optimal strategies are named ``p`` and ``q`` in the
+ # background documentation, and we need to extract them from
+ # the CVXOPT ``x`` and ``z`` variables. The objective values
+ # :math:`nu` and :math:`omega` can also be found in the CVXOPT
+ # ``x`` and ``y`` variables; however, they're stored
+ # conveniently as separate entries in the solution dictionary.
+ 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():]
+
+ # 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).
+ if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
+ 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).
+ #
+ # 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)
+
+ return Solution(p1_value, p1_optimal, p2_optimal)
def solution(self):
>>> print(SLG.solution())
Game value: -6.1724138
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::
>>> print(SLG.solution())
Game value: 0.0312500
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
# 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')
-
# 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])
+ h = matrix([self._zero(), self._zero()])
# 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])
+ c = matrix([-1, self._zero()])
- # 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))
+ try:
+ # First try with a stricter tolerance. Who knows, it might work.
+ return self._try_solution(c, h, C.cvxopt_dims(), b,
+ tolerance = options.ABS_TOL / 10)
- # 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')
+ except (PoorScalingException, GameUnsolvableException):
+ # Ok, that didn't work. Let's try it with the default.
+ return self._try_solution(c, h, C.cvxopt_dims(), b,
+ tolerance = options.ABS_TOL)
- # 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':
- # 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.
- raise PoorScalingException(self)
- else:
- raise e
- # The optimal strategies are named ``p`` and ``q`` in the
- # background documentation, and we need to extract them from
- # the CVXOPT ``x`` and ``z`` variables. The objective values
- # :math:`nu` and :math:`omega` can also be found in the CVXOPT
- # ``x`` and ``y`` variables; however, they're stored
- # conveniently as separate entries in the solution dictionary.
- 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():]
+ def condition(self):
+ r"""
+ Return the condition number of this game.
- # 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).
- if soln_dict['status'] in ['primal infeasible', 'dual infeasible']:
- 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)
+ 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`).
- return Solution(p1_value, p1_optimal, p2_optimal)
+ 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