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