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
 346         EXAMPLES:
 347
 348             >>> K = SymmetricPSD(2)
 349             >>> matrix([[1,0],[0,1]]) in K
 350             True
 351
 352             >>> K = SymmetricPSD(2)
 353             >>> matrix([[0,0],[0,0]]) in K
 354             True
 355
 356             >>> K = SymmetricPSD(3)
 357             >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
 358             True
 359
 360             >>> K = SymmetricPSD(5)
 361             >>> A = matrix([[5,4,3,2,1],
 362             ...            [4,5,4,3,2],
 363             ...            [3,4,5,4,3],
 364             ...            [2,3,4,5,4],
 365             ...            [1,2,3,4,5]])
 366             >>> A in K
 367             True
 368
 369             >>> K = SymmetricPSD(5)
 370             >>> A = matrix([[1,0,0,0,0],
 371             ...            [0,1,0,0,0],
 372             ...            [0,0,0,0,0],
 373             ...            [0,0,0,1,0],
 374             ...            [0,0,0,0,1]])
 375             >>> A in K
 376             True
 377
 378             >>> K = SymmetricPSD(2)
 379             >>> [[1,2],[2,3]] in K
 380             Traceback (most recent call last):
 381             ...
 382             TypeError: the given point is not a cvxopt.base.matrix
 383
 384             >>> K = SymmetricPSD(3)
 385             >>> matrix([[1,2],[3,4]]) in K
 386             Traceback (most recent call last):
 387             ...
 388             TypeError: the given point has the wrong dimensions
 389
 390         """
 391         if not isinstance(point, matrix):
 392             raise TypeError('the given point is not a cvxopt.base.matrix')
 393         if not point.size == (self.dimension(), self.dimension()):
 394             raise TypeError('the given point has the wrong dimensions')
 395         if not point.typecode == 'd':
 396             point = matrix(point, (self.dimension(), self.dimension()), 'd')
 397         return all([e >= 0 for e in eigenvalues(point)])
 398
 399
 400     def contains_strict(self, point):
 401         """
 402         Return whether or not ``point`` belongs to the interior
 403         of this cone.
 404
 405         INPUT:
 406
 407         An instance of the ``cvxopt.base.matrix`` class having
 408         dimensions ``(n,n)`` where ``n`` is the dimension of this cone.
 409         Its type code must be 'd'.
 410
 411         EXAMPLES:
 412
 413             >>> K = SymmetricPSD(2)
 414             >>> K.contains_strict(matrix([[1,0],[0,1]]))
 415             True
 416
 417             >>> K = SymmetricPSD(2)
 418             >>> K.contains_strict(matrix([[0,0],[0,0]]))
 419             False
 420
 421             >>> K = SymmetricPSD(3)
 422             >>> matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]) in K
 423             True
 424
 425             >>> K = SymmetricPSD(5)
 426             >>> A = matrix([[5,4,3,2,1],
 427             ...            [4,5,4,3,2],
 428             ...            [3,4,5,4,3],
 429             ...            [2,3,4,5,4],
 430             ...            [1,2,3,4,5]])
 431             >>> A in K
 432             True
 433
 434             >>> K = SymmetricPSD(5)
 435             >>> A = matrix([[1,0,0,0,0],
 436             ...            [0,1,0,0,0],
 437             ...            [0,0,0,0,0],
 438             ...            [0,0,0,1,0],
 439             ...            [0,0,0,0,1]])
 440             >>> K.contains_strict(A)
 441             False
 442
 443             >>> K = SymmetricPSD(2)
 444             >>> K.contains_strict([[1,2],[2,3]])
 445             Traceback (most recent call last):
 446             ...
 447             TypeError: the given point is not a cvxopt.base.matrix
 448
 449             >>> K = SymmetricPSD(3)
 450             >>> K.contains_strict(matrix([[1,2],[3,4]]))
 451             Traceback (most recent call last):
 452             ...
 453             TypeError: the given point has the wrong dimensions
 454
 455         """
 456         if not isinstance(point, matrix):
 457             raise TypeError('the given point is not a cvxopt.base.matrix')
 458         if not point.size == (self.dimension(), self.dimension()):
 459             raise TypeError('the given point has the wrong dimensions')
 460         if not point.typecode == 'd':
 461             point = matrix(point, (self.dimension(), self.dimension()), 'd')
 462         return all([e > 0 for e in eigenvalues(point)])
 463
 464
 465 class CartesianProduct(SymmetricCone):
 466     """
 467     A cartesian product of symmetric cones, which is itself a symmetric
 468     cone.
 469
 470     EXAMPLES:
 471
 472         >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 473         >>> print(K)
 474         Cartesian product of dimension 5 with 2 factors:
 475           * Nonnegative orthant in the real 3-space
 476           * Lorentz "ice cream" cone in the real 2-space
 477
 478     """
 479     def __init__(self, *factors):
 480         my_dimension = sum([f.dimension() for f in factors])
 481         super().__init__(my_dimension)
 482         self._factors = factors
 483
 484     def __str__(self):
 485         """
 486         Output a human-readable description of myself.
 487         """
 488         tpl = 'Cartesian product of dimension {:d} with {:d} factors:'
 489         tpl += '\n  * {!s}' * len(self.factors())
 490         format_args = [self.dimension(), len(self.factors())]
 491         format_args += list(self.factors())
 492         return tpl.format(*format_args)
 493
 494     def __contains__(self, point):
 495         """
 496         Return whether or not ``point`` belongs to this cone.
 497
 498         INPUT:
 499
 500         An instance of the ``cvxopt.base.matrix`` class having
 501         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 502
 503         EXAMPLES:
 504
 505             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 506             >>> matrix([1,2,3,1,0.5,0.5]) in K
 507             True
 508
 509             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 510             >>> matrix([0,0,0,1,0,1]) in K
 511             True
 512
 513             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 514             >>> matrix([1,1,1,1,1,1]) in K
 515             False
 516
 517             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 518             >>> matrix([1,-1,1,1,0,1]) in K
 519             False
 520
 521             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 522             >>> [1,2,3,4,5,6] in K
 523             Traceback (most recent call last):
 524             ...
 525             TypeError: the given point is not a cvxopt.base.matrix
 526
 527             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 528             >>> matrix([1,2]) in K
 529             Traceback (most recent call last):
 530             ...
 531             TypeError: the given point has the wrong dimensions
 532
 533         """
 534         if not isinstance(point, matrix):
 535             raise TypeError('the given point is not a cvxopt.base.matrix')
 536         if not point.size == (self.dimension(), 1):
 537             raise TypeError('the given point has the wrong dimensions')
 538
 539         for factor in self.factors():
 540             # Split off the components of ``point`` corresponding to
 541             # ``factor``.
 542             factor_part = point[0:factor.dimension()]
 543             if not factor_part in factor:
 544                 return False
 545             point = point[factor.dimension():]
 546
 547         return True
 548
 549
 550     def contains_strict(self, point):
 551         """
 552         Return whether or not ``point`` belongs to the interior
 553         of this cone.
 554
 555         INPUT:
 556
 557         An instance of the ``cvxopt.base.matrix`` class having
 558         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 559
 560         EXAMPLES:
 561
 562             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 563             >>> K.contains_strict(matrix([1,2,3,1,0.5,0.5]))
 564             True
 565
 566             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 567             >>> K.contains_strict(matrix([1,2,3,1,0,1]))
 568             False
 569
 570             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 571             >>> K.contains_strict(matrix([0,1,1,1,0.5,0.5]))
 572             False
 573
 574             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 575             >>> K.contains_strict(matrix([1,1,1,1,1,1]))
 576             False
 577
 578             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 579             >>> K.contains_strict(matrix([1,-1,1,1,0,1]))
 580             False
 581
 582             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 583             >>> K.contains_strict([1,2,3,4,5,6])
 584             Traceback (most recent call last):
 585             ...
 586             TypeError: the given point is not a cvxopt.base.matrix
 587
 588             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 589             >>> K.contains_strict(matrix([1,2]))
 590             Traceback (most recent call last):
 591             ...
 592             TypeError: the given point has the wrong dimensions
 593
 594         """
 595         if not isinstance(point, matrix):
 596             raise TypeError('the given point is not a cvxopt.base.matrix')
 597         if not point.size == (self.dimension(), 1):
 598             raise TypeError('the given point has the wrong dimensions')
 599
 600         for factor in self.factors():
 601             # Split off the components of ``point`` corresponding to
 602             # ``factor``.
 603             factor_part = point[0:factor.dimension()]
 604             if not factor.contains_strict(factor_part):
 605                 return False
 606             point = point[factor.dimension():]
 607
 608         return True
 609
 610
 611     def factors(self):
 612         """
 613         Return a tuple containing the factors (in order) of this
 614         cartesian product.
 615
 616         EXAMPLES:
 617
 618             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 619             >>> len(K.factors())
 620             2
 621
 622         """
 623         return self._factors
 624
 625     def cvxopt_dims(self):
 626         """
 627         Return a dictionary of dimensions corresponding to the factors
 628         of this cartesian product. The format of this dictionary is
 629         described in the CVXOPT user's guide:
 630
 631           http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
 632
 633         EXAMPLES:
 634
 635             >>> K = CartesianProduct(NonnegativeOrthant(3),
 636             ...                      IceCream(2),
 637             ...                      IceCream(3))
 638             >>> d = K.cvxopt_dims()
 639             >>> (d['l'], d['q'], d['s'])
 640             (3, [2, 3], [])
 641
 642         """
 643         dims = {'l':0, 'q':[], 's':[]}
 644         dims['l'] += sum([K.dimension()
 645                           for K in self.factors()
 646                           if isinstance(K, NonnegativeOrthant)])
 647         dims['q'] = [K.dimension()
 648                      for K in self.factors()
 649                      if isinstance(K, IceCream)]
 650         dims['s'] = [K.dimension()
 651                      for K in self.factors()
 652                      if isinstance(K, SymmetricPSD)]
 653         return dims
 654
 655