]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/cones.py
2 Class definitions for all of the symmetric cones (and their superclass,
3 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 def __init__(self
, dimension
):
23 A generic constructor for symmetric cones.
25 When constructing a single symmetric cone (i.e. not a cartesian
26 product of them), the only information that we need is its
27 dimension. We take that dimension as a parameter, and store it
32 - ``dimension`` -- the dimension of this cone.
36 raise ValueError('cones must have dimension greater than zero')
38 self
._dimension
= dimension
41 def __contains__(self
, point
):
43 Return whether or not ``point`` belongs to this cone.
47 >>> K = SymmetricCone(5)
48 >>> matrix([1,2]) in K
49 Traceback (most recent call last):
54 raise NotImplementedError
56 def contains_strict(self
, point
):
58 Return whether or not ``point`` belongs to the interior
63 >>> K = SymmetricCone(5)
64 >>> K.contains_strict(matrix([1,2]))
65 Traceback (most recent call last):
69 raise NotImplementedError
73 Return the dimension of this symmetric cone.
75 The dimension of this symmetric cone is recorded during its
76 creation. This method simply returns the recorded value, and
77 should not need to be overridden in subclasses. We prefer to do
78 any special computation in ``__init__()`` and record the result
79 in ``self._dimension``.
83 >>> K = SymmetricCone(5)
88 return self
._dimension
91 class NonnegativeOrthant(SymmetricCone
):
93 The nonnegative orthant in ``n`` dimensions.
97 >>> K = NonnegativeOrthant(3)
99 Nonnegative orthant in the real 3-space
104 Output a human-readable description of myself.
106 tpl
= 'Nonnegative orthant in the real {:d}-space'
107 return tpl
.format(self
.dimension())
109 def __contains__(self
, point
):
111 Return whether or not ``point`` belongs to this cone.
115 An instance of the ``cvxopt.base.matrix`` class having
116 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
120 >>> K = NonnegativeOrthant(3)
121 >>> matrix([1,2,3]) in K
124 >>> K = NonnegativeOrthant(3)
125 >>> matrix([1,-0.1,3]) in K
128 >>> K = NonnegativeOrthant(3)
130 Traceback (most recent call last):
132 TypeError: the given point is not a cvxopt.base.matrix
134 >>> K = NonnegativeOrthant(3)
135 >>> matrix([1,2]) in K
136 Traceback (most recent call last):
138 TypeError: the given point has the wrong dimensions
141 if not isinstance(point
, matrix
):
142 raise TypeError('the given point is not a cvxopt.base.matrix')
143 if not point
.size
== (self
.dimension(), 1):
144 raise TypeError('the given point has the wrong dimensions')
146 return all([x
>= 0 for x
in point
])
149 def contains_strict(self
, point
):
151 Return whether or not ``point`` belongs to the interior of this
156 An instance of the ``cvxopt.base.matrix`` class having
157 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
161 >>> K = NonnegativeOrthant(3)
162 >>> K.contains_strict(matrix([1,2,3]))
165 >>> K = NonnegativeOrthant(3)
166 >>> K.contains_strict(matrix([1,0,1]))
169 >>> K = NonnegativeOrthant(3)
170 >>> K.contains_strict(matrix([1,-0.1,3]))
173 >>> K = NonnegativeOrthant(3)
174 >>> K.contains_strict([1,2,3])
175 Traceback (most recent call last):
177 TypeError: the given point is not a cvxopt.base.matrix
179 >>> K = NonnegativeOrthant(3)
180 >>> K.contains_strict(matrix([1,2]))
181 Traceback (most recent call last):
183 TypeError: the given point has the wrong dimensions
186 if not isinstance(point
, matrix
):
187 raise TypeError('the given point is not a cvxopt.base.matrix')
188 if not point
.size
== (self
.dimension(), 1):
189 raise TypeError('the given point has the wrong dimensions')
191 return all([x
> 0 for x
in point
])
195 class IceCream(SymmetricCone
):
197 The nonnegative orthant in ``n`` dimensions.
203 Lorentz "ice cream" cone in the real 3-space
208 Output a human-readable description of myself.
210 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
211 return tpl
.format(self
.dimension())
214 def __contains__(self
, point
):
216 Return whether or not ``point`` belongs to this cone.
220 An instance of the ``cvxopt.base.matrix`` class having
221 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
226 >>> matrix([1,0.5,0.5]) in K
230 >>> matrix([1,0,1]) in K
234 >>> matrix([1,1,1]) in K
239 Traceback (most recent call last):
241 TypeError: the given point is not a cvxopt.base.matrix
244 >>> matrix([1,2]) in K
245 Traceback (most recent call last):
247 TypeError: the given point has the wrong dimensions
250 if not isinstance(point
, matrix
):
251 raise TypeError('the given point is not a cvxopt.base.matrix')
252 if not point
.size
== (self
.dimension(), 1):
253 raise TypeError('the given point has the wrong dimensions')
256 if self
.dimension() == 1:
257 # In one dimension, the ice cream cone is the nonnegative
262 return height
>= norm(radius
)
265 def contains_strict(self
, point
):
267 Return whether or not ``point`` belongs to the interior
272 An instance of the ``cvxopt.base.matrix`` class having
273 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
278 >>> K.contains_strict(matrix([1,0.5,0.5]))
282 >>> K.contains_strict(matrix([1,0,1]))
286 >>> K.contains_strict(matrix([1,1,1]))
290 >>> K.contains_strict([1,2,3])
291 Traceback (most recent call last):
293 TypeError: the given point is not a cvxopt.base.matrix
296 >>> K.contains_strict(matrix([1,2]))
297 Traceback (most recent call last):
299 TypeError: the given point has the wrong dimensions
302 if not isinstance(point
, matrix
):
303 raise TypeError('the given point is not a cvxopt.base.matrix')
304 if not point
.size
== (self
.dimension(), 1):
305 raise TypeError('the given point has the wrong dimensions')
308 if self
.dimension() == 1:
309 # In one dimension, the ice cream cone is the nonnegative
314 return height
> norm(radius
)
317 class SymmetricPSD(SymmetricCone
):
319 The cone of real symmetric positive-semidefinite matrices.
321 This cone has a dimension ``n`` associated with it, but we let ``n``
322 refer to the dimension of the domain of our matrices and not the
323 dimension of the (much larger) space in which the matrices
324 themselves live. In other words, our ``n`` is the ``n`` that appears
325 in the usual notation `S^{n}` for symmetric matrices.
327 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
332 >>> K = SymmetricPSD(3)
334 Cone of symmetric positive-semidefinite matrices on the real 3-space
341 Output a human-readable description of myself.
343 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
344 'on the real {:d}-space'
345 return tpl
.format(self
.dimension())
348 def __contains__(self
, point
):
350 Return whether or not ``point`` belongs to this cone.
354 An instance of the ``cvxopt.base.matrix`` class having
355 dimensions ``(n,n)`` where ``n`` is the dimension of this cone.
359 >>> K = SymmetricPSD(2)
360 >>> matrix([[1,0],[0,1]]) in K
363 >>> K = SymmetricPSD(2)
364 >>> matrix([[0,0],[0,0]]) in K
367 >>> K = SymmetricPSD(3)
368 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
371 >>> K = SymmetricPSD(5)
372 >>> A = matrix([[5,4,3,2,1],
380 >>> K = SymmetricPSD(5)
381 >>> A = matrix([[1,0,0,0,0],
389 >>> K = SymmetricPSD(2)
390 >>> [[1,2],[2,3]] in K
391 Traceback (most recent call last):
393 TypeError: the given point is not a cvxopt.base.matrix
395 >>> K = SymmetricPSD(3)
396 >>> matrix([[1,2],[3,4]]) in K
397 Traceback (most recent call last):
399 TypeError: the given point has the wrong dimensions
402 if not isinstance(point
, matrix
):
403 raise TypeError('the given point is not a cvxopt.base.matrix')
404 if not point
.size
== (self
.dimension(), self
.dimension()):
405 raise TypeError('the given point has the wrong dimensions')
406 if not point
.typecode
== 'd':
407 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
408 return all([e
>= 0 for e
in eigenvalues(point
)])
411 def contains_strict(self
, point
):
413 Return whether or not ``point`` belongs to the interior
418 An instance of the ``cvxopt.base.matrix`` class having
419 dimensions ``(n,n)`` where ``n`` is the dimension of this cone.
420 Its type code must be 'd'.
424 >>> K = SymmetricPSD(2)
425 >>> K.contains_strict(matrix([[1,0],[0,1]]))
428 >>> K = SymmetricPSD(2)
429 >>> K.contains_strict(matrix([[0,0],[0,0]]))
432 >>> K = SymmetricPSD(3)
433 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
436 >>> K = SymmetricPSD(5)
437 >>> A = matrix([[5,4,3,2,1],
445 >>> K = SymmetricPSD(5)
446 >>> A = matrix([[1,0,0,0,0],
451 >>> K.contains_strict(A)
454 >>> K = SymmetricPSD(2)
455 >>> K.contains_strict([[1,2],[2,3]])
456 Traceback (most recent call last):
458 TypeError: the given point is not a cvxopt.base.matrix
460 >>> K = SymmetricPSD(3)
461 >>> K.contains_strict(matrix([[1,2],[3,4]]))
462 Traceback (most recent call last):
464 TypeError: the given point has the wrong dimensions
467 if not isinstance(point
, matrix
):
468 raise TypeError('the given point is not a cvxopt.base.matrix')
469 if not point
.size
== (self
.dimension(), self
.dimension()):
470 raise TypeError('the given point has the wrong dimensions')
471 if not point
.typecode
== 'd':
472 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
473 return all([e
> 0 for e
in eigenvalues(point
)])
476 class CartesianProduct(SymmetricCone
):
478 A cartesian product of symmetric cones, which is itself a symmetric
483 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
485 Cartesian product of dimension 5 with 2 factors:
486 * Nonnegative orthant in the real 3-space
487 * Lorentz "ice cream" cone in the real 2-space
490 def __init__(self
, *factors
):
491 my_dimension
= sum([f
.dimension() for f
in factors
])
492 super().__init
__(my_dimension
)
493 self
._factors
= factors
497 Output a human-readable description of myself.
499 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
500 tpl
+= '\n * {!s}' * len(self
.factors())
501 format_args
= [self
.dimension(), len(self
.factors())]
502 format_args
+= list(self
.factors())
503 return tpl
.format(*format_args
)
505 def __contains__(self
, point
):
507 Return whether or not ``point`` belongs to this cone.
511 An instance of the ``cvxopt.base.matrix`` class having
512 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
516 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
517 >>> matrix([1,2,3,1,0.5,0.5]) in K
520 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
521 >>> matrix([0,0,0,1,0,1]) in K
524 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
525 >>> matrix([1,1,1,1,1,1]) in K
528 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
529 >>> matrix([1,-1,1,1,0,1]) in K
532 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
533 >>> [1,2,3,4,5,6] in K
534 Traceback (most recent call last):
536 TypeError: the given point is not a cvxopt.base.matrix
538 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
539 >>> matrix([1,2]) in K
540 Traceback (most recent call last):
542 TypeError: the given point has the wrong dimensions
545 if not isinstance(point
, matrix
):
546 raise TypeError('the given point is not a cvxopt.base.matrix')
547 if not point
.size
== (self
.dimension(), 1):
548 raise TypeError('the given point has the wrong dimensions')
550 for factor
in self
.factors():
551 # Split off the components of ``point`` corresponding to
553 factor_part
= point
[0:factor
.dimension()]
554 if not factor_part
in factor
:
556 point
= point
[factor
.dimension():]
561 def contains_strict(self
, point
):
563 Return whether or not ``point`` belongs to the interior
568 An instance of the ``cvxopt.base.matrix`` class having
569 dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
573 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
574 >>> K.contains_strict(matrix([1,2,3,1,0.5,0.5]))
577 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
578 >>> K.contains_strict(matrix([1,2,3,1,0,1]))
581 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
582 >>> K.contains_strict(matrix([0,1,1,1,0.5,0.5]))
585 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
586 >>> K.contains_strict(matrix([1,1,1,1,1,1]))
589 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
590 >>> K.contains_strict(matrix([1,-1,1,1,0,1]))
593 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
594 >>> K.contains_strict([1,2,3,4,5,6])
595 Traceback (most recent call last):
597 TypeError: the given point is not a cvxopt.base.matrix
599 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
600 >>> K.contains_strict(matrix([1,2]))
601 Traceback (most recent call last):
603 TypeError: the given point has the wrong dimensions
606 if not isinstance(point
, matrix
):
607 raise TypeError('the given point is not a cvxopt.base.matrix')
608 if not point
.size
== (self
.dimension(), 1):
609 raise TypeError('the given point has the wrong dimensions')
611 for factor
in self
.factors():
612 # Split off the components of ``point`` corresponding to
614 factor_part
= point
[0:factor
.dimension()]
615 if not factor
.contains_strict(factor_part
):
617 point
= point
[factor
.dimension():]
624 Return a tuple containing the factors (in order) of this
629 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
636 def cvxopt_dims(self
):
638 Return a dictionary of dimensions corresponding to the factors
639 of this cartesian product. The format of this dictionary is
640 described in the CVXOPT user's guide:
642 http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
646 >>> K = CartesianProduct(NonnegativeOrthant(3),
649 >>> d = K.cvxopt_dims()
650 >>> (d['l'], d['q'], d['s'])
654 dims
= {'l':0, 'q':[], 's':[]}
655 dims
['l'] += sum([K
.dimension()
656 for K
in self
.factors()
657 if isinstance(K
, NonnegativeOrthant
)])
658 dims
['q'] = [K
.dimension()
659 for K
in self
.factors()
660 if isinstance(K
, IceCream
)]
661 dims
['s'] = [K
.dimension()
662 for K
in self
.factors()
663 if isinstance(K
, SymmetricPSD
)]