"""
Class definitions for all of the symmetric cones (and their superclass,
-SymmetricCone) supported by CVXOPT.
+:class:`SymmetricCone`) supported by CVXOPT.
"""
from cvxopt import matrix
-from matrices import norm
+from matrices import eigenvalues, norm
+import options
class SymmetricCone:
"""
3. The cone of symmetric positive-semidefinite matrices.
This class is intended to encompass them all.
- """
- def __init__(self, dimension):
- """
- A generic constructor for symmetric cones.
- When constructing a single symmetric cone (i.e. not a cartesian
- product of them), the only information that we need is its
- dimension. We take that dimension as a parameter, and store it
- for later.
+ 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.
- INPUT:
+ Raises
+ ------
- - ``dimension`` -- the dimension of this cone.
+ 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.
- EXAMPLES:
+ Parameters
+ ----------
- >>> K = SymmetricCone(5)
- >>> matrix([1,2]) in K
- Traceback (most recent call last):
- ...
- NotImplementedError
+ point : matrix
+ The point to test for membership in this cone.
- """
- raise NotImplementedError
+ Raises
+ ------
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of this cone.
+ NotImplementedError
+ Always, this method must be implemented in subclasses.
- EXAMPLES:
+ Examples
+ --------
>>> K = SymmetricCone(5)
- >>> K.contains_strict(matrix([1,2]))
+ >>> matrix([1,2]) in K
Traceback (most recent call last):
...
NotImplementedError
+
"""
raise NotImplementedError
+
+
def dimension(self):
"""
Return the dimension of this symmetric cone.
any special computation in ``__init__()`` and record the result
in ``self._dimension``.
- EXAMPLES:
+ Returns
+ -------
+
+ int
+ The stored dimension (from when this cone was constructed)
+ of this cone.
+
+ Examples
+ --------
>>> K = SymmetricCone(5)
>>> K.dimension()
class NonnegativeOrthant(SymmetricCone):
"""
- The nonnegative orthant in ``n`` dimensions.
+ The nonnegative orthant in the given number of dimensions.
- EXAMPLES:
+ Examples
+ --------
>>> K = NonnegativeOrthant(3)
>>> print(K)
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.
- INPUT:
-
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of 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.
- EXAMPLES:
+ Parameters
+ ----------
- >>> K = NonnegativeOrthant(3)
- >>> matrix([1,2,3]) in K
- True
+ point : matrix
+ A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
+ where ``n`` is the :meth:`dimension` of this cone.
- >>> K = NonnegativeOrthant(3)
- >>> matrix([1,-0.1,3]) in K
- False
+ Returns
+ -------
- >>> 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')
+ bool
- return all([x >= 0 for x in point])
+ ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
+ Raises
+ ------
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior of this
- cone.
+ TypeError
+ If ``point`` is not a :class:`cvxopt.base.matrix`.
- INPUT:
+ TypeError
+ If ``point`` has the wrong dimensions.
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
+ Examples
+ --------
- EXAMPLES:
+ All of these coordinates are positive enough:
>>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,2,3]))
+ >>> matrix([1,2,3]) in K
True
+ The one negative coordinate pushes this point outside of ``K``:
+
>>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,0,1]))
+ >>> matrix([1,-0.1,3]) in K
False
+ A boundary point is considered inside of ``K``:
>>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,-0.1,3]))
- False
+ >>> matrix([1,0,3]) in K
+ True
+
+ Junk arguments don't work:
>>> K = NonnegativeOrthant(3)
- >>> K.contains_strict([1,2,3])
+ >>> [1,2,3] in K
Traceback (most recent call last):
...
TypeError: the given point is not a cvxopt.base.matrix
>>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,2]))
+ >>> matrix([1,2]) in K
Traceback (most recent call last):
...
TypeError: the given point has the wrong dimensions
if not point.size == (self.dimension(), 1):
raise TypeError('the given point has the wrong dimensions')
- return all([x > 0 for x in point])
+ return all([x > -options.ABS_TOL for x in point])
class IceCream(SymmetricCone):
"""
- The nonnegative orthant in ``n`` dimensions.
+ The Lorentz "ice cream" cone in the given number of dimensions.
- EXAMPLES:
+ Examples
+ --------
>>> K = IceCream(3)
>>> print(K)
"""
Return whether or not ``point`` belongs to this cone.
- INPUT:
+ 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.
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
+ Parameters
+ ----------
- EXAMPLES:
+ 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):
if self.dimension() == 1:
# In one dimension, the ice cream cone is the nonnegative
# orthant.
- return height >= 0
+ return height > -options.ABS_TOL
else:
radius = point[1:]
- return height >= norm(radius)
+ return norm(radius) < (height + options.ABS_TOL)
+
- def contains_strict(self, point):
+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):
"""
- Return whether or not ``point`` belongs to the interior
- of this cone.
+ Output a human-readable description of myself.
+ """
+ tpl = 'Cone of symmetric positive-semidefinite matrices ' \
+ 'on the real {:d}-space'
+ return tpl.format(self.dimension())
- INPUT:
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
+ def __contains__(self, point):
+ """
+ Return whether or not ``point`` belongs to this cone.
- EXAMPLES:
+ 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.
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,0.5,0.5]))
+ 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 = IceCream(3)
- >>> K.contains_strict(matrix([1,0,1]))
- False
+ >>> K = SymmetricPSD(3)
+ >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
+ True
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,1,1]))
- False
+ >>> 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
- >>> K = IceCream(3)
- >>> K.contains_strict([1,2,3])
+ 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
+
+ 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 = IceCream(3)
- >>> K.contains_strict(matrix([1,2]))
+ >>> 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(), 1):
+ 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')
+ return all([e > -options.ABS_TOL for e in eigenvalues(point)])
- height = point[0]
- if self.dimension() == 1:
- # In one dimension, the ice cream cone is the nonnegative
- # orthant.
- return height > 0
- else:
- radius = point[1:]
- return height > norm(radius)
-
-
-class SymmetricPSD(SymmetricCone):
- """
- The nonnegative orthant in ``n`` dimensions.
-
- EXAMPLES:
-
- >>> K = SymmetricPSD(3)
- >>> print(K)
- Cone of symmetric positive-semidefinite matrices on the real 3-space
-
- """
- 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())
class CartesianProduct(SymmetricCone):
A cartesian product of symmetric cones, which is itself a symmetric
cone.
- EXAMPLES:
+ Examples
+ --------
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
>>> print(K)
super().__init__(my_dimension)
self._factors = factors
+
def __str__(self):
"""
Output a human-readable description of myself.
format_args += list(self.factors())
return tpl.format(*format_args)
+
def __contains__(self, point):
"""
Return whether or not ``point`` belongs to this cone.
- INPUT:
-
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
-
- EXAMPLES:
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> matrix([1,2,3,1,0.5,0.5]) in K
- True
+ 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.
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> matrix([0,0,0,1,0,1]) in K
- True
+ Parameters
+ ----------
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> matrix([1,1,1,1,1,1]) in K
- False
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> matrix([1,-1,1,1,0,1]) in K
- False
-
- >>> 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]) in K
- Traceback (most recent call last):
- ...
- TypeError: the given point has the wrong dimensions
+ point : tuple of matrix
+ A tuple of :class:`cvxopt.base.matrix` corresponding to the
+ :meth:`factors` of this cartesian product.
- """
- 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')
+ Returns
+ -------
- for factor in self.factors():
- # Split off the components of ``point`` corresponding to
- # ``factor``.
- factor_part = point[0:factor.dimension()]
- if not factor_part in factor:
- return False
- point = point[factor.dimension():]
+ bool
- return True
+ ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
+ Raises
+ ------
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of this cone.
+ TypeError
+ If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
- INPUT:
+ TypeError
+ If any element of ``point`` has the wrong dimensions.
- An instance of the ``cvxopt.base.matrix`` class having
- dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
+ Examples
+ --------
- EXAMPLES:
+ The result depends on how containment is defined for our factors:
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict(matrix([1,2,3,1,0.5,0.5]))
+ >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
True
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict(matrix([1,2,3,1,0,1]))
- False
+ >>> (matrix([0,0,0]), matrix([1,0,1])) in K
+ True
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict(matrix([0,1,1,1,0.5,0.5]))
+ >>> (matrix([1,1,1]), matrix([1,1,1])) in K
False
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict(matrix([1,1,1,1,1,1]))
+ >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
False
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict(matrix([1,-1,1,1,0,1]))
- False
+ Junk arguments don't work:
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict([1,2,3,4,5,6])
+ >>> [[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))
- >>> K.contains_strict(matrix([1,2]))
+ >>> (matrix([1,2]), matrix([3,4,5,6])) 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')
-
- for factor in self.factors():
- # Split off the components of ``point`` corresponding to
- # ``factor``.
- factor_part = point[0:factor.dimension()]
- if not factor.contains_strict(factor_part):
- return False
- point = point[factor.dimension():]
+ return all([p in f for (p,f) in zip(point, self.factors())])
- return True
def factors(self):
Return a tuple containing the factors (in order) of this
cartesian product.
- EXAMPLES:
+ Returns
+ -------
+
+ tuple of :class:`SymmetricCone`.
+ The factors of this cartesian product.
+
+ Examples
+ --------
>>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
>>> len(K.factors())
"""
return self._factors
+
def cvxopt_dims(self):
"""
Return a dictionary of dimensions corresponding to the factors
http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
- EXAMPLES:
+ Returns
+ -------
+
+ dict
+ A dimension dictionary suitable to feed to CVXOPT.
+
+ Examples
+ --------
>>> K = CartesianProduct(NonnegativeOrthant(3),
... IceCream(2),
projects / dunshire.git / blobdiff