]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/cones.py
d7c9b62e02314e1b637a3c1caf00f1d68612b050
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
12 An instance of a symmetric (self-dual and homogeneous) cone.
14 There are three types of symmetric cones supported by CVXOPT:
16 1. The nonnegative orthant in the real n-space.
17 2. The Lorentz "ice cream" cone, or the second-order cone.
18 3. The cone of symmetric positive-semidefinite matrices.
20 This class is intended to encompass them all.
22 When constructing a single symmetric cone (i.e. not a
23 :class:`CartesianProduct` of them), the only information that we
24 need is its dimension. We take that dimension as a parameter, and
31 The dimension of this cone.
37 If you try to create a cone with dimension zero or less.
40 def __init__(self
, dimension
):
42 A generic constructor for symmetric cones.
45 raise ValueError('cones must have dimension greater than zero')
47 self
._dimension
= dimension
50 def __contains__(self
, point
):
52 Return whether or not ``point`` belongs to this cone.
58 The point to test for membership in this cone.
64 Always, this method must be implemented in subclasses.
69 >>> K = SymmetricCone(5)
70 >>> matrix([1,2]) in K
71 Traceback (most recent call last):
76 raise NotImplementedError
82 Return the dimension of this symmetric cone.
84 The dimension of this symmetric cone is recorded during its
85 creation. This method simply returns the recorded value, and
86 should not need to be overridden in subclasses. We prefer to do
87 any special computation in ``__init__()`` and record the result
88 in ``self._dimension``.
94 The stored dimension (from when this cone was constructed)
100 >>> K = SymmetricCone(5)
105 return self
._dimension
108 class NonnegativeOrthant(SymmetricCone
):
110 The nonnegative orthant in the given number of dimensions.
115 >>> K = NonnegativeOrthant(3)
117 Nonnegative orthant in the real 3-space
122 Output a human-readable description of myself.
124 tpl
= 'Nonnegative orthant in the real {:d}-space'
125 return tpl
.format(self
.dimension())
128 def __contains__(self
, point
):
130 Return whether or not ``point`` belongs to this cone.
132 Since this test is expected to work on points whose components
133 are floating point numbers, it doesn't make any sense to
134 distinguish between strict and non-strict containment -- the
135 test uses a tolerance parameter.
137 This test will err on the side of caution, and return ``True``
138 only when the ``point`` lies inside this cone *past* the
139 tolerance guarantee. That means if you ask whether or not a
140 boundary point lies in this cone, you will get ``False`` as your
147 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
148 where ``n`` is the :meth:`dimension` of this cone.
155 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
161 If ``point`` is not a :class:`cvxopt.base.matrix`.
164 If ``point`` has the wrong dimensions.
169 All of these coordinates are positive enough:
171 >>> K = NonnegativeOrthant(3)
172 >>> matrix([1,2,3]) in K
175 The one negative coordinate pushes this point outside of ``K``:
177 >>> K = NonnegativeOrthant(3)
178 >>> matrix([1,-0.1,3]) in K
181 However, not even a boundary point is considered inside of ``K``:
182 >>> K = NonnegativeOrthant(3)
183 >>> matrix([1,0,3]) in K
186 Junk arguments don't work:
188 >>> K = NonnegativeOrthant(3)
190 Traceback (most recent call last):
192 TypeError: the given point is not a cvxopt.base.matrix
194 >>> K = NonnegativeOrthant(3)
195 >>> matrix([1,2]) in K
196 Traceback (most recent call last):
198 TypeError: the given point has the wrong dimensions
201 if not isinstance(point
, matrix
):
202 raise TypeError('the given point is not a cvxopt.base.matrix')
203 if not point
.size
== (self
.dimension(), 1):
204 raise TypeError('the given point has the wrong dimensions')
206 return all([x
> options
.ABS_TOL
for x
in point
])
210 class IceCream(SymmetricCone
):
212 The Lorentz "ice cream" cone in the given number of dimensions.
219 Lorentz "ice cream" cone in the real 3-space
224 Output a human-readable description of myself.
226 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
227 return tpl
.format(self
.dimension())
230 def __contains__(self
, point
):
232 Return whether or not ``point`` belongs to this cone.
234 Since this test is expected to work on points whose components
235 are floating point numbers, it doesn't make any sense to
236 distinguish between strict and non-strict containment -- the
237 test uses a tolerance parameter.
239 This test will err on the side of caution, and return ``True``
240 only when the ``point`` lies inside this cone *past* the
241 tolerance guarantee. That means if you ask whether or not a
242 boundary point lies in this cone, you will get ``False`` as your
249 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
250 where ``n`` is the :meth:`dimension` of this cone.
257 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
263 If ``point`` is not a :class:`cvxopt.base.matrix`.
266 If ``point`` has the wrong dimensions.
271 This point lies well within the ice cream cone:
274 >>> matrix([1,0.5,0.5]) in K
277 But this one lies on its boundary and runs foul of the tolerance:
280 >>> matrix([1,0,1]) in K
283 This point lies entirely outside of the ice cream cone:
286 >>> matrix([1,1,1]) in K
289 Junk arguments don't work:
293 Traceback (most recent call last):
295 TypeError: the given point is not a cvxopt.base.matrix
298 >>> matrix([1,2]) in K
299 Traceback (most recent call last):
301 TypeError: the given point has the wrong dimensions
304 if not isinstance(point
, matrix
):
305 raise TypeError('the given point is not a cvxopt.base.matrix')
306 if not point
.size
== (self
.dimension(), 1):
307 raise TypeError('the given point has the wrong dimensions')
310 if self
.dimension() == 1:
311 # In one dimension, the ice cream cone is the nonnegative
313 return height
> options
.ABS_TOL
316 return norm(radius
) < (height
- options
.ABS_TOL
)
320 class SymmetricPSD(SymmetricCone
):
322 The cone of real symmetric positive-semidefinite matrices.
324 This cone has a dimension ``n`` associated with it, but we let ``n``
325 refer to the dimension of the domain of our matrices and not the
326 dimension of the (much larger) space in which the matrices
327 themselves live. In other words, our ``n`` is the ``n`` that appears
328 in the usual notation :math:`S^{n}` for symmetric matrices.
330 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
331 :math:`\left(n^{2} + n\right)/2)`.
336 >>> K = SymmetricPSD(3)
338 Cone of symmetric positive-semidefinite matrices on the real 3-space
345 Output a human-readable description of myself.
347 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
348 'on the real {:d}-space'
349 return tpl
.format(self
.dimension())
352 def __contains__(self
, point
):
354 Return whether or not ``point`` belongs to this cone.
356 Since this test is expected to work on points whose components
357 are floating point numbers, it doesn't make any sense to
358 distinguish between strict and non-strict containment -- the
359 test uses a tolerance parameter.
361 This test will err on the side of caution, and return ``True``
362 only when the ``point`` lies inside this cone *past* the
363 tolerance guarantee. That means if you ask whether or not a
364 boundary point lies in this cone, you will get ``False`` as your
371 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
372 where ``n`` is the :meth:`dimension` of this cone.
379 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
385 If ``point`` is not a :class:`cvxopt.base.matrix`.
388 If ``point`` has the wrong dimensions.
393 These all lie in the interior of the Symmetric PSD cone:
395 >>> K = SymmetricPSD(2)
396 >>> matrix([[1,0],[0,1]]) in K
399 >>> K = SymmetricPSD(3)
400 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
403 >>> K = SymmetricPSD(5)
404 >>> A = matrix([[5,4,3,2,1],
412 But any matrix with a zero eigenvalue will lie on the boundary
413 of the Symmetric PSD cone and run foul of our tolerance:
415 >>> K = SymmetricPSD(2)
416 >>> matrix([[0,0],[0,0]]) in K
419 >>> K = SymmetricPSD(5)
420 >>> A = matrix([[1,0,0,0,0],
428 Junk arguments don't work:
430 >>> K = SymmetricPSD(2)
431 >>> [[1,2],[2,3]] in K
432 Traceback (most recent call last):
434 TypeError: the given point is not a cvxopt.base.matrix
436 >>> K = SymmetricPSD(3)
437 >>> matrix([[1,2],[3,4]]) in K
438 Traceback (most recent call last):
440 TypeError: the given point has the wrong dimensions
443 if not isinstance(point
, matrix
):
444 raise TypeError('the given point is not a cvxopt.base.matrix')
445 if not point
.size
== (self
.dimension(), self
.dimension()):
446 raise TypeError('the given point has the wrong dimensions')
447 if not point
.typecode
== 'd':
448 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
449 return all([e
> options
.ABS_TOL
for e
in eigenvalues(point
)])
453 class CartesianProduct(SymmetricCone
):
455 A cartesian product of symmetric cones, which is itself a symmetric
461 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
463 Cartesian product of dimension 5 with 2 factors:
464 * Nonnegative orthant in the real 3-space
465 * Lorentz "ice cream" cone in the real 2-space
468 def __init__(self
, *factors
):
469 my_dimension
= sum([f
.dimension() for f
in factors
])
470 super().__init
__(my_dimension
)
471 self
._factors
= factors
476 Output a human-readable description of myself.
478 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
479 tpl
+= '\n * {!s}' * len(self
.factors())
480 format_args
= [self
.dimension(), len(self
.factors())]
481 format_args
+= list(self
.factors())
482 return tpl
.format(*format_args
)
485 def __contains__(self
, point
):
487 Return whether or not ``point`` belongs to this cone.
489 The ``point`` is expected to be a tuple of points which will be
490 tested for membership in this cone's factors. If each point in
491 the tuple belongs to its corresponding factor, then the whole
492 point belongs to this cone. Otherwise, it doesn't.
497 point : tuple of matrix
498 A tuple of :class:`cvxopt.base.matrix` corresponding to the
499 :meth:`factors` of this cartesian product.
506 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
512 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
515 If any element of ``point`` has the wrong dimensions.
520 The result depends on how containment is defined for our factors:
522 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
523 >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
526 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
527 >>> (matrix([0,0,0]), matrix([1,0,1])) in K
530 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
531 >>> (matrix([1,1,1]), matrix([1,1,1])) in K
534 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
535 >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
538 Junk arguments don't work:
540 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
541 >>> [[1,2,3],[4,5,6]] in K
542 Traceback (most recent call last):
544 TypeError: the given point is not a cvxopt.base.matrix
546 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
547 >>> (matrix([1,2]), matrix([3,4,5,6])) in K
548 Traceback (most recent call last):
550 TypeError: the given point has the wrong dimensions
553 return all([p
in f
for (p
,f
) in zip(point
, self
.factors())])
559 Return a tuple containing the factors (in order) of this
565 tuple of :class:`SymmetricCone`.
566 The factors of this cartesian product.
571 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
579 def cvxopt_dims(self
):
581 Return a dictionary of dimensions corresponding to the factors
582 of this cartesian product. The format of this dictionary is
583 described in the CVXOPT user's guide:
585 http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
591 A dimension dictionary suitable to feed to CVXOPT.
596 >>> K = CartesianProduct(NonnegativeOrthant(3),
599 >>> d = K.cvxopt_dims()
600 >>> (d['l'], d['q'], d['s'])
604 dims
= {'l':0, 'q':[], 's':[]}
605 dims
['l'] += sum([K
.dimension()
606 for K
in self
.factors()
607 if isinstance(K
, NonnegativeOrthant
)])
608 dims
['q'] = [K
.dimension()
609 for K
in self
.factors()
610 if isinstance(K
, IceCream
)]
611 dims
['s'] = [K
.dimension()
612 for K
in self
.factors()
613 if isinstance(K
, SymmetricPSD
)]