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