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 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     def __contains__(self, point):
  41         """
  42         Return whether or not ``point`` belongs to this cone.
  43
  44         EXAMPLES:
  45
  46             >>> K = SymmetricCone(5)
  47             >>> matrix([1,2]) in K
  48             Traceback (most recent call last):
  49             ...
  50             NotImplementedError
  51
  52         """
  53         raise NotImplementedError
  54
  55     def contains_strict(self, point):
  56         """
  57         Return whether or not ``point`` belongs to the interior
  58         of this cone.
  59
  60         EXAMPLES:
  61
  62             >>> K = SymmetricCone(5)
  63             >>> K.contains_strict(matrix([1,2]))
  64             Traceback (most recent call last):
  65             ...
  66             NotImplementedError
  67         """
  68         raise NotImplementedError
  69
  70     def dimension(self):
  71         """
  72         Return the dimension of this symmetric cone.
  73
  74         The dimension of this symmetric cone is recorded during its
  75         creation. This method simply returns the recorded value, and
  76         should not need to be overridden in subclasses. We prefer to do
  77         any special computation in ``__init__()`` and record the result
  78         in ``self._dimension``.
  79
  80         EXAMPLES:
  81
  82             >>> K = SymmetricCone(5)
  83             >>> K.dimension()
  84             5
  85
  86         """
  87         return self._dimension
  88
  89
  90 class NonnegativeOrthant(SymmetricCone):
  91     """
  92     The nonnegative orthant in ``n`` dimensions.
  93
  94     EXAMPLES:
  95
  96         >>> K = NonnegativeOrthant(3)
  97         >>> print(K)
  98         Nonnegative orthant in the real 3-space
  99
 100     """
 101     def __str__(self):
 102         """
 103         Output a human-readable description of myself.
 104         """
 105         tpl = 'Nonnegative orthant in the real {:d}-space'
 106         return tpl.format(self.dimension())
 107
 108     def __contains__(self, point):
 109         """
 110         Return whether or not ``point`` belongs to this cone.
 111
 112         INPUT:
 113
 114         An instance of the ``cvxopt.base.matrix`` class having
 115         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 116
 117         EXAMPLES:
 118
 119             >>> K = NonnegativeOrthant(3)
 120             >>> matrix([1,2,3]) in K
 121             True
 122
 123             >>> K = NonnegativeOrthant(3)
 124             >>> matrix([1,-0.1,3]) in K
 125             False
 126
 127             >>> K = NonnegativeOrthant(3)
 128             >>> [1,2,3] in K
 129             Traceback (most recent call last):
 130             ...
 131             TypeError: the given point is not a cvxopt.base.matrix
 132
 133             >>> K = NonnegativeOrthant(3)
 134             >>> matrix([1,2]) in K
 135             Traceback (most recent call last):
 136             ...
 137             TypeError: the given point has the wrong dimensions
 138
 139         """
 140         if not isinstance(point, matrix):
 141             raise TypeError('the given point is not a cvxopt.base.matrix')
 142         if not point.size == (self.dimension(), 1):
 143             raise TypeError('the given point has the wrong dimensions')
 144
 145         return all([x >= 0 for x in point])
 146
 147
 148     def contains_strict(self, point):
 149         """
 150         Return whether or not ``point`` belongs to the interior of this
 151         cone.
 152
 153         INPUT:
 154
 155         An instance of the ``cvxopt.base.matrix`` class having
 156         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 157
 158         EXAMPLES:
 159
 160             >>> K = NonnegativeOrthant(3)
 161             >>> K.contains_strict(matrix([1,2,3]))
 162             True
 163
 164             >>> K = NonnegativeOrthant(3)
 165             >>> K.contains_strict(matrix([1,0,1]))
 166             False
 167
 168             >>> K = NonnegativeOrthant(3)
 169             >>> K.contains_strict(matrix([1,-0.1,3]))
 170             False
 171
 172             >>> K = NonnegativeOrthant(3)
 173             >>> K.contains_strict([1,2,3])
 174             Traceback (most recent call last):
 175             ...
 176             TypeError: the given point is not a cvxopt.base.matrix
 177
 178             >>> K = NonnegativeOrthant(3)
 179             >>> K.contains_strict(matrix([1,2]))
 180             Traceback (most recent call last):
 181             ...
 182             TypeError: the given point has the wrong dimensions
 183
 184         """
 185         if not isinstance(point, matrix):
 186             raise TypeError('the given point is not a cvxopt.base.matrix')
 187         if not point.size == (self.dimension(), 1):
 188             raise TypeError('the given point has the wrong dimensions')
 189
 190         return all([x > 0 for x in point])
 191
 192
 193
 194 class IceCream(SymmetricCone):
 195     """
 196     The nonnegative orthant in ``n`` dimensions.
 197
 198     EXAMPLES:
 199
 200         >>> K = IceCream(3)
 201         >>> print(K)
 202         Lorentz "ice cream" cone in the real 3-space
 203
 204     """
 205     def __str__(self):
 206         """
 207         Output a human-readable description of myself.
 208         """
 209         tpl = 'Lorentz "ice cream" cone in the real {:d}-space'
 210         return tpl.format(self.dimension())
 211
 212
 213     def __contains__(self, point):
 214         """
 215         Return whether or not ``point`` belongs to this cone.
 216
 217         INPUT:
 218
 219         An instance of the ``cvxopt.base.matrix`` class having
 220         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 221
 222         EXAMPLES:
 223
 224             >>> K = IceCream(3)
 225             >>> matrix([1,0.5,0.5]) in K
 226             True
 227
 228             >>> K = IceCream(3)
 229             >>> matrix([1,0,1]) in K
 230             True
 231
 232             >>> K = IceCream(3)
 233             >>> matrix([1,1,1]) in K
 234             False
 235
 236             >>> K = IceCream(3)
 237             >>> [1,2,3] in K
 238             Traceback (most recent call last):
 239             ...
 240             TypeError: the given point is not a cvxopt.base.matrix
 241
 242             >>> K = IceCream(3)
 243             >>> matrix([1,2]) in K
 244             Traceback (most recent call last):
 245             ...
 246             TypeError: the given point has the wrong dimensions
 247
 248         """
 249         if not isinstance(point, matrix):
 250             raise TypeError('the given point is not a cvxopt.base.matrix')
 251         if not point.size == (self.dimension(), 1):
 252             raise TypeError('the given point has the wrong dimensions')
 253
 254         height = point[0]
 255         if self.dimension() == 1:
 256             # In one dimension, the ice cream cone is the nonnegative
 257             # orthant.
 258             return height >= 0
 259         else:
 260             radius = point[1:]
 261             return height >= norm(radius)
 262
 263
 264     def contains_strict(self, point):
 265         """
 266         Return whether or not ``point`` belongs to the interior
 267         of this cone.
 268
 269         INPUT:
 270
 271         An instance of the ``cvxopt.base.matrix`` class having
 272         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 273
 274         EXAMPLES:
 275
 276             >>> K = IceCream(3)
 277             >>> K.contains_strict(matrix([1,0.5,0.5]))
 278             True
 279
 280             >>> K = IceCream(3)
 281             >>> K.contains_strict(matrix([1,0,1]))
 282             False
 283
 284             >>> K = IceCream(3)
 285             >>> K.contains_strict(matrix([1,1,1]))
 286             False
 287
 288             >>> K = IceCream(3)
 289             >>> K.contains_strict([1,2,3])
 290             Traceback (most recent call last):
 291             ...
 292             TypeError: the given point is not a cvxopt.base.matrix
 293
 294             >>> K = IceCream(3)
 295             >>> K.contains_strict(matrix([1,2]))
 296             Traceback (most recent call last):
 297             ...
 298             TypeError: the given point has the wrong dimensions
 299
 300         """
 301         if not isinstance(point, matrix):
 302             raise TypeError('the given point is not a cvxopt.base.matrix')
 303         if not point.size == (self.dimension(), 1):
 304             raise TypeError('the given point has the wrong dimensions')
 305
 306         height = point[0]
 307         if self.dimension() == 1:
 308             # In one dimension, the ice cream cone is the nonnegative
 309             # orthant.
 310             return height > 0
 311         else:
 312             radius = point[1:]
 313             return height > norm(radius)
 314
 315
 316 class SymmetricPSD(SymmetricCone):
 317     """
 318     The nonnegative orthant in ``n`` dimensions.
 319
 320     EXAMPLES:
 321
 322         >>> K = SymmetricPSD(3)
 323         >>> print(K)
 324         Cone of symmetric positive-semidefinite matrices on the real 3-space
 325
 326     """
 327     def __str__(self):
 328         """
 329         Output a human-readable description of myself.
 330         """
 331         tpl = 'Cone of symmetric positive-semidefinite matrices ' \
 332               'on the real {:d}-space'
 333         return tpl.format(self.dimension())
 334
 335
 336 class CartesianProduct(SymmetricCone):
 337     """
 338     A cartesian product of symmetric cones, which is itself a symmetric
 339     cone.
 340
 341     EXAMPLES:
 342
 343         >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 344         >>> print(K)
 345         Cartesian product of dimension 5 with 2 factors:
 346           * Nonnegative orthant in the real 3-space
 347           * Lorentz "ice cream" cone in the real 2-space
 348
 349     """
 350     def __init__(self, *factors):
 351         my_dimension = sum([f.dimension() for f in factors])
 352         super().__init__(my_dimension)
 353         self._factors = factors
 354
 355     def __str__(self):
 356         """
 357         Output a human-readable description of myself.
 358         """
 359         tpl = 'Cartesian product of dimension {:d} with {:d} factors:'
 360         tpl += '\n  * {!s}' * len(self.factors())
 361         format_args = [self.dimension(), len(self.factors())]
 362         format_args += list(self.factors())
 363         return tpl.format(*format_args)
 364
 365     def __contains__(self, point):
 366         """
 367         Return whether or not ``point`` belongs to this cone.
 368
 369         INPUT:
 370
 371         An instance of the ``cvxopt.base.matrix`` class having
 372         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 373
 374         EXAMPLES:
 375
 376             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 377             >>> matrix([1,2,3,1,0.5,0.5]) in K
 378             True
 379
 380             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 381             >>> matrix([0,0,0,1,0,1]) in K
 382             True
 383
 384             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 385             >>> matrix([1,1,1,1,1,1]) in K
 386             False
 387
 388             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 389             >>> matrix([1,-1,1,1,0,1]) in K
 390             False
 391
 392             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 393             >>> [1,2,3,4,5,6] in K
 394             Traceback (most recent call last):
 395             ...
 396             TypeError: the given point is not a cvxopt.base.matrix
 397
 398             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 399             >>> matrix([1,2]) in K
 400             Traceback (most recent call last):
 401             ...
 402             TypeError: the given point has the wrong dimensions
 403
 404         """
 405         if not isinstance(point, matrix):
 406             raise TypeError('the given point is not a cvxopt.base.matrix')
 407         if not point.size == (self.dimension(), 1):
 408             raise TypeError('the given point has the wrong dimensions')
 409
 410         for factor in self.factors():
 411             # Split off the components of ``point`` corresponding to
 412             # ``factor``.
 413             factor_part = point[0:factor.dimension()]
 414             if not factor_part in factor:
 415                 return False
 416             point = point[factor.dimension():]
 417
 418         return True
 419
 420
 421     def contains_strict(self, point):
 422         """
 423         Return whether or not ``point`` belongs to the interior
 424         of this cone.
 425
 426         INPUT:
 427
 428         An instance of the ``cvxopt.base.matrix`` class having
 429         dimensions ``(n,1)`` where ``n`` is the dimension of this cone.
 430
 431         EXAMPLES:
 432
 433             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 434             >>> K.contains_strict(matrix([1,2,3,1,0.5,0.5]))
 435             True
 436
 437             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 438             >>> K.contains_strict(matrix([1,2,3,1,0,1]))
 439             False
 440
 441             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 442             >>> K.contains_strict(matrix([0,1,1,1,0.5,0.5]))
 443             False
 444
 445             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 446             >>> K.contains_strict(matrix([1,1,1,1,1,1]))
 447             False
 448
 449             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 450             >>> K.contains_strict(matrix([1,-1,1,1,0,1]))
 451             False
 452
 453             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 454             >>> K.contains_strict([1,2,3,4,5,6])
 455             Traceback (most recent call last):
 456             ...
 457             TypeError: the given point is not a cvxopt.base.matrix
 458
 459             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(3))
 460             >>> K.contains_strict(matrix([1,2]))
 461             Traceback (most recent call last):
 462             ...
 463             TypeError: the given point has the wrong dimensions
 464
 465         """
 466         if not isinstance(point, matrix):
 467             raise TypeError('the given point is not a cvxopt.base.matrix')
 468         if not point.size == (self.dimension(), 1):
 469             raise TypeError('the given point has the wrong dimensions')
 470
 471         for factor in self.factors():
 472             # Split off the components of ``point`` corresponding to
 473             # ``factor``.
 474             factor_part = point[0:factor.dimension()]
 475             if not factor.contains_strict(factor_part):
 476                 return False
 477             point = point[factor.dimension():]
 478
 479         return True
 480
 481
 482     def factors(self):
 483         """
 484         Return a tuple containing the factors (in order) of this
 485         cartesian product.
 486
 487         EXAMPLES:
 488
 489             >>> K = CartesianProduct(NonnegativeOrthant(3), IceCream(2))
 490             >>> len(K.factors())
 491             2
 492
 493         """
 494         return self._factors
 495
 496     def cvxopt_dims(self):
 497         """
 498         Return a dictionary of dimensions corresponding to the factors
 499         of this cartesian product. The format of this dictionary is
 500         described in the CVXOPT user's guide:
 501
 502           http://cvxopt.org/userguide/coneprog.html#linear-cone-programs
 503
 504         EXAMPLES:
 505
 506             >>> K = CartesianProduct(NonnegativeOrthant(3),
 507             ...                      IceCream(2),
 508             ...                      IceCream(3))
 509             >>> d = K.cvxopt_dims()
 510             >>> (d['l'], d['q'], d['s'])
 511             (3, [2, 3], [])
 512
 513         """
 514         dims = {'l':0, 'q':[], 's':[]}
 515         dims['l'] += sum([K.dimension()
 516                           for K in self.factors()
 517                           if isinstance(K, NonnegativeOrthant)])
 518         dims['q'] = [K.dimension()
 519                      for K in self.factors()
 520                      if isinstance(K, IceCream)]
 521         dims['s'] = [K.dimension()
 522                      for K in self.factors()
 523                      if isinstance(K, SymmetricPSD)]
 524         return dims
 525
 526