src/dunshire/cones.py

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