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::
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 ``<c,x>`` 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]
+ <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):
+ """
+ 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]
+ <BLANKLINE>
+
+ """
+
+ 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]
+ <BLANKLINE>
+
+ """
+ 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
[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 <c,x> 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):
projects / dunshire.git / blobdiff