X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2Fdunshire%2Fcones.py;fp=src%2Fdunshire%2Fcones.py;h=0000000000000000000000000000000000000000;hb=bdb596b84a06d0c97e39d42586a51fc36ba44186;hp=7fc8bf94993e4df86b2f57c2e6b6d6aefa65d8c4;hpb=21a2eb9a647a48c0e94d02c60ef8785c4ea35f7b;p=dunshire.git diff --git a/src/dunshire/cones.py b/src/dunshire/cones.py deleted file mode 100644 index 7fc8bf9..0000000 --- a/src/dunshire/cones.py +++ /dev/null @@ -1,617 +0,0 @@ -""" -Class definitions for all of the symmetric cones (and their superclass, -:class:`SymmetricCone`) supported by CVXOPT. -""" - -from cvxopt import matrix - -from .matrices import eigenvalues, norm -from . import options - -class SymmetricCone: - """ - An instance of a symmetric (self-dual and homogeneous) cone. - - There are three types of symmetric cones supported by CVXOPT: - - 1. The nonnegative orthant in the real n-space. - 2. The Lorentz "ice cream" cone, or the second-order cone. - 3. The cone of symmetric positive-semidefinite matrices. - - This class is intended to encompass them all. - - When constructing a single symmetric cone (i.e. not a - :class:`CartesianProduct` of them), the only information that we - need is its dimension. We take that dimension as a parameter, and - store it for later. - - Parameters - ---------- - - dimension : int - The dimension of this cone. - - Raises - ------ - - ValueError - If you try to create a cone with dimension zero or less. - - """ - def __init__(self, dimension): - """ - A generic constructor for symmetric cones. - """ - if dimension <= 0: - raise ValueError('cones must have dimension greater than zero') - - self._dimension = dimension - - - def __contains__(self, point): - """ - Return whether or not ``point`` belongs to this cone. - - Parameters - ---------- - - point : matrix - The point to test for membership in this cone. - - Raises - ------ - - NotImplementedError - Always, this method must be implemented in subclasses. - - Examples - -------- - - >>> K = SymmetricCone(5) - >>> matrix([1,2]) in K - Traceback (most recent call last): - ... - NotImplementedError - - """ - raise NotImplementedError - - - - def dimension(self): - """ - Return the dimension of this symmetric cone. - - The dimension of this symmetric cone is recorded during its - creation. This method simply returns the recorded value, and - should not need to be overridden in subclasses. We prefer to do - any special computation in ``__init__()`` and record the result - in ``self._dimension``. - - Returns - ------- - - int - The stored dimension (from when this cone was constructed) - of this cone. - - Examples - -------- - - >>> K = SymmetricCone(5) - >>> K.dimension() - 5 - - """ - return self._dimension - - -class NonnegativeOrthant(SymmetricCone): - """ - The nonnegative orthant in the given number of dimensions. - - Examples - -------- - - >>> K = NonnegativeOrthant(3) - >>> print(K) - Nonnegative orthant in the real 3-space - - """ - def __str__(self): - """ - Output a human-readable description of myself. - """ - tpl = 'Nonnegative orthant in the real {:d}-space' - return tpl.format(self.dimension()) - - - def __contains__(self, point): - """ - Return whether or not ``point`` belongs to this cone. - - Since this test is expected to work on points whose components - are floating point numbers, it doesn't make any sense to - distinguish between strict and non-strict containment -- the - test uses a tolerance parameter. - - Parameters - ---------- - - point : matrix - A :class:`cvxopt.base.matrix` having dimensions ``(n,1)`` - where ``n`` is the :meth:`dimension` of this cone. - - Returns - ------- - - bool - - ``True`` if ``point`` belongs to this cone, ``False`` otherwise. - - Raises - ------ - - TypeError - If ``point`` is not a :class:`cvxopt.base.matrix`. - - TypeError - If ``point`` has the wrong dimensions. - - Examples - -------- - - All of these coordinates are positive enough: - - >>> K = NonnegativeOrthant(3) - >>> matrix([1,2,3]) in K - True - - The one negative coordinate pushes this point outside of ``K``: - - >>> K = NonnegativeOrthant(3) - >>> matrix([1,-0.1,3]) in K - False - - A boundary point is considered inside of ``K``: - >>> K = NonnegativeOrthant(3) - >>> matrix([1,0,3]) in K - True - - Junk arguments don't work: - - >>> K = NonnegativeOrthant(3) - >>> [1,2,3] in K - Traceback (most recent call last): - ... - TypeError: the given point is not a cvxopt.base.matrix - - >>> K = NonnegativeOrthant(3) - >>> matrix([1,2]) in K - Traceback (most recent call last): - ... - TypeError: the given point has the wrong dimensions - - """ - if not isinstance(point, matrix): - raise TypeError('the given point is not a cvxopt.base.matrix') - if not point.size == (self.dimension(), 1): - raise TypeError('the given point has the wrong dimensions') - - return all([x > -options.ABS_TOL for x in point]) - - - -class IceCream(SymmetricCone): - """ - The Lorentz "ice cream" cone in the given number of dimensions. - - Examples - -------- - - >>> K = IceCream(3) - >>> print(K) - Lorentz "ice cream" cone in the real 3-space - - """ - def __str__(self): - """ - Output a human-readable description of myself. - """ - tpl = 'Lorentz "ice cream" cone in the real {:d}-space' - return tpl.format(self.dimension()) - - - def __contains__(self, point): - """ - Return whether or not ``point`` belongs to this cone. - - Since this test is expected to work on points whose components - are floating point numbers, it doesn't make any sense to - distinguish between strict and non-strict containment -- the - test uses a tolerance parameter. - - Parameters - ---------- - - point : matrix - A :class:`cvxopt.base.matrix` having dimensions ``(n,1)`` - where ``n`` is the :meth:`dimension` of this cone. - - Returns - ------- - - bool - - ``True`` if ``point`` belongs to this cone, ``False`` otherwise. - - Raises - ------ - - TypeError - If ``point`` is not a :class:`cvxopt.base.matrix`. - - TypeError - If ``point`` has the wrong dimensions. - - Examples - -------- - - This point lies well within the ice cream cone: - - >>> K = IceCream(3) - >>> matrix([1,0.5,0.5]) in K - True - - This one lies on its boundary: - - >>> K = IceCream(3) - >>> matrix([1,0,1]) in K - True - - This point lies entirely outside of the ice cream cone: - - >>> K = IceCream(3) - >>> matrix([1,1,1]) in K - False - - Junk arguments don't work: - - >>> K = IceCream(3) - >>> [1,2,3] in K - Traceback (most recent call last): - ... - TypeError: the given point is not a cvxopt.base.matrix - - >>> K = IceCream(3) - >>> matrix([1,2]) in K - Traceback (most recent call last): - ... - TypeError: the given point has the wrong dimensions - - """ - if not isinstance(point, matrix): - raise TypeError('the given point is not a cvxopt.base.matrix') - if not point.size == (self.dimension(), 1): - raise TypeError('the given point has the wrong dimensions') - - height = point[0] - if self.dimension() == 1: - # In one dimension, the ice cream cone is the nonnegative - # orthant. - return height > -options.ABS_TOL - else: - radius = point[1:] - return norm(radius) < (height + options.ABS_TOL) - - - -class SymmetricPSD(SymmetricCone): - r""" - The cone of real symmetric positive-semidefinite matrices. - - This cone has a dimension ``n`` associated with it, but we let ``n`` - refer to the dimension of the domain of our matrices and not the - dimension of the (much larger) space in which the matrices - themselves live. In other words, our ``n`` is the ``n`` that appears - in the usual notation :math:`S^{n}` for symmetric matrices. - - As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension - :math:`\left(n^{2} + n\right)/2)`. - - Examples - -------- - - >>> K = SymmetricPSD(3) - >>> print(K) - Cone of symmetric positive-semidefinite matrices on the real 3-space - >>> K.dimension() - 3 - - """ - def __str__(self): - """ - Output a human-readable description of myself. - """ - tpl = 'Cone of symmetric positive-semidefinite matrices ' \ - 'on the real {:d}-space' - return tpl.format(self.dimension()) - - - def __contains__(self, point): - """ - Return whether or not ``point`` belongs to this cone. - - Since this test is expected to work on points whose components - are floating point numbers, it doesn't make any sense to - distinguish between strict and non-strict containment -- the - test uses a tolerance parameter. - - Parameters - ---------- - - point : matrix - A :class:`cvxopt.base.matrix` having dimensions ``(n,n)`` - where ``n`` is the :meth:`dimension` of this cone. - - Returns - ------- - - bool - - ``True`` if ``point`` belongs to this cone, ``False`` otherwise. - - Raises - ------ - - TypeError - If ``point`` is not a :class:`cvxopt.base.matrix`. - - TypeError - If ``point`` has the wrong dimensions. - - Examples - -------- - - These all lie in the interior of the Symmetric PSD cone: - - >>> K = SymmetricPSD(2) - >>> matrix([[1,0],[0,1]]) in K - True - - >>> K = SymmetricPSD(3) - >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K - True - - >>> K = SymmetricPSD(5) - >>> A = matrix([[5,4,3,2,1], - ... [4,5,4,3,2], - ... [3,4,5,4,3], - ... [2,3,4,5,4], - ... [1,2,3,4,5]]) - >>> A in K - True - - Boundary points lie in the cone as well: - - >>> K = SymmetricPSD(2) - >>> matrix([[0,0],[0,0]]) in K - True - - >>> K = SymmetricPSD(5) - >>> A = matrix([[1,0,0,0,0], - ... [0,1,0,0,0], - ... [0,0,0,0,0], - ... [0,0,0,1,0], - ... [0,0,0,0,1]]) - >>> A in K - True - - However, this matrix has a negative eigenvalue: - - >>> K = SymmetricPSD(2) - >>> A = matrix([[ 1, -2], - ... [-2, 1]]) - >>> A in K - False - - An asymmetric cone with positive eigenvalues is not in the cone: - - >>> K = SymmetricPSD(2) - >>> A = matrix([[10, 2], - ... [4, 8]]) - >>> A in K - False - - Junk arguments don't work: - - >>> K = SymmetricPSD(2) - >>> [[1,2],[2,3]] in K - Traceback (most recent call last): - ... - TypeError: the given point is not a cvxopt.base.matrix - - >>> K = SymmetricPSD(3) - >>> matrix([[1,2],[3,4]]) in K - Traceback (most recent call last): - ... - TypeError: the given point has the wrong dimensions - - """ - if not isinstance(point, matrix): - raise TypeError('the given point is not a cvxopt.base.matrix') - if not point.size == (self.dimension(), self.dimension()): - raise TypeError('the given point has the wrong dimensions') - if not point.typecode == 'd': - point = matrix(point, (self.dimension(), self.dimension()), 'd') - if not norm(point - point.trans()) < options.ABS_TOL: - # It's not symmetric. - return False - return all([e > -options.ABS_TOL for e in eigenvalues(point)]) - - - -class CartesianProduct(SymmetricCone): - """ - A cartesian product of symmetric cones, which is itself a symmetric - cone. - - Examples - -------- - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2)) - >>> print(K) - Cartesian product of dimension 5 with 2 factors: - * Nonnegative orthant in the real 3-space - * Lorentz "ice cream" cone in the real 2-space - - """ - def __init__(self, *factors): - my_dimension = sum([f.dimension() for f in factors]) - super().__init__(my_dimension) - self._factors = factors - - - def __str__(self): - """ - Output a human-readable description of myself. - """ - tpl = 'Cartesian product of dimension {:d} with {:d} factors:' - tpl += '\n * {!s}' * len(self.factors()) - format_args = [self.dimension(), len(self.factors())] - format_args += list(self.factors()) - return tpl.format(*format_args) - - - def __contains__(self, point): - """ - Return whether or not ``point`` belongs to this cone. - - The ``point`` is expected to be a tuple of points which will be - tested for membership in this cone's factors. If each point in - the tuple belongs to its corresponding factor, then the whole - point belongs to this cone. Otherwise, it doesn't. - - Parameters - ---------- - - point : tuple of matrix - A tuple of :class:`cvxopt.base.matrix` corresponding to the - :meth:`factors` of this cartesian product. - - Returns - ------- - - bool - - ``True`` if ``point`` belongs to this cone, ``False`` otherwise. - - Raises - ------ - - TypeError - If ``point`` is not a tuple of :class:`cvxopt.base.matrix`. - - TypeError - If any element of ``point`` has the wrong dimensions. - - Examples - -------- - - The result depends on how containment is defined for our factors: - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K - True - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> (matrix([0,0,0]), matrix([1,0,1])) in K - True - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> (matrix([1,1,1]), matrix([1,1,1])) in K - False - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> (matrix([1,-1,1]), matrix([1,0,1])) in K - False - - Junk arguments don't work: - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> [[1,2,3],[4,5,6]] in K - Traceback (most recent call last): - ... - TypeError: the given point is not a cvxopt.base.matrix - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3)) - >>> (matrix([1,2]), matrix([3,4,5,6])) in K - Traceback (most recent call last): - ... - TypeError: the given point has the wrong dimensions - - """ - return all([p in f for (p, f) in zip(point, self.factors())]) - - - - def factors(self): - """ - Return a tuple containing the factors (in order) of this - cartesian product. - - Returns - ------- - - tuple of :class:`SymmetricCone`. - The factors of this cartesian product. - - Examples - -------- - - >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2)) - >>> len(K.factors()) - 2 - - """ - return self._factors - - - def cvxopt_dims(self): - """ - Return a dictionary of dimensions corresponding to the factors - of this cartesian product. The format of this dictionary is - described in the CVXOPT user's guide: - - http://cvxopt.org/userguide/coneprog.html#linear-cone-programs - - Returns - ------- - - dict - A dimension dictionary suitable to feed to CVXOPT. - - Examples - -------- - - >>> K = CartesianProduct(NonnegativeOrthant(3), - ... IceCream(2), - ... IceCream(3)) - >>> d = K.cvxopt_dims() - >>> (d['l'], d['q'], d['s']) - (3, [2, 3], []) - - """ - dims = {'l':0, 'q':[], 's':[]} - dims['l'] += sum([K.dimension() - for K in self.factors() - if isinstance(K, NonnegativeOrthant)]) - dims['q'] = [K.dimension() - for K in self.factors() - if isinstance(K, IceCream)] - dims['s'] = [K.dimension() - for K in self.factors() - if isinstance(K, SymmetricPSD)] - return dims - -