X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=dunshire%2Fgames.py;h=19b2f5b34276275258e4ccd0bcd9b9b143e7608c;hb=fca2dba7c55f8eb55462c8376d56266792701de1;hp=951c7f4bc16088e4b82cc91cb90eb41c9e90db5f;hpb=37d44f04834d61eb3c089b52e4ca7cdd75253520;p=dunshire.git diff --git a/dunshire/games.py b/dunshire/games.py index 951c7f4..19b2f5b 100644 --- a/dunshire/games.py +++ b/dunshire/games.py @@ -577,11 +577,11 @@ class SymmetricLinearGame: def A(self): - """ + r""" 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. + This matrix :math`A` appears on the right-hand side of :math:`Ax + = b` in the statement of the CVXOPT conelp program. .. warning:: @@ -613,12 +613,12 @@ class SymmetricLinearGame: - def _G(self): + def G(self): r""" Return the matrix ``G`` used in our CVXOPT construction. - Thus matrix ``G`` appears on the left-hand side of ``Gx + s = h`` - in the statement of the CVXOPT conelp program. + Thus matrix :math:`G` appears on the left-hand side of :math:`Gx + + s = h` in the statement of the CVXOPT conelp program. .. warning:: @@ -640,7 +640,7 @@ class SymmetricLinearGame: >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._G()) + >>> 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] @@ -655,12 +655,13 @@ class SymmetricLinearGame: append_col(self.e1(), -self.L())) - def _c(self): - """ + def c(self): + r""" 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. + The column vector :math:`c` appears in the objective function + value :math:`\left\langle c,x \right\rangle` in the statement of + the CVXOPT conelp program. .. warning:: @@ -682,7 +683,7 @@ class SymmetricLinearGame: >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._c()) + >>> print(SLG.c()) [-1.0000000] [ 0.0000000] [ 0.0000000] @@ -697,8 +698,7 @@ class SymmetricLinearGame: """ Return the cone ``C`` used in our CVXOPT construction. - The cone ``C`` is the cone over which the conelp program takes - place. + This is the cone over which the conelp program takes place. Returns ------- @@ -723,11 +723,11 @@ class SymmetricLinearGame: """ return CartesianProduct(self._K, self._K) - def _h(self): + 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 + The :math:`h` vector appears on the right-hand side of :math:`Gx + s = h` in the statement of the CVXOPT conelp program. .. warning:: @@ -750,7 +750,7 @@ class SymmetricLinearGame: >>> e1 = [1,2,3] >>> e2 = [1,1,1] >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG._h()) + >>> print(SLG.h()) [0.0000000] [0.0000000] [0.0000000] @@ -809,17 +809,32 @@ class SymmetricLinearGame: 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 normalize - :meth:`e2`, 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. + 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 + s = - self.G()*x return {'x': x, 's': s} @@ -827,6 +842,29 @@ class SymmetricLinearGame: 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()) @@ -855,6 +893,19 @@ class SymmetricLinearGame: A nonnegative real number; the largest singular value of the matrix :meth:`L`. + Examples + -------- + + >>> from dunshire import * + >>> from dunshire.matrices import specnorm + >>> L = [[1,2],[3,4]] + >>> K = NonnegativeOrthant(2) + >>> e1 = [1,1] + >>> e2 = e1 + >>> SLG = SymmetricLinearGame(L,K,e1,e2) + >>> specnorm(SLG.L()) == SLG._L_specnorm() + True + """ if self._L_specnorm_value is None: self._L_specnorm_value = specnorm(self.L()) @@ -909,6 +960,23 @@ class SymmetricLinearGame: A scaling factor to be multiplied by ``ABS_TOL`` when making comparisons involving solutions of this game. + Examples + -------- + + The spectral norm of ``L`` in this case is around ``5.464``, and + the optimal strategies both have norm one, so we expect the + tolerance scale to be somewhere around ``2 * 5.464``, or + ``10.929``:: + + >>> from dunshire import * + >>> L = [[1,2],[3,4]] + >>> K = NonnegativeOrthant(2) + >>> e1 = [1,1] + >>> e2 = e1 + >>> SLG = SymmetricLinearGame(L,K,e1,e2) + >>> SLG.tolerance_scale(SLG.solution()) + 10.929... + """ norm_p1_opt = norm(solution.player1_optimal()) norm_p2_opt = norm(solution.player2_optimal()) @@ -1074,9 +1142,9 @@ class SymmetricLinearGame: """ try: opts = {'show_progress': False} - soln_dict = solvers.conelp(self._c(), - self._G(), - self._h(), + soln_dict = solvers.conelp(self.c(), + self.G(), + self.h(), self.C().cvxopt_dims(), self.A(), self.b(), @@ -1134,12 +1202,14 @@ class SymmetricLinearGame: # same. Even if CVXOPT bails out due to numerical difficulty, # it will have some candidate points in mind. If those # candidates are good enough, we take them. We do the same - # check (perhaps pointlessly so) for "optimal" results. + # check for "optimal" results. # # First we check that the primal/dual objective values are - # close enough (one could be low by ABS_TOL, the other high by - # it) because otherwise CVXOPT might return "unknown" and give - # us two points in the cone that are nowhere near optimal. + # close enough because otherwise CVXOPT might return "unknown" + # and give us two points in the cone that are nowhere near + # optimal. And in fact, we need to ensure that they're close + # for "optimal" results, too, because we need to know how + # lenient to be in our testing. # if abs(p1_value - p2_value) > self.tolerance_scale(soln)*ABS_TOL: printing.options['dformat'] = DEBUG_FLOAT_FORMAT @@ -1186,7 +1256,7 @@ class SymmetricLinearGame: 1.809... """ - return (condition_number(self._G()) + condition_number(self.A()))/2 + return (condition_number(self.G()) + condition_number(self.A()))/2 def dual(self):