Coverage for picos/expressions/exp_extremum.py: 85.00%
200 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-02-15 14:21 +0000
« prev ^ index » next coverage.py v6.5.0, created at 2023-02-15 14:21 +0000
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# ------------------------------------------------------------------------------
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]
101 def _get_mutables(self):
102 return frozenset(mtb for x in self.expressions for mtb in x.mutables)
104 def _replace_mutables(self, mapping):
105 return self.__class__(
106 x._replace_mutables(mapping) for x in self.expressions)
108 def _freeze_mutables(self, freeze):
109 return self.__class__(
110 x._freeze_mutables(freeze) for x in self.expressions)
112 @property
113 def argnum(self):
114 """Number of expressions under the extremum."""
115 return len(self.expressions)
117 @classmethod
118 def _mul(cls, self, other, forward):
119 if isinstance(other, AffineExpression) and other.constant:
120 factor = other.safe_value
122 if not factor:
123 return AffineExpression.zero()
124 elif factor == 1:
125 return self
126 elif factor == -1:
127 return -self
129 if forward:
130 string = glyphs.clever_mul(self.string, other.string)
131 else:
132 string = glyphs.clever_mul(other.string, self.string)
134 cls_ = self.__class__ if factor > 0 else self._other_class
136 product = cls_(factor*x for x in self.expressions)
137 product._typeStr = "Scaled " + product._typeStr
138 product._symbStr = string
140 return product
142 if forward:
143 return Expression.__mul__(self, other)
144 else:
145 return Expression.__rmul__(self, other)
147 @convert_operands(scalarRHS=True)
148 @refine_operands()
149 def __mul__(self, other):
150 return ExtremumBase._mul(self, other, True)
152 @convert_operands(scalarRHS=True)
153 @refine_operands()
154 def __rmul__(self, other):
155 return ExtremumBase._mul(self, other, False)
157 @cached_selfinverse_unary_operator
158 def __neg__(self):
159 return self._other_class(-x for x in self.expressions)
162class MaximumBase:
163 """Base implementation of :class:`ExtremumBase` for maximums."""
165 # --------------------------------------------------------------------------
166 # Abstract method implementations for ExtremumBase.
167 # --------------------------------------------------------------------------
169 @property
170 def _extremum(self):
171 return max
173 @property
174 def _extremum_word(self):
175 return "maximum"
177 @property
178 def _extremum_glyph(self):
179 return glyphs.max
181 def _property(self, x):
182 return x.convex
184 @property
185 def _property_word(self):
186 return "convex"
188 # --------------------------------------------------------------------------
189 # Abstract method implementations for Expression.
190 # --------------------------------------------------------------------------
192 def _is_convex(self):
193 return True
195 def _is_concave(self):
196 return False
199class MinimumBase:
200 """Base implementation of :class:`ExtremumBase` for minimums."""
202 # --------------------------------------------------------------------------
203 # Abstract method implementations for ExtremumBase.
204 # --------------------------------------------------------------------------
206 @property
207 def _extremum(self):
208 return min
210 @property
211 def _extremum_word(self):
212 return "minimum"
214 @property
215 def _extremum_glyph(self):
216 return glyphs.min
218 def _property(self, x):
219 return x.concave
221 @property
222 def _property_word(self):
223 return "concave"
225 # --------------------------------------------------------------------------
226 # Abstract method implementations for Expression.
227 # --------------------------------------------------------------------------
229 def _is_convex(self):
230 return False
232 def _is_concave(self):
233 return True
236class Extremum(ExtremumBase, Expression):
237 """Base class for :class:`MaximumConvex` and :class:`MinimumConcave`.
239 .. note::
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 """
247 # --------------------------------------------------------------------------
248 # Initialization and factory methods.
249 # --------------------------------------------------------------------------
251 def __init__(self, expressions):
252 """Construct a :class:`MaximumConvex` or :class:`MinimumConcave`.
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]))
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)
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))
277 if not x.scalar:
278 raise TypeError(
279 "The expression {} is not scalar.".format(x.string))
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__))
287 self._expressions = expressions
289 typeStr = "{} of {} Functions".format(
290 self._extremum_word.title(), self._property_word.title())
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]))
297 Expression.__init__(self, typeStr, symbStr)
299 # --------------------------------------------------------------------------
300 # Abstract method implementations for ExtremumBase.
301 # --------------------------------------------------------------------------
303 @property
304 def expressions(self):
305 """The expressions under the extremum."""
306 return self._expressions
308 # --------------------------------------------------------------------------
309 # Abstract method implementations for Expression, except _predict.
310 # --------------------------------------------------------------------------
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
320 Subtype = namedtuple("Subtype", ("types",))
322 def _get_subtype(self):
323 return self.Subtype(tuple(x.type for x in self._expressions))
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))
331 # --------------------------------------------------------------------------
332 # Constraint-creating operators, and _predict.
333 # --------------------------------------------------------------------------
335 @classmethod
336 def _predict(cls, subtype, relation, other):
337 assert isinstance(subtype, cls.Subtype)
339 convex = issubclass(cls, MaximumConvex)
340 concave = issubclass(cls, MinimumConcave)
342 if relation == operator.__le__:
343 if not convex:
344 return NotImplemented
346 if not issubclass(other.clstype, AffineExpression) \
347 or other.subtype.dim != 1:
348 return NotImplemented
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
356 if not issubclass(other.clstype, AffineExpression) \
357 or other.subtype.dim != 1:
358 return NotImplemented
360 return ExtremumConstraint.make_type(
361 lhs_types=subtype.types, relation=Constraint.GE, rhs_type=other)
363 return NotImplemented
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))
373 if isinstance(other, AffineExpression):
374 return ExtremumConstraint(self, Constraint.LE, other)
376 return NotImplemented
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))
386 if isinstance(other, AffineExpression):
387 return ExtremumConstraint(self, Constraint.GE, other)
389 return NotImplemented
392class MaximumConvex(MaximumBase, Extremum):
393 """The maximum over a set of convex scalar expressions.
395 :Example:
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 """
409 # --------------------------------------------------------------------------
410 # Abstract method implementations for ExtremumBase.
411 # --------------------------------------------------------------------------
413 @property
414 def _other_class(self):
415 return MinimumConcave
418class MinimumConcave(MinimumBase, Extremum):
419 """The minimum over a set of concave scalar expressions.
421 :Example:
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 """
438 # --------------------------------------------------------------------------
439 # Abstract method implementations for ExtremumBase.
440 # --------------------------------------------------------------------------
442 @property
443 def _other_class(self):
444 return MaximumConvex
447# --------------------------------------
448__all__ = api_end(_API_START, globals())