Coverage for picos/expressions/exp

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

4# This file is part of PICOS.

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

19"""Implements :class:`MaximumConvex` and :class:`MinimumConcave`."""

21import operator

22from abc import ABC, abstractmethod

23from collections import namedtuple

25import cvxopt

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

36_API_START = api_start(globals())

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

40class ExtremumBase(ABC):

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

43 In particular, this is also used by the uncertain

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

46 Must be inherited with priority with respect to

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

48 """

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

51 # Implemented by MaximumBase and MinimumBase.

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

54 @property

55 @abstractmethod

56 def _extremum(self):

57 pass

59 @property

60 @abstractmethod

61 def _extremum_word(self):

62 pass

64 @property

65 @abstractmethod

66 def _extremum_glyph(self):

67 pass

69 @abstractmethod

70 def _property(self, x):

71 pass

73 @property

74 @abstractmethod

75 def _property_word(self):

76 pass

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

79 # Implemented by the expression class.

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

82 @property

83 @abstractmethod

84 def _other_class(self):

85 pass

87 @property

88 @abstractmethod

89 def expressions(self):

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

91 pass

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

94 # Provided/implemented by this base class.

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

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 @classmethod

118 def _mul(cls, self, other, forward):

119 if isinstance(other, AffineExpression) and other.constant:

120 factor = other.safe_value

121

122 if not factor:

123 return AffineExpression.zero()

124 elif factor == 1:

125 return self

126 elif factor == -1:

127 return -self

128

129 if forward:

130 string = glyphs.clever_mul(self.string, other.string)

131 else:

132 string = glyphs.clever_mul(other.string, self.string)

133

134 cls_ = self.__class__ if factor > 0 else self._other_class

135

136 product = cls_(factor*x for x in self.expressions)

137 product._typeStr = "Scaled " + product._typeStr

138 product._symbStr = string

139

140 return product

141

142 if forward:

143 return Expression.__mul__(self, other)

144 else:

145 return Expression.__rmul__(self, other)

146

147 @convert_operands(scalarRHS=True)

148 @refine_operands()

149 def __mul__(self, other):

150 return ExtremumBase._mul(self, other, True)

151

152 @convert_operands(scalarRHS=True)

153 @refine_operands()

154 def __rmul__(self, other):

155 return ExtremumBase._mul(self, other, False)

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

Coverage for picos/expressions/exp_extremum.py: 85.00%

200 statements