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:`UncertainAffineExpression`.""" 

20 

21import operator 

22from collections import namedtuple 

23 

24from ...apidoc import api_end, api_start 

25from ...caching import cached_property, cached_unary_operator 

26from ...constraints.uncertain import (ConicallyUncertainAffineConstraint, 

27 ScenarioUncertainConicConstraint) 

28from ..data import convert_operands, cvxopt_K 

29from ..exp_affine import AffineExpression 

30from ..exp_biaffine import BiaffineExpression 

31from ..expression import ExpressionType, refine_operands, validate_prediction 

32from ..variables import BaseVariable 

33from .uexpression import UncertainExpression 

34 

35# NOTE: May not import ConicPerturbationSet from .pert_conic here because the 

36# latter imports from .perturbation which in turn needs to import 

37# UncertainAffineExpression as a base class of Perturbation from here. 

38 

39 

40_API_START = api_start(globals()) 

41# ------------------------------- 

42 

43 

44class UncertainAffineExpression(UncertainExpression, BiaffineExpression): 

45 r"""A multidimensional uncertain affine expression. 

46 

47 This expression has the form 

48 

49 .. math:: 

50 

51 A(x,\theta) = B(x,\theta) + P(x) + Q(\theta) + C 

52 

53 where :math:`B`, :math:`P`, :math:`Q`, :math:`C` and :math:`x` are defined 

54 as for the :class:`~.exp_biaffine.BiaffineExpression` base class and 

55 :math:`\theta` is an uncertain perturbation parameter confined to 

56 (distributed according to) a perturbation set (distribution) :math:`\Theta`. 

57 

58 If no coefficient matrices defining :math:`B` and :math:`P` are provided, 

59 then this expression represents uncertain data confined to an uncertainty 

60 set :math:`\{Q(\theta) + C \mid \theta \in \Theta\}` (distributed according 

61 to :math:`Q(\Theta) + C`) where :math:`C` can be understood as a nominal 

62 data value while :math:`Q(\theta)` quantifies the uncertainty on the data. 

63 """ 

64 

65 # -------------------------------------------------------------------------- 

66 # Abstract method implementations for Expression, except _predict. 

67 # -------------------------------------------------------------------------- 

68 

69 Subtype = namedtuple("Subtype", ("shape", "universe_type")) 

70 Subtype.dim = property(lambda self: self.shape[0] * self.shape[1]) 

71 

72 def _get_subtype(self): 

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

74 return self.Subtype(self._shape, self.universe.type) 

75 

76 # -------------------------------------------------------------------------- 

77 # Method overridings for Expression. 

78 # -------------------------------------------------------------------------- 

79 

80 def _get_refined(self): 

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

82 if self.certain: 

83 return AffineExpression(self.string, self.shape, self._coefs) 

84 else: 

85 return self 

86 

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

88 # Abstract method implementations for BiaffineExpression. 

89 # -------------------------------------------------------------------------- 

90 

91 @classmethod 

92 def _get_bilinear_terms_allowed(cls): 

93 """Implement for :class:`~.exp_biaffine.BiaffineExpression`.""" 

94 return True 

95 

96 @classmethod 

97 def _get_parameters_allowed(cls): 

98 """Implement for :class:`~.exp_biaffine.BiaffineExpression`.""" 

99 return True 

100 

101 @classmethod 

102 def _get_basetype(cls): 

103 """Implement :meth:`~.exp_biaffine.BiaffineExpression._get_basetype`.""" 

104 return UncertainAffineExpression 

105 

106 @classmethod 

107 def _get_typecode(cls): 

108 """Implement :meth:`~.exp_biaffine.BiaffineExpression._get_typecode`.""" 

109 return "d" 

110 

111 # -------------------------------------------------------------------------- 

112 # Method overridings for BiaffineExpression. 

113 # -------------------------------------------------------------------------- 

114 

115 @classmethod 

116 def _get_type_string_base(cls): 

117 """Override for :class:`~.exp_biaffine.BiaffineExpression`.""" 

118 # TODO: Allow the strings "Uncertain (Linear Expression|Constant)". 

119 return "Uncertain {}".format("Affine Expression") 

120 

121 def __init__(self, string, shape=(1, 1), coefficients={}): 

122 """Construct an :class:`UncertainAffineExpression`. 

123 

124 Extends :meth:`.exp_biaffine.BiaffineExpression.__init__`. 

125 

126 This constructor is meant for internal use. As a user, you will want to 

127 first define a universe (e.g. 

128 :class:`~.pert_conic.ConicPerturbationSet`) for a 

129 :class:`perturbation parameter <.perturbation.Perturbation>` and use 

130 that parameter as a building block to create more complex uncertain 

131 expressions. 

132 """ 

133 from .perturbation import Perturbation 

134 

135 BiaffineExpression.__init__(self, string, shape, coefficients) 

136 

137 if not all(isinstance(prm, Perturbation) for prm in self.parameters): 

138 raise TypeError("Uncertain affine expressions may not depend on " 

139 "parameters other than perturbation parameters.") 

140 

141 for pair in self._bilinear_coefs: 

142 x, y = pair 

143 

144 d = sum(isinstance(var, BaseVariable) for var in pair) 

145 p = sum(isinstance(var, Perturbation) for var in pair) 

146 

147 # Forbid a quadratic part. 

148 if d > 1: 

149 raise TypeError("Tried to create an uncertain affine " 

150 "expression that is {}.".format( 

151 "quadratic in {}".format(x.string) if x is y else 

152 "biaffine in {} and {}".format(x.string, y.string))) 

153 

154 # Forbid quadratic dependence on the perturbation parameter. 

155 if p > 1: 

156 assert x is y 

157 raise NotImplementedError("Uncertain affine expressions may " 

158 "only depend affinely on the perturbation parameter. Tried " 

159 "to create one that is quadratic in {}.".format(x.string)) 

160 

161 assert d == 1 and p == 1 

162 

163 @classmethod 

164 def _common_basetype(cls, other, reverse=False): 

165 from ..exp_affine import AffineExpression 

166 

167 # HACK: AffineExpression is not a subclass of UncertainAffineExpression 

168 # but we can treat it as one when it comes to basetype detection. 

169 if issubclass(other._get_basetype(), AffineExpression): 

170 return UncertainAffineExpression 

171 else: 

172 return BiaffineExpression._common_basetype.__func__( 

173 cls, other, reverse) 

174 

175 def _is_convex(self): 

176 return True 

177 

178 def _is_concave(self): 

179 return True 

180 

181 # -------------------------------------------------------------------------- 

182 # Class-specific properties. 

183 # -------------------------------------------------------------------------- 

184 

185 @cached_property 

186 def _sorted_bilinear_coefs(self): 

187 """Bilinear part coefficients with perturbation on the right side.""" 

188 from .perturbation import Perturbation 

189 

190 coefs = {} 

191 for mtbs, coef in self._bilinear_coefs.items(): 

192 x, y = mtbs 

193 

194 if isinstance(x, Perturbation): 

195 # Obtain a fitting commutation matrix. 

196 K = cvxopt_K(y.dim, x.dim, self._typecode) 

197 

198 # Make coef apply to vec(y*x.T) instead of vec(x*y.T). 

199 coef = coef * K 

200 

201 # Swap x and y. 

202 x, y = y, x 

203 

204 assert isinstance(x, BaseVariable) 

205 assert isinstance(y, Perturbation) 

206 

207 coefs[x, y] = coef 

208 

209 return coefs 

210 

211 # -------------------------------------------------------------------------- 

212 # Expression-creating operators. 

213 # -------------------------------------------------------------------------- 

214 

215 @cached_unary_operator 

216 def __abs__(self): 

217 """Denote the Euclidean or Frobenius norm of the expression.""" 

218 from .uexp_norm import UncertainNorm 

219 

220 return UncertainNorm(self) 

221 

222 # -------------------------------------------------------------------------- 

223 # Constraint-creating operators and _predict. 

224 # -------------------------------------------------------------------------- 

225 

226 @classmethod 

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

228 from ..cone_nno import NonnegativeOrthant 

229 from ..cone_psd import PositiveSemidefiniteCone 

230 from ..set import Set 

231 from .pert_conic import ConicPerturbationSet 

232 from .pert_scenario import ScenarioPerturbationSet 

233 

234 assert isinstance(subtype, cls.Subtype) 

235 

236 universe = subtype.universe_type 

237 

238 if relation in (operator.__le__, operator.__ge__): 

239 if issubclass(universe.clstype, ConicPerturbationSet): 

240 if issubclass(other.clstype, 

241 (AffineExpression, UncertainAffineExpression)) \ 

242 and other.subtype.shape == subtype.shape: 

243 return ConicallyUncertainAffineConstraint.make_type( 

244 dim=subtype.dim, 

245 universe_subtype=universe.subtype) 

246 elif issubclass(universe.clstype, ScenarioPerturbationSet): 

247 if issubclass(other.clstype, 

248 (AffineExpression, UncertainAffineExpression)) \ 

249 and other.subtype.shape == subtype.shape: 

250 return ScenarioUncertainConicConstraint.make_type( 

251 dim=subtype.dim, 

252 scenario_count=universe.subtype.scenario_count, 

253 cone_type=NonnegativeOrthant.make_type(subtype.dim)) 

254 elif relation in (operator.__lshift__, operator.__rshift__): 

255 if relation == operator.__lshift__ \ 

256 and issubclass(other.clstype, Set): 

257 own_type = ExpressionType(cls, subtype) 

258 return other.predict(operator.__rshift__, own_type) 

259 

260 if issubclass(other.clstype, 

261 (AffineExpression, UncertainAffineExpression)) \ 

262 and other.subtype.shape == subtype.shape: 

263 if subtype.shape[0] != subtype.shape[1]: 

264 return NotImplemented 

265 

266 self = ExpressionType(cls, subtype) 

267 

268 return self.predict(operator.__lshift__, 

269 PositiveSemidefiniteCone.make_type(dim=None)) 

270 

271 return NotImplemented 

272 

273 @convert_operands(sameShape=True) 

274 @validate_prediction 

275 @refine_operands() 

276 def __le__(self, other): 

277 from ..cone_nno import NonnegativeOrthant 

278 from .pert_conic import ConicPerturbationSet 

279 from .pert_scenario import ScenarioPerturbationSet 

280 

281 if isinstance(self.perturbation.universe, ConicPerturbationSet): 

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

283 return ConicallyUncertainAffineConstraint(self - other) 

284 elif isinstance(self.perturbation.universe, ScenarioPerturbationSet): 

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

286 return ScenarioUncertainConicConstraint( 

287 other - self, NonnegativeOrthant(len(self))) 

288 else: 

289 raise NotImplementedError("Uncertain affine constraints " 

290 "parameterized by {} are not supported.".format( 

291 self.perturbation.universe.__class__.__name__)) 

292 

293 return NotImplemented 

294 

295 @convert_operands(sameShape=True) 

296 @validate_prediction 

297 @refine_operands() 

298 def __ge__(self, other): 

299 from ..cone_nno import NonnegativeOrthant 

300 from .pert_conic import ConicPerturbationSet 

301 from .pert_scenario import ScenarioPerturbationSet 

302 

303 if isinstance(self.perturbation.universe, ConicPerturbationSet): 

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

305 return ConicallyUncertainAffineConstraint(other - self) 

306 elif isinstance(self.perturbation.universe, ScenarioPerturbationSet): 

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

308 return ScenarioUncertainConicConstraint( 

309 self - other, NonnegativeOrthant(len(self))) 

310 else: 

311 raise NotImplementedError("Uncertain affine constraints " 

312 "parameterized by {} are not supported.".format( 

313 self.perturbation.universe.__class__.__name__)) 

314 

315 return NotImplemented 

316 

317 @staticmethod 

318 def _lmi_helper(lower, greater): 

319 from ..cone_psd import PositiveSemidefiniteCone 

320 

321 if isinstance(lower, UncertainAffineExpression) \ 

322 and isinstance(greater, UncertainAffineExpression) \ 

323 and lower.perturbation is not greater.perturbation: 

324 # NOTE: This failure cannot be predicted. 

325 raise ValueError("Can only form a linear matrix inequality if one " 

326 "side is certain or both sides depend on the same uncertainty.") 

327 

328 diff = greater - lower 

329 

330 if not diff.square: 

331 raise TypeError("Can only form a linear matrix inequality from " 

332 "square matrices.") 

333 

334 if not diff.hermitian: 

335 # NOTE: This failure cannot be predicted. 

336 raise TypeError("Can only form a linear matrix inequality from " 

337 "hermitian matrices.") 

338 

339 return diff << PositiveSemidefiniteCone() 

340 

341 def _lshift_implementation(self, other): 

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

343 return self._lmi_helper(self, other) 

344 

345 return NotImplemented 

346 

347 def _rshift_implementation(self, other): 

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

349 return self._lmi_helper(other, self) 

350 

351 return NotImplemented 

352 

353 

354# -------------------------------------- 

355__all__ = api_end(_API_START, globals())