"""
Class definitions for all of the symmetric cones (and their superclass,
-class:`SymmetricCone`) supported by CVXOPT.
+:class:`SymmetricCone`) supported by CVXOPT.
"""
from cvxopt import matrix
from matrices import eigenvalues, norm
+import options
class SymmetricCone:
"""
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):
"""
raise NotImplementedError
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of this cone.
-
- Parameters
- ----------
-
- point : matrix
- The point to test for strict membership in this cone.
-
- Raises
- ------
-
- NotImplementedError
- Always, this method must be implemented in subclasses.
-
- Examples
- --------
-
- >>> K = SymmetricCone(5)
- >>> K.contains_strict(matrix([1,2]))
- Traceback (most recent call last):
- ...
- NotImplementedError
- """
- raise NotImplementedError
-
def dimension(self):
"""
"""
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
----------
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)
- >>> [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 >= 0 for x in point])
-
-
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior of this
- cone.
-
- 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 the interior of this cone,
- ``False`` otherwise.
-
- Raises
- ------
-
- TypeError
- If ``point`` is not a :class:`cvxopt.base.matrix`.
-
- TypeError
- If ``point`` has the wrong dimensions.
-
- Examples
- --------
-
- >>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,2,3]))
+ >>> matrix([1,0,3]) in K
True
- >>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,0,1]))
- False
-
- >>> K = NonnegativeOrthant(3)
- >>> K.contains_strict(matrix([1,-0.1,3]))
- False
+ 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])
"""
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
----------
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)
-
-
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of this cone.
-
- 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 the interior of this cone,
- ``False`` otherwise.
-
- Raises
- ------
-
- TypeError
- If ``point`` is not a :class:`cvxopt.base.matrix`.
-
- TypeError
- If ``point`` has the wrong dimensions.
-
- Examples
- --------
-
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,0.5,0.5]))
- True
-
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,0,1]))
- False
-
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,1,1]))
- False
-
- >>> K = IceCream(3)
- >>> K.contains_strict([1,2,3])
- Traceback (most recent call last):
- ...
- TypeError: the given point is not a cvxopt.base.matrix
-
- >>> K = IceCream(3)
- >>> K.contains_strict(matrix([1,2]))
- 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 norm(radius) < (height + options.ABS_TOL)
- 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):
- """
+ 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 `S^{n}` for symmetric matrices.
+ in the usual notation :math:`S^{n}` for symmetric matrices.
As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
- ``(n**2 + n)/2)``.
+ :math:`\left(n^{2} + n\right)/2)`.
Examples
--------
"""
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
----------
Examples
--------
- >>> K = SymmetricPSD(2)
- >>> matrix([[1,0],[0,1]]) in K
- True
+ These all lie in the interior of the Symmetric PSD cone:
>>> K = SymmetricPSD(2)
- >>> matrix([[0,0],[0,0]]) in K
+ >>> matrix([[1,0],[0,1]]) in K
True
>>> K = SymmetricPSD(3)
>>> 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]])
+ ... [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]])
+ ... [0,1,0,0,0],
+ ... [0,0,0,0,0],
+ ... [0,0,0,1,0],
+ ... [0,0,0,0,1]])
>>> A in K
True
- >>> 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')
- return all([e >= 0 for e in eigenvalues(point)])
-
-
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of this cone.
-
- 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 the interior of this cone,
- ``False`` otherwise.
+ However, this matrix has a negative eigenvalue:
- Raises
- ------
-
- TypeError
- If ``point`` is not a :class:`cvxopt.base.matrix`.
-
- TypeError
- If ``point`` has the wrong dimensions.
-
- Examples
- --------
-
- >>> K = SymmetricPSD(2)
- >>> K.contains_strict(matrix([[1,0],[0,1]]))
- True
-
- >>> K = SymmetricPSD(2)
- >>> K.contains_strict(matrix([[0,0],[0,0]]))
- False
+ >>> K = SymmetricPSD(2)
+ >>> A = matrix([[ 1, -2],
+ ... [-2, 1]])
+ >>> A in K
+ False
- >>> K = SymmetricPSD(3)
- >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
- True
+ An asymmetric cone with positive eigenvalues is not in the cone:
- >>> 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 = SymmetricPSD(2)
+ >>> A = matrix([[10, 2],
+ ... [4, 8]])
+ >>> A in K
+ False
- >>> 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]])
- >>> K.contains_strict(A)
- False
+ Junk arguments don't work:
>>> K = SymmetricPSD(2)
- >>> K.contains_strict([[1,2],[2,3]])
+ >>> [[1,2],[2,3]] in K
Traceback (most recent call last):
...
TypeError: the given point is not a cvxopt.base.matrix
>>> K = SymmetricPSD(3)
- >>> K.contains_strict(matrix([[1,2],[3,4]]))
+ >>> matrix([[1,2],[3,4]]) in K
Traceback (most recent call last):
...
TypeError: the given point has the wrong dimensions
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 > 0 for e in eigenvalues(point)])
+ 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):
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
>>> (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 has the wrong dimensions
"""
- return all([p in f for (p,f) in zip(point, self.factors())])
-
-
- def contains_strict(self, point):
- """
- Return whether or not ``point`` belongs to the interior
- of 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 the interior of its corresponding factor,
- then the whole point belongs to the interior of 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 the interior of 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
- --------
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict((matrix([1,2,3]), matrix([1,0.5,0.5])))
- True
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict((matrix([0,0,0]), matrix([1,0,1])))
- False
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict((matrix([1,1,1]), matrix([1,1,1])))
- False
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict((matrix([1,-1,1]), matrix([1,0,1])))
- False
-
- >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
- >>> K.contains_strict([[1,2,3],[4,5,6]])
- 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([3,4,5,6])))
- Traceback (most recent call last):
- ...
- TypeError: the given point has the wrong dimensions
-
- """
- return all([f.contains_strict(p)
- for (p,f) in zip(point, self.factors())])
+ return all([p in f for (p, f) in zip(point, self.factors())])
projects / dunshire.git / blobdiff