From 479cd91a21bb68b88021575741d812378971a7c9 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Mon, 10 Oct 2016 11:54:29 -0400 Subject: [PATCH] Begin overhauling docs to numpy format. --- src/dunshire/errors.py | 27 +-- src/dunshire/matrices.py | 153 +++++++++++--- src/dunshire/symmetric_linear_game.py | 282 +++++++++++++++----------- 3 files changed, 306 insertions(+), 156 deletions(-) diff --git a/src/dunshire/errors.py b/src/dunshire/errors.py index 322479f..4e292ac 100644 --- a/src/dunshire/errors.py +++ b/src/dunshire/errors.py @@ -12,7 +12,8 @@ def _pretty_format_dict(dictionary): The dictionary is also sorted so that it can be tested repeatably. - EXAMPLES: + Examples + -------- >>> d = {'foo': 1.234, 'bar': matrix([1,2,3])} >>> print(_pretty_format_dict(d)) @@ -39,12 +40,20 @@ def _pretty_format_dict(dictionary): class GameUnsolvableException(Exception): """ - Every linear game has a solution (this follows from a general - min-max theorem). If we can't solve the conic program associated - with a linear game, then something is wrong with either the model of - the input. + An exception raised when a game cannot be solved. - EXAMPLES: + Every linear game has a solution. If we can't solve the conic + program associated with a linear game, then something is wrong with + either the model or the input, and this exception should be raised. + + Parameters + ---------- + + solution_dict : dict + The solution dictionary returned from the failed cone program. + + Examples + -------- >>> d = {'residual as dual infeasibility certificate': None, ... 'y': matrix([1,1]), @@ -91,12 +100,6 @@ class GameUnsolvableException(Exception): def __init__(self, solution_dict): """ Create a new GameUnsolvableException object. - - INPUT: - - - ``solution_dict`` -- the solution dictionary returned from the - cone program. - """ super().__init__() self._solution_dict = solution_dict diff --git a/src/dunshire/matrices.py b/src/dunshire/matrices.py index 2006fd2..38d4afe 100644 --- a/src/dunshire/matrices.py +++ b/src/dunshire/matrices.py @@ -1,20 +1,36 @@ """ Utility functions for working with CVXOPT matrices (instances of the -``cvxopt.base.matrix`` class). +class:`cvxopt.base.matrix` class). """ from math import sqrt from cvxopt import matrix from cvxopt.lapack import syev +import options + def append_col(left, right): """ Append the matrix ``right`` to the right side of the matrix ``left``. - EXAMPLES: + Parameters + ---------- + left, right : matrix + The two matrices to append to one another. + + Examples + -------- >>> A = matrix([1,2,3,4], (2,2)) >>> B = matrix([5,6,7,8,9,10], (2,3)) + >>> print(A) + [ 1 3] + [ 2 4] + + >>> print(B) + [ 5 7 9] + [ 6 8 10] + >>> print(append_col(A,B)) [ 1 3 5 7 9] [ 2 4 6 8 10] @@ -27,10 +43,25 @@ def append_row(top, bottom): """ Append the matrix ``bottom`` to the bottom of the matrix ``top``. - EXAMPLES: + Parameters + ---------- + top, bottom : matrix + The two matrices to append to one another. + + Examples + -------- >>> A = matrix([1,2,3,4], (2,2)) >>> B = matrix([5,6,7,8,9,10], (3,2)) + >>> print(A) + [ 1 3] + [ 2 4] + + >>> print(B) + [ 5 8] + [ 6 9] + [ 7 10] + >>> print(append_row(A,B)) [ 1 3] [ 2 4] @@ -43,29 +74,66 @@ def append_row(top, bottom): return matrix([top, bottom]) -def eigenvalues(real_matrix): +def eigenvalues(symmat): """ - Return the eigenvalues of the given ``real_matrix``. + Return the eigenvalues of the given symmetric real matrix. - EXAMPLES: + Parameters + ---------- + + symmat : matrix + The real symmetric matrix whose eigenvalues you want. + + + Raises + ------ + TypeError + If the input matrix is not symmetric. + + Examples + -------- >>> A = matrix([[2,1],[1,2]], tc='d') >>> eigenvalues(A) [1.0, 3.0] + If the input matrix is not symmetric, it may not have real + eigenvalues, and we don't know what to do:: + + >>> A = matrix([[1,2],[3,4]]) + >>> eigenvalues(A) + Traceback (most recent call last): + ... + TypeError: input must be a symmetric real matrix + """ - domain_dim = real_matrix.size[0] # Assume ``real_matrix`` is square. + if not norm(symmat.trans() - symmat) < options.ABS_TOL: + # Ensure that ``symmat`` is symmetric (and thus square). + raise TypeError('input must be a symmetric real matrix') + + domain_dim = symmat.size[0] eigs = matrix(0, (domain_dim, 1), tc='d') - syev(real_matrix, eigs) + syev(symmat, eigs) return list(eigs) def identity(domain_dim): """ - Return a ``domain_dim``-by-``domain_dim`` dense integer identity - matrix. + Create an identity matrix of the given dimensions. - EXAMPLES: + Parameters + ---------- + + domain_dim : int + The dimension of the vector space on which the identity will act. + + Returns + ------- + matrix + A ``domain_dim``-by-``domain_dim`` dense integer identity matrix. + + Examples + -------- >>> print(identity(3)) [ 1 0 0] @@ -85,10 +153,21 @@ def identity(domain_dim): def inner_product(vec1, vec2): """ - Compute the (Euclidean) inner product of the two vectors ``vec1`` - and ``vec2``. + Compute the Euclidean inner product of two vectors. + + Parameters + ---------- + + vec1, vec2 : matrix + The two vectors whose inner product you want. - EXAMPLES: + Returns + ------- + float + The inner product of ``vec1`` and ``vec2``. + + Examples + -------- >>> x = [1,2,3] >>> y = [3,4,1] @@ -116,11 +195,25 @@ def inner_product(vec1, vec2): def norm(matrix_or_vector): """ - Return the Frobenius norm of ``matrix_or_vector``, which is the same - thing as its Euclidean norm when it's a vector (when one of its - dimensions is unity). + Return the Frobenius norm of a matrix or vector. + + When the input is a vector, its matrix-Frobenius norm is the same + thing as its vector-Euclidean norm. + + Parameters + ---------- + + matrix_or_vector : matrix + The matrix or vector whose norm you want. + + Returns + ------- - EXAMPLES: + float + The norm of ``matrix_or_vector``. + + Examples + -------- >>> v = matrix([1,1]) >>> print('{:.5f}'.format(norm(v))) @@ -134,11 +227,25 @@ def norm(matrix_or_vector): return sqrt(inner_product(matrix_or_vector, matrix_or_vector)) -def vec(real_matrix): +def vec(mat): """ - Create a long vector in column-major order from ``real_matrix``. + Create a long vector in column-major order from ``mat``. + + Parameters + ---------- + + mat : matrix + Any sort of real matrix that you want written as a long vector. + + Returns + ------- + + matrix + An ``len(mat)``-by-``1`` long column vector containign the + entries of ``mat`` in column major order. - EXAMPLES: + Examples + -------- >>> A = matrix([[1,2],[3,4]]) >>> print(A) @@ -153,7 +260,7 @@ def vec(real_matrix): [ 4] - Note that if ``real_matrix`` is a vector, this function is a no-op: + Note that if ``mat`` is a vector, this function is a no-op: >>> v = matrix([1,2,3,4], (4,1)) >>> print(v) @@ -170,4 +277,4 @@ def vec(real_matrix): """ - return matrix(real_matrix, (len(real_matrix), 1)) + return matrix(mat, (len(mat), 1)) diff --git a/src/dunshire/symmetric_linear_game.py b/src/dunshire/symmetric_linear_game.py index 7be55d7..e2d2978 100644 --- a/src/dunshire/symmetric_linear_game.py +++ b/src/dunshire/symmetric_linear_game.py @@ -1,8 +1,8 @@ """ Symmetric linear games and their solutions. -This module contains the main 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. """ # These few are used only for tests. @@ -25,6 +25,19 @@ class Solution: """ A representation of the solution of a linear game. It should contain the value of the game, and both players' strategies. + + Examples + -------- + + >>> print(Solution(10, matrix([1,2]), matrix([3,4]))) + Game value: 10.0000000 + Player 1 optimal: + [ 1] + [ 2] + Player 2 optimal: + [ 3] + [ 4] + """ def __init__(self, game_value, p1_optimal, p2_optimal): """ @@ -45,17 +58,7 @@ class Solution: * The optimal strategy of player one. * The optimal strategy of player two. - EXAMPLES: - - >>> print(Solution(10, matrix([1,2]), matrix([3,4]))) - Game value: 10.0000000 - Player 1 optimal: - [ 1] - [ 2] - Player 2 optimal: - [ 3] - [ 4] - + The two optimal strategy vectors are indented by two spaces. """ tpl = 'Game value: {:.7f}\n' \ 'Player 1 optimal:{:s}\n' \ @@ -72,6 +75,14 @@ class Solution: def game_value(self): """ Return the game value for this solution. + + Examples + -------- + + >>> s = Solution(10, matrix([1,2]), matrix([3,4])) + >>> s.game_value() + 10 + """ return self._game_value @@ -79,6 +90,16 @@ class Solution: def player1_optimal(self): """ Return player one's optimal strategy in this solution. + + Examples + -------- + + >>> s = Solution(10, matrix([1,2]), matrix([3,4])) + >>> print(s.player1_optimal()) + [ 1] + [ 2] + + """ return self._player1_optimal @@ -86,6 +107,16 @@ class Solution: def player2_optimal(self): """ Return player two's optimal strategy in this solution. + + Examples + -------- + + >>> s = Solution(10, matrix([1,2]), matrix([3,4])) + >>> print(s.player2_optimal()) + [ 3] + [ 4] + + """ return self._player2_optimal @@ -107,9 +138,111 @@ class SymmetricLinearGame: two respectively. The ambient space is assumed to be the span of ``K``. + + Examples + -------- + + >>> from cones import NonnegativeOrthant + >>> K = NonnegativeOrthant(3) + >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] + >>> e1 = [1,1,1] + >>> e2 = [1,2,3] + >>> SLG = SymmetricLinearGame(L, K, e1, e2) + >>> print(SLG) + The linear game (L, K, e1, e2) where + L = [ 1 -5 -15] + [ -1 2 -3] + [-12 -15 1], + K = Nonnegative orthant in the real 3-space, + e1 = [ 1] + [ 1] + [ 1], + e2 = [ 1] + [ 2] + [ 3]. + + + Lists can (and probably should) be used for every argument:: + + >>> from cones import NonnegativeOrthant + >>> K = NonnegativeOrthant(2) + >>> L = [[1,0],[0,1]] + >>> e1 = [1,1] + >>> e2 = [1,1] + >>> G = SymmetricLinearGame(L, K, e1, e2) + >>> print(G) + The linear game (L, K, e1, e2) where + L = [ 1 0] + [ 0 1], + K = Nonnegative orthant in the real 2-space, + e1 = [ 1] + [ 1], + e2 = [ 1] + [ 1]. + + The points ``e1`` and ``e2`` can also be passed as some other + enumerable type (of the correct length) without much harm, since + there is no row/column ambiguity:: + + >>> import cvxopt + >>> import numpy + >>> from cones import NonnegativeOrthant + >>> K = NonnegativeOrthant(2) + >>> L = [[1,0],[0,1]] + >>> e1 = cvxopt.matrix([1,1]) + >>> e2 = numpy.matrix([1,1]) + >>> G = SymmetricLinearGame(L, K, e1, e2) + >>> print(G) + The linear game (L, K, e1, e2) where + L = [ 1 0] + [ 0 1], + K = Nonnegative orthant in the real 2-space, + e1 = [ 1] + [ 1], + e2 = [ 1] + [ 1]. + + However, ``L`` will always be intepreted as a list of rows, even + if it is passed as a :class:`cvxopt.base.matrix` which is + otherwise indexed by columns:: + + >>> import cvxopt + >>> from cones import NonnegativeOrthant + >>> K = NonnegativeOrthant(2) + >>> L = [[1,2],[3,4]] + >>> e1 = [1,1] + >>> e2 = e1 + >>> G = SymmetricLinearGame(L, K, e1, e2) + >>> print(G) + The linear game (L, K, e1, e2) where + L = [ 1 2] + [ 3 4], + K = Nonnegative orthant in the real 2-space, + e1 = [ 1] + [ 1], + e2 = [ 1] + [ 1]. + >>> L = cvxopt.matrix(L) + >>> print(L) + [ 1 3] + [ 2 4] + + >>> G = SymmetricLinearGame(L, K, e1, e2) + >>> print(G) + The linear game (L, K, e1, e2) where + L = [ 1 2] + [ 3 4], + K = Nonnegative orthant in the real 2-space, + e1 = [ 1] + [ 1], + e2 = [ 1] + [ 1]. + """ def __init__(self, L, K, e1, e2): """ + Create a new SymmetricLinearGame object. + INPUT: - ``L`` -- an square matrix represented as a list of lists @@ -126,83 +259,6 @@ class SymmetricLinearGame: - ``e2`` -- the interior point of ``K`` belonging to player two; it can be of any enumerable type having the correct length. - EXAMPLES: - - Lists can (and probably should) be used for every argument: - - >>> from cones import NonnegativeOrthant - >>> K = NonnegativeOrthant(2) - >>> L = [[1,0],[0,1]] - >>> e1 = [1,1] - >>> e2 = [1,1] - >>> G = SymmetricLinearGame(L, K, e1, e2) - >>> print(G) - The linear game (L, K, e1, e2) where - L = [ 1 0] - [ 0 1], - K = Nonnegative orthant in the real 2-space, - e1 = [ 1] - [ 1], - e2 = [ 1] - [ 1]. - - The points ``e1`` and ``e2`` can also be passed as some other - enumerable type (of the correct length) without much harm, since - there is no row/column ambiguity: - - >>> import cvxopt - >>> import numpy - >>> from cones import NonnegativeOrthant - >>> K = NonnegativeOrthant(2) - >>> L = [[1,0],[0,1]] - >>> e1 = cvxopt.matrix([1,1]) - >>> e2 = numpy.matrix([1,1]) - >>> G = SymmetricLinearGame(L, K, e1, e2) - >>> print(G) - The linear game (L, K, e1, e2) where - L = [ 1 0] - [ 0 1], - K = Nonnegative orthant in the real 2-space, - e1 = [ 1] - [ 1], - e2 = [ 1] - [ 1]. - - However, ``L`` will always be intepreted as a list of rows, even - if it is passed as a ``cvxopt.base.matrix`` which is otherwise - indexed by columns: - - >>> import cvxopt - >>> from cones import NonnegativeOrthant - >>> K = NonnegativeOrthant(2) - >>> L = [[1,2],[3,4]] - >>> e1 = [1,1] - >>> e2 = e1 - >>> G = SymmetricLinearGame(L, K, e1, e2) - >>> print(G) - The linear game (L, K, e1, e2) where - L = [ 1 2] - [ 3 4], - K = Nonnegative orthant in the real 2-space, - e1 = [ 1] - [ 1], - e2 = [ 1] - [ 1]. - >>> L = cvxopt.matrix(L) - >>> print(L) - [ 1 3] - [ 2 4] - - >>> G = SymmetricLinearGame(L, K, e1, e2) - >>> print(G) - The linear game (L, K, e1, e2) where - L = [ 1 2] - [ 3 4], - K = Nonnegative orthant in the real 2-space, - e1 = [ 1] - [ 1], - e2 = [ 1] - [ 1]. """ self._K = K self._e1 = matrix(e1, (K.dimension(), 1)) @@ -221,29 +277,7 @@ class SymmetricLinearGame: def __str__(self): """ - Return a string representatoin of this game. - - EXAMPLES: - - >>> from cones import NonnegativeOrthant - >>> K = NonnegativeOrthant(3) - >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]] - >>> e1 = [1,1,1] - >>> e2 = [1,2,3] - >>> SLG = SymmetricLinearGame(L, K, e1, e2) - >>> print(SLG) - The linear game (L, K, e1, e2) where - L = [ 1 -5 -15] - [ -1 2 -3] - [-12 -15 1], - K = Nonnegative orthant in the real 3-space, - e1 = [ 1] - [ 1] - [ 1], - e2 = [ 1] - [ 2] - [ 3]. - + Return a string representation of this game. """ tpl = 'The linear game (L, K, e1, e2) where\n' \ ' L = {:s},\n' \ @@ -269,10 +303,11 @@ class SymmetricLinearGame: GameUnsolvableException is raised. It can be printed to get the raw output from CVXOPT. - EXAMPLES: + Examples + -------- This example is computed in Gowda and Ravindran in the section - "The value of a Z-transformation": + "The value of a Z-transformation":: >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) @@ -292,7 +327,7 @@ class SymmetricLinearGame: [0.5517241] The value of the following game can be computed using the fact - that the identity is invertible: + that the identity is invertible:: >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) @@ -363,7 +398,8 @@ class SymmetricLinearGame: """ Return the dual game to this game. - EXAMPLES: + Examples + -------- >>> from cones import NonnegativeOrthant >>> K = NonnegativeOrthant(3) @@ -385,8 +421,11 @@ class SymmetricLinearGame: [ 1]. """ - return SymmetricLinearGame(self._L, # It will be transposed in __init__(). - self._K, # Since "K" is symmetric. + # We pass ``self._L`` right back into the constructor, because + # it will be transposed there. And keep in mind that ``self._K`` + # is its own dual. + return SymmetricLinearGame(self._L, + self._K, self._e2, self._e1) @@ -441,8 +480,9 @@ class SymmetricLinearGameTest(TestCase): # the fudge factor we make up later. ambient_dim = randint(2, 10) K = IceCream(ambient_dim) - e1 = [1] - e2 = [1] + e1 = [1] # Set the "height" of e1 to one + e2 = [1] # And the same for e2 + # If we choose the rest of the components of e1,e2 randomly # between 0 and 1, then the largest the squared norm of the # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We -- 2.44.2