]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/cones.py
905dd8edf7092b83ef7c1275b2a09430f18c10e1
2 Class definitions for all of the symmetric cones (and their superclass,
3 :class:`SymmetricCone`) supported by CVXOPT.
6 from cvxopt
import matrix
7 from matrices
import eigenvalues
, norm
11 An instance of a symmetric (self-dual and homogeneous) cone.
13 There are three types of symmetric cones supported by CVXOPT:
15 1. The nonnegative orthant in the real n-space.
16 2. The Lorentz "ice cream" cone, or the second-order cone.
17 3. The cone of symmetric positive-semidefinite matrices.
19 This class is intended to encompass them all.
21 When constructing a single symmetric cone (i.e. not a
22 :class:`CartesianProduct` of them), the only information that we
23 need is its dimension. We take that dimension as a parameter, and
30 The dimension of this cone.
36 If you try to create a cone with dimension zero or less.
39 def __init__(self
, dimension
):
41 A generic constructor for symmetric cones.
44 raise ValueError('cones must have dimension greater than zero')
46 self
._dimension
= dimension
49 def __contains__(self
, point
):
51 Return whether or not ``point`` belongs to this cone.
57 The point to test for membership in this cone.
63 Always, this method must be implemented in subclasses.
68 >>> K = SymmetricCone(5)
69 >>> matrix([1,2]) in K
70 Traceback (most recent call last):
75 raise NotImplementedError
78 def contains_strict(self
, point
):
80 Return whether or not ``point`` belongs to the interior
87 The point to test for strict membership in this cone.
93 Always, this method must be implemented in subclasses.
98 >>> K = SymmetricCone(5)
99 >>> K.contains_strict(matrix([1,2]))
100 Traceback (most recent call last):
104 raise NotImplementedError
109 Return the dimension of this symmetric cone.
111 The dimension of this symmetric cone is recorded during its
112 creation. This method simply returns the recorded value, and
113 should not need to be overridden in subclasses. We prefer to do
114 any special computation in ``__init__()`` and record the result
115 in ``self._dimension``.
121 The stored dimension (from when this cone was constructed)
127 >>> K = SymmetricCone(5)
132 return self
._dimension
135 class NonnegativeOrthant(SymmetricCone
):
137 The nonnegative orthant in the given number of dimensions.
142 >>> K = NonnegativeOrthant(3)
144 Nonnegative orthant in the real 3-space
149 Output a human-readable description of myself.
151 tpl
= 'Nonnegative orthant in the real {:d}-space'
152 return tpl
.format(self
.dimension())
155 def __contains__(self
, point
):
157 Return whether or not ``point`` belongs to this cone.
163 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
164 where ``n`` is the :meth:`dimension` of this cone.
171 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
177 If ``point`` is not a :class:`cvxopt.base.matrix`.
180 If ``point`` has the wrong dimensions.
185 >>> K = NonnegativeOrthant(3)
186 >>> matrix([1,2,3]) in K
189 >>> K = NonnegativeOrthant(3)
190 >>> matrix([1,-0.1,3]) in K
193 >>> K = NonnegativeOrthant(3)
195 Traceback (most recent call last):
197 TypeError: the given point is not a cvxopt.base.matrix
199 >>> K = NonnegativeOrthant(3)
200 >>> matrix([1,2]) in K
201 Traceback (most recent call last):
203 TypeError: the given point has the wrong dimensions
206 if not isinstance(point
, matrix
):
207 raise TypeError('the given point is not a cvxopt.base.matrix')
208 if not point
.size
== (self
.dimension(), 1):
209 raise TypeError('the given point has the wrong dimensions')
211 return all([x
>= 0 for x
in point
])
214 def contains_strict(self
, point
):
216 Return whether or not ``point`` belongs to the interior of this
223 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
224 where ``n`` is the :meth:`dimension` of this cone.
231 ``True`` if ``point`` belongs to the interior of this cone,
238 If ``point`` is not a :class:`cvxopt.base.matrix`.
241 If ``point`` has the wrong dimensions.
246 >>> K = NonnegativeOrthant(3)
247 >>> K.contains_strict(matrix([1,2,3]))
250 >>> K = NonnegativeOrthant(3)
251 >>> K.contains_strict(matrix([1,0,1]))
254 >>> K = NonnegativeOrthant(3)
255 >>> K.contains_strict(matrix([1,-0.1,3]))
258 >>> K = NonnegativeOrthant(3)
259 >>> K.contains_strict([1,2,3])
260 Traceback (most recent call last):
262 TypeError: the given point is not a cvxopt.base.matrix
264 >>> K = NonnegativeOrthant(3)
265 >>> K.contains_strict(matrix([1,2]))
266 Traceback (most recent call last):
268 TypeError: the given point has the wrong dimensions
271 if not isinstance(point
, matrix
):
272 raise TypeError('the given point is not a cvxopt.base.matrix')
273 if not point
.size
== (self
.dimension(), 1):
274 raise TypeError('the given point has the wrong dimensions')
276 return all([x
> 0 for x
in point
])
280 class IceCream(SymmetricCone
):
282 The Lorentz "ice cream" cone in the given number of dimensions.
289 Lorentz "ice cream" cone in the real 3-space
294 Output a human-readable description of myself.
296 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
297 return tpl
.format(self
.dimension())
300 def __contains__(self
, point
):
302 Return whether or not ``point`` belongs to this cone.
308 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
309 where ``n`` is the :meth:`dimension` of this cone.
316 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
322 If ``point`` is not a :class:`cvxopt.base.matrix`.
325 If ``point`` has the wrong dimensions.
331 >>> matrix([1,0.5,0.5]) in K
335 >>> matrix([1,0,1]) in K
339 >>> matrix([1,1,1]) in K
344 Traceback (most recent call last):
346 TypeError: the given point is not a cvxopt.base.matrix
349 >>> matrix([1,2]) in K
350 Traceback (most recent call last):
352 TypeError: the given point has the wrong dimensions
355 if not isinstance(point
, matrix
):
356 raise TypeError('the given point is not a cvxopt.base.matrix')
357 if not point
.size
== (self
.dimension(), 1):
358 raise TypeError('the given point has the wrong dimensions')
361 if self
.dimension() == 1:
362 # In one dimension, the ice cream cone is the nonnegative
367 return height
>= norm(radius
)
370 def contains_strict(self
, point
):
372 Return whether or not ``point`` belongs to the interior
379 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
380 where ``n`` is the :meth:`dimension` of this cone.
387 ``True`` if ``point`` belongs to the interior of this cone,
394 If ``point`` is not a :class:`cvxopt.base.matrix`.
397 If ``point`` has the wrong dimensions.
403 >>> K.contains_strict(matrix([1,0.5,0.5]))
407 >>> K.contains_strict(matrix([1,0,1]))
411 >>> K.contains_strict(matrix([1,1,1]))
415 >>> K.contains_strict([1,2,3])
416 Traceback (most recent call last):
418 TypeError: the given point is not a cvxopt.base.matrix
421 >>> K.contains_strict(matrix([1,2]))
422 Traceback (most recent call last):
424 TypeError: the given point has the wrong dimensions
427 if not isinstance(point
, matrix
):
428 raise TypeError('the given point is not a cvxopt.base.matrix')
429 if not point
.size
== (self
.dimension(), 1):
430 raise TypeError('the given point has the wrong dimensions')
433 if self
.dimension() == 1:
434 # In one dimension, the ice cream cone is the nonnegative
439 return height
> norm(radius
)
442 class SymmetricPSD(SymmetricCone
):
444 The cone of real symmetric positive-semidefinite matrices.
446 This cone has a dimension ``n`` associated with it, but we let ``n``
447 refer to the dimension of the domain of our matrices and not the
448 dimension of the (much larger) space in which the matrices
449 themselves live. In other words, our ``n`` is the ``n`` that appears
450 in the usual notation :math:`S^{n}` for symmetric matrices.
452 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
453 :math:`\left(n^{2} + n\right)/2)`.
458 >>> K = SymmetricPSD(3)
460 Cone of symmetric positive-semidefinite matrices on the real 3-space
467 Output a human-readable description of myself.
469 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
470 'on the real {:d}-space'
471 return tpl
.format(self
.dimension())
474 def __contains__(self
, point
):
476 Return whether or not ``point`` belongs to this cone.
482 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
483 where ``n`` is the :meth:`dimension` of this cone.
490 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
496 If ``point`` is not a :class:`cvxopt.base.matrix`.
499 If ``point`` has the wrong dimensions.
504 >>> K = SymmetricPSD(2)
505 >>> matrix([[1,0],[0,1]]) in K
508 >>> K = SymmetricPSD(2)
509 >>> matrix([[0,0],[0,0]]) in K
512 >>> K = SymmetricPSD(3)
513 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
516 >>> K = SymmetricPSD(5)
517 >>> A = matrix([[5,4,3,2,1],
525 >>> K = SymmetricPSD(5)
526 >>> A = matrix([[1,0,0,0,0],
534 >>> K = SymmetricPSD(2)
535 >>> [[1,2],[2,3]] in K
536 Traceback (most recent call last):
538 TypeError: the given point is not a cvxopt.base.matrix
540 >>> K = SymmetricPSD(3)
541 >>> matrix([[1,2],[3,4]]) in K
542 Traceback (most recent call last):
544 TypeError: the given point has the wrong dimensions
547 if not isinstance(point
, matrix
):
548 raise TypeError('the given point is not a cvxopt.base.matrix')
549 if not point
.size
== (self
.dimension(), self
.dimension()):
550 raise TypeError('the given point has the wrong dimensions')
551 if not point
.typecode
== 'd':
552 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
553 return all([e
>= 0 for e
in eigenvalues(point
)])
556 def contains_strict(self
, point
):
558 Return whether or not ``point`` belongs to the interior
565 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
566 where ``n`` is the :meth:`dimension` of this cone.
573 ``True`` if ``point`` belongs to the interior of this cone,
580 If ``point`` is not a :class:`cvxopt.base.matrix`.
583 If ``point`` has the wrong dimensions.
588 >>> K = SymmetricPSD(2)
589 >>> K.contains_strict(matrix([[1,0],[0,1]]))
592 >>> K = SymmetricPSD(2)
593 >>> K.contains_strict(matrix([[0,0],[0,0]]))
596 >>> K = SymmetricPSD(3)
597 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
600 >>> K = SymmetricPSD(5)
601 >>> A = matrix([[5,4,3,2,1],
609 >>> K = SymmetricPSD(5)
610 >>> A = matrix([[1,0,0,0,0],
615 >>> K.contains_strict(A)
618 >>> K = SymmetricPSD(2)
619 >>> K.contains_strict([[1,2],[2,3]])
620 Traceback (most recent call last):
622 TypeError: the given point is not a cvxopt.base.matrix
624 >>> K = SymmetricPSD(3)
625 >>> K.contains_strict(matrix([[1,2],[3,4]]))
626 Traceback (most recent call last):
628 TypeError: the given point has the wrong dimensions
631 if not isinstance(point
, matrix
):
632 raise TypeError('the given point is not a cvxopt.base.matrix')
633 if not point
.size
== (self
.dimension(), self
.dimension()):
634 raise TypeError('the given point has the wrong dimensions')
635 if not point
.typecode
== 'd':
636 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
637 return all([e
> 0 for e
in eigenvalues(point
)])
640 class CartesianProduct(SymmetricCone
):
642 A cartesian product of symmetric cones, which is itself a symmetric
648 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
650 Cartesian product of dimension 5 with 2 factors:
651 * Nonnegative orthant in the real 3-space
652 * Lorentz "ice cream" cone in the real 2-space
655 def __init__(self
, *factors
):
656 my_dimension
= sum([f
.dimension() for f
in factors
])
657 super().__init
__(my_dimension
)
658 self
._factors
= factors
663 Output a human-readable description of myself.
665 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
666 tpl
+= '\n * {!s}' * len(self
.factors())
667 format_args
= [self
.dimension(), len(self
.factors())]
668 format_args
+= list(self
.factors())
669 return tpl
.format(*format_args
)
672 def __contains__(self
, point
):
674 Return whether or not ``point`` belongs to this cone.
676 The ``point`` is expected to be a tuple of points which will be
677 tested for membership in this cone's factors. If each point in
678 the tuple belongs to its corresponding factor, then the whole
679 point belongs to this cone. Otherwise, it doesn't.
684 point : tuple of matrix
685 A tuple of :class:`cvxopt.base.matrix` corresponding to the
686 :meth:`factors` of this cartesian product.
693 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
699 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
702 If any element of ``point`` has the wrong dimensions.
707 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
708 >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
711 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
712 >>> (matrix([0,0,0]), matrix([1,0,1])) in K
715 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
716 >>> (matrix([1,1,1]), matrix([1,1,1])) in K
719 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
720 >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
723 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
724 >>> [[1,2,3],[4,5,6]] in K
725 Traceback (most recent call last):
727 TypeError: the given point is not a cvxopt.base.matrix
729 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
730 >>> (matrix([1,2]), matrix([3,4,5,6])) in K
731 Traceback (most recent call last):
733 TypeError: the given point has the wrong dimensions
736 return all([p
in f
for (p
,f
) in zip(point
, self
.factors())])
739 def contains_strict(self
, point
):
741 Return whether or not ``point`` belongs to the interior
744 The ``point`` is expected to be a tuple of points which will be
745 tested for membership in this cone's factors. If each point in
746 the tuple belongs to the interior of its corresponding factor,
747 then the whole point belongs to the interior of this
748 cone. Otherwise, it doesn't.
753 point : tuple of matrix
754 A tuple of :class:`cvxopt.base.matrix` corresponding to the
755 :meth:`factors` of this cartesian product.
762 ``True`` if ``point`` belongs to the interior of this cone,
769 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
772 If any element of ``point`` has the wrong dimensions.
777 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
778 >>> K.contains_strict((matrix([1,2,3]), matrix([1,0.5,0.5])))
781 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
782 >>> K.contains_strict((matrix([0,0,0]), matrix([1,0,1])))
785 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
786 >>> K.contains_strict((matrix([1,1,1]), matrix([1,1,1])))
789 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
790 >>> K.contains_strict((matrix([1,-1,1]), matrix([1,0,1])))
793 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
794 >>> K.contains_strict([[1,2,3],[4,5,6]])
795 Traceback (most recent call last):
797 TypeError: the given point is not a cvxopt.base.matrix
799 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
800 >>> K.contains_strict((matrix([1,2]), matrix([3,4,5,6])))
801 Traceback (most recent call last):
803 TypeError: the given point has the wrong dimensions
806 return all([f
.contains_strict(p
)
807 for (p
,f
) in zip(point
, self
.factors())])
813 Return a tuple containing the factors (in order) of this
819 tuple of :class:`SymmetricCone`.
820 The factors of this cartesian product.
825 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
833 def cvxopt_dims(self
):
835 Return a dictionary of dimensions corresponding to the factors
836 of this cartesian product. The format of this dictionary is
837 described in the CVXOPT user's guide:
839 http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
845 A dimension dictionary suitable to feed to CVXOPT.
850 >>> K = CartesianProduct(NonnegativeOrthant(3),
853 >>> d = K.cvxopt_dims()
854 >>> (d['l'], d['q'], d['s'])
858 dims
= {'l':0, 'q':[], 's':[]}
859 dims
['l'] += sum([K
.dimension()
860 for K
in self
.factors()
861 if isinstance(K
, NonnegativeOrthant
)])
862 dims
['q'] = [K
.dimension()
863 for K
in self
.factors()
864 if isinstance(K
, IceCream
)]
865 dims
['s'] = [K
.dimension()
866 for K
in self
.factors()
867 if isinstance(K
, SymmetricPSD
)]