Use "2" as a numerically-better factor in player[12]_start().

[dunshire.git] / dunshire / games.py

diff --git a/dunshire/games.py b/dunshire/games.py
index 3ed89bb3f2f70b30d0313cbe5a578e4f53e47421..f9877b334cfa3bcf2d60c6269ecbf4340de24eb1 100644 (file)
--- a/dunshire/games.py
+++ b/dunshire/games.py
@@ -4,8 +4,6 @@ Symmetric linear games and their solutions.
 This module contains the main :class:`SymmetricLinearGame` class that
 knows how to solve a linear game.
 """
 This module contains the main :class:`SymmetricLinearGame` class that
 knows how to solve a linear game.
 """

-from math import sqrt
-

 from cvxopt import matrix, printing, solvers
 from .cones import CartesianProduct, IceCream, NonnegativeOrthant
 from .errors import GameUnsolvableException, PoorScalingException
 from cvxopt import matrix, printing, solvers
 from .cones import CartesianProduct, IceCream, NonnegativeOrthant
 from .errors import GameUnsolvableException, PoorScalingException


@@ -24,7 +22,7 @@ class Solution:
     --------
 
         >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
     --------
 
         >>> print(Solution(10, matrix([1,2]), matrix([3,4])))

-        Game value: 10.0000000
+        Game value: 10.000...

         Player 1 optimal:
           [ 1]
           [ 2]
         Player 1 optimal:
           [ 1]
           [ 2]


@@ -833,9 +831,10 @@ class SymmetricLinearGame:
             # 45-45-90 triangle and the shortest distance to the
             # outside of the cone should be 1/sqrt(2) of that.
             # It works in R^2, so it works everywhere, right?
             # 45-45-90 triangle and the shortest distance to the
             # outside of the cone should be 1/sqrt(2) of that.
             # It works in R^2, so it works everywhere, right?

+            # We use "2" because it's better numerically than sqrt(2).

             height = self.e1()[0]
             radius = norm(self.e1()[1:])
             height = self.e1()[0]
             radius = norm(self.e1()[1:])

-            dist = (height - radius) / sqrt(2)
+            dist = (height - radius) / 2

         else:
             raise NotImplementedError
 
         else:
             raise NotImplementedError
 


@@ -846,6 +845,38 @@ class SymmetricLinearGame:
         return {'x': x, 's': s}
 
 
         return {'x': x, 's': s}
 
 

+    def player2_start(self):
+        """
+        Return a feasible starting point for player two.
+        """
+        q = self.e1() / (norm(self.e1()) ** 2)
+
+        # Compute the distance from p to the outside of K.
+        if isinstance(self.K(), NonnegativeOrthant):
+            # How far is it to a wall?
+            dist = min(list(self.e2()))
+        elif isinstance(self.K(), IceCream):
+            # How far is it to the boundary of the ball that defines
+            # the ice-cream cone at a given height? Now draw a
+            # 45-45-90 triangle and the shortest distance to the
+            # outside of the cone should be 1/sqrt(2) of that.
+            # It works in R^2, so it works everywhere, right?
+            # We use "2" because it's better numerically than sqrt(2).
+            height = self.e2()[0]
+            radius = norm(self.e2()[1:])
+            dist = (height - radius) / 2
+        else:
+            raise NotImplementedError
+
+        omega = specnorm(self.L())/(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 solution(self):
         """
         Solve this linear game and return a :class:`Solution`.
     def solution(self):
         """
         Solve this linear game and return a :class:`Solution`.


@@ -880,11 +911,11 @@ class SymmetricLinearGame:
             >>> e2 = [1,1,1]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> print(SLG.solution())
             >>> e2 = [1,1,1]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> print(SLG.solution())

-            Game value: -6.1724138
+            Game value: -6.172...

             Player 1 optimal:
             Player 1 optimal:

-              [ 0.551...]
-              [-0.000...]
-              [ 0.448...]
+              [0.551...]
+              [0.000...]
+              [0.448...]

             Player 2 optimal:
               [0.448...]
               [0.000...]
             Player 2 optimal:
               [0.448...]
               [0.000...]


@@ -900,7 +931,7 @@ class SymmetricLinearGame:
             >>> e2 = [4,5,6]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> print(SLG.solution())
             >>> e2 = [4,5,6]
             >>> SLG = SymmetricLinearGame(L, K, e1, e2)
             >>> print(SLG.solution())

-            Game value: 0.0312500
+            Game value: 0.031...

             Player 1 optimal:
               [0.031...]
               [0.062...]
             Player 1 optimal:
               [0.031...]
               [0.062...]


@@ -936,8 +967,8 @@ class SymmetricLinearGame:
             >>> print(SLG.solution())
             Game value: 18.767...
             Player 1 optimal:
             >>> print(SLG.solution())
             Game value: 18.767...
             Player 1 optimal:

-              [-0.000...]
-              [ 9.766...]
+              [0.000...]
+              [9.766...]

             Player 2 optimal:
               [1.047...]
               [0.000...]
             Player 2 optimal:
               [1.047...]
               [0.000...]


@@ -954,8 +985,8 @@ class SymmetricLinearGame:
             >>> print(SLG.solution())
             Game value: 24.614...
             Player 1 optimal:
             >>> print(SLG.solution())
             Game value: 24.614...
             Player 1 optimal:

-              [ 6.371...]
-              [-0.000...]
+              [6.371...]
+              [0.000...]

             Player 2 optimal:
               [2.506...]
               [0.000...]
             Player 2 optimal:
               [2.506...]
               [0.000...]


@@ -969,6 +1000,7 @@ class SymmetricLinearGame:
                                        self.C().cvxopt_dims(),
                                        self.A(),
                                        self.b(),
                                        self.C().cvxopt_dims(),
                                        self.A(),
                                        self.b(),

+                                       primalstart=self.player1_start(),

                                        options=opts)
         except ValueError as error:
             if str(error) == 'math domain error':
                                        options=opts)
         except ValueError as error:
             if str(error) == 'math domain error':