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