]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/games.py
2 Symmetric linear games and their solutions.
4 This module contains the main :class:`SymmetricLinearGame` class that
5 knows how to solve a linear game.
8 # These few are used only for tests.
10 from random
import randint
, uniform
11 from unittest
import TestCase
13 # These are mostly actually needed.
14 from cvxopt
import matrix
, printing
, solvers
15 from .cones
import CartesianProduct
, IceCream
, NonnegativeOrthant
16 from .errors
import GameUnsolvableException
17 from .matrices
import (append_col
, append_row
, eigenvalues_re
, identity
,
21 printing
.options
['dformat'] = options
.FLOAT_FORMAT
22 solvers
.options
['show_progress'] = options
.VERBOSE
27 A representation of the solution of a linear game. It should contain
28 the value of the game, and both players' strategies.
33 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
34 Game value: 10.0000000
43 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
45 Create a new Solution object from a game value and two optimal
46 strategies for the players.
48 self
._game
_value
= game_value
49 self
._player
1_optimal
= p1_optimal
50 self
._player
2_optimal
= p2_optimal
54 Return a string describing the solution of a linear game.
56 The three data that are described are,
58 * The value of the game.
59 * The optimal strategy of player one.
60 * The optimal strategy of player two.
62 The two optimal strategy vectors are indented by two spaces.
64 tpl
= 'Game value: {:.7f}\n' \
65 'Player 1 optimal:{:s}\n' \
66 'Player 2 optimal:{:s}'
68 p1_str
= '\n{!s}'.format(self
.player1_optimal())
69 p1_str
= '\n '.join(p1_str
.splitlines())
70 p2_str
= '\n{!s}'.format(self
.player2_optimal())
71 p2_str
= '\n '.join(p2_str
.splitlines())
73 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
78 Return the game value for this solution.
83 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
88 return self
._game
_value
91 def player1_optimal(self
):
93 Return player one's optimal strategy in this solution.
98 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
99 >>> print(s.player1_optimal())
105 return self
._player
1_optimal
108 def player2_optimal(self
):
110 Return player two's optimal strategy in this solution.
115 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
116 >>> print(s.player2_optimal())
122 return self
._player
2_optimal
125 class SymmetricLinearGame
:
127 A representation of a symmetric linear game.
129 The data for a symmetric linear game are,
131 * A "payoff" operator ``L``.
132 * A symmetric cone ``K``.
133 * Two points ``e1`` and ``e2`` in the interior of ``K``.
135 The ambient space is assumed to be the span of ``K``.
137 With those data understood, the game is played as follows. Players
138 one and two choose points :math:`x` and :math:`y` respectively, from
139 their respective strategy sets,
146 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
151 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
155 Afterwards, a "payout" is computed as :math:`\left\langle
156 L\left(x\right), y \right\rangle` and is paid to player one out of
157 player two's pocket. The game is therefore zero sum, and we suppose
158 that player one would like to guarantee himself the largest minimum
159 payout possible. That is, player one wishes to,
164 &\underset{y \in \Delta_{2}}{\min}\left(
165 \left\langle L\left(x\right), y \right\rangle
167 \text{subject to } & x \in \Delta_{1}.
170 Player two has the simultaneous goal to,
175 &\underset{x \in \Delta_{1}}{\max}\left(
176 \left\langle L\left(x\right), y \right\rangle
178 \text{subject to } & y \in \Delta_{2}.
181 These goals obviously conflict (the game is zero sum), but an
182 existence theorem guarantees at least one optimal min-max solution
183 from which neither player would like to deviate. This class is
184 able to find such a solution.
189 L : list of list of float
190 A matrix represented as a list of ROWS. This representation
191 agrees with (for example) SageMath and NumPy, but not with CVXOPT
192 (whose matrix constructor accepts a list of columns).
194 K : :class:`SymmetricCone`
195 The symmetric cone instance over which the game is played.
198 The interior point of ``K`` belonging to player one; it
199 can be of any iterable type having the correct length.
202 The interior point of ``K`` belonging to player two; it
203 can be of any enumerable type having the correct length.
209 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
214 >>> K = NonnegativeOrthant(3)
215 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
218 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
220 The linear game (L, K, e1, e2) where
224 K = Nonnegative orthant in the real 3-space,
232 Lists can (and probably should) be used for every argument::
234 >>> K = NonnegativeOrthant(2)
235 >>> L = [[1,0],[0,1]]
238 >>> G = SymmetricLinearGame(L, K, e1, e2)
240 The linear game (L, K, e1, e2) where
243 K = Nonnegative orthant in the real 2-space,
249 The points ``e1`` and ``e2`` can also be passed as some other
250 enumerable type (of the correct length) without much harm, since
251 there is no row/column ambiguity::
255 >>> K = NonnegativeOrthant(2)
256 >>> L = [[1,0],[0,1]]
257 >>> e1 = cvxopt.matrix([1,1])
258 >>> e2 = numpy.matrix([1,1])
259 >>> G = SymmetricLinearGame(L, K, e1, e2)
261 The linear game (L, K, e1, e2) where
264 K = Nonnegative orthant in the real 2-space,
270 However, ``L`` will always be intepreted as a list of rows, even
271 if it is passed as a :class:`cvxopt.base.matrix` which is
272 otherwise indexed by columns::
275 >>> K = NonnegativeOrthant(2)
276 >>> L = [[1,2],[3,4]]
279 >>> G = SymmetricLinearGame(L, K, e1, e2)
281 The linear game (L, K, e1, e2) where
284 K = Nonnegative orthant in the real 2-space,
289 >>> L = cvxopt.matrix(L)
294 >>> G = SymmetricLinearGame(L, K, e1, e2)
296 The linear game (L, K, e1, e2) where
299 K = Nonnegative orthant in the real 2-space,
306 def __init__(self
, L
, K
, e1
, e2
):
308 Create a new SymmetricLinearGame object.
311 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
312 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
314 # Our input ``L`` is indexed by rows but CVXOPT matrices are
315 # indexed by columns, so we need to transpose the input before
316 # feeding it to CVXOPT.
317 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
319 if not self
._e
1 in K
:
320 raise ValueError('the point e1 must lie in the interior of K')
322 if not self
._e
2 in K
:
323 raise ValueError('the point e2 must lie in the interior of K')
327 Return a string representation of this game.
329 tpl
= 'The linear game (L, K, e1, e2) where\n' \
334 indented_L
= '\n '.join(str(self
._L).splitlines())
335 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
336 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
337 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
342 Solve this linear game and return a :class:`Solution`.
348 A :class:`Solution` object describing the game's value and
349 the optimal strategies of both players.
353 GameUnsolvableException
354 If the game could not be solved (if an optimal solution to its
355 associated cone program was not found).
360 This example is computed in Gowda and Ravindran in the section
361 "The value of a Z-transformation"::
363 >>> K = NonnegativeOrthant(3)
364 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
367 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
368 >>> print(SLG.solution())
369 Game value: -6.1724138
379 The value of the following game can be computed using the fact
380 that the identity is invertible::
382 >>> K = NonnegativeOrthant(3)
383 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
386 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
387 >>> print(SLG.solution())
388 Game value: 0.0312500
399 # The cone "C" that appears in the statement of the CVXOPT
401 C
= CartesianProduct(self
._K
, self
._K
)
403 # The column vector "b" that appears on the right-hand side of
404 # Ax = b in the statement of the CVXOPT conelp program.
405 b
= matrix([1], tc
='d')
407 # A column of zeros that fits K.
408 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
410 # The column vector "h" that appears on the right-hand side of
411 # Gx + s = h in the statement of the CVXOPT conelp program.
412 h
= matrix([zero
, zero
])
414 # The column vector "c" that appears in the objective function
415 # value <c,x> in the statement of the CVXOPT conelp program.
416 c
= matrix([-1, zero
])
418 # The matrix "G" that appears on the left-hand side of Gx + s = h
419 # in the statement of the CVXOPT conelp program.
420 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
421 append_col(self
._e
1, -self
._L))
423 # The matrix "A" that appears on the right-hand side of Ax = b
424 # in the statement of the CVXOPT conelp program.
425 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
427 # Actually solve the thing and obtain a dictionary describing
429 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
431 p1_value
= -soln_dict
['primal objective']
432 p2_value
= -soln_dict
['dual objective']
433 p1_optimal
= soln_dict
['x'][1:]
434 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
436 # The "status" field contains "optimal" if everything went
437 # according to plan. Other possible values are "primal
438 # infeasible", "dual infeasible", "unknown", all of which mean
439 # we didn't get a solution. The "infeasible" ones are the
440 # worst, since they indicate that CVXOPT is convinced the
441 # problem is infeasible (and that cannot happen).
442 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
443 raise GameUnsolvableException(soln_dict
)
444 elif soln_dict
['status'] == 'unknown':
445 # When we get a status of "unknown", we may still be able
446 # to salvage a solution out of the returned
447 # dictionary. Often this is the result of numerical
448 # difficulty and we can simply check that the primal/dual
449 # objectives match (within a tolerance) and that the
450 # primal/dual optimal solutions are within the cone (to a
451 # tolerance as well).
452 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
453 raise GameUnsolvableException(soln_dict
)
454 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
455 raise GameUnsolvableException(soln_dict
)
457 return Solution(p1_value
, p1_optimal
, p2_optimal
)
462 Return the dual game to this game.
464 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
465 then its dual is :math:`G^{*} =
466 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
467 is symmetric, :math:`K^{*} = K`.
472 >>> K = NonnegativeOrthant(3)
473 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
476 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
477 >>> print(SLG.dual())
478 The linear game (L, K, e1, e2) where
482 K = Nonnegative orthant in the real 3-space,
491 # We pass ``self._L`` right back into the constructor, because
492 # it will be transposed there. And keep in mind that ``self._K``
494 return SymmetricLinearGame(self
._L,
501 def _random_matrix(dims
):
503 Generate a random square (``dims``-by-``dims``) matrix. This is used
504 only by the :class:`SymmetricLinearGameTest` class.
506 return matrix([[uniform(-10, 10) for i
in range(dims
)]
507 for j
in range(dims
)])
509 def _random_nonnegative_matrix(dims
):
511 Generate a random square (``dims``-by-``dims``) matrix with
512 nonnegative entries. This is used only by the
513 :class:`SymmetricLinearGameTest` class.
515 L
= _random_matrix(dims
)
516 return matrix([abs(entry
) for entry
in L
], (dims
, dims
))
518 def _random_diagonal_matrix(dims
):
520 Generate a random square (``dims``-by-``dims``) matrix with nonzero
521 entries only on the diagonal. This is used only by the
522 :class:`SymmetricLinearGameTest` class.
524 return matrix([[uniform(-10, 10)*int(i
== j
) for i
in range(dims
)]
525 for j
in range(dims
)])
528 def _random_skew_symmetric_matrix(dims
):
530 Generate a random skew-symmetrix (``dims``-by-``dims``) matrix.
535 >>> A = _random_skew_symmetric_matrix(randint(1, 10))
536 >>> norm(A + A.trans()) < options.ABS_TOL
540 strict_ut
= [[uniform(-10, 10)*int(i
< j
) for i
in range(dims
)]
541 for j
in range(dims
)]
543 strict_ut
= matrix(strict_ut
, (dims
, dims
))
544 return strict_ut
- strict_ut
.trans()
547 def _random_lyapunov_like_icecream(dims
):
549 Generate a random Lyapunov-like matrix over the ice-cream cone in
552 a
= matrix([uniform(-10, 10)], (1, 1))
553 b
= matrix([uniform(-10, 10) for idx
in range(dims
-1)], (dims
-1, 1))
554 D
= _random_skew_symmetric_matrix(dims
-1) + a
*identity(dims
-1)
555 row1
= append_col(a
, b
.trans())
556 row2
= append_col(b
, D
)
557 return append_row(row1
, row2
)
560 def _random_orthant_params():
562 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
563 random game over the nonnegative orthant. This is only used by
564 the :class:`SymmetricLinearGameTest` class.
566 ambient_dim
= randint(1, 10)
567 K
= NonnegativeOrthant(ambient_dim
)
568 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
569 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
570 L
= _random_matrix(K
.dimension())
571 return (L
, K
, matrix(e1
), matrix(e2
))
574 def _random_icecream_params():
576 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
577 random game over the ice cream cone. This is only used by
578 the :class:`SymmetricLinearGameTest` class.
580 # Use a minimum dimension of two to avoid divide-by-zero in
581 # the fudge factor we make up later.
582 ambient_dim
= randint(2, 10)
583 K
= IceCream(ambient_dim
)
584 e1
= [1] # Set the "height" of e1 to one
585 e2
= [1] # And the same for e2
587 # If we choose the rest of the components of e1,e2 randomly
588 # between 0 and 1, then the largest the squared norm of the
589 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
590 # need to make it less than one (the height of the cone) so
591 # that the whole thing is in the cone. The norm of the
592 # non-height part is sqrt(dim(K) - 1), and we can divide by
594 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
595 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
596 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
597 L
= _random_matrix(K
.dimension())
599 return (L
, K
, matrix(e1
), matrix(e2
))
602 # Tell pylint to shut up about the large number of methods.
603 class SymmetricLinearGameTest(TestCase
): # pylint: disable=R0904
605 Tests for the SymmetricLinearGame and Solution classes.
607 def assert_within_tol(self
, first
, second
):
609 Test that ``first`` and ``second`` are equal within our default
612 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
615 def assert_norm_within_tol(self
, first
, second
):
617 Test that ``first`` and ``second`` vectors are equal in the
618 sense that the norm of their difference is within our default
621 self
.assert_within_tol(norm(first
- second
), 0)
624 def assert_solution_exists(self
, L
, K
, e1
, e2
):
626 Given the parameters needed to construct a SymmetricLinearGame,
627 ensure that that game has a solution.
629 # The matrix() constructor assumes that ``L`` is a list of
630 # columns, so we transpose it to agree with what
631 # SymmetricLinearGame() thinks.
632 G
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
635 expected
= inner_product(L
*soln
.player1_optimal(),
636 soln
.player2_optimal())
637 self
.assert_within_tol(soln
.game_value(), expected
)
640 def test_solution_exists_orthant(self
):
642 Every linear game has a solution, so we should be able to solve
643 every symmetric linear game over the NonnegativeOrthant. Pick
644 some parameters randomly and give it a shot. The resulting
645 optimal solutions should give us the optimal game value when we
646 apply the payoff operator to them.
648 (L
, K
, e1
, e2
) = _random_orthant_params()
649 self
.assert_solution_exists(L
, K
, e1
, e2
)
652 def test_solution_exists_icecream(self
):
654 Like :meth:`test_solution_exists_nonnegative_orthant`, except
655 over the ice cream cone.
657 (L
, K
, e1
, e2
) = _random_icecream_params()
658 self
.assert_solution_exists(L
, K
, e1
, e2
)
661 def test_negative_value_z_operator(self
):
663 Test the example given in Gowda/Ravindran of a Z-matrix with
664 negative game value on the nonnegative orthant.
666 K
= NonnegativeOrthant(2)
669 L
= [[1, -2], [-2, 1]]
670 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
671 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
674 def assert_scaling_works(self
, L
, K
, e1
, e2
):
676 Test that scaling ``L`` by a nonnegative number scales the value
677 of the game by the same number.
679 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
680 value1
= game1
.solution().game_value()
682 alpha
= uniform(0.1, 10)
683 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
684 value2
= game2
.solution().game_value()
685 self
.assert_within_tol(alpha
*value1
, value2
)
688 def test_scaling_orthant(self
):
690 Test that scaling ``L`` by a nonnegative number scales the value
691 of the game by the same number over the nonnegative orthant.
693 (L
, K
, e1
, e2
) = _random_orthant_params()
694 self
.assert_scaling_works(L
, K
, e1
, e2
)
697 def test_scaling_icecream(self
):
699 The same test as :meth:`test_nonnegative_scaling_orthant`,
700 except over the ice cream cone.
702 (L
, K
, e1
, e2
) = _random_icecream_params()
703 self
.assert_scaling_works(L
, K
, e1
, e2
)
706 def assert_translation_works(self
, L
, K
, e1
, e2
):
708 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
709 the value of the associated game by alpha.
711 # We need to use ``L`` later, so make sure we transpose it
712 # before passing it in as a column-indexed matrix.
713 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
714 soln1
= game1
.solution()
715 value1
= soln1
.game_value()
716 x_bar
= soln1
.player1_optimal()
717 y_bar
= soln1
.player2_optimal()
719 alpha
= uniform(-10, 10)
720 tensor_prod
= e1
*e2
.trans()
722 # This is the "correct" representation of ``M``, but COLUMN
724 M
= L
+ alpha
*tensor_prod
726 # so we have to transpose it when we feed it to the constructor.
727 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
728 value2
= game2
.solution().game_value()
730 self
.assert_within_tol(value1
+ alpha
, value2
)
732 # Make sure the same optimal pair works.
733 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
736 def test_translation_orthant(self
):
738 Test that translation works over the nonnegative orthant.
740 (L
, K
, e1
, e2
) = _random_orthant_params()
741 self
.assert_translation_works(L
, K
, e1
, e2
)
744 def test_translation_icecream(self
):
746 The same as :meth:`test_translation_orthant`, except over the
749 (L
, K
, e1
, e2
) = _random_icecream_params()
750 self
.assert_translation_works(L
, K
, e1
, e2
)
753 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
755 Check the value of the "opposite" game that gives rise to a
756 value that is the negation of the original game. Comes from
759 # We need to use ``L`` later, so make sure we transpose it
760 # before passing it in as a column-indexed matrix.
761 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
763 # This is the "correct" representation of ``M``, but
767 # so we have to transpose it when we feed it to the constructor.
768 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
770 soln1
= game1
.solution()
771 x_bar
= soln1
.player1_optimal()
772 y_bar
= soln1
.player2_optimal()
773 soln2
= game2
.solution()
775 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
777 # Make sure the switched optimal pair works.
778 self
.assert_within_tol(soln2
.game_value(),
779 inner_product(M
*y_bar
, x_bar
))
782 def test_opposite_game_orthant(self
):
784 Test the value of the "opposite" game over the nonnegative
787 (L
, K
, e1
, e2
) = _random_orthant_params()
788 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
791 def test_opposite_game_icecream(self
):
793 Like :meth:`test_opposite_game_orthant`, except over the
796 (L
, K
, e1
, e2
) = _random_icecream_params()
797 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
800 def assert_orthogonality(self
, L
, K
, e1
, e2
):
802 Two orthogonality relations hold at an optimal solution, and we
805 # We need to use ``L`` later, so make sure we transpose it
806 # before passing it in as a column-indexed matrix.
807 game
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
808 soln
= game
.solution()
809 x_bar
= soln
.player1_optimal()
810 y_bar
= soln
.player2_optimal()
811 value
= soln
.game_value()
813 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
814 self
.assert_within_tol(ip1
, 0)
816 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
817 self
.assert_within_tol(ip2
, 0)
820 def test_orthogonality_orthant(self
):
822 Check the orthgonality relationships that hold for a solution
823 over the nonnegative orthant.
825 (L
, K
, e1
, e2
) = _random_orthant_params()
826 self
.assert_orthogonality(L
, K
, e1
, e2
)
829 def test_orthogonality_icecream(self
):
831 Check the orthgonality relationships that hold for a solution
832 over the ice-cream cone.
834 (L
, K
, e1
, e2
) = _random_icecream_params()
835 self
.assert_orthogonality(L
, K
, e1
, e2
)
838 def test_positive_operator_value(self
):
840 Test that a positive operator on the nonnegative orthant gives
841 rise to a a game with a nonnegative value.
843 This test theoretically applies to the ice-cream cone as well,
844 but we don't know how to make positive operators on that cone.
846 (K
, e1
, e2
) = _random_orthant_params()[1:]
847 L
= _random_nonnegative_matrix(K
.dimension())
849 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
850 self
.assertTrue(game
.solution().game_value() >= -options
.ABS_TOL
)
853 def assert_lyapunov_works(self
, L
, K
, e1
, e2
):
855 Check that Lyapunov games act the way we expect.
857 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
858 soln
= game
.solution()
860 # We only check for positive/negative stability if the game
861 # value is not basically zero. If the value is that close to
862 # zero, we just won't check any assertions.
863 eigs
= eigenvalues_re(L
)
864 if soln
.game_value() > options
.ABS_TOL
:
865 # L should be positive stable
866 positive_stable
= all([eig
> -options
.ABS_TOL
for eig
in eigs
])
867 self
.assertTrue(positive_stable
)
868 elif soln
.game_value() < -options
.ABS_TOL
:
869 # L should be negative stable
870 negative_stable
= all([eig
< options
.ABS_TOL
for eig
in eigs
])
871 self
.assertTrue(negative_stable
)
873 # The dual game's value should always equal the primal's.
874 dualsoln
= game
.dual().solution()
875 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())
878 def test_lyapunov_orthant(self
):
880 Test that a Lyapunov game on the nonnegative orthant works.
882 (K
, e1
, e2
) = _random_orthant_params()[1:]
883 L
= _random_diagonal_matrix(K
.dimension())
885 self
.assert_lyapunov_works(L
, K
, e1
, e2
)
888 def test_lyapunov_icecream(self
):
890 Test that a Lyapunov game on the ice-cream cone works.
892 (K
, e1
, e2
) = _random_icecream_params()[1:]
893 L
= _random_lyapunov_like_icecream(K
.dimension())
895 self
.assert_lyapunov_works(L
, K
, e1
, e2
)