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:`MaximumConvex` and :class:`MinimumConcave`.""" 

20 

21import operator 

22from abc import ABC, abstractmethod 

23from collections import namedtuple 

24 

25import cvxopt 

26 

27from .. import glyphs 

28from ..apidoc import api_end, api_start 

29from ..caching import cached_selfinverse_unary_operator 

30from ..constraints import Constraint, ExtremumConstraint 

31from ..formatting import arguments 

32from .data import convert_operands 

33from .exp_affine import AffineExpression, Constant 

34from .expression import Expression, refine_operands, validate_prediction 

35 

36_API_START = api_start(globals()) 

37# ------------------------------- 

38 

39 

40class ExtremumBase(ABC): 

41 """Base class for :class:`Extremum` and similar classes. 

42 

43 In particular, this is also used by the uncertain 

44 :class:`~.uexp_rand_pwl.RandomExtremumAffine`. 

45 

46 Must be inherited with priority with respect to 

47 :class:`~picos.expressions.Expression`. 

48 """ 

49 

50 # -------------------------------------------------------------------------- 

51 # Implemented by MaximumBase and MinimumBase. 

52 # -------------------------------------------------------------------------- 

53 

54 @property 

55 @abstractmethod 

56 def _extremum(self): 

57 pass 

58 

59 @property 

60 @abstractmethod 

61 def _extremum_word(self): 

62 pass 

63 

64 @property 

65 @abstractmethod 

66 def _extremum_glyph(self): 

67 pass 

68 

69 @abstractmethod 

70 def _property(self, x): 

71 pass 

72 

73 @property 

74 @abstractmethod 

75 def _property_word(self): 

76 pass 

77 

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

79 # Implemented by the expression class. 

80 # -------------------------------------------------------------------------- 

81 

82 @property 

83 @abstractmethod 

84 def _other_class(self): 

85 pass 

86 

87 @property 

88 @abstractmethod 

89 def expressions(self): 

90 """The expressions under the extremum.""" 

91 pass 

92 

93 # -------------------------------------------------------------------------- 

94 # Provided/implemented by this base class. 

95 # -------------------------------------------------------------------------- 

96 

97 @property 

98 def _extremum_short_word(self): 

99 return self._extremum_word[:3] 

100 

101 def _get_mutables(self): 

102 return frozenset(mtb for x in self._expressions for mtb in x.mutables) 

103 

104 def _replace_mutables(self, mapping): 

105 return self.__class__( 

106 x._replace_mutables(mapping) for x in self._expressions) 

107 

108 def _freeze_mutables(self, freeze): 

109 return self.__class__( 

110 x._freeze_mutables(freeze) for x in self._expressions) 

111 

112 @property 

113 def argnum(self): 

114 """Number of expressions under the extremum.""" 

115 return len(self._expressions) 

116 

117 @convert_operands(scalarRHS=True) 

118 @refine_operands() 

119 def __mul__(self, other): 

120 if isinstance(other, AffineExpression): 

121 if not other.constant: 

122 raise NotImplementedError("You may only multiply a {} of {} " 

123 "expressions with a constant term.".format( 

124 self._extremum_word, self._property_word)) 

125 

126 value = other.safe_value 

127 

128 if value == 0: 

129 return Constant(0) 

130 elif value == 1: 

131 return self 

132 elif value > 0: 

133 product = self.__class__(value*x for x in self._expressions) 

134 product._typeStr = "Scaled " + product._typeStr 

135 product._symbStr = glyphs.clever_mul(self.string, other.string) 

136 return product 

137 else: 

138 return self._other_class(value*x for x in self._expressions) 

139 else: 

140 return NotImplemented 

141 

142 @convert_operands(scalarRHS=True) 

143 @refine_operands() 

144 def __rmul__(self, other): 

145 if isinstance(other, AffineExpression): 

146 product = self.__mul__(other) 

147 value = other.safe_value 

148 

149 if value > 0 and value != 1: 

150 # NOTE: product is a fresh expression in this case. 

151 product._symbStr = glyphs.clever_mul(other.string, self.string) 

152 

153 return product 

154 else: 

155 return NotImplemented 

156 

157 @cached_selfinverse_unary_operator 

158 def __neg__(self): 

159 return self._other_class(-x for x in self._expressions) 

160 

161 

162class MaximumBase: 

163 """Base implementation of :class:`ExtremumBase` for maximums.""" 

164 

165 # -------------------------------------------------------------------------- 

166 # Abstract method implementations for ExtremumBase. 

167 # -------------------------------------------------------------------------- 

168 

169 @property 

170 def _extremum(self): 

171 return max 

172 

173 @property 

174 def _extremum_word(self): 

175 return "maximum" 

176 

177 @property 

178 def _extremum_glyph(self): 

179 return glyphs.max 

180 

181 def _property(self, x): 

182 return x.convex 

183 

184 @property 

185 def _property_word(self): 

186 return "convex" 

187 

188 # -------------------------------------------------------------------------- 

189 # Abstract method implementations for Expression. 

190 # -------------------------------------------------------------------------- 

191 

192 def _is_convex(self): 

193 return True 

194 

195 def _is_concave(self): 

196 return False 

197 

198 

199class MinimumBase: 

200 """Base implementation of :class:`ExtremumBase` for minimums.""" 

201 

202 # -------------------------------------------------------------------------- 

203 # Abstract method implementations for ExtremumBase. 

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

205 

206 @property 

207 def _extremum(self): 

208 return min 

209 

210 @property 

211 def _extremum_word(self): 

212 return "minimum" 

213 

214 @property 

215 def _extremum_glyph(self): 

216 return glyphs.min 

217 

218 def _property(self, x): 

219 return x.concave 

220 

221 @property 

222 def _property_word(self): 

223 return "concave" 

224 

225 # -------------------------------------------------------------------------- 

226 # Abstract method implementations for Expression. 

227 # -------------------------------------------------------------------------- 

228 

229 def _is_convex(self): 

230 return False 

231 

232 def _is_concave(self): 

233 return True 

234 

235 

236class Extremum(ExtremumBase, Expression): 

237 """Base class for :class:`MaximumConvex` and :class:`MinimumConcave`. 

238 

239 .. note:: 

240 

241 This can represent the maximum (minimum) over convex (concave) uncertain 

242 expressions as long as the uncertainty is not of stochastic nature. 

243 In this case, the extremum implicitly goes over the perturbation 

244 parameters as well. 

245 """ 

246 

247 # -------------------------------------------------------------------------- 

248 # Initialization and factory methods. 

249 # -------------------------------------------------------------------------- 

250 

251 def __init__(self, expressions): 

252 """Construct a :class:`MaximumConvex` or :class:`MinimumConcave`. 

253 

254 :param expressions: 

255 A collection of all convex or all concave expressions. 

256 """ 

257 # Multidimensional expressions are iterable and yield expressions but 

258 # denoting their extremum is handled by SumExtremes. 

259 if isinstance(expressions, Expression): 

260 word = self._property_word 

261 raise TypeError("The class {} is not designed to represent the {} " 

262 "over (the elements of) a single expression. This is the job of" 

263 " SumExtremes. Use picos.{} to use whichever is appropriate." 

264 .format(self.__class__.__name__, word, word[:3])) 

265 

266 # Load constant data and refine expressions. 

267 expressions = tuple( 

268 x.refined if isinstance(x, Expression) else Constant(x) 

269 for x in expressions) 

270 

271 # Validate that every expression is convex (concave) and scalar. 

272 for x in expressions: 

273 if not self._property(x): 

274 raise TypeError("The expression {} is not {}." 

275 .format(x.string, self._property_word)) 

276 

277 if not x.scalar: 

278 raise TypeError( 

279 "The expression {} is not scalar.".format(x.string)) 

280 

281 # Handle uncertain but not random expressions. 

282 if any(x.uncertain and x.random for x in expressions): 

283 raise NotImplementedError("The (fallback) class {} does not handle " 

284 "random expressions as taking the expectation does not commute " 

285 "with taking the extremum.".format(self.__class__.__name__)) 

286 

287 self._expressions = expressions 

288 

289 typeStr = "{} of {} Functions".format( 

290 self._extremum_word.title(), self._property_word.title()) 

291 

292 symbStr = self._extremum_glyph(arguments([ 

293 x.string if x.certain 

294 else x.worst_case_string(self._extremum_short_word) 

295 for x in expressions])) 

296 

297 Expression.__init__(self, typeStr, symbStr) 

298 

299 # -------------------------------------------------------------------------- 

300 # Abstract method implementations for ExtremumBase. 

301 # -------------------------------------------------------------------------- 

302 

303 @property 

304 def expressions(self): 

305 """The expressions under the extremum.""" 

306 return self._expressions 

307 

308 # -------------------------------------------------------------------------- 

309 # Abstract method implementations for Expression, except _predict. 

310 # -------------------------------------------------------------------------- 

311 

312 def _get_refined(self): 

313 if len(self._expressions) == 1: 

314 return self._expressions[0] 

315 elif all(x.constant for x in self._expressions): 

316 return self._extremum(self._expressions, key=lambda x: x.safe_value) 

317 else: 

318 return self 

319 

320 Subtype = namedtuple("Subtype", ("types",)) 

321 

322 def _get_subtype(self): 

323 return self.Subtype(tuple(x.type for x in self._expressions)) 

324 

325 def _get_value(self): 

326 return cvxopt.matrix(self._extremum( 

327 x.safe_value if x.certain 

328 else x.worst_case_value(self._extremum_short_word) 

329 for x in self._expressions)) 

330 

331 # -------------------------------------------------------------------------- 

332 # Constraint-creating operators, and _predict. 

333 # -------------------------------------------------------------------------- 

334 

335 @classmethod 

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

337 assert isinstance(subtype, cls.Subtype) 

338 

339 convex = issubclass(cls, MaximumConvex) 

340 concave = issubclass(cls, MinimumConcave) 

341 

342 if relation == operator.__le__: 

343 if not convex: 

344 return NotImplemented 

345 

346 if not issubclass(other.clstype, AffineExpression) \ 

347 or other.subtype.dim != 1: 

348 return NotImplemented 

349 

350 return ExtremumConstraint.make_type( 

351 lhs_types=subtype.types, relation=Constraint.LE, rhs_type=other) 

352 elif relation == operator.__ge__: 

353 if not concave: 

354 return NotImplemented 

355 

356 if not issubclass(other.clstype, AffineExpression) \ 

357 or other.subtype.dim != 1: 

358 return NotImplemented 

359 

360 return ExtremumConstraint.make_type( 

361 lhs_types=subtype.types, relation=Constraint.GE, rhs_type=other) 

362 

363 return NotImplemented 

364 

365 @convert_operands(scalarRHS=True) 

366 @validate_prediction 

367 @refine_operands() 

368 def __le__(self, other): 

369 if not self.convex: 

370 raise TypeError("Cannot upper-bound the nonconvex expression {}." 

371 .format(self.string)) 

372 

373 if isinstance(other, AffineExpression): 

374 return ExtremumConstraint(self, Constraint.LE, other) 

375 

376 return NotImplemented 

377 

378 @convert_operands(scalarRHS=True) 

379 @validate_prediction 

380 @refine_operands() 

381 def __ge__(self, other): 

382 if not self.concave: 

383 raise TypeError("Cannot lower-bound the nonconcave expression {}." 

384 .format(self.string)) 

385 

386 if isinstance(other, AffineExpression): 

387 return ExtremumConstraint(self, Constraint.GE, other) 

388 

389 return NotImplemented 

390 

391 

392class MaximumConvex(MaximumBase, Extremum): 

393 """The maximum over a set of convex scalar expressions. 

394 

395 :Example: 

396 

397 >>> import picos 

398 >>> x = picos.RealVariable("x", 4) 

399 >>> a = abs(x) 

400 >>> b = picos.sum(x) 

401 >>> c = picos.max([a, b]); c 

402 <Maximum of Convex Functions: max(‖x‖, ∑(x))> 

403 >>> 2*c 

404 <Scaled Maximum of Convex Functions: 2·max(‖x‖, ∑(x))> 

405 >>> c <= 5 

406 <Maximum of Convex Functions Constraint: max(‖x‖, ∑(x)) ≤ 5> 

407 """ 

408 

409 # -------------------------------------------------------------------------- 

410 # Abstract method implementations for ExtremumBase. 

411 # -------------------------------------------------------------------------- 

412 

413 @property 

414 def _other_class(self): 

415 return MinimumConcave 

416 

417 

418class MinimumConcave(MinimumBase, Extremum): 

419 """The minimum over a set of concave scalar expressions. 

420 

421 :Example: 

422 

423 >>> import picos 

424 >>> x = picos.RealVariable("x", 4) 

425 >>> a = picos.sum(x) 

426 >>> b = 2*a 

427 >>> c = picos.min([a, b]); c 

428 <Minimum of Concave Functions: min(∑(x), 2·∑(x))> 

429 >>> -1*c 

430 <Maximum of Convex Functions: max(-∑(x), -2·∑(x))> 

431 >>> C = 5 <= c; C 

432 <Minimum of Concave Functions Constraint: min(∑(x), 2·∑(x)) ≥ 5> 

433 >>> x.value = 1 

434 >>> C.slack 

435 -1.0 

436 """ 

437 

438 # -------------------------------------------------------------------------- 

439 # Abstract method implementations for ExtremumBase. 

440 # -------------------------------------------------------------------------- 

441 

442 @property 

443 def _other_class(self): 

444 return MaximumConvex 

445 

446 

447# -------------------------------------- 

448__all__ = api_end(_API_START, globals())