From f3eb81258445fb9cc905f1e06dd7e6d00fbb76fc Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Thu, 3 Nov 2016 16:58:17 -0400 Subject: [PATCH] Use private methods for the rest of the CVXOPT vectors/matrices. We already had private methods for _zero(), _A(), and _G(). Now we have them for the rest of the matrices and vectors as well. This improves consistency, and maybe more importantly prevents people from ever thinking it's safe to pass the same matrix to CVXOPT twice. --- dunshire/games.py | 248 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 221 insertions(+), 27 deletions(-) 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): -- 2.43.2