src/dunshire/cones.py

   1 """
   2 Class definitions for all of the symmetric cones (and their superclass,
   3 SymmetricCone) supported by CVXOPT.
   4 """
   5
   6 from cvxopt import matrix
   7 from matrices import eigenvalues, norm
   8
   9 class SymmetricCone:
  10     """
  11     An instance of a symmetric (self-dual and homogeneous) cone.
  12
  13     There are three types of symmetric cones supported by CVXOPT:
  14
  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.
  18
  19     This class is intended to encompass them all.
  20     """
  21     def __init__(self, dimension):
  22         """
  23         A generic constructor for symmetric cones.
  24
  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
  28         for later.
  29
  30         INPUT:
  31
  32         - ``dimension`` -- the dimension of this cone.
  33
  34         """
  35         if dimension <= 0:
  36             raise ValueError('cones must have dimension greater than zero')
  37
  38         self._dimension = dimension
  39
  40
  41     def __contains__(self, point):
  42         """
  43         Return whether or not ``point`` belongs to this cone.
  44
  45         EXAMPLES:
  46
  47             >>> K = SymmetricCone(5)
  48             >>> matrix([1,2]) in K
  49             Traceback (most recent call last):
  50             ...
  51             NotImplementedError
  52
  53         """
  54         raise NotImplementedError
  55
  56     def contains_strict(self, point):
  57         """
  58         Return whether or not ``point`` belongs to the interior
  59         of this cone.
  60
  61         EXAMPLES:
  62
  63             >>> K = SymmetricCone(5)
  64             >>> K.contains_strict(matrix([1,2]))
  65             Traceback (most recent call last):
  66             ...
  67             NotImplementedError
  68         """
  69         raise NotImplementedError
  70
  71     def dimension(self):
  72         """
  73         Return the dimension of this symmetric cone.
  74
  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``.
  80
  81         EXAMPLES:
  82
  83             >>> K = SymmetricCone(5)
  84             >>> K.dimension()
  85             5
  86
  87         """
  88         return self._dimension
  89
  90
  91 class NonnegativeOrthant(SymmetricCone):
  92     """
  93     The nonnegative orthant in ``n`` dimensions.
  94
  95     EXAMPLES:
  96
  97         >>> K = NonnegativeOrthant(3)
  98         >>> print(K)
  99         Nonnegative orthant in the real 3-space
 100
 101     """
 102     def __str__(self):
 103         """
 104         Output a human-readable description of myself.
 105         """
 106         tpl = 'Nonnegative orthant in the real {:d}-space'
 107         return tpl.format(self.dimension())
 108
 109     def __contains__(self, point):
 110         """
 111         Return whether or not ``point`` belongs to this cone.
 112
 113         INPUT:
 114
 115         An instance of the ``cvxopt.base.matrix`` class having
 116         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 117
 118         EXAMPLES:
 119
 120             >>> K = NonnegativeOrthant(3)
 121             >>> matrix([1,2,3]) in K
 122             True
 123
 124             >>> K = NonnegativeOrthant(3)
 125             >>> matrix([1,-0.1,3]) in K
 126             False
 127
 128             >>> K = NonnegativeOrthant(3)
 129             >>> [1,2,3] in K
 130             Traceback (most recent call last):
 131             ...
 132             TypeError: the given point is not a cvxopt.base.matrix
 133
 134             >>> K = NonnegativeOrthant(3)
 135             >>> matrix([1,2]) in K
 136             Traceback (most recent call last):
 137             ...
 138             TypeError: the given point has the wrong dimensions
 139
 140         """
 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')
 145
 146         return all([x >= 0 for x in point])
 147
 148
 149     def contains_strict(self, point):
 150         """
 151         Return whether or not ``point`` belongs to the interior of this
 152         cone.
 153
 154         INPUT:
 155
 156         An instance of the ``cvxopt.base.matrix`` class having
 157         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 158
 159         EXAMPLES:
 160
 161             >>> K = NonnegativeOrthant(3)
 162             >>> K.contains_strict(matrix([1,2,3]))
 163             True
 164
 165             >>> K = NonnegativeOrthant(3)
 166             >>> K.contains_strict(matrix([1,0,1]))
 167             False
 168
 169             >>> K = NonnegativeOrthant(3)
 170             >>> K.contains_strict(matrix([1,-0.1,3]))
 171             False
 172
 173             >>> K = NonnegativeOrthant(3)
 174             >>> K.contains_strict([1,2,3])
 175             Traceback (most recent call last):
 176             ...
 177             TypeError: the given point is not a cvxopt.base.matrix
 178
 179             >>> K = NonnegativeOrthant(3)
 180             >>> K.contains_strict(matrix([1,2]))
 181             Traceback (most recent call last):
 182             ...
 183             TypeError: the given point has the wrong dimensions
 184
 185         """
 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')
 190
 191         return all([x > 0 for x in point])
 192
 193
 194
 195 class IceCream(SymmetricCone):
 196     """
 197     The nonnegative orthant in ``n`` dimensions.
 198
 199     EXAMPLES:
 200
 201         >>> K = IceCream(3)
 202         >>> print(K)
 203         Lorentz "ice cream" cone in the real 3-space
 204
 205     """
 206     def __str__(self):
 207         """
 208         Output a human-readable description of myself.
 209         """
 210         tpl = 'Lorentz "ice cream" cone in the real {:d}-space'
 211         return tpl.format(self.dimension())
 212
 213
 214     def __contains__(self, point):
 215         """
 216         Return whether or not ``point`` belongs to this cone.
 217
 218         INPUT:
 219
 220         An instance of the ``cvxopt.base.matrix`` class having
 221         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 222
 223         EXAMPLES:
 224
 225             >>> K = IceCream(3)
 226             >>> matrix([1,0.5,0.5]) in K
 227             True
 228
 229             >>> K = IceCream(3)
 230             >>> matrix([1,0,1]) in K
 231             True
 232
 233             >>> K = IceCream(3)
 234             >>> matrix([1,1,1]) in K
 235             False
 236
 237             >>> K = IceCream(3)
 238             >>> [1,2,3] in K
 239             Traceback (most recent call last):
 240             ...
 241             TypeError: the given point is not a cvxopt.base.matrix
 242
 243             >>> K = IceCream(3)
 244             >>> matrix([1,2]) in K
 245             Traceback (most recent call last):
 246             ...
 247             TypeError: the given point has the wrong dimensions
 248
 249         """
 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')
 254
 255         height = point[0]
 256         if self.dimension() == 1:
 257             # In one dimension, the ice cream cone is the nonnegative
 258             # orthant.
 259             return height >= 0
 260         else:
 261             radius = point[1:]
 262             return height >= norm(radius)
 263
 264
 265     def contains_strict(self, point):
 266         """
 267         Return whether or not ``point`` belongs to the interior
 268         of this cone.
 269
 270         INPUT:
 271
 272         An instance of the ``cvxopt.base.matrix`` class having
 273         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 274
 275         EXAMPLES:
 276
 277             >>> K = IceCream(3)
 278             >>> K.contains_strict(matrix([1,0.5,0.5]))
 279             True
 280
 281             >>> K = IceCream(3)
 282             >>> K.contains_strict(matrix([1,0,1]))
 283             False
 284
 285             >>> K = IceCream(3)
 286             >>> K.contains_strict(matrix([1,1,1]))
 287             False
 288
 289             >>> K = IceCream(3)
 290             >>> K.contains_strict([1,2,3])
 291             Traceback (most recent call last):
 292             ...
 293             TypeError: the given point is not a cvxopt.base.matrix
 294
 295             >>> K = IceCream(3)
 296             >>> K.contains_strict(matrix([1,2]))
 297             Traceback (most recent call last):
 298             ...
 299             TypeError: the given point has the wrong dimensions
 300
 301         """
 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')
 306
 307         height = point[0]
 308         if self.dimension() == 1:
 309             # In one dimension, the ice cream cone is the nonnegative
 310             # orthant.
 311             return height > 0
 312         else:
 313             radius = point[1:]
 314             return height > norm(radius)
 315
 316
 317 class SymmetricPSD(SymmetricCone):
 318     """
 319     The nonnegative orthant in ``n`` dimensions.
 320
 321     EXAMPLES:
 322
 323         >>> K = SymmetricPSD(3)
 324         >>> print(K)
 325         Cone of symmetric positive-semidefinite matrices on the real 3-space
 326
 327     """
 328     def __str__(self):
 329         """
 330         Output a human-readable description of myself.
 331         """
 332         tpl = 'Cone of symmetric positive-semidefinite matrices ' \
 333               'on the real {:d}-space'
 334         return tpl.format(self.dimension())
 335
 336
 337     def __contains__(self, point):
 338         """
 339         Return whether or not ``point`` belongs to this cone.
 340
 341         INPUT:
 342
 343         An instance of the ``cvxopt.base.matrix`` class having
 344         dimensions ``(n,n)`` where ``n`` is the dimension of this cone.
 345         Its type code must be 'd'.
 346
 347         EXAMPLES:
 348
 349             >>> K = SymmetricPSD(2)
 350             >>> matrix([[1,0],[0,1]], tc='d') in K
 351             True
 352
 353             >>> K = SymmetricPSD(2)
 354             >>> matrix([[0,0],[0,0]], tc='d') in K
 355             True
 356
 357             >>> K = SymmetricPSD(2)
 358             >>> [[1,2],[2,3]] in K
 359             Traceback (most recent call last):
 360             ...
 361             TypeError: the given point is not a cvxopt.base.matrix
 362
 363             >>> K = SymmetricPSD(3)
 364             >>> matrix([[1,2],[3,4]], tc='d') in K
 365             Traceback (most recent call last):
 366             ...
 367             TypeError: the given point has the wrong dimensions
 368
 369         """
 370         if not isinstance(point, matrix):
 371             raise TypeError('the given point is not a cvxopt.base.matrix')
 372         if not point.size == (self.dimension(), self.dimension()):
 373             raise TypeError('the given point has the wrong dimensions')
 374         return all([e >= 0 for e in eigenvalues(point)])
 375
 376
 377     def contains_strict(self, point):
 378         """
 379         Return whether or not ``point`` belongs to the interior
 380         of this cone.
 381
 382         INPUT:
 383
 384         An instance of the ``cvxopt.base.matrix`` class having
 385         dimensions ``(n,n)`` where ``n`` is the dimension of this cone.
 386         Its type code must be 'd'.
 387
 388         EXAMPLES:
 389
 390             >>> K = SymmetricPSD(2)
 391             >>> K.contains_strict(matrix([[1,0],[0,1]], tc='d'))
 392             True
 393
 394             >>> K = SymmetricPSD(2)
 395             >>> K.contains_strict(matrix([[0,0],[0,0]], tc='d'))
 396             False
 397
 398             >>> K = SymmetricPSD(2)
 399             >>> K.contains_strict([[1,2],[2,3]])
 400             Traceback (most recent call last):
 401             ...
 402             TypeError: the given point is not a cvxopt.base.matrix
 403
 404             >>> K = SymmetricPSD(3)
 405             >>> K.contains_strict(matrix([[1,2],[3,4]], tc='d'))
 406             Traceback (most recent call last):
 407             ...
 408             TypeError: the given point has the wrong dimensions
 409
 410         """
 411         if not isinstance(point, matrix):
 412             raise TypeError('the given point is not a cvxopt.base.matrix')
 413         if not point.size == (self.dimension(), self.dimension()):
 414             raise TypeError('the given point has the wrong dimensions')
 415         return all([e > 0 for e in eigenvalues(point)])
 416
 417
 418 class CartesianProduct(SymmetricCone):
 419     """
 420     A cartesian product of symmetric cones, which is itself a symmetric
 421     cone.
 422
 423     EXAMPLES:
 424
 425         >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 426         >>> print(K)
 427         Cartesian product of dimension 5 with 2 factors:
 428           * Nonnegative orthant in the real 3-space
 429           * Lorentz "ice cream" cone in the real 2-space
 430
 431     """
 432     def __init__(self, *factors):
 433         my_dimension = sum([f.dimension() for f in factors])
 434         super().__init__(my_dimension)
 435         self._factors = factors
 436
 437     def __str__(self):
 438         """
 439         Output a human-readable description of myself.
 440         """
 441         tpl = 'Cartesian product of dimension {:d} with {:d} factors:'
 442         tpl += '\n  * {!s}' * len(self.factors())
 443         format_args = [self.dimension(), len(self.factors())]
 444         format_args += list(self.factors())
 445         return tpl.format(*format_args)
 446
 447     def __contains__(self, point):
 448         """
 449         Return whether or not ``point`` belongs to this cone.
 450
 451         INPUT:
 452
 453         An instance of the ``cvxopt.base.matrix`` class having
 454         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 455
 456         EXAMPLES:
 457
 458             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 459             >>> matrix([1,2,3,1,0.5,0.5]) in K
 460             True
 461
 462             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 463             >>> matrix([0,0,0,1,0,1]) in K
 464             True
 465
 466             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 467             >>> matrix([1,1,1,1,1,1]) in K
 468             False
 469
 470             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 471             >>> matrix([1,-1,1,1,0,1]) in K
 472             False
 473
 474             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 475             >>> [1,2,3,4,5,6] in K
 476             Traceback (most recent call last):
 477             ...
 478             TypeError: the given point is not a cvxopt.base.matrix
 479
 480             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 481             >>> matrix([1,2]) in K
 482             Traceback (most recent call last):
 483             ...
 484             TypeError: the given point has the wrong dimensions
 485
 486         """
 487         if not isinstance(point, matrix):
 488             raise TypeError('the given point is not a cvxopt.base.matrix')
 489         if not point.size == (self.dimension(), 1):
 490             raise TypeError('the given point has the wrong dimensions')
 491
 492         for factor in self.factors():
 493             # Split off the components of ``point`` corresponding to
 494             # ``factor``.
 495             factor_part = point[0:factor.dimension()]
 496             if not factor_part in factor:
 497                 return False
 498             point = point[factor.dimension():]
 499
 500         return True
 501
 502
 503     def contains_strict(self, point):
 504         """
 505         Return whether or not ``point`` belongs to the interior
 506         of this cone.
 507
 508         INPUT:
 509
 510         An instance of the ``cvxopt.base.matrix`` class having
 511         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 512
 513         EXAMPLES:
 514
 515             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 516             >>> K.contains_strict(matrix([1,2,3,1,0.5,0.5]))
 517             True
 518
 519             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 520             >>> K.contains_strict(matrix([1,2,3,1,0,1]))
 521             False
 522
 523             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 524             >>> K.contains_strict(matrix([0,1,1,1,0.5,0.5]))
 525             False
 526
 527             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 528             >>> K.contains_strict(matrix([1,1,1,1,1,1]))
 529             False
 530
 531             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 532             >>> K.contains_strict(matrix([1,-1,1,1,0,1]))
 533             False
 534
 535             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 536             >>> K.contains_strict([1,2,3,4,5,6])
 537             Traceback (most recent call last):
 538             ...
 539             TypeError: the given point is not a cvxopt.base.matrix
 540
 541             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 542             >>> K.contains_strict(matrix([1,2]))
 543             Traceback (most recent call last):
 544             ...
 545             TypeError: the given point has the wrong dimensions
 546
 547         """
 548         if not isinstance(point, matrix):
 549             raise TypeError('the given point is not a cvxopt.base.matrix')
 550         if not point.size == (self.dimension(), 1):
 551             raise TypeError('the given point has the wrong dimensions')
 552
 553         for factor in self.factors():
 554             # Split off the components of ``point`` corresponding to
 555             # ``factor``.
 556             factor_part = point[0:factor.dimension()]
 557             if not factor.contains_strict(factor_part):
 558                 return False
 559             point = point[factor.dimension():]
 560
 561         return True
 562
 563
 564     def factors(self):
 565         """
 566         Return a tuple containing the factors (in order) of this
 567         cartesian product.
 568
 569         EXAMPLES:
 570
 571             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 572             >>> len(K.factors())
 573             2
 574
 575         """
 576         return self._factors
 577
 578     def cvxopt_dims(self):
 579         """
 580         Return a dictionary of dimensions corresponding to the factors
 581         of this cartesian product. The format of this dictionary is
 582         described in the CVXOPT user's guide:
 583
 584           http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
 585
 586         EXAMPLES:
 587
 588             >>> K = CartesianProduct(NonnegativeOrthant(3),
 589             ...                      IceCream(2),
 590             ...                      IceCream(3))
 591             >>> d = K.cvxopt_dims()
 592             >>> (d['l'], d['q'], d['s'])
 593             (3, [2, 3], [])
 594
 595         """
 596         dims = {'l':0, 'q':[], 's':[]}
 597         dims['l'] += sum([K.dimension()
 598                           for K in self.factors()
 599                           if isinstance(K, NonnegativeOrthant)])
 600         dims['q'] = [K.dimension()
 601                      for K in self.factors()
 602                      if isinstance(K, IceCream)]
 603         dims['s'] = [K.dimension()
 604                      for K in self.factors()
 605                      if isinstance(K, SymmetricPSD)]
 606         return dims
 607
 608