Coverage for picos/expressions/set_ball.py: 81.69%

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# ------------------------------------------------------------------------------ 

19 

20"""Implements :class:`Ball`.""" 

21 

22import operator 

23from collections import namedtuple 

24 

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 

31 

32_API_START = api_start(globals()) 

33# ------------------------------- 

34 

35 

36class Ball(Set): 

37 r"""A ball of radius :math:`r` according to a (generalized) :math:`p`-norm. 

38 

39 :Definition: 

40 

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. 

44 

45 Let :math:`r \in \mathbb{R}`. 

46 

47 1. For :math:`p \in [1, \infty)` or :math:`p = \infty` (input as 

48 ``float("inf")``), this is the convex set 

49 

50 .. math:: 

51 

52 \{x \in \mathbb{K} \mid \lVert x \rVert_p \leq r\} 

53 

54 for any 

55 

56 .. math:: 

57 

58 \mathbb{K} \in \bigcup_{m, n \in \mathbb{Z}_{\geq 1}} 

59 \left( \mathbb{C}^n \cup \mathbb{C}^{m \times n} \right). 

60 

61 2. For a generalized :math:`p`-norm with :math:`p \in (0, 1)`, this is the 

62 convex set 

63 

64 .. math:: 

65 

66 \{x \in \mathbb{K} \mid \lVert x \rVert_p \geq r \land x \geq 0\} 

67 

68 for any 

69 

70 .. math:: 

71 

72 \mathbb{K} \in \bigcup_{m, n \in \mathbb{Z}_{\geq 1}} 

73 \left( \mathbb{R}^n \cup \mathbb{R}^{m \times n} \right). 

74 

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. 

78 

79 Note further that :math:`r` may be any scalar affine expression, it does not 

80 need to be constant. 

81 

82 .. note:: 

83 

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 """ 

88 

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. 

92 

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) 

103 

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))) 

110 

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))) 

123 

124 self._num = num 

125 self._den = den 

126 self._limit = denominator_limit 

127 self._radius = radius 

128 

129 Set.__init__(self, typeStr, symbStr) 

130 

131 @property 

132 def p(self): 

133 """The value :math:`p` defining the :math:`p`-norm used. 

134 

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) 

139 

140 @property 

141 def r(self): 

142 """The ball's radius :math:`r`.""" 

143 return self._radius 

144 

145 def _get_mutables(self): 

146 return self._radius._get_mutables() 

147 

148 def _replace_mutables(self, mapping): 

149 return self.__class__( 

150 self.p, self._radius._replace_mutables(mapping), self._limit) 

151 

152 Subtype = namedtuple("Subtype", ("num", "den")) 

153 

154 def _get_subtype(self): 

155 return self.Subtype(self._num, self._den) 

156 

157 @classmethod 

158 def _predict(cls, subtype, relation, other): 

159 assert isinstance(subtype, cls.Subtype) 

160 

161 num = subtype.num 

162 den = subtype.den 

163 p = float(num) / float(den) 

164 

165 if relation == operator.__rshift__: 

166 if issubclass(other.clstype, ComplexAffineExpression): 

167 complex = not issubclass(other.clstype, AffineExpression) 

168 

169 if complex and p < 1: 

170 return NotImplemented 

171 

172 # The shape of the real, vectorized version of the element. 

173 shape = (other.subtype.dim * (2 if complex else 1), 1) 

174 

175 norm = Norm.make_type(shape, num, den, num, den) 

176 

177 # HACK: Whether the radius is constant makes no difference. 

178 radius = AffineExpression.make_type((1, 1), None, None) 

179 

180 if p >= 1: 

181 return norm.predict(operator.__le__, radius) 

182 else: 

183 return norm.predict(operator.__ge__, radius) 

184 

185 return NotImplemented 

186 

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.") 

193 

194 norm = Norm(element, self.p, denominator_limit=self._limit) 

195 

196 if self.p >= 1: 

197 return norm <= self._radius 

198 else: 

199 return norm >= self._radius 

200 else: 

201 return NotImplemented 

202 

203 

204# -------------------------------------- 

205__all__ = api_end(_API_START, globals())