--- /dev/null
+"""
+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
+
+
projects / dunshire.git / blobdiff