src/dunshire/cones.py

   1 """
   2 Class definitions for all of the symmetric cones (and their superclass,
   3 :class:`SymmetricCone`) supported by CVXOPT.
   4 """
   5
   6 from cvxopt import matrix
   7 from matrices import eigenvalues, norm
   8 import options
   9
  10 class SymmetricCone:
  11     """
  12     An instance of a symmetric (self-dual and homogeneous) cone.
  13
  14     There are three types of symmetric cones supported by CVXOPT:
  15
  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.
  19
  20     This class is intended to encompass them all.
  21
  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
  25     store it for later.
  26
  27     Parameters
  28     ----------
  29
  30     dimension : int
  31         The dimension of this cone.
  32
  33     Raises
  34     ------
  35
  36     ValueError
  37         If you try to create a cone with dimension zero or less.
  38
  39     """
  40     def __init__(self, dimension):
  41         """
  42         A generic constructor for symmetric cones.
  43         """
  44         if dimension <= 0:
  45             raise ValueError('cones must have dimension greater than zero')
  46
  47         self._dimension = dimension
  48
  49
  50     def __contains__(self, point):
  51         """
  52         Return whether or not ``point`` belongs to this cone.
  53
  54         Parameters
  55         ----------
  56
  57         point : matrix
  58             The point to test for membership in this cone.
  59
  60         Raises
  61         ------
  62
  63         NotImplementedError
  64             Always, this method must be implemented in subclasses.
  65
  66         Examples
  67         --------
  68
  69             >>> K = SymmetricCone(5)
  70             >>> matrix([1,2]) in K
  71             Traceback (most recent call last):
  72             ...
  73             NotImplementedError
  74
  75         """
  76         raise NotImplementedError
  77
  78
  79
  80     def dimension(self):
  81         """
  82         Return the dimension of this symmetric cone.
  83
  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``.
  89
  90         Returns
  91         -------
  92
  93         int
  94             The stored dimension (from when this cone was constructed)
  95             of this cone.
  96
  97         Examples
  98         --------
  99
 100             >>> K = SymmetricCone(5)
 101             >>> K.dimension()
 102             5
 103
 104         """
 105         return self._dimension
 106
 107
 108 class NonnegativeOrthant(SymmetricCone):
 109     """
 110     The nonnegative orthant in the given number of dimensions.
 111
 112     Examples
 113     --------
 114
 115         >>> K = NonnegativeOrthant(3)
 116         >>> print(K)
 117         Nonnegative orthant in the real 3-space
 118
 119     """
 120     def __str__(self):
 121         """
 122         Output a human-readable description of myself.
 123         """
 124         tpl = 'Nonnegative orthant in the real {:d}-space'
 125         return tpl.format(self.dimension())
 126
 127
 128     def __contains__(self, point):
 129         """
 130         Return whether or not ``point`` belongs to this cone.
 131
 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.
 136
 137         Parameters
 138         ----------
 139
 140         point : matrix
 141             A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
 142             where ``n`` is the :meth:`dimension` of this cone.
 143
 144         Returns
 145         -------
 146
 147         bool
 148
 149            ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
 150
 151         Raises
 152         ------
 153
 154         TypeError
 155             If ``point`` is not a :class:`cvxopt.base.matrix`.
 156
 157         TypeError
 158             If ``point`` has the wrong dimensions.
 159
 160         Examples
 161         --------
 162
 163         All of these coordinates are positive enough:
 164
 165             >>> K = NonnegativeOrthant(3)
 166             >>> matrix([1,2,3]) in K
 167             True
 168
 169         The one negative coordinate pushes this point outside of ``K``:
 170
 171             >>> K = NonnegativeOrthant(3)
 172             >>> matrix([1,-0.1,3]) in K
 173             False
 174
 175         A boundary point is considered inside of ``K``:
 176             >>> K = NonnegativeOrthant(3)
 177             >>> matrix([1,0,3]) in K
 178             True
 179
 180         Junk arguments don't work:
 181
 182             >>> K = NonnegativeOrthant(3)
 183             >>> [1,2,3] in K
 184             Traceback (most recent call last):
 185             ...
 186             TypeError: the given point is not a cvxopt.base.matrix
 187
 188             >>> K = NonnegativeOrthant(3)
 189             >>> matrix([1,2]) in K
 190             Traceback (most recent call last):
 191             ...
 192             TypeError: the given point has the wrong dimensions
 193
 194         """
 195         if not isinstance(point, matrix):
 196             raise TypeError('the given point is not a cvxopt.base.matrix')
 197         if not point.size == (self.dimension(), 1):
 198             raise TypeError('the given point has the wrong dimensions')
 199
 200         return all([x > -options.ABS_TOL for x in point])
 201
 202
 203
 204 class IceCream(SymmetricCone):
 205     """
 206     The Lorentz "ice cream" cone in the given number of dimensions.
 207
 208     Examples
 209     --------
 210
 211         >>> K = IceCream(3)
 212         >>> print(K)
 213         Lorentz "ice cream" cone in the real 3-space
 214
 215     """
 216     def __str__(self):
 217         """
 218         Output a human-readable description of myself.
 219         """
 220         tpl = 'Lorentz "ice cream" cone in the real {:d}-space'
 221         return tpl.format(self.dimension())
 222
 223
 224     def __contains__(self, point):
 225         """
 226         Return whether or not ``point`` belongs to this cone.
 227
 228         Since this test is expected to work on points whose components
 229         are floating point numbers, it doesn't make any sense to
 230         distinguish between strict and non-strict containment -- the
 231         test uses a tolerance parameter.
 232
 233         Parameters
 234         ----------
 235
 236         point : matrix
 237             A :class:`cvxopt.base.matrix` having dimensions ``(n,1)``
 238             where ``n`` is the :meth:`dimension` of this cone.
 239
 240         Returns
 241         -------
 242
 243         bool
 244
 245            ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
 246
 247         Raises
 248         ------
 249
 250         TypeError
 251             If ``point`` is not a :class:`cvxopt.base.matrix`.
 252
 253         TypeError
 254             If ``point`` has the wrong dimensions.
 255
 256         Examples
 257         --------
 258
 259         This point lies well within the ice cream cone:
 260
 261             >>> K = IceCream(3)
 262             >>> matrix([1,0.5,0.5]) in K
 263             True
 264
 265         This one lies on its boundary:
 266
 267             >>> K = IceCream(3)
 268             >>> matrix([1,0,1]) in K
 269             True
 270
 271         This point lies entirely outside of the ice cream cone:
 272
 273             >>> K = IceCream(3)
 274             >>> matrix([1,1,1]) in K
 275             False
 276
 277         Junk arguments don't work:
 278
 279             >>> K = IceCream(3)
 280             >>> [1,2,3] in K
 281             Traceback (most recent call last):
 282             ...
 283             TypeError: the given point is not a cvxopt.base.matrix
 284
 285             >>> K = IceCream(3)
 286             >>> matrix([1,2]) in K
 287             Traceback (most recent call last):
 288             ...
 289             TypeError: the given point has the wrong dimensions
 290
 291         """
 292         if not isinstance(point, matrix):
 293             raise TypeError('the given point is not a cvxopt.base.matrix')
 294         if not point.size == (self.dimension(), 1):
 295             raise TypeError('the given point has the wrong dimensions')
 296
 297         height = point[0]
 298         if self.dimension() == 1:
 299             # In one dimension, the ice cream cone is the nonnegative
 300             # orthant.
 301             return height > -options.ABS_TOL
 302         else:
 303             radius = point[1:]
 304             return norm(radius) < (height + options.ABS_TOL)
 305
 306
 307
 308 class SymmetricPSD(SymmetricCone):
 309     r"""
 310     The cone of real symmetric positive-semidefinite matrices.
 311
 312     This cone has a dimension ``n`` associated with it, but we let ``n``
 313     refer to the dimension of the domain of our matrices and not the
 314     dimension of the (much larger) space in which the matrices
 315     themselves live. In other words, our ``n`` is the ``n`` that appears
 316     in the usual notation :math:`S^{n}` for symmetric matrices.
 317
 318     As a result, the cone ``SymmetricPSD(n)`` lives in a space of dimension
 319     :math:`\left(n^{2} + n\right)/2)`.
 320
 321     Examples
 322     --------
 323
 324         >>> K = SymmetricPSD(3)
 325         >>> print(K)
 326         Cone of symmetric positive-semidefinite matrices on the real 3-space
 327         >>> K.dimension()
 328         3
 329
 330     """
 331     def __str__(self):
 332         """
 333         Output a human-readable description of myself.
 334         """
 335         tpl = 'Cone of symmetric positive-semidefinite matrices ' \
 336               'on the real {:d}-space'
 337         return tpl.format(self.dimension())
 338
 339
 340     def __contains__(self, point):
 341         """
 342         Return whether or not ``point`` belongs to this cone.
 343
 344         Since this test is expected to work on points whose components
 345         are floating point numbers, it doesn't make any sense to
 346         distinguish between strict and non-strict containment -- the
 347         test uses a tolerance parameter.
 348
 349         Parameters
 350         ----------
 351
 352         point : matrix
 353             A :class:`cvxopt.base.matrix` having dimensions ``(n,n)``
 354             where ``n`` is the :meth:`dimension` of this cone.
 355
 356         Returns
 357         -------
 358
 359         bool
 360
 361            ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
 362
 363         Raises
 364         ------
 365
 366         TypeError
 367             If ``point`` is not a :class:`cvxopt.base.matrix`.
 368
 369         TypeError
 370             If ``point`` has the wrong dimensions.
 371
 372         Examples
 373         --------
 374
 375         These all lie in the interior of the Symmetric PSD cone:
 376
 377             >>> K = SymmetricPSD(2)
 378             >>> matrix([[1,0],[0,1]]) in K
 379             True
 380
 381             >>> K = SymmetricPSD(3)
 382             >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
 383             True
 384
 385             >>> K = SymmetricPSD(5)
 386             >>> A = matrix([[5,4,3,2,1],
 387             ...             [4,5,4,3,2],
 388             ...             [3,4,5,4,3],
 389             ...             [2,3,4,5,4],
 390             ...             [1,2,3,4,5]])
 391             >>> A in K
 392             True
 393
 394         Boundary points lie in the cone as well:
 395
 396             >>> K = SymmetricPSD(2)
 397             >>> matrix([[0,0],[0,0]]) in K
 398             True
 399
 400             >>> K = SymmetricPSD(5)
 401             >>> A = matrix([[1,0,0,0,0],
 402             ...             [0,1,0,0,0],
 403             ...             [0,0,0,0,0],
 404             ...             [0,0,0,1,0],
 405             ...             [0,0,0,0,1]])
 406             >>> A in K
 407             True
 408
 409         However, this matrix has a negative eigenvalue:
 410
 411            >>> K = SymmetricPSD(2)
 412            >>> A = matrix([[ 1, -2],
 413            ...             [-2,  1]])
 414            >>> A in K
 415            False
 416
 417         An asymmetric cone with positive eigenvalues is not in the cone:
 418
 419            >>> K = SymmetricPSD(2)
 420            >>> A = matrix([[10, 2],
 421            ...             [4,  8]])
 422            >>> A in K
 423            False
 424
 425         Junk arguments don't work:
 426
 427             >>> K = SymmetricPSD(2)
 428             >>> [[1,2],[2,3]] in K
 429             Traceback (most recent call last):
 430             ...
 431             TypeError: the given point is not a cvxopt.base.matrix
 432
 433             >>> K = SymmetricPSD(3)
 434             >>> matrix([[1,2],[3,4]]) in K
 435             Traceback (most recent call last):
 436             ...
 437             TypeError: the given point has the wrong dimensions
 438
 439         """
 440         if not isinstance(point, matrix):
 441             raise TypeError('the given point is not a cvxopt.base.matrix')
 442         if not point.size == (self.dimension(), self.dimension()):
 443             raise TypeError('the given point has the wrong dimensions')
 444         if not point.typecode == 'd':
 445             point = matrix(point, (self.dimension(), self.dimension()), 'd')
 446         if not norm(point - point.trans()) < options.ABS_TOL:
 447             # It's not symmetric.
 448             return False
 449         return all([e > -options.ABS_TOL for e in eigenvalues(point)])
 450
 451
 452
 453 class CartesianProduct(SymmetricCone):
 454     """
 455     A cartesian product of symmetric cones, which is itself a symmetric
 456     cone.
 457
 458     Examples
 459     --------
 460
 461         >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 462         >>> print(K)
 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
 466
 467     """
 468     def __init__(self, *factors):
 469         my_dimension = sum([f.dimension() for f in factors])
 470         super().__init__(my_dimension)
 471         self._factors = factors
 472
 473
 474     def __str__(self):
 475         """
 476         Output a human-readable description of myself.
 477         """
 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)
 483
 484
 485     def __contains__(self, point):
 486         """
 487         Return whether or not ``point`` belongs to this cone.
 488
 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.
 493
 494         Parameters
 495         ----------
 496
 497         point : tuple of matrix
 498             A tuple of :class:`cvxopt.base.matrix` corresponding to the
 499             :meth:`factors` of this cartesian product.
 500
 501         Returns
 502         -------
 503
 504         bool
 505
 506            ``True`` if ``point`` belongs to this cone, ``False`` otherwise.
 507
 508         Raises
 509         ------
 510
 511         TypeError
 512             If ``point`` is not a tuple of :class:`cvxopt.base.matrix`.
 513
 514         TypeError
 515             If any element of ``point`` has the wrong dimensions.
 516
 517         Examples
 518         --------
 519
 520         The result depends on how containment is defined for our factors:
 521
 522             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 523             >>> (matrix([1,2,3]), matrix([1,0.5,0.5])) in K
 524             True
 525
 526             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 527             >>> (matrix([0,0,0]), matrix([1,0,1])) in K
 528             True
 529
 530             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 531             >>> (matrix([1,1,1]), matrix([1,1,1])) in K
 532             False
 533
 534             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 535             >>> (matrix([1,-1,1]), matrix([1,0,1])) in K
 536             False
 537
 538         Junk arguments don't work:
 539
 540             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 541             >>> [[1,2,3],[4,5,6]] in K
 542             Traceback (most recent call last):
 543             ...
 544             TypeError: the given point is not a cvxopt.base.matrix
 545
 546             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 547             >>> (matrix([1,2]), matrix([3,4,5,6])) in K
 548             Traceback (most recent call last):
 549             ...
 550             TypeError: the given point has the wrong dimensions
 551
 552         """
 553         return all([p in f for (p, f) in zip(point, self.factors())])
 554
 555
 556
 557     def factors(self):
 558         """
 559         Return a tuple containing the factors (in order) of this
 560         cartesian product.
 561
 562         Returns
 563         -------
 564
 565         tuple of :class:`SymmetricCone`.
 566             The factors of this cartesian product.
 567
 568         Examples
 569         --------
 570
 571             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 572             >>> len(K.factors())
 573             2
 574
 575         """
 576         return self._factors
 577
 578
 579     def cvxopt_dims(self):
 580         """
 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:
 584
 585           http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
 586
 587         Returns
 588         -------
 589
 590         dict
 591             A dimension dictionary suitable to feed to CVXOPT.
 592
 593         Examples
 594         --------
 595
 596             >>> K = CartesianProduct(NonnegativeOrthant(3),
 597             ...                      IceCream(2),
 598             ...                      IceCream(3))
 599             >>> d = K.cvxopt_dims()
 600             >>> (d['l'], d['q'], d['s'])
 601             (3, [2, 3], [])
 602
 603         """
 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)]
 614         return dims
 615
 616