]>
gitweb.michael.orlitzky.com - dunshire.git/blob - cones.py
7fc8bf94993e4df86b2f57c2e6b6d6aefa65d8c4
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
83 Return the dimension of this symmetric cone.
85 The dimension of this symmetric cone is recorded during its
86 creation. This method simply returns the recorded value, and
87 should not need to be overridden in subclasses. We prefer to do
88 any special computation in ``__init__()`` and record the result
89 in ``self._dimension``.
95 The stored dimension (from when this cone was constructed)
101 >>> K = SymmetricCone(5)
106 return self
._dimension
109 class NonnegativeOrthant(SymmetricCone
):
111 The nonnegative orthant in the given number of dimensions.
116 >>> K = NonnegativeOrthant(3)
118 Nonnegative orthant in the real 3-space
123 Output a human-readable description of myself.
125 tpl
= 'Nonnegative orthant in the real {:d}-space'
126 return tpl
.format(self
.dimension())
129 def __contains__(self
, point
):
131 Return whether or not ``point`` belongs to this cone.
133 Since this test is expected to work on points whose components
134 are floating point numbers, it doesn't make any sense to
135 distinguish between strict and non-strict containment -- the
136 test uses a tolerance parameter.
142 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
143 where ``n`` is the :meth:`dimension` of this cone.
150 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
156 If ``point`` is not a :class:`cvxopt.base.matrix`.
159 If ``point`` has the wrong dimensions.
164 All of these coordinates are positive enough:
166 >>> K = NonnegativeOrthant(3)
167 >>> matrix([1,2,3]) in K
170 The one negative coordinate pushes this point outside of ``K``:
172 >>> K = NonnegativeOrthant(3)
173 >>> matrix([1,-0.1,3]) in K
176 A boundary point is considered inside of ``K``:
177 >>> K = NonnegativeOrthant(3)
178 >>> matrix([1,0,3]) in K
181 Junk arguments don't work:
183 >>> K = NonnegativeOrthant(3)
185 Traceback (most recent call last):
187 TypeError: the given point is not a cvxopt.base.matrix
189 >>> K = NonnegativeOrthant(3)
190 >>> matrix([1,2]) in K
191 Traceback (most recent call last):
193 TypeError: the given point has the wrong dimensions
196 if not isinstance(point
, matrix
):
197 raise TypeError('the given point is not a cvxopt.base.matrix')
198 if not point
.size
== (self
.dimension(), 1):
199 raise TypeError('the given point has the wrong dimensions')
201 return all([x
> -options
.ABS_TOL
for x
in point
])
205 class IceCream(SymmetricCone
):
207 The Lorentz "ice cream" cone in the given number of dimensions.
214 Lorentz "ice cream" cone in the real 3-space
219 Output a human-readable description of myself.
221 tpl
= 'Lorentz "ice cream" cone in the real {:d}-space'
222 return tpl
.format(self
.dimension())
225 def __contains__(self
, point
):
227 Return whether or not ``point`` belongs to this cone.
229 Since this test is expected to work on points whose components
230 are floating point numbers, it doesn't make any sense to
231 distinguish between strict and non-strict containment -- the
232 test uses a tolerance parameter.
238 A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
239 where ``n`` is the :meth:`dimension` of this cone.
246 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
252 If ``point`` is not a :class:`cvxopt.base.matrix`.
255 If ``point`` has the wrong dimensions.
260 This point lies well within the ice cream cone:
263 >>> matrix([1,0.5,0.5]) in K
266 This one lies on its boundary:
269 >>> matrix([1,0,1]) in K
272 This point lies entirely outside of the ice cream cone:
275 >>> matrix([1,1,1]) in K
278 Junk arguments don't work:
282 Traceback (most recent call last):
284 TypeError: the given point is not a cvxopt.base.matrix
287 >>> matrix([1,2]) in K
288 Traceback (most recent call last):
290 TypeError: the given point has the wrong dimensions
293 if not isinstance(point
, matrix
):
294 raise TypeError('the given point is not a cvxopt.base.matrix')
295 if not point
.size
== (self
.dimension(), 1):
296 raise TypeError('the given point has the wrong dimensions')
299 if self
.dimension() == 1:
300 # In one dimension, the ice cream cone is the nonnegative
302 return height
> -options
.ABS_TOL
305 return norm(radius
) < (height
+ options
.ABS_TOL
)
309 class SymmetricPSD(SymmetricCone
):
311 The cone of real symmetric positive-semidefinite matrices.
313 This cone has a dimension ``n`` associated with it, but we let ``n``
314 refer to the dimension of the domain of our matrices and not the
315 dimension of the (much larger) space in which the matrices
316 themselves live. In other words, our ``n`` is the ``n`` that appears
317 in the usual notation :math:`S^{n}` for symmetric matrices.
319 As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
320 :math:`\left(n^{2} + n\right)/2)`.
325 >>> K = SymmetricPSD(3)
327 Cone of symmetric positive-semidefinite matrices on the real 3-space
334 Output a human-readable description of myself.
336 tpl
= 'Cone of symmetric positive-semidefinite matrices ' \
337 'on the real {:d}-space'
338 return tpl
.format(self
.dimension())
341 def __contains__(self
, point
):
343 Return whether or not ``point`` belongs to this cone.
345 Since this test is expected to work on points whose components
346 are floating point numbers, it doesn't make any sense to
347 distinguish between strict and non-strict containment -- the
348 test uses a tolerance parameter.
354 A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
355 where ``n`` is the :meth:`dimension` of this cone.
362 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
368 If ``point`` is not a :class:`cvxopt.base.matrix`.
371 If ``point`` has the wrong dimensions.
376 These all lie in the interior of the Symmetric PSD cone:
378 >>> K = SymmetricPSD(2)
379 >>> matrix([[1,0],[0,1]]) in K
382 >>> K = SymmetricPSD(3)
383 >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
386 >>> K = SymmetricPSD(5)
387 >>> A = matrix([[5,4,3,2,1],
395 Boundary points lie in the cone as well:
397 >>> K = SymmetricPSD(2)
398 >>> matrix([[0,0],[0,0]]) in K
401 >>> K = SymmetricPSD(5)
402 >>> A = matrix([[1,0,0,0,0],
410 However, this matrix has a negative eigenvalue:
412 >>> K = SymmetricPSD(2)
413 >>> A = matrix([[ 1, -2],
418 An asymmetric cone with positive eigenvalues is not in the cone:
420 >>> K = SymmetricPSD(2)
421 >>> A = matrix([[10, 2],
426 Junk arguments don't work:
428 >>> K = SymmetricPSD(2)
429 >>> [[1,2],[2,3]] in K
430 Traceback (most recent call last):
432 TypeError: the given point is not a cvxopt.base.matrix
434 >>> K = SymmetricPSD(3)
435 >>> matrix([[1,2],[3,4]]) in K
436 Traceback (most recent call last):
438 TypeError: the given point has the wrong dimensions
441 if not isinstance(point
, matrix
):
442 raise TypeError('the given point is not a cvxopt.base.matrix')
443 if not point
.size
== (self
.dimension(), self
.dimension()):
444 raise TypeError('the given point has the wrong dimensions')
445 if not point
.typecode
== 'd':
446 point
= matrix(point
, (self
.dimension(), self
.dimension()), 'd')
447 if not norm(point
- point
.trans()) < options
.ABS_TOL
:
448 # It's not symmetric.
450 return all([e
> -options
.ABS_TOL
for e
in eigenvalues(point
)])
454 class CartesianProduct(SymmetricCone
):
456 A cartesian product of symmetric cones, which is itself a symmetric
462 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
464 Cartesian product of dimension 5 with 2 factors:
465 * Nonnegative orthant in the real 3-space
466 * Lorentz "ice cream" cone in the real 2-space
469 def __init__(self
, *factors
):
470 my_dimension
= sum([f
.dimension() for f
in factors
])
471 super().__init
__(my_dimension
)
472 self
._factors
= factors
477 Output a human-readable description of myself.
479 tpl
= 'Cartesian product of dimension {:d} with {:d} factors:'
480 tpl
+= '\n * {!s}' * len(self
.factors())
481 format_args
= [self
.dimension(), len(self
.factors())]
482 format_args
+= list(self
.factors())
483 return tpl
.format(*format_args
)
486 def __contains__(self
, point
):
488 Return whether or not ``point`` belongs to this cone.
490 The ``point`` is expected to be a tuple of points which will be
491 tested for membership in this cone's factors. If each point in
492 the tuple belongs to its corresponding factor, then the whole
493 point belongs to this cone. Otherwise, it doesn't.
498 point : tuple of matrix
499 A tuple of :class:`cvxopt.base.matrix` corresponding to the
500 :meth:`factors` of this cartesian product.
507 ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
513 If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
516 If any element of ``point`` has the wrong dimensions.
521 The result depends on how containment is defined for our factors:
523 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
524 >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
527 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
528 >>> (matrix([0,0,0]), matrix([1,0,1])) in K
531 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
532 >>> (matrix([1,1,1]), matrix([1,1,1])) in K
535 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
536 >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
539 Junk arguments don't work:
541 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
542 >>> [[1,2,3],[4,5,6]] in K
543 Traceback (most recent call last):
545 TypeError: the given point is not a cvxopt.base.matrix
547 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
548 >>> (matrix([1,2]), matrix([3,4,5,6])) in K
549 Traceback (most recent call last):
551 TypeError: the given point has the wrong dimensions
554 return all([p
in f
for (p
, f
) in zip(point
, self
.factors())])
560 Return a tuple containing the factors (in order) of this
566 tuple of :class:`SymmetricCone`.
567 The factors of this cartesian product.
572 >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
580 def cvxopt_dims(self
):
582 Return a dictionary of dimensions corresponding to the factors
583 of this cartesian product. The format of this dictionary is
584 described in the CVXOPT user's guide:
586 http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
592 A dimension dictionary suitable to feed to CVXOPT.
597 >>> K = CartesianProduct(NonnegativeOrthant(3),
600 >>> d = K.cvxopt_dims()
601 >>> (d['l'], d['q'], d['s'])
605 dims
= {'l':0, 'q':[], 's':[]}
606 dims
['l'] += sum([K
.dimension()
607 for K
in self
.factors()
608 if isinstance(K
, NonnegativeOrthant
)])
609 dims
['q'] = [K
.dimension()
610 for K
in self
.factors()
611 if isinstance(K
, IceCream
)]
612 dims
['s'] = [K
.dimension()
613 for K
in self
.factors()
614 if isinstance(K
, SymmetricPSD
)]