X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=dunshire%2Fgames.py;h=a0c52279869510090f9d051a92b479bfefa3fbdd;hb=687820b6a899842773f79bc1c830458b65de2ad3;hp=cfb62a33d8a2666828323019729af0f1b5ab99d7;hpb=709cd03fff79e76f9fd78ba70711ea2694607e05;p=dunshire.git diff --git a/dunshire/games.py b/dunshire/games.py index cfb62a3..a0c5227 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -9,9 +9,9 @@ from .cones import CartesianProduct from .errors import GameUnsolvableException, PoorScalingException from .matrices import (append_col, append_row, condition_number, identity, inner_product, norm, specnorm) -from . import options +from .options import ABS_TOL, FLOAT_FORMAT, DEBUG_FLOAT_FORMAT -printing.options['dformat'] = options.FLOAT_FORMAT +printing.options['dformat'] = FLOAT_FORMAT class Solution: @@ -731,7 +731,7 @@ class SymmetricLinearGame: return CartesianProduct(self._K, self._K) def _h(self): - """ + r""" Return the ``h`` vector used in our CVXOPT construction. The ``h`` vector appears on the right-hand side of :math:`Gx + s @@ -773,7 +773,7 @@ class SymmetricLinearGame: @staticmethod def b(): - """ + r""" Return the ``b`` vector used in our CVXOPT construction. The vector ``b`` appears on the right-hand side of :math:`Ax = @@ -848,18 +848,81 @@ class SymmetricLinearGame: def _L_specnorm(self): """ - Compute the spectral norm of ``L`` and cache it. + Compute the spectral norm of :meth:`L` and cache it. + + The spectral norm of the matrix :meth:`L` is used in a few + places. Since it can be expensive to compute, we want to cache + its value. That is not possible in :func:`specnorm`, which lies + outside of a class, so this is the place to do it. + + Returns + ------- + + float + A nonnegative real number; the largest singular value of + the matrix :meth:`L`. + """ 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." + + 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 + ``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 + + .. math:: + + \left\lVert L \right\rVert_{2} + \left( \left\lVert \bar{x} \right\rVert + + \left\lVert \bar{y} \right\rVert + \right), + + where :math:`\bar{x}` and :math:`\bar{y}` are optimal solutions + for players one and two respectively. This scaling factor is not + formally justified, but attempting anything smaller leads to + test failures. + + .. warning:: + + Optimal solutions are not unique, so the scaling factor + obtained from ``solution`` may not work when comparing other + solutions. + + Parameters + ---------- + + solution : Solution + A solution of this game, used to obtain the norms of the + optimal strategies. + + Returns + ------- + + float + A scaling factor to be multiplied by ``ABS_TOL`` when + making comparisons involving solutions of this game. + + """ norm_p1_opt = norm(solution.player1_optimal()) norm_p2_opt = norm(solution.player2_optimal()) scale = self._L_specnorm()*(norm_p1_opt + norm_p2_opt) + + # Don't return anything smaller than 1... we can't go below + # out "minimum tolerance." return max(1, scale) @@ -977,6 +1040,44 @@ class SymmetricLinearGame: [2.506...] [0.000...] + This is another one that was difficult numerically, and caused + trouble even after we fixed the first two:: + + >>> from dunshire import * + >>> L = [[57.22233908627052301199, 41.70631373437460354126], + ... [83.04512571985074487202, 57.82581810406928468637]] + >>> K = NonnegativeOrthant(2) + >>> e1 = [7.31887017043399268346, 0.89744171905822367474] + >>> e2 = [0.11099824781179848388, 6.12564670639315345113] + >>> SLG = SymmetricLinearGame(L,K,e1,e2) + >>> print(SLG.solution()) + Game value: 70.437... + Player 1 optimal: + [9.009...] + [0.000...] + Player 2 optimal: + [0.136...] + [0.000...] + + And finally, here's one that returns an "optimal" solution, but + whose primal/dual objective function values are far apart:: + + >>> from dunshire import * + >>> L = [[ 6.49260076597376212248, -0.60528030227678542019], + ... [ 2.59896077096751731972, -0.97685530240286766457]] + >>> K = IceCream(2) + >>> e1 = [1, 0.43749513972645248661] + >>> e2 = [1, 0.46008379832200291260] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG.solution()) + Game value: 11.596... + Player 1 optimal: + [ 1.852...] + [-1.852...] + Player 2 optimal: + [ 1.777...] + [-1.777...] + """ try: opts = {'show_progress': False} @@ -994,7 +1095,7 @@ class SymmetricLinearGame: # 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 + printing.options['dformat'] = DEBUG_FLOAT_FORMAT raise PoorScalingException(self) else: raise error @@ -1019,7 +1120,7 @@ class SymmetricLinearGame: # 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 + printing.options['dformat'] = DEBUG_FLOAT_FORMAT raise GameUnsolvableException(self, soln_dict) # For the game value, we could use any of: @@ -1047,14 +1148,14 @@ class SymmetricLinearGame: # 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 + if abs(p1_value - p2_value) > self.tolerance_scale(soln)*ABS_TOL: + printing.options['dformat'] = 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 + printing.options['dformat'] = DEBUG_FLOAT_FORMAT raise GameUnsolvableException(self, soln_dict) return soln @@ -1088,10 +1189,8 @@ class SymmetricLinearGame: >>> e1 = [1] >>> e2 = e1 >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> actual = SLG.condition() - >>> expected = 1.8090169943749477 - >>> abs(actual - expected) < options.ABS_TOL - True + >>> SLG.condition() + 1.809... """ return (condition_number(self._G()) + condition_number(self.A()))/2