]>
gitweb.michael.orlitzky.com - dunshire.git/blob - dunshire/cones.py
2 Class definitions for all of the symmetric cones (and their superclass,
3 :class:`SymmetricCone`) supported by CVXOPT.
6 from cvxopt
import matrix
8 from .matrices
import eigenvalues
, norm
13 An instance of a symmetric (self-dual and homogeneous) cone.
15 There are three types of symmetric cones supported by CVXOPT:
17 1. The nonnegative orthant in the real n-space.
18 2. The Lorentz "ice cream" cone, or the second-order cone.
19 3. The cone of symmetric positive-semidefinite matrices.
21 This class is intended to encompass them all.
23 When constructing a single symmetric cone (i.e. not a
24 :class:`CartesianProduct` of them), the only information that we
25 need is its dimension. We take that dimension as a parameter, and
32 The dimension of this cone.
38 If you try to create a cone with dimension zero or less.
41 def __init__(self
, dimension
):
43 A generic constructor for symmetric cones.
46 raise ValueError('cones must have dimension greater than zero')
48 self
._dimension
= dimension
51 def __contains__(self
, point
):
53 Return whether or not ``point`` belongs to this cone.
59 The point to test for membership in this cone.
65 Always, this method must be implemented in subclasses.
70 >>> K = SymmetricCone(5)
71 >>> matrix([1,2]) in K
72 Traceback (most recent call last):
77 raise NotImplementedError
80 def ball_radius(self
, point
):
82 Return the radius of a ball around ``point`` in this cone.
84 Since a radius cannot be negative, the ``point`` must be
85 contained in this cone; otherwise, an error is raised.
91 A point contained in this cone.
97 A radius ``r`` such that the ball of radius ``r`` centered at
98 ``point`` is contained entirely within this cone.
104 Always, this method must be implemented in subclasses.
109 >>> K = SymmetricCone(5)
110 >>> K.ball_radius(matrix([1,1,1,1,1]))
111 Traceback (most recent call last):
116 raise NotImplementedError
121 Return the dimension of this symmetric cone.
123 The dimension of this symmetric cone is recorded during its
124 creation. This method simply returns the recorded value, and
125 should not need to be overridden in subclasses. We prefer to do
126 any special computation in ``__init__()`` and record the result
127 in ``self._dimension``.
133 The stored dimension (from when this cone was constructed)
139 >>> K = SymmetricCone(5)
144 return self
._dimension
147 class NonnegativeOrthant(SymmetricCone
):
149 The nonnegative orthant in the given number of dimensions.
154 >>> K = NonnegativeOrthant(3)
156 Nonnegative orthant in the real 3-space
161 Output a human-readable description of myself.
163 tpl
= 'Nonnegative orthant in the real {:d}-space'
164 return tpl
.format(self
.dimension())
167 def __contains__(self
, point
):
169 Return whether or not ``point`` belongs to this cone.
171 Since this test is expected to work on points whose components
172 are floating point numbers, it doesn't make any sense to
173 distinguish between strict and non-strict containment -- the
174 test uses a tolerance parameter.
180 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
181 where ``n`` is the :meth:`dimension` of this cone.
188 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
194 If ``point`` is not a :class:`cvxopt.base.matrix`.
197 If ``point`` has the wrong dimensions.
202 All of these coordinates are positive enough:
204 >>> K = NonnegativeOrthant(3)
205 >>> matrix([1,2,3]) in K
208 The one negative coordinate pushes this point outside of ``K``:
210 >>> K = NonnegativeOrthant(3)
211 >>> matrix([1,-0.1,3]) in K
214 A boundary point is considered inside of ``K``:
215 >>> K = NonnegativeOrthant(3)
216 >>> matrix([1,0,3]) in K
219 Junk arguments don't work:
221 >>> K = NonnegativeOrthant(3)
223 Traceback (most recent call last):
225 TypeError: the given point is not a cvxopt.base.matrix
227 >>> K = NonnegativeOrthant(3)
228 >>> matrix([1,2]) in K
229 Traceback (most recent call last):
231 TypeError: the given point has the wrong dimensions
234 if not isinstance(point
, matrix
):
235 raise TypeError('the given point is not a cvxopt.base.matrix')
236 if not point
.size
== (self
.dimension(), 1):
237 raise TypeError('the given point has the wrong dimensions')
239 return all([x
> -options
.ABS_TOL
for x
in point
])
242 def ball_radius(self
, point
):
244 Return the radius of a ball around ``point`` in this cone.
246 Since a radius cannot be negative, the ``point`` must be
247 contained in this cone; otherwise, an error is raised.
249 The minimum distance from ``point`` to the complement of this
250 cone will always occur at its projection onto that set. It is
251 not hard to see that the projection is directly along one of the
252 coordinates, and so the minimum distance from ``point`` to the
253 boundary of this cone is the smallest coordinate of
254 ``point``. Therefore any radius less than that will work; we
255 divide it in half somewhat arbitrarily.
261 A point contained in this cone.
267 A radius ``r`` such that the ball of radius ``r`` centered at
268 ``point`` is contained entirely within this cone.
274 If ``point`` is not a :class:`cvxopt.base.matrix`.
277 If ``point`` has the wrong dimensions.
280 if ``point`` is not contained in this cone.
285 >>> K = NonnegativeOrthant(5)
286 >>> K.ball_radius(matrix([1,2,3,4,5]))
290 if not isinstance(point
, matrix
):
291 raise TypeError('the given point is not a cvxopt.base.matrix')
292 if not point
.size
== (self
.dimension(), 1):
293 raise TypeError('the given point has the wrong dimensions')
294 if not point
in self
:
295 raise ValueError('the given point does not lie in the cone')
297 return min(list(point
)) / 2.0
301 class IceCream(SymmetricCone
):
303 The Lorentz "ice cream" cone in the given number of dimensions.
310 Lorentz "ice cream" cone in the real 3-space
315 Output a human-readable description of myself.
317 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
318 return tpl
.format(self
.dimension())
321 def __contains__(self
, point
):
323 Return whether or not ``point`` belongs to this cone.
325 Since this test is expected to work on points whose components
326 are floating point numbers, it doesn't make any sense to
327 distinguish between strict and non-strict containment -- the
328 test uses a tolerance parameter.
334 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
335 where ``n`` is the :meth:`dimension` of this cone.
342 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
348 If ``point`` is not a :class:`cvxopt.base.matrix`.
351 If ``point`` has the wrong dimensions.
356 This point lies well within the ice cream cone:
359 >>> matrix([1,0.5,0.5]) in K
362 This one lies on its boundary:
365 >>> matrix([1,0,1]) in K
368 This point lies entirely outside of the ice cream cone:
371 >>> matrix([1,1,1]) in K
374 Junk arguments don't work:
378 Traceback (most recent call last):
380 TypeError: the given point is not a cvxopt.base.matrix
383 >>> matrix([1,2]) in K
384 Traceback (most recent call last):
386 TypeError: the given point has the wrong dimensions
389 if not isinstance(point
, matrix
):
390 raise TypeError('the given point is not a cvxopt.base.matrix')
391 if not point
.size
== (self
.dimension(), 1):
392 raise TypeError('the given point has the wrong dimensions')
395 if self
.dimension() == 1:
396 # In one dimension, the ice cream cone is the nonnegative
398 return height
> -options
.ABS_TOL
401 return norm(radius
) < (height
+ options
.ABS_TOL
)
404 def ball_radius(self
, point
):
406 Return the radius of a ball around ``point`` in this cone.
408 Since a radius cannot be negative, the ``point`` must be
409 contained in this cone; otherwise, an error is raised.
411 The minimum distance from ``point`` to the complement of this
412 cone will always occur at its projection onto that set. It is
413 not hard to see that the projection is at a "down and out" angle
414 of :math:`\pi/4` towards the outside of the cone. If one draws a
415 right triangle involving the ``point`` and that projection, it
416 becomes clear that the distance between ``point`` and its
417 projection is a factor of :math:`1/\sqrt(2)` times the "horizontal"
418 distance from ``point`` to boundary of this cone. For simplicity
419 we take :math:`1/2` instead.
425 A point contained in this cone.
431 A radius ``r`` such that the ball of radius ``r`` centered at
432 ``point`` is contained entirely within this cone.
438 If ``point`` is not a :class:`cvxopt.base.matrix`.
441 If ``point`` has the wrong dimensions.
444 if ``point`` is not contained in this cone.
449 The height of ``x`` below is one (its first coordinate), and so
450 the radius of the circle obtained from a height-one cross
451 section is also one. Note that the last two coordinates of ``x``
452 are half of the way to the boundary of the cone, and in the
453 direction of a 30-60-90 triangle. If one follows those
454 coordinates, they hit at :math:`\left(1, \frac{\sqrt(3)}{2},
455 \frac{1}{2}\right)` having unit norm. Thus the "horizontal"
456 distance to the boundary of the cone is :math:`1 - \left\lVert x
457 \right\rVert`, which simplifies to :math:`1/2`. And rather than
458 involve a square root, we divide by two for a final safe radius
461 >>> from math import sqrt
463 >>> x = matrix([1, sqrt(3)/4.0, 1/4.0])
468 if not isinstance(point
, matrix
):
469 raise TypeError('the given point is not a cvxopt.base.matrix')
470 if not point
.size
== (self
.dimension(), 1):
471 raise TypeError('the given point has the wrong dimensions')
472 if not point
in self
:
473 raise ValueError('the given point does not lie in the cone')
476 radius
= norm(point
[1:])
477 return (height
- radius
) / 2.0
480 class SymmetricPSD(SymmetricCone
):
482 The cone of real symmetric positive-semidefinite matrices.
484 This cone has a dimension ``n`` associated with it, but we let ``n``
485 refer to the dimension of the domain of our matrices and not the
486 dimension of the (much larger) space in which the matrices
487 themselves live. In other words, our ``n`` is the ``n`` that appears
488 in the usual notation :math:`S^{n}` for symmetric matrices.
490 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
491 :math:`\left(n^{2} + n\right)/2)`.
496 >>> K = SymmetricPSD(3)
498 Cone of symmetric positive-semidefinite matrices on the real 3-space
505 Output a human-readable description of myself.
507 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
508 'on the real {:d}-space'
509 return tpl
.format(self
.dimension())
512 def __contains__(self
, point
):
514 Return whether or not ``point`` belongs to this cone.
516 Since this test is expected to work on points whose components
517 are floating point numbers, it doesn't make any sense to
518 distinguish between strict and non-strict containment -- the
519 test uses a tolerance parameter.
525 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
526 where ``n`` is the :meth:`dimension` of this cone.
533 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
539 If ``point`` is not a :class:`cvxopt.base.matrix`.
542 If ``point`` has the wrong dimensions.
547 These all lie in the interior of the Symmetric PSD cone:
549 >>> K = SymmetricPSD(2)
550 >>> matrix([[1,0],[0,1]]) in K
553 >>> K = SymmetricPSD(3)
554 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
557 >>> K = SymmetricPSD(5)
558 >>> A = matrix([[5,4,3,2,1],
566 Boundary points lie in the cone as well:
568 >>> K = SymmetricPSD(2)
569 >>> matrix([[0,0],[0,0]]) in K
572 >>> K = SymmetricPSD(5)
573 >>> A = matrix([[1,0,0,0,0],
581 However, this matrix has a negative eigenvalue:
583 >>> K = SymmetricPSD(2)
584 >>> A = matrix([[ 1, -2],
589 An asymmetric cone with positive eigenvalues is not in the cone:
591 >>> K = SymmetricPSD(2)
592 >>> A = matrix([[10, 2],
597 Junk arguments don't work:
599 >>> K = SymmetricPSD(2)
600 >>> [[1,2],[2,3]] in K
601 Traceback (most recent call last):
603 TypeError: the given point is not a cvxopt.base.matrix
605 >>> K = SymmetricPSD(3)
606 >>> matrix([[1,2],[3,4]]) in K
607 Traceback (most recent call last):
609 TypeError: the given point has the wrong dimensions
612 if not isinstance(point
, matrix
):
613 raise TypeError('the given point is not a cvxopt.base.matrix')
614 if not point
.size
== (self
.dimension(), self
.dimension()):
615 raise TypeError('the given point has the wrong dimensions')
616 if not point
.typecode
== 'd':
617 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
618 if not norm(point
- point
.trans()) < options
.ABS_TOL
:
619 # It's not symmetric.
621 return all([e
> -options
.ABS_TOL
for e
in eigenvalues(point
)])
625 class CartesianProduct(SymmetricCone
):
627 A cartesian product of symmetric cones, which is itself a symmetric
633 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
635 Cartesian product of dimension 5 with 2 factors:
636 * Nonnegative orthant in the real 3-space
637 * Lorentz "ice cream" cone in the real 2-space
640 def __init__(self
, *factors
):
641 my_dimension
= sum([f
.dimension() for f
in factors
])
642 super().__init
__(my_dimension
)
643 self
._factors
= factors
648 Output a human-readable description of myself.
650 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
651 tpl
+= '\n * {!s}' * len(self
.factors())
652 format_args
= [self
.dimension(), len(self
.factors())]
653 format_args
+= list(self
.factors())
654 return tpl
.format(*format_args
)
657 def __contains__(self
, point
):
659 Return whether or not ``point`` belongs to this cone.
661 The ``point`` is expected to be a tuple of points which will be
662 tested for membership in this cone's factors. If each point in
663 the tuple belongs to its corresponding factor, then the whole
664 point belongs to this cone. Otherwise, it doesn't.
669 point : tuple of matrix
670 A tuple of :class:`cvxopt.base.matrix` corresponding to the
671 :meth:`factors` of this cartesian product.
678 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
684 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
687 If any element of ``point`` has the wrong dimensions.
692 The result depends on how containment is defined for our factors:
694 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
695 >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
698 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
699 >>> (matrix([0,0,0]), matrix([1,0,1])) in K
702 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
703 >>> (matrix([1,1,1]), matrix([1,1,1])) in K
706 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
707 >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
710 Junk arguments don't work:
712 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
713 >>> [[1,2,3],[4,5,6]] in K
714 Traceback (most recent call last):
716 TypeError: the given point is not a cvxopt.base.matrix
718 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
719 >>> (matrix([1,2]), matrix([3,4,5,6])) in K
720 Traceback (most recent call last):
722 TypeError: the given point has the wrong dimensions
725 return all([p
in f
for (p
, f
) in zip(point
, self
.factors())])
731 Return a tuple containing the factors (in order) of this
737 tuple of SymmetricCone.
738 The factors of this cartesian product.
743 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
751 def cvxopt_dims(self
):
753 Return a dictionary of dimensions corresponding to the
754 factors of this cartesian product. The format of this dictionary
755 is described in the `CVXOPT user's guide
756 <http://cvxopt.org/userguide/coneprog.html#linear-cone-programs>`_.
762 A dimension dictionary suitable to feed to CVXOPT.
767 >>> K = CartesianProduct(NonnegativeOrthant(3),
770 >>> d = K.cvxopt_dims()
771 >>> (d['l'], d['q'], d['s'])
775 dims
= {'l':0, 'q':[], 's':[]}
776 dims
['l'] += sum([K
.dimension()
777 for K
in self
.factors()
778 if isinstance(K
, NonnegativeOrthant
)])
779 dims
['q'] = [K
.dimension()
780 for K
in self
.factors()
781 if isinstance(K
, IceCream
)]
782 dims
['s'] = [K
.dimension()
783 for K
in self
.factors()
784 if isinstance(K
, SymmetricPSD
)]