Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1# ------------------------------------------------------------------------------ 

2# Copyright (C) 2020 Maximilian Stahlberg 

3# 

4# This file is part of PICOS. 

5# 

6# PICOS is free software: you can redistribute it and/or modify it under the 

7# terms of the GNU General Public License as published by the Free Software 

8# Foundation, either version 3 of the License, or (at your option) any later 

9# version. 

10# 

11# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY 

12# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 

13# A PARTICULAR PURPOSE. See the GNU General Public License for more details. 

14# 

15# You should have received a copy of the GNU General Public License along with 

16# this program. If not, see <http://www.gnu.org/licenses/>. 

17# ------------------------------------------------------------------------------ 

18 

19"""Implements :class:`UncertainNorm`.""" 

20 

21import operator 

22from collections import namedtuple 

23 

24import cvxopt 

25import numpy 

26 

27from ... import glyphs 

28from ...apidoc import api_end, api_start 

29from ...caching import cached_unary_operator 

30from ...constraints.uncertain import (BallUncertainNormConstraint, 

31 ScenarioUncertainConicConstraint) 

32from ..cone_soc import SecondOrderCone 

33from ..data import convert_operands, cvx2np 

34from ..exp_affine import AffineExpression 

35from ..exp_biaffine import BiaffineExpression 

36from ..exp_norm import Norm 

37from ..expression import Expression, refine_operands, validate_prediction 

38from .pert_conic import ConicPerturbationSet, UnitBallPerturbationSet 

39from .pert_scenario import ScenarioPerturbationSet 

40from .uexp_affine import UncertainAffineExpression 

41from .uexp_sqnorm import UncertainSquaredNorm 

42from .uexpression import UncertainExpression 

43 

44_API_START = api_start(globals()) 

45# ------------------------------- 

46 

47 

48class UncertainNorm(UncertainExpression, Expression): 

49 """Euclidean or Frobenius norm of an uncertain affine expression.""" 

50 

51 # -------------------------------------------------------------------------- 

52 # Initialization and factory methods. 

53 # -------------------------------------------------------------------------- 

54 

55 def __init__(self, x): 

56 """Construct an :class:`UncertainNorm`. 

57 

58 :param x: 

59 The uncertain affine expression to denote the norm of. 

60 :type x: 

61 ~picos.expressions.uncertain.uexp_affine.UncertainAffineExpression 

62 """ 

63 if not isinstance(x, UncertainAffineExpression): 

64 raise TypeError("Can only form the uncertain norm of an uncertain " 

65 "affine expression, not of {}.".format(type(x).__name__)) 

66 

67 # Refine perturbation set from ellipsoidal to unit ball. 

68 if x.uncertain and isinstance(x.universe, ConicPerturbationSet) \ 

69 and x.universe.ellipsoidal: 

70 x = x.replace_mutables(x.universe.unit_ball_form[1]) 

71 assert isinstance(x.universe, UnitBallPerturbationSet) 

72 

73 if len(x) == 1: 

74 typeStr = "Uncertain Absolute Value" 

75 symbStr = glyphs.abs(x.string) 

76 else: 

77 typeStr = "Uncertain {} Norm".format( 

78 "Euclidean" if 1 in x.shape else "Frobenius") 

79 symbStr = glyphs.norm(x.string) 

80 

81 Expression.__init__(self, typeStr, symbStr) 

82 

83 self._x = x 

84 

85 # -------------------------------------------------------------------------- 

86 # Properties. 

87 # -------------------------------------------------------------------------- 

88 

89 @property 

90 def x(self): 

91 """Uncertain affine expression under the norm.""" 

92 return self._x 

93 

94 # -------------------------------------------------------------------------- 

95 # Abstract method implementations for Expression, except _predict. 

96 # -------------------------------------------------------------------------- 

97 

98 @cached_unary_operator 

99 def _get_refined(self): 

100 """Implement :meth:`~.expression.Expression._get_refined`.""" 

101 if self.certain: 

102 return Norm(self._x.refined) 

103 else: 

104 return self 

105 

106 Subtype = namedtuple("Subtype", ("argdim", "universe_type")) 

107 

108 def _get_subtype(self): 

109 """Implement :meth:`~.expression.Expression._get_subtype`.""" 

110 return self.Subtype(len(self._x), self.universe.type) 

111 

112 def _get_value(self): 

113 value = self._x._get_value() 

114 

115 if len(value) == 1: 

116 return abs(value) 

117 else: 

118 return cvxopt.matrix(numpy.linalg.norm(numpy.ravel(cvx2np(value)))) 

119 

120 @cached_unary_operator 

121 def _get_mutables(self): 

122 return self._x.mutables 

123 

124 def _is_convex(self): 

125 return True 

126 

127 def _is_concave(self): 

128 return False 

129 

130 def _replace_mutables(self, mapping): 

131 return self.__class__(self._x._replace_mutables(mapping)) 

132 

133 def _freeze_mutables(self, freeze): 

134 return self.__class__(self._x._freeze_mutables(freeze)) 

135 

136 # -------------------------------------------------------------------------- 

137 # Python special method implementations, except constraint-creating ones. 

138 # -------------------------------------------------------------------------- 

139 

140 @convert_operands(scalarRHS=True) 

141 @refine_operands() 

142 def __pow__(self, other): 

143 if isinstance(other, AffineExpression): 

144 if not other.constant or other.value != 2: 

145 raise NotImplementedError( 

146 "You may only take an uncertain norm to the power of two.") 

147 

148 return UncertainSquaredNorm(self._x) 

149 else: 

150 return NotImplemented 

151 

152 # -------------------------------------------------------------------------- 

153 # Constraint-creating operators and _predict. 

154 # -------------------------------------------------------------------------- 

155 

156 @classmethod 

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

158 assert isinstance(subtype, cls.Subtype) 

159 

160 AE = AffineExpression 

161 BAE = BiaffineExpression 

162 UAE = UncertainAffineExpression 

163 CPS = ConicPerturbationSet 

164 UBPS = UnitBallPerturbationSet 

165 SPS = ScenarioPerturbationSet 

166 

167 if issubclass(other.clstype, BAE) and other.subtype.dim != 1: 

168 return NotImplemented 

169 

170 if relation is not operator.__le__: 

171 return NotImplemented 

172 

173 if issubclass(subtype.universe_type.clstype, UBPS): 

174 if issubclass(other.clstype, (AE, UAE)): 

175 if issubclass(other.clstype, UAE) \ 

176 and not issubclass(other.subtype.universe_type.clstype, CPS): 

177 return NotImplemented 

178 

179 if issubclass(other.clstype, UAE): 

180 bound_universe_subtype = other.subtype.universe_type.subtype 

181 else: 

182 bound_universe_subtype = None 

183 

184 return BallUncertainNormConstraint.make_type( 

185 dim=subtype.argdim, 

186 norm_universe_subtype=subtype.universe_type.subtype, 

187 bound_universe_subtype=bound_universe_subtype) 

188 elif issubclass(subtype.universe_type.clstype, SPS): 

189 if issubclass(other.clstype, (AE, UAE)): 

190 if issubclass(other.clstype, UAE) \ 

191 and not issubclass(other.subtype.universe_type.clstype, SPS): 

192 return NotImplemented 

193 

194 return ScenarioUncertainConicConstraint.make_type( 

195 dim=(subtype.argdim + 1), 

196 scenario_count=subtype.universe_type.subtype.scenario_count, 

197 cone_type=SecondOrderCone.make_type(dim=None)) 

198 else: 

199 return NotImplemented 

200 

201 return NotImplemented 

202 

203 @convert_operands(scalarRHS=True) 

204 @validate_prediction 

205 @refine_operands() 

206 def __le__(self, other): 

207 if isinstance(self._x.universe, UnitBallPerturbationSet): 

208 if isinstance(other, (AffineExpression, UncertainAffineExpression)): 

209 # Upper bound must be certain or conically uncertain. 

210 if isinstance(other, UncertainAffineExpression) \ 

211 and not isinstance(other.universe, ConicPerturbationSet): 

212 raise TypeError( 

213 "May only upper bound a conically uncertain norm with a" 

214 " certain or another conically uncertain expression.") 

215 

216 # Uncertain upper bound must have independent uncertainty. 

217 # NOTE: Can only be predicted up to the perturbation type. 

218 if isinstance(other, UncertainAffineExpression) \ 

219 and self.perturbation is other.perturbation: 

220 raise ValueError("If the upper bound to a conically " 

221 "uncertain norm is itself uncertain, then the " 

222 "uncertainty in both sides must be independent " 

223 "(distinct perturbation parameters).") 

224 

225 return BallUncertainNormConstraint(self, other) 

226 elif isinstance(self._x.universe, ScenarioPerturbationSet): 

227 if isinstance(other, (AffineExpression, UncertainAffineExpression)): 

228 # Upper bound must be certain or scenario uncertain. 

229 if isinstance(other, UncertainAffineExpression) \ 

230 and not isinstance(other.universe, ScenarioPerturbationSet): 

231 raise TypeError( 

232 "May only upper bound a scenario uncertain norm with a" 

233 " certain or another scenario uncertain expression.") 

234 

235 # Uncertain upper bound must have equal uncertainty. 

236 # NOTE: Can only be predicted up to the perturbation type. 

237 if isinstance(other, UncertainAffineExpression) \ 

238 and self.perturbation is not other.perturbation: 

239 raise ValueError( 

240 "If the upper bound to a scenario uncertain norm is " 

241 "itself uncertain, then the uncertainty in both sides " 

242 "must be equal (same perturbation parameter).") 

243 

244 return (other // self._x.vec) << SecondOrderCone() 

245 elif isinstance(self._x.universe, ConicPerturbationSet): 

246 # The universe could not be refined to a UnitBallPerturbationSet. 

247 assert not self._x.universe.ellipsoidal 

248 raise TypeError("Upper-bounding an uncertain norm whose " 

249 "perturbation parameter lives in a conic perturbation set is " 

250 "only supported if the perturbation set is an ellipsoid.") 

251 else: 

252 raise TypeError("Upper-bounding an uncertain norm whose " 

253 "perturbation parameter is described by an instance of {} is " 

254 "not supported.".format(self._x.universe.__class__.__name__)) 

255 

256 # Make sure the Python NotImplemented-triggered TypeError works. 

257 assert not isinstance(other, 

258 (AffineExpression, UncertainAffineExpression)) 

259 

260 return NotImplemented 

261 

262 

263# -------------------------------------- 

264__all__ = api_end(_API_START, globals())