X-Git-Url: http://gitweb.michael.orlitzky.com/?p=dunshire.git;a=blobdiff_plain;f=dunshire%2Fgames.py;h=13c84f88b55824ca1f75630645f732a0e60f74a6;hp=6480d7d31153afcc419d331e0cd416a64253a188;hb=f3eb81258445fb9cc905f1e06dd7e6d00fbb76fc;hpb=2a59d8c4a2d7723a52de15e3d1f8ffce76bb948a diff --git a/dunshire/games.py b/dunshire/games.py index 6480d7d..13c84f8 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -422,7 +422,7 @@ class SymmetricLinearGame: r""" Return the matrix ``G`` used in our CVXOPT construction. - Thus matrix ``G``that appears on the left-hand side of ``Gx + s = h`` + Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h`` in the statement of the CVXOPT conelp program. .. warning:: @@ -460,13 +460,223 @@ class SymmetricLinearGame: 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. + def _c(self): + """ + Return the vector ``c`` used in our CVXOPT construction. + + The column vector ``c`` appears in the objective function + value ```` 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 ``K.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] + + + """ + 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*K.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] + + + """ + + return matrix([self._zero(), self._zero()]) + + def _b(self): + """ + 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. + + .. 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] + + + """ + return matrix([1], tc='d') + + + def _try_solution(self, tolerance): + """ + Solve this linear game within ``tolerance``, if possible. + + This private function is the one that does all of the actual + work for :meth:`solution`. This method accepts a ``tolerance``, + and what :meth:`solution` does is call this method twice with + two different tolerances. First it tries a strict tolerance, and + then it tries a looser one. + + .. warning:: + + If you try to be smart and precompute the matrices used by + this function (the ones passed to ``conelp``), then you're + going to shoot yourself in the foot. CVXOPT can and will + clobber some (but not all) of its input matrices. This isn't + performance sensitive, so play it safe. + + Parameters + ---------- + + tolerance : float + The absolute tolerance to pass to the CVXOPT solver. + + Returns + ------- + + :class:`Solution` + A :class:`Solution` object describing the game's value and + the optimal strategies of both players. + + Raises + ------ + GameUnsolvableException + If the game could not be solved (if an optimal solution to its + associated cone program was not found). + + PoorScalingException + If the game could not be solved because CVXOPT crashed while + trying to take the square root of a negative number. + + Examples + -------- + + This game can be solved easily, so the first attempt in + :meth:`solution` should succeed:: + + >>> from dunshire import * + >>> from dunshire.matrices import norm + >>> 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) + >>> s1 = SLG.solution() + >>> s2 = SLG._try_solution(options.ABS_TOL) + >>> abs(s1.game_value() - s2.game_value()) < ABS_TOL + True + >>> norm(s1.player1_optimal() - s2.player1_optimal()) < ABS_TOL + True + >>> norm(s1.player2_optimal() - s2.player2_optimal()) < ABS_TOL + True + + """ try: solvers.options['show_progress'] = options.VERBOSE solvers.options['abs_tol'] = tolerance - soln_dict = solvers.conelp(c,self._G(),h,C,self._A(),b) + soln_dict = solvers.conelp(self._c(), + self._G(), + self._h(), + self._C().cvxopt_dims(), + self._A(), + self._b()) except ValueError as e: if str(e) == 'math domain error': # Oops, CVXOPT tried to take the square root of a @@ -582,31 +792,15 @@ class SymmetricLinearGame: [0.187...] """ - # The cone "C" that appears in the statement of the CVXOPT - # conelp program. - C = CartesianProduct(self._K, self._K) - - # 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') - - # 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([self._zero(), self._zero()]) - - # The column vector "c" that appears in the objective function - # value in the statement of the CVXOPT conelp program. - c = matrix([-1, self._zero()]) - 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) + # First try with a stricter tolerance. Who knows, it might + # work. If it does, we prefer that solution. + return self._try_solution(options.ABS_TOL / 10) 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) + # Ok, that didn't work. Let's try it with the default + # tolerance, and whatever happens, happens. + return self._try_solution(tolerance = options.ABS_TOL) def condition(self):