Michael Orlitzky [Sun, 13 Nov 2016 20:32:43 +0000 (15:32 -0500)]
Make the c(), G(), and h() methods of games public.
These don't really *need* to be public, but having them available and
documented should be helpful to anyone who wants to understand how we
transform our game into a cone program.
Michael Orlitzky [Sat, 12 Nov 2016 12:39:20 +0000 (07:39 -0500)]
Enable the dual starting point and fix the test tolerance.
We set dualstart=player2_start(), but that caused some tests to fail
as unknown or optimal but not valid. So the new epsilon_scale() method
is used to verify the primal/dual optimal in solution(). After that,
the tests of course fail, because we're accepting much more-wrong
solutions. Incorporating epsilon_scale() into the test suite fixes
that.
Michael Orlitzky [Sat, 12 Nov 2016 12:35:12 +0000 (07:35 -0500)]
Add an epsilon_scale() method for games.
When testing, we often need to know how lenient to be when making
comparisons. Trying to figure out just how lenient has been a huge
source of problems, and ultimately, the scaling factor (applied to
ABS_TOL) probably depends on properties of the solution.
This commit adds a new method, epsilon_scale(), that returns a safe
(very lenient) scaling factor. If things are within epsilon_scale()
times ABS_TOL, we consider then equal, or optimal, or whatever.
Replace _try_solution() with something more reliable and update tests.
This huge change eliminates _try_solution() entirely. It turns out
that if we just solve with the default tolerance and then *test* what
we get back (regardless of the "status" field), we do better than the
two-phase _try_solution() approach. Well, we fail less, anyway.
The code for solution is now fairly simple. It solves the problem, and
if it isn't infeasible, checks the solution for sanity: the
primal/dual values are close (within 2*ABS_TOL) and the optimal points
are in the cone. If those two things are true, we return the solution
even if CVXOPT said "unknown". This fixes two test failures, which are
now included as doctests to ensure that they can be solved.
Moreover, the value of a game is now set to be the payoff at the
optimal points. Before, we simply took the primal optimal value from
CVXOPT. That was causing some test failures though, and either one is
just as good as the other and mathematically unjustified as yet. There
were existing tests to check the payoff at the optimal points, but they
became redundant and were removed.
Finally, all of the tests have been updated to use more conservative
modifiers, not based on the condition number of the game. Some failures
are still being ironed out, but they are rare.
Note: the _c(), _h(), etc. methods on the game are now overkill since
they are only used once, but they don't hurt I guess.
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.
Add more docs for a few private methods and implement the do-over.
Some examples and return type documentation were added for the
_zero(), _A(), and _G() methods of SymmetricLinearGame. The _zero()
method was also uncached, since attempting to cache _A() and _G()
revealed that CVXOPT clobbers them. The zero vector appears safe, but
let's play it safe.
This also implements a two-stage retry for the solution of a game. Our
default tolerance is now 1e-6, but when we're trying to solve a game,
we try it with 1e7 first. If we can solve it with the stricter
tolerance, then great. If not, we use the default.
Take the condition number into account when evaluating test results.
This adds a ``modifier`` parameter to the assert_within_tol() method
used in the SymmetricLinearGame unit tests. The condition number of
the game is always passed in as the modifier, and that lets us allow a
larger tolerance for nasty matrices.
Our ABS_TOL is less than the CVXOPT default, and it looks like using
ours reduces the number of "unknown" results that we get. So let's try
that for now.
Change EPSILON to something more conservative in the test suite.
The old value of EPSILON was more lenient, but the new one can
actually be justified. The tests are currently pretty reliable, but
some tolerance > EPSILON failures are still occurring so this will
probably need to be massaged some more.