- # 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)
+ .. 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):
+ 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.
+
+ .. 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():
+ 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.
+
+ 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 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())
+ 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.
+
+ 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())
+ 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 :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 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)