Coverage for picos/expressions/set_ball.py: 81.69%
71 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
1# ------------------------------------------------------------------------------
2# Copyright (C) 2019 Maximilian Stahlberg
3# Based on the original picos.expressions module by Guillaume Sagnol.
4#
5# This file is part of PICOS.
6#
7# PICOS is free software: you can redistribute it and/or modify it under the
8# terms of the GNU General Public License as published by the Free Software
9# Foundation, either version 3 of the License, or (at your option) any later
10# version.
11#
12# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
13# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
14# A PARTICULAR PURPOSE. See the GNU General Public License for more details.
15#
16# You should have received a copy of the GNU General Public License along with
17# this program. If not, see <http://www.gnu.org/licenses/>.
18# ------------------------------------------------------------------------------
20"""Implements :class:`Ball`."""
22import operator
23from collections import namedtuple
25from .. import glyphs
26from ..apidoc import api_end, api_start
27from .data import convert_and_refine_arguments, make_fraction
28from .exp_affine import AffineExpression, ComplexAffineExpression, Constant
29from .exp_norm import Norm
30from .set import Set
32_API_START = api_start(globals())
33# -------------------------------
36class Ball(Set):
37 r"""A ball of radius :math:`r` according to a (generalized) :math:`p`-norm.
39 :Definition:
41 In the following, :math:`\lVert \cdot \rVert_p` refers to the vector
42 :math:`p`-norm or to the entrywise matrix :math:`p`-norm, depending on the
43 argument. See :class:`~picos.Norm` for definitions.
45 Let :math:`r \in \mathbb{R}`.
47 1. For :math:`p \in [1, \infty)` or :math:`p = \infty` (input as
48 ``float("inf")``), this is the convex set
50 .. math::
52 \{x \in \mathbb{K} \mid \lVert x \rVert_p \leq r\}
54 for any
56 .. math::
58 \mathbb{K} \in \bigcup_{m, n \in \mathbb{Z}_{\geq 1}}
59 \left( \mathbb{C}^n \cup \mathbb{C}^{m \times n} \right).
61 2. For a generalized :math:`p`-norm with :math:`p \in (0, 1)`, this is the
62 convex set
64 .. math::
66 \{x \in \mathbb{K} \mid \lVert x \rVert_p \geq r \land x \geq 0\}
68 for any
70 .. math::
72 \mathbb{K} \in \bigcup_{m, n \in \mathbb{Z}_{\geq 1}}
73 \left( \mathbb{R}^n \cup \mathbb{R}^{m \times n} \right).
75 Note that :math:`x` may not be complex if :math:`p < 1` due to the implicit
76 :math:`x \geq 0` constraint in this case, which is not meaningful on the
77 complex field.
79 Note further that :math:`r` may be any scalar affine expression, it does not
80 need to be constant.
82 .. note::
84 Due to significant differences in scope, :class:`Ball` is not a
85 subclass of :class:`~.set_ellipsoid.Ellipsoid` even though both
86 classes can represent Euclidean balls around the origin.
87 """
89 @convert_and_refine_arguments("radius")
90 def __init__(self, radius=Constant(1), p=2, denominator_limit=1000):
91 """Construct a :math:`p`-norm ball of given radius.
93 :param radius: The ball's radius.
94 :type radius:
95 float or ~picos.expressions.AffineExpression
96 :param float p: The value for :math:`p`, which is cast to a limited
97 precision fraction.
98 :param int denominator_limit: The largest allowed denominator when
99 casting :math:`p` to a fraction. Higher values can yield a greater
100 precision at reduced performance.
101 """
102 num, den, p, pStr = make_fraction(p, denominator_limit)
104 if not isinstance(radius, AffineExpression):
105 raise TypeError("The ball's radius must be given as a real affine "
106 "expression, not as {}.".format(type(radius).__name__))
107 elif not radius.scalar:
108 raise TypeError("The ball's radius must be scalar, not of shape {}."
109 .format(glyphs.shape(radius.shape)))
111 var = glyphs.free_var_name(radius.string)
112 unit = "Unit " if radius.is1 else ""
113 if p >= 1:
114 typeStr = "{}{}-norm Ball" \
115 .format(unit, pStr if den == 1 else glyphs.parenth(pStr))
116 symbStr = glyphs.set(glyphs.sep(
117 var, glyphs.le(glyphs.pnorm(var, pStr), radius.string)))
118 else:
119 typeStr = "Nonneg. Compl. of {}{}-norm Ball" \
120 .format(unit, pStr if den == 1 else glyphs.parenth(pStr))
121 symbStr = glyphs.set(glyphs.sep(glyphs.ge(var, 0),
122 glyphs.ge(glyphs.pnorm(var, pStr), radius.string)))
124 self._num = num
125 self._den = den
126 self._limit = denominator_limit
127 self._radius = radius
129 Set.__init__(self, typeStr, symbStr)
131 @property
132 def p(self):
133 """The value :math:`p` defining the :math:`p`-norm used.
135 This is a limited precision version of the parameter used when the ball
136 was constructed.
137 """
138 return float(self._num) / float(self._den)
140 @property
141 def r(self):
142 """The ball's radius :math:`r`."""
143 return self._radius
145 def _get_mutables(self):
146 return self._radius._get_mutables()
148 def _replace_mutables(self, mapping):
149 return self.__class__(
150 self.p, self._radius._replace_mutables(mapping), self._limit)
152 Subtype = namedtuple("Subtype", ("num", "den"))
154 def _get_subtype(self):
155 return self.Subtype(self._num, self._den)
157 @classmethod
158 def _predict(cls, subtype, relation, other):
159 assert isinstance(subtype, cls.Subtype)
161 num = subtype.num
162 den = subtype.den
163 p = float(num) / float(den)
165 if relation == operator.__rshift__:
166 if issubclass(other.clstype, ComplexAffineExpression):
167 complex = not issubclass(other.clstype, AffineExpression)
169 if complex and p < 1:
170 return NotImplemented
172 # The shape of the real, vectorized version of the element.
173 shape = (other.subtype.dim * (2 if complex else 1), 1)
175 norm = Norm.make_type(shape, num, den, num, den)
177 # HACK: Whether the radius is constant makes no difference.
178 radius = AffineExpression.make_type((1, 1), None, None)
180 if p >= 1:
181 return norm.predict(operator.__le__, radius)
182 else:
183 return norm.predict(operator.__ge__, radius)
185 return NotImplemented
187 def _rshift_implementation(self, element):
188 if isinstance(element, ComplexAffineExpression):
189 if element.complex and self.p < 1:
190 raise TypeError("Cannot constrain a complex expression to be "
191 "in the nonnegative complement of a generalized p-norm "
192 "ball: Nonnegativity is not clear.")
194 norm = Norm(element, self.p, denominator_limit=self._limit)
196 if self.p >= 1:
197 return norm <= self._radius
198 else:
199 return norm >= self._radius
200 else:
201 return NotImplemented
204# --------------------------------------
205__all__ = api_end(_API_START, globals())