]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/cones.py
764e1daa528d594897a5017164b6c2012ed003cc
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.
33 def __init__(self
, dimension
):
35 A generic constructor for symmetric cones.
38 raise ValueError('cones must have dimension greater than zero')
40 self
._dimension
= dimension
43 def __contains__(self
, point
):
45 Return whether or not ``point`` belongs to this cone.
51 The point to test for membership in this cone.
57 Always, this method must be implemented in subclasses.
62 >>> K = SymmetricCone(5)
63 >>> matrix([1,2]) in K
64 Traceback (most recent call last):
69 raise NotImplementedError
72 def contains_strict(self
, point
):
74 Return whether or not ``point`` belongs to the interior
81 The point to test for strict membership in this cone.
87 Always, this method must be implemented in subclasses.
92 >>> K = SymmetricCone(5)
93 >>> K.contains_strict(matrix([1,2]))
94 Traceback (most recent call last):
98 raise NotImplementedError
103 Return the dimension of this symmetric cone.
105 The dimension of this symmetric cone is recorded during its
106 creation. This method simply returns the recorded value, and
107 should not need to be overridden in subclasses. We prefer to do
108 any special computation in ``__init__()`` and record the result
109 in ``self._dimension``.
115 The stored dimension (from when this cone was constructed)
121 >>> K = SymmetricCone(5)
126 return self
._dimension
129 class NonnegativeOrthant(SymmetricCone
):
131 The nonnegative orthant in the given number of dimensions.
136 >>> K = NonnegativeOrthant(3)
138 Nonnegative orthant in the real 3-space
143 Output a human-readable description of myself.
145 tpl
= 'Nonnegative orthant in the real {:d}-space'
146 return tpl
.format(self
.dimension())
149 def __contains__(self
, point
):
151 Return whether or not ``point`` belongs to this cone.
157 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
158 where ``n`` is the :meth:`dimension` of this cone.
165 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
171 If ``point`` is not a :class:`cvxopt.base.matrix`.
174 If ``point`` has the wrong dimensions.
179 >>> K = NonnegativeOrthant(3)
180 >>> matrix([1,2,3]) in K
183 >>> K = NonnegativeOrthant(3)
184 >>> matrix([1,-0.1,3]) in K
187 >>> K = NonnegativeOrthant(3)
189 Traceback (most recent call last):
191 TypeError: the given point is not a cvxopt.base.matrix
193 >>> K = NonnegativeOrthant(3)
194 >>> matrix([1,2]) in K
195 Traceback (most recent call last):
197 TypeError: the given point has the wrong dimensions
200 if not isinstance(point
, matrix
):
201 raise TypeError('the given point is not a cvxopt.base.matrix')
202 if not point
.size
== (self
.dimension(), 1):
203 raise TypeError('the given point has the wrong dimensions')
205 return all([x
>= 0 for x
in point
])
208 def contains_strict(self
, point
):
210 Return whether or not ``point`` belongs to the interior of this
217 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
218 where ``n`` is the :meth:`dimension` of this cone.
225 ``True`` if ``point`` belongs to the interior of this cone,
232 If ``point`` is not a :class:`cvxopt.base.matrix`.
235 If ``point`` has the wrong dimensions.
240 >>> K = NonnegativeOrthant(3)
241 >>> K.contains_strict(matrix([1,2,3]))
244 >>> K = NonnegativeOrthant(3)
245 >>> K.contains_strict(matrix([1,0,1]))
248 >>> K = NonnegativeOrthant(3)
249 >>> K.contains_strict(matrix([1,-0.1,3]))
252 >>> K = NonnegativeOrthant(3)
253 >>> K.contains_strict([1,2,3])
254 Traceback (most recent call last):
256 TypeError: the given point is not a cvxopt.base.matrix
258 >>> K = NonnegativeOrthant(3)
259 >>> K.contains_strict(matrix([1,2]))
260 Traceback (most recent call last):
262 TypeError: the given point has the wrong dimensions
265 if not isinstance(point
, matrix
):
266 raise TypeError('the given point is not a cvxopt.base.matrix')
267 if not point
.size
== (self
.dimension(), 1):
268 raise TypeError('the given point has the wrong dimensions')
270 return all([x
> 0 for x
in point
])
274 class IceCream(SymmetricCone
):
276 The Lorentz "ice cream" cone in the given number of dimensions.
283 Lorentz "ice cream" cone in the real 3-space
288 Output a human-readable description of myself.
290 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
291 return tpl
.format(self
.dimension())
294 def __contains__(self
, point
):
296 Return whether or not ``point`` belongs to this cone.
302 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
303 where ``n`` is the :meth:`dimension` of this cone.
310 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
316 If ``point`` is not a :class:`cvxopt.base.matrix`.
319 If ``point`` has the wrong dimensions.
325 >>> matrix([1,0.5,0.5]) in K
329 >>> matrix([1,0,1]) in K
333 >>> matrix([1,1,1]) in K
338 Traceback (most recent call last):
340 TypeError: the given point is not a cvxopt.base.matrix
343 >>> matrix([1,2]) in K
344 Traceback (most recent call last):
346 TypeError: the given point has the wrong dimensions
349 if not isinstance(point
, matrix
):
350 raise TypeError('the given point is not a cvxopt.base.matrix')
351 if not point
.size
== (self
.dimension(), 1):
352 raise TypeError('the given point has the wrong dimensions')
355 if self
.dimension() == 1:
356 # In one dimension, the ice cream cone is the nonnegative
361 return height
>= norm(radius
)
364 def contains_strict(self
, point
):
366 Return whether or not ``point`` belongs to the interior
373 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
374 where ``n`` is the :meth:`dimension` of this cone.
381 ``True`` if ``point`` belongs to the interior of this cone,
388 If ``point`` is not a :class:`cvxopt.base.matrix`.
391 If ``point`` has the wrong dimensions.
397 >>> K.contains_strict(matrix([1,0.5,0.5]))
401 >>> K.contains_strict(matrix([1,0,1]))
405 >>> K.contains_strict(matrix([1,1,1]))
409 >>> K.contains_strict([1,2,3])
410 Traceback (most recent call last):
412 TypeError: the given point is not a cvxopt.base.matrix
415 >>> K.contains_strict(matrix([1,2]))
416 Traceback (most recent call last):
418 TypeError: the given point has the wrong dimensions
421 if not isinstance(point
, matrix
):
422 raise TypeError('the given point is not a cvxopt.base.matrix')
423 if not point
.size
== (self
.dimension(), 1):
424 raise TypeError('the given point has the wrong dimensions')
427 if self
.dimension() == 1:
428 # In one dimension, the ice cream cone is the nonnegative
433 return height
> norm(radius
)
436 class SymmetricPSD(SymmetricCone
):
438 The cone of real symmetric positive-semidefinite matrices.
440 This cone has a dimension ``n`` associated with it, but we let ``n``
441 refer to the dimension of the domain of our matrices and not the
442 dimension of the (much larger) space in which the matrices
443 themselves live. In other words, our ``n`` is the ``n`` that appears
444 in the usual notation `S^{n}` for symmetric matrices.
446 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
452 >>> K = SymmetricPSD(3)
454 Cone of symmetric positive-semidefinite matrices on the real 3-space
461 Output a human-readable description of myself.
463 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
464 'on the real {:d}-space'
465 return tpl
.format(self
.dimension())
468 def __contains__(self
, point
):
470 Return whether or not ``point`` belongs to this cone.
476 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
477 where ``n`` is the :meth:`dimension` of this cone.
484 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
490 If ``point`` is not a :class:`cvxopt.base.matrix`.
493 If ``point`` has the wrong dimensions.
498 >>> K = SymmetricPSD(2)
499 >>> matrix([[1,0],[0,1]]) in K
502 >>> K = SymmetricPSD(2)
503 >>> matrix([[0,0],[0,0]]) in K
506 >>> K = SymmetricPSD(3)
507 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
510 >>> K = SymmetricPSD(5)
511 >>> A = matrix([[5,4,3,2,1],
519 >>> K = SymmetricPSD(5)
520 >>> A = matrix([[1,0,0,0,0],
528 >>> K = SymmetricPSD(2)
529 >>> [[1,2],[2,3]] in K
530 Traceback (most recent call last):
532 TypeError: the given point is not a cvxopt.base.matrix
534 >>> K = SymmetricPSD(3)
535 >>> matrix([[1,2],[3,4]]) in K
536 Traceback (most recent call last):
538 TypeError: the given point has the wrong dimensions
541 if not isinstance(point
, matrix
):
542 raise TypeError('the given point is not a cvxopt.base.matrix')
543 if not point
.size
== (self
.dimension(), self
.dimension()):
544 raise TypeError('the given point has the wrong dimensions')
545 if not point
.typecode
== 'd':
546 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
547 return all([e
>= 0 for e
in eigenvalues(point
)])
550 def contains_strict(self
, point
):
552 Return whether or not ``point`` belongs to the interior
559 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
560 where ``n`` is the :meth:`dimension` of this cone.
567 ``True`` if ``point`` belongs to the interior of this cone,
574 If ``point`` is not a :class:`cvxopt.base.matrix`.
577 If ``point`` has the wrong dimensions.
582 >>> K = SymmetricPSD(2)
583 >>> K.contains_strict(matrix([[1,0],[0,1]]))
586 >>> K = SymmetricPSD(2)
587 >>> K.contains_strict(matrix([[0,0],[0,0]]))
590 >>> K = SymmetricPSD(3)
591 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
594 >>> K = SymmetricPSD(5)
595 >>> A = matrix([[5,4,3,2,1],
603 >>> K = SymmetricPSD(5)
604 >>> A = matrix([[1,0,0,0,0],
609 >>> K.contains_strict(A)
612 >>> K = SymmetricPSD(2)
613 >>> K.contains_strict([[1,2],[2,3]])
614 Traceback (most recent call last):
616 TypeError: the given point is not a cvxopt.base.matrix
618 >>> K = SymmetricPSD(3)
619 >>> K.contains_strict(matrix([[1,2],[3,4]]))
620 Traceback (most recent call last):
622 TypeError: the given point has the wrong dimensions
625 if not isinstance(point
, matrix
):
626 raise TypeError('the given point is not a cvxopt.base.matrix')
627 if not point
.size
== (self
.dimension(), self
.dimension()):
628 raise TypeError('the given point has the wrong dimensions')
629 if not point
.typecode
== 'd':
630 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
631 return all([e
> 0 for e
in eigenvalues(point
)])
634 class CartesianProduct(SymmetricCone
):
636 A cartesian product of symmetric cones, which is itself a symmetric
642 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
644 Cartesian product of dimension 5 with 2 factors:
645 * Nonnegative orthant in the real 3-space
646 * Lorentz "ice cream" cone in the real 2-space
649 def __init__(self
, *factors
):
650 my_dimension
= sum([f
.dimension() for f
in factors
])
651 super().__init
__(my_dimension
)
652 self
._factors
= factors
657 Output a human-readable description of myself.
659 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
660 tpl
+= '\n * {!s}' * len(self
.factors())
661 format_args
= [self
.dimension(), len(self
.factors())]
662 format_args
+= list(self
.factors())
663 return tpl
.format(*format_args
)
666 def __contains__(self
, point
):
668 Return whether or not ``point`` belongs to this cone.
670 The ``point`` is expected to be a tuple of points which will be
671 tested for membership in this cone's factors. If each point in
672 the tuple belongs to its corresponding factor, then the whole
673 point belongs to this cone. Otherwise, it doesn't.
678 point : tuple of matrix
679 A tuple of :class:`cvxopt.base.matrix` corresponding to the
680 :meth:`factors` of this cartesian product.
687 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
693 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
696 If any element of ``point`` has the wrong dimensions.
701 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
702 >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
705 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
706 >>> (matrix([0,0,0]), matrix([1,0,1])) in K
709 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
710 >>> (matrix([1,1,1]), matrix([1,1,1])) in K
713 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
714 >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
717 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
718 >>> [[1,2,3],[4,5,6]] in K
719 Traceback (most recent call last):
721 TypeError: the given point is not a cvxopt.base.matrix
723 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
724 >>> (matrix([1,2]), matrix([3,4,5,6])) in K
725 Traceback (most recent call last):
727 TypeError: the given point has the wrong dimensions
730 return all([p
in f
for (p
,f
) in zip(point
, self
.factors())])
733 def contains_strict(self
, point
):
735 Return whether or not ``point`` belongs to the interior
738 The ``point`` is expected to be a tuple of points which will be
739 tested for membership in this cone's factors. If each point in
740 the tuple belongs to the interior of its corresponding factor,
741 then the whole point belongs to the interior of this
742 cone. Otherwise, it doesn't.
747 point : tuple of matrix
748 A tuple of :class:`cvxopt.base.matrix` corresponding to the
749 :meth:`factors` of this cartesian product.
756 ``True`` if ``point`` belongs to the interior of this cone,
763 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
766 If any element of ``point`` has the wrong dimensions.
771 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
772 >>> K.contains_strict((matrix([1,2,3]), matrix([1,0.5,0.5])))
775 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
776 >>> K.contains_strict((matrix([0,0,0]), matrix([1,0,1])))
779 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
780 >>> K.contains_strict((matrix([1,1,1]), matrix([1,1,1])))
783 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
784 >>> K.contains_strict((matrix([1,-1,1]), matrix([1,0,1])))
787 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
788 >>> K.contains_strict([[1,2,3],[4,5,6]])
789 Traceback (most recent call last):
791 TypeError: the given point is not a cvxopt.base.matrix
793 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
794 >>> K.contains_strict((matrix([1,2]), matrix([3,4,5,6])))
795 Traceback (most recent call last):
797 TypeError: the given point has the wrong dimensions
800 return all([f
.contains_strict(p
)
801 for (p
,f
) in zip(point
, self
.factors())])
807 Return a tuple containing the factors (in order) of this
813 tuple of :class:`SymmetricCone`.
814 The factors of this cartesian product.
819 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
827 def cvxopt_dims(self
):
829 Return a dictionary of dimensions corresponding to the factors
830 of this cartesian product. The format of this dictionary is
831 described in the CVXOPT user's guide:
833 http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
839 A dimension dictionary suitable to feed to CVXOPT.
844 >>> K = CartesianProduct(NonnegativeOrthant(3),
847 >>> d = K.cvxopt_dims()
848 >>> (d['l'], d['q'], d['s'])
852 dims
= {'l':0, 'q':[], 's':[]}
853 dims
['l'] += sum([K
.dimension()
854 for K
in self
.factors()
855 if isinstance(K
, NonnegativeOrthant
)])
856 dims
['q'] = [K
.dimension()
857 for K
in self
.factors()
858 if isinstance(K
, IceCream
)]
859 dims
['s'] = [K
.dimension()
860 for K
in self
.factors()
861 if isinstance(K
, SymmetricPSD
)]