Coverage for picos/expressions/expression.py : 72.14%

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) 2019 Maximilian Stahlberg
3# Based on the original picos.expressions module by Guillaume Sagnol.
4#
5# This file is part of PICOS.
6#
7# PICOS is free software: you can redistribute it and/or modify it under the
8# terms of the GNU General Public License as published by the Free Software
9# Foundation, either version 3 of the License, or (at your option) any later
10# version.
11#
12# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
13# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
14# A PARTICULAR PURPOSE. See the GNU General Public License for more details.
15#
16# You should have received a copy of the GNU General Public License along with
17# this program. If not, see <http://www.gnu.org/licenses/>.
18# ------------------------------------------------------------------------------
20"""Backend for expression type implementations."""
22import functools
23import operator
24import threading
25import warnings
26from abc import ABC, abstractmethod
27from contextlib import contextmanager
29import cvxopt
31from .. import glyphs
32from ..apidoc import api_end, api_start
33from ..caching import cached_property
34from ..constraints import ConstraintType
35from ..containers import DetailedType
36from ..legacy import deprecated
37from .data import convert_operands
39_API_START = api_start(globals())
40# -------------------------------
43def validate_prediction(the_operator):
44 """Validate that the constraint outcome matches the predicted outcome."""
45 @functools.wraps(the_operator)
46 def wrapper(lhs, rhs, *args, **kwargs):
47 from .set import Set
49 def what():
50 return "({}).{}({})".format(
51 lhs._symbStr, the_operator.__name__, rhs._symbStr)
53 assert isinstance(lhs, (Expression, Set)) \
54 and isinstance(rhs, (Expression, Set)), \
55 "validate_prediction must occur below convert_operands."
57 lhs_type = lhs.type
58 rhs_type = rhs.type
60 try:
61 abstract_operator = getattr(operator, the_operator.__name__)
62 except AttributeError as error:
63 raise AssertionError("validate_prediction may only decorate "
64 "standard operator implementations.") from error
66 try:
67 predictedType = lhs_type.predict(abstract_operator, rhs_type)
68 except NotImplementedError:
69 predictedType = None # No prediction was made.
70 except PredictedFailure:
71 predictedType = NotImplemented # Prediction is "not possible".
73 try:
74 outcome = the_operator(lhs, rhs, *args, **kwargs)
75 except Exception as error:
76 # Case where the prediction is positive and the outcome is negative.
77 if predictedType not in (None, NotImplemented):
78 warnings.warn(
79 "Outcome for {} was predicted {} but the operation raised "
80 "an error: \"{}\" This a noncritical error (false positive)"
81 " in PICOS' constraint outcome prediction."
82 .format(what(), predictedType, error),
83 category=RuntimeWarning, stacklevel=3)
84 raise
85 else:
86 raise
88 # Case where the prediction is negative and the outcome is positive.
89 if predictedType is NotImplemented and outcome is not NotImplemented:
90 raise AssertionError(
91 "The operation {} was predicted to fail but it produced "
92 "an output of {}.".format(what(), outcome.type))
94 # Case where no prediction was made.
95 if not predictedType:
96 return outcome
98 # Case where the outcome is try-to-reverse-the-operation.
99 if outcome is NotImplemented:
100 return outcome
102 # Case where the prediction and the outcome are positive but differ.
103 outcomeType = outcome.type
104 if not predictedType.equals(outcomeType):
105 raise AssertionError("Outcome for {} was predicted {} but is {}."
106 .format(what(), predictedType, outcomeType))
108 return outcome
109 return wrapper
112def refine_operands(stop_at_affine=False):
113 """Cast :meth:`~Expression.refined` on both operands.
115 If the left hand side operand (i.e. ``self``) is refined to an instance of a
116 different type, then, instead of the decorated method, the method with the
117 same name on the refined type is invoked with the (refined) right hand side
118 operand as its argument.
120 This decorator is supposed to be used on all constraint creating binary
121 operator methods so that degenerated instances (e.g. a complex affine
122 expression with an imaginary part of zero) can occur but are not used in
123 constraints. This speeds up many computations involving expressions as these
124 degenerate cases do not need to be detected. Note that
125 :attr:`Expression.type` also refers to the refined version of an expression.
127 :param bool stop_at_affine: Do not refine any affine expressions, in
128 particular do not refine complex affine expressions to real ones.
129 """
130 def decorator(the_operator):
131 @functools.wraps(the_operator)
132 def wrapper(lhs, rhs, *args, **kwargs):
133 from .exp_affine import ComplexAffineExpression
134 from .set import Set
136 assert isinstance(lhs, (Expression, Set)) \
137 and isinstance(rhs, (Expression, Set)), \
138 "refine_operands must occur below convert_operands."
140 if stop_at_affine and isinstance(lhs, ComplexAffineExpression):
141 lhs_refined = lhs
142 else:
143 lhs_refined = lhs.refined
145 if type(lhs_refined) is not type(lhs):
146 assert hasattr(lhs_refined, the_operator.__name__), \
147 "refine_operand transformed 'self' to another type that " \
148 "does not define an operator with the same name as the " \
149 "decorated one."
151 refined_operation = getattr(lhs_refined, the_operator.__name__)
153 return refined_operation(rhs, *args, **kwargs)
155 if stop_at_affine and isinstance(rhs, ComplexAffineExpression):
156 rhs_refined = rhs
157 else:
158 rhs_refined = rhs.refined
160 return the_operator(lhs_refined, rhs_refined, *args, **kwargs)
161 return wrapper
162 return decorator
165# TODO: Once PICOS requires Python >= 3.7, use a ContextVar instead.
166class _Refinement(threading.local):
167 allowed = True
170_REFINEMENT = _Refinement()
173@contextmanager
174def no_refinement():
175 """Context manager that disables the effect of :meth:`Expression.refined`.
177 This can be necessary to ensure that the outcome of a constraint coversion
178 is as predicted, in particular when PICOS uses overridden comparison
179 operators for constraint creation internally.
180 """
181 _REFINEMENT.allowed = False
183 try:
184 yield
185 finally:
186 _REFINEMENT.allowed = True
189class NotValued(RuntimeError):
190 """The operation cannot be performed due to a mutable without a value.
192 Note that the :attr:`~.expression.Expression.value` and
193 :attr:`~.expression.Expression.value_as_matrix` attributes do not raise this
194 exception, but return :obj:`None`.
195 """
197 pass
200class PredictedFailure(TypeError):
201 """Denotes that comparing two expressions will not form a constraint."""
203 pass
206class ExpressionType(DetailedType):
207 """The detailed type of an expression for predicting constraint outcomes.
209 This is suffcient to predict the detailed type of any constraint that can be
210 created by comparing with another expression.
211 """
213 @staticmethod
214 def _relation_str(relation):
215 if relation is operator.__eq__:
216 return "=="
217 elif relation is operator.__le__:
218 return "<="
219 elif relation is operator.__ge__:
220 return ">="
221 elif relation is operator.__lshift__:
222 return "<<"
223 elif relation is operator.__rshift__:
224 return ">>"
225 else:
226 return "??"
228 @staticmethod
229 def _swap_relation(relation):
230 if relation is operator.__eq__:
231 return operator.__eq__
232 elif relation is operator.__le__:
233 return operator.__ge__
234 elif relation is operator.__ge__:
235 return operator.__le__
236 elif relation is operator.__lshift__:
237 return operator.__rshift__
238 elif relation is operator.__rshift__:
239 return operator.__lshift__
240 else:
241 return None
243 def predict(self, relation, other):
244 """Predict the constraint outcome of comparing expressions.
246 :param relation:
247 An object from the :mod:`operator` namespace representing the
248 operation being predicted.
250 :param other:
251 Another expression type representing the right hand side operand.
252 :type other:
253 ~picos.expressions.expression.ExpressionType
255 :Example:
257 >>> import operator, picos
258 >>> a = picos.RealVariable("x") + 1
259 >>> b = picos.RealVariable("y") + 2
260 >>> (a <= b).type == a.type.predict(operator.__le__, b.type)
261 True
262 """
263 if not isinstance(other, ExpressionType):
264 raise TypeError("The 'other' argument must be another {} instance."
265 .format(self.__class__.__name__))
267 # Perform the forward prediction.
268 result = self.clstype._predict(self.subtype, relation, other)
270 # Fall back to the backward prediction.
271 if result is NotImplemented:
272 reverse = self._swap_relation(relation)
273 result = other.clstype._predict(other.subtype, reverse, self)
275 # If both fail, the prediction is "not possible".
276 if result is NotImplemented:
277 raise PredictedFailure(
278 "The statement {} {} {} is predicted to error."
279 .format(self, self._relation_str(relation), other))
280 else:
281 assert isinstance(result, ConstraintType)
282 return result
285class Expression(ABC):
286 """Abstract base class for mathematical expressions, including mutables.
288 For mutables, this is the secondary base class, with
289 :class:`~.mutable.Mutable` or a subclass thereof being the primary one.
290 """
292 def __init__(self, typeStr, symbStr):
293 """Perform basic initialization for :class:`Expression` instances.
295 :param str typeStr: Short string denoting the expression type.
296 :param str symbStr: Algebraic string description of the expression.
297 """
298 self._typeStr = typeStr
299 """A string describing the expression type."""
301 self._symbStr = symbStr
302 """A symbolic string representation of the expression. It is always used
303 by __descr__, and it is equivalent to the value returned by __str__ when
304 the expression is not fully valued."""
306 @property
307 def string(self):
308 """Symbolic string representation of the expression.
310 Use this over Python's :class:`str` if you want to output the symbolic
311 representation even when the expression is valued.
312 """
313 return self._symbStr
315 # --------------------------------------------------------------------------
316 # Abstract and default-implementation methods.
317 # --------------------------------------------------------------------------
319 def _get_refined(self):
320 """See :attr:`refined`."""
321 return self
323 def _get_clstype(self):
324 """Return the Python class part of the expression's detailed type."""
325 return self.__class__
327 @property
328 @abstractmethod
329 def Subtype(self):
330 """The class of which :attr:`subtype` returns an instance.
332 Instances must be hashable. By convention a
333 :func:`namedtuple <collections.namedtuple>` class.
335 .. warning::
336 This should be declared in the class body as e.g.
337 `Subtype = namedtuple(…)` and not as a property so that it's static.
338 """
339 pass
341 @abstractmethod
342 def _get_subtype(self):
343 """See :attr:`subtype`."""
344 pass
346 @classmethod
347 @abstractmethod
348 def _predict(cls, subtype, relation, other):
349 """Predict the constraint outcome of a comparison.
351 :param object subtype: An object returned by the :meth:`_get_subtype`
352 instance method of :class:`cls`.
353 :param method-wrapper relation: A function from the :mod:`operator`
354 namespace, such as :func:`operator.__le__`. See
355 :class:`ExpressionType` for what operators are defined.
356 :param ExpressionType other: The detailed type of another expression.
357 :returns: Either the :obj:`NotImplemented` token or a
358 :class:`ConstraintType` object such that an instance of :class:`cls`
359 with the given subtype, when compared with another expression with
360 the given expression type, returns a constraint with that constraint
361 type.
362 """
363 pass
365 @abstractmethod
366 def _get_value(self):
367 """Return the numeric value of the expression as a CVXOPT matrix.
369 :raises NotValued: When the value is not fully defined.
371 Method implementations need to return an independent copy of the value
372 that the user is allowed to change without affecting the expression.
373 """
374 pass
376 def _set_value(self, value):
377 raise NotImplementedError("Setting the value on an instance of {} is "
378 "not supported, but you can value any mutables involved instead."
379 .format(type(self).__name__))
381 def _get_shape(self):
382 """Return the algebraic shape of the expression."""
383 return (1, 1)
385 @abstractmethod
386 def _get_mutables(self):
387 """Return the set of mutables that are involved in the expression."""
388 pass
390 @abstractmethod
391 def _is_convex(self):
392 """Whether the expression is convex in its :attr:`variables`.
394 Method implementations may assume that the expression is refined. Thus,
395 degenerate cases affected by refinement do not need to be considered.
397 For uncertain expressions, this assumes the perturbation as constant.
398 """
399 pass
401 @abstractmethod
402 def _is_concave(self):
403 """Whether the expression is concave in its :attr:`variables`.
405 Method implementations may assume that the expression is refined. Thus,
406 degenerate cases affected by refinement do not need to be considered.
408 For uncertain expressions, this assumes the perturbation as constant.
409 """
410 pass
412 @abstractmethod
413 def _replace_mutables(self, mapping):
414 """Return a copy of the expression concerning different mutables.
416 This is the fast internal-use counterpart to :meth:`replace_mutables`.
418 The returned expression should be of the same type as ``self`` (no
419 refinement) so that it can be substituted in composite expressions.
421 :param dict mapping:
422 A mutable replacement map. The caller must ensure the following
423 properties:
425 1. This must be a complete map from existing mutables to the same
426 mutable, another mutable, or a real-valued affine expression
427 (completeness).
428 2. The shape and vectorization format of each replacement must match
429 the existing mutable. Replacing with affine expressions is only
430 allowed when the existing mutable uses the trivial
431 :class:`~vectorizations.FullVectorization` (soudness).
432 3. Mutables that appear in a replacement may be the same as the
433 mutable being replaced but may otherwise not appear in the
434 expression (freshness).
435 4. Mutables may appear at most once anywhere in the image of the map
436 (uniqueness).
438 If any property is not fulfilled, the implementation does not need
439 to raise a proper exception but may fail arbitrarily.
440 """
441 pass
443 @abstractmethod
444 def _freeze_mutables(self, subset):
445 """Return a copy with some mutables frozen to their current value.
447 This is the fast internal-use counterpart to :meth:`frozen`.
449 The returned expression should be of the same type as ``self`` (no
450 refinement) so that it can be substituted in composite expressions.
452 :param dict subset:
453 An iterable of valued :class:`mutables <.mutable.Mutable>` that
454 should be frozen. May include mutables that are not present in the
455 expression, but may not include mutables without a value.
456 """
457 pass
459 # --------------------------------------------------------------------------
460 # An interface to the abstract and default-implementation methods above.
461 # --------------------------------------------------------------------------
463 @property
464 def refined(self):
465 """A refined version of the expression.
467 The refined expression can be an instance of a different
468 :class:`Expression` subclass than the original expression, if that type
469 is better suited for the mathematical object in question.
471 The refined expression is automatically used instead of the original one
472 whenever a constraint is created, and in some other places.
474 The idea behind refined expressions is that operations that produce new
475 expressions can be executed quickly without checking for exceptionnel
476 cases. For instance, the sum of two
477 :class:`~.exp_affine.ComplexAffineExpression` instances could have the
478 complex part eliminated so that storing the result as an
479 :class:`~.exp_affine.AffineExpression` would be prefered, but checking
480 for this case on every addition would be too slow. Refinement is used
481 sparingly to detect such cases at times where it makes the most sense.
483 Refinement may be disallowed within a context with the
484 :func:`no_refinement` context manager. In this case, this property
485 returns the expression as is.
486 """
487 if not _REFINEMENT.allowed:
488 return self
490 fine = self._get_refined()
492 if fine is not self:
493 # Recursively refine until the expression doesn't change further.
494 return fine.refined
495 else:
496 return fine
498 @property
499 def subtype(self):
500 """The subtype part of the expression's detailed type.
502 Returns a hashable object that, together with the Python class part of
503 the expression's type, is sufficient to predict the constraint outcome
504 (constraint class and subtype) of any comparison operation with any
505 other expression.
507 By convention the object returned is a
508 :func:`namedtuple <collections.namedtuple>` instance.
509 """
510 return self._get_subtype()
512 @property
513 def type(self):
514 """The expression's detailed type for constraint prediction.
516 The returned value is suffcient to predict the detailed type of any
517 constraint that can be created by comparing with another expression.
519 Since constraints are created from
520 :attr:`~.expression.Expression.refined` expressions only, the Python
521 class part of the detailed type may differ from the type of the
522 expression whose :attr:`type` is queried.
523 """
524 refined = self.refined
525 return ExpressionType(refined._get_clstype(), refined._get_subtype())
527 @classmethod
528 def make_type(cls, *args, **kwargs):
529 """Create a detailed expression type from subtype parameters."""
530 return ExpressionType(cls, cls.Subtype(*args, **kwargs))
532 def _wrap_get_value(self, asMatrix, staySafe):
533 """Enhance the implementation of :attr:`_get_value`.
535 Checks the type of any value returned and offers conversion options.
537 :param bool asMatrix:
538 Whether scalar values are returned as matrices.
540 :param bool staySafe:
541 Whether :exc:`NotValued` exceptions are raised. Otherwise missing
542 values are returned as :obj:`None`.
543 """
544 try:
545 value = self._get_value()
546 except NotValued:
547 if staySafe:
548 raise
549 else:
550 return None
552 assert isinstance(value, (cvxopt.matrix, cvxopt.spmatrix)), \
553 "Expression._get_value implementations must return a CVXOPT matrix."
555 if value.size == (1, 1) and not asMatrix:
556 return value[0]
557 else:
558 return value
560 value = property(
561 lambda self: self._wrap_get_value(asMatrix=False, staySafe=False),
562 lambda self, x: self._set_value(x),
563 lambda self: self._set_value(None),
564 r"""Value of the expression, or :obj:`None`.
566 It is defined if the expression is constant or if all mutables involved
567 in the expression are valued. Mutables can be valued directly by writing
568 to their :attr:`value` attribute. Variables are also valued by PICOS
569 when an optimization solution is found.
571 Some expressions can also be valued directly if PICOS can find a minimal
572 norm mutable assignment that makes the expression have the desired
573 value. In particular, this works with affine expressions whose linear
574 part has an under- or well-determined coefficient matrix.
576 :returns:
577 The value as a Python scalar or CVXOPT matrix, or :obj:`None` if it
578 is not defined.
580 :Distinction:
582 - Unlike :attr:`safe_value` and :attr:`safe_value_as_matrix`, an
583 undefined value is returned as :obj:`None`.
584 - Unlike :attr:`value_as_matrix` and :attr:`safe_value_as_matrix`,
585 scalars are returned as scalar types.
586 - For uncertain expressions, see also
587 :meth:`~.uexpression.UncertainExpression.worst_case_value`.
589 :Example:
591 >>> from picos import RealVariable
592 >>> x = RealVariable("x", (1,3))
593 >>> y = RealVariable("y", (1,3))
594 >>> e = x - 2*y + 3
595 >>> print("e:", e)
596 e: x - 2·y + [3]
597 >>> e.value = [4, 5, 6]
598 >>> print("e: ", e, "\nx: ", x, "\ny: ", y, sep = "")
599 e: [ 4.00e+00 5.00e+00 6.00e+00]
600 x: [ 2.00e-01 4.00e-01 6.00e-01]
601 y: [-4.00e-01 -8.00e-01 -1.20e+00]
602 """)
604 safe_value = property(
605 lambda self: self._wrap_get_value(asMatrix=False, staySafe=True),
606 lambda self, x: self._set_value(x),
607 lambda self: self._set_value(None),
608 """Value of the expression, if defined.
610 Refer to :attr:`value` for when it is defined.
612 :returns:
613 The value as a Python scalar or CVXOPT matrix.
615 :raises ~picos.NotValued:
616 If the value is not defined.
618 :Distinction:
620 - Unlike :attr:`value`, an undefined value raises an exception.
621 - Like :attr:`value`, scalars are returned as scalar types.
622 """)
624 value_as_matrix = property(
625 lambda self: self._wrap_get_value(asMatrix=True, staySafe=False),
626 lambda self, x: self._set_value(x),
627 lambda self: self._set_value(None),
628 r"""Value of the expression as a CVXOPT matrix type, or :obj:`None`.
630 Refer to :attr:`value` for when it is defined (not :obj:`None`).
632 :returns:
633 The value as a CVXOPT matrix, or :obj:`None` if it is not defined.
635 :Distinction:
637 - Like :attr:`value`, an undefined value is returned as :obj:`None`.
638 - Unlike :attr:`value`, scalars are returned as :math:`1 \times 1`
639 matrices.
640 """)
642 safe_value_as_matrix = property(
643 lambda self: self._wrap_get_value(asMatrix=True, staySafe=True),
644 lambda self, x: self._set_value(x),
645 lambda self: self._set_value(None),
646 r"""Value of the expression as a CVXOPT matrix type, if defined.
648 Refer to :attr:`value` for when it is defined.
650 :returns:
651 The value as a CVXOPT matrix.
653 :raises ~picos.NotValued:
654 If the value is not defined.
656 :Distinction:
658 - Unlike :attr:`value`, an undefined value raises an exception.
659 - Unlike :attr:`value`, scalars are returned as :math:`1 \times 1`
660 matrices.
661 """)
663 @property
664 def valued(self):
665 """Whether the expression is valued.
667 .. note::
669 Querying this attribute is *not* faster than immediately querying
670 :attr:`value` and checking whether it is :obj:`None`. Use it only if
671 you do not need to know the value, but only whether it is available.
673 :Example:
675 >>> from picos import RealVariable
676 >>> x = RealVariable("x", 3)
677 >>> x.valued
678 False
679 >>> x.value
680 >>> print((x|1))
681 ∑(x)
682 >>> x.value = [1, 2, 3]
683 >>> (x|1).valued
684 True
685 >>> print((x|1))
686 6.0
687 """
688 try:
689 self._get_value()
690 except NotValued:
691 return False
692 else:
693 return True
695 @valued.setter
696 def valued(self, x):
697 if x is False:
698 self._set_value(None)
699 else:
700 raise ValueError("You may only assign 'False' to the 'valued' "
701 "attribute, which is the same as setting 'value' to 'None'.")
703 shape = property(
704 lambda self: self._get_shape(),
705 doc=_get_shape.__doc__)
707 size = property(
708 lambda self: self._get_shape(),
709 doc="""The same as :attr:`shape`.""")
711 @property
712 def scalar(self):
713 """Whether the expression is scalar."""
714 return self._get_shape() == (1, 1)
716 @property
717 def square(self):
718 """Whether the expression is a square matrix."""
719 shape = self._get_shape()
720 return shape[0] == shape[1]
722 mutables = property(
723 lambda self: self._get_mutables(),
724 doc=_get_mutables.__doc__)
726 @property
727 def constant(self):
728 """Whether the expression involves no mutables."""
729 return not self._get_mutables()
731 @cached_property
732 def variables(self):
733 """The set of decision variables that are involved in the expression."""
734 from .variables import BaseVariable
736 return frozenset(mutable for mutable in self._get_mutables()
737 if isinstance(mutable, BaseVariable))
739 @cached_property
740 def parameters(self):
741 """The set of parameters that are involved in the expression."""
742 from .variables import BaseVariable
744 return frozenset(mutable for mutable in self._get_mutables()
745 if not isinstance(mutable, BaseVariable))
747 @property
748 def convex(self):
749 """Whether the expression is convex."""
750 return self.refined._is_convex()
752 @property
753 def concave(self):
754 """Whether the expression is concave."""
755 return self.refined._is_concave()
757 def replace_mutables(self, replacement):
758 """Return a copy of the expression concerning different mutables.
760 New mutables must have the same shape and vectorization format as the
761 mutables that they replace. This means in particular that
762 :class:`~.variables.RealVariable`, :class:`~.variables.IntegerVariable`
763 and :class:`~.variables.BinaryVariable` of same shape are
764 interchangeable.
766 If the mutables to be replaced do not appear in the expression, then
767 the expression is not copied but returned as is.
769 :param replacement:
770 Either a map from mutables or mutable names to new mutables or an
771 iterable of new mutables to replace existing mutables of same name
772 with. See the section on advanced usage for additional options.
773 :type replacement:
774 tuple or list or dict
776 :returns Expression:
777 The new expression, refined to a more suitable type if possible.
779 :Advanced replacement:
781 It is also possible to replace mutables with real affine expressions
782 concerning pairwise disjoint sets of fresh mutables. This works only on
783 real-valued mutables that have a trivial internal vectorization format
784 (i.e. :class:`~.vectorizations.FullVectorization`). The shape of the
785 replacing expression must match the variable's. Additional limitations
786 depending on the type of expression that the replacement is invoked on
787 are possible. The ``replacement`` argument must be a dictionary.
789 :Example:
791 >>> import picos
792 >>> x = picos.RealVariable("x"); x.value = 1
793 >>> y = picos.RealVariable("y"); y.value = 10
794 >>> z = picos.RealVariable("z"); z.value = 100
795 >>> c = picos.Constant("c", 1000)
796 >>> a = x + 2*y; a
797 <1×1 Real Linear Expression: x + 2·y>
798 >>> a.value
799 21.0
800 >>> b = a.replace_mutables({y: z}); b # Replace y with z.
801 <1×1 Real Linear Expression: x + 2·z>
802 >>> b.value
803 201.0
804 >>> d = a.replace_mutables({x: 2*x + z, y: c}); d # Advanced use.
805 <1×1 Real Affine Expression: 2·x + z + 2·c>
806 >>> d.value
807 2102.0
808 """
809 from .exp_biaffine import BiaffineExpression
810 from .mutable import Mutable
811 from .vectorizations import FullVectorization
813 # Change an iterable of mutables to a map from names to mutables.
814 if not isinstance(replacement, dict):
815 if not all(isinstance(new, Mutable) for new in replacement):
816 raise TypeError("If 'replacement' is a non-dictionary iterable,"
817 " then it may only contain mutables.")
819 new_replacement = {new.name: new for new in replacement}
821 if len(new_replacement) != len(replacement):
822 raise TypeError("If 'replacement' is a non-dictionary iterable,"
823 " then the mutables within must have unique names.")
825 replacement = new_replacement
827 # Change a map from names to a map from existing mutables.
828 # Names that reference non-existing mutables are dropped.
829 old_mtbs_by_name = {mtb.name: mtb for mtb in self.mutables}
830 replacing_by_name = False
831 new_replacement = {}
832 for old, new in replacement.items():
833 if isinstance(old, Mutable):
834 new_replacement[old] = new
835 elif not isinstance(old, str):
836 raise TypeError(
837 "Keys of 'replacement' must be mutables or names thereof.")
838 else:
839 replacing_by_name = True
840 if old in old_mtbs_by_name:
841 new_replacement[old_mtbs_by_name[old]] = new
842 replacement = new_replacement
844 # Check unique naming of existing mutables if it matters.
845 if replacing_by_name and len(old_mtbs_by_name) != len(self.mutables):
846 raise RuntimeError("Cannot replace mutables by name in {} as "
847 "its mutables are not uniquely named.".format(self.string))
849 # Remove non-existing sources and identities.
850 assert all(isinstance(old, Mutable) for old in replacement)
851 replacement = {old: new for old, new in replacement.items()
852 if old is not new and old in self.mutables}
854 # Do nothing if there is nothing to replace.
855 if not replacement:
856 return self
858 # Validate individual replacement requirements.
859 for old, new in replacement.items():
860 # Replacement must be a mutable or biaffine expression.
861 if not isinstance(new, BiaffineExpression):
862 raise TypeError("Can only replace mutables with other mutables "
863 "or affine expressions thereof.")
865 # Shapes must match.
866 if old.shape != new.shape:
867 raise TypeError(
868 "Cannot replace {} with {} in {}: Differing shape."
869 .format(old.name, new.name, self.string))
871 # Special requirements when replacing with mutables or expressions.
872 if isinstance(new, Mutable):
873 # Vectorization formats must match.
874 if type(old._vec) != type(new._vec): # noqa: E721
875 raise TypeError("Cannot replace {} with {} in {}: "
876 "Differing vectorization."
877 .format(old.name, new.name, self.string))
878 else:
879 # Replaced mutable must use a trivial vectorization.
880 if not isinstance(old._vec, FullVectorization):
881 raise TypeError("Can only replace mutables using a trivial "
882 "vectorization format with affine expressions.")
884 # Replacing expression must be real-valued and affine.
885 if new._bilinear_coefs or new.complex:
886 raise TypeError("Can only replace mutables with real-valued"
887 " affine expressions.")
889 old_mtbs_set = set(replacement)
890 new_mtbs_lst = [mtb # Excludes each mutable being replaced.
891 for old, new in replacement.items()
892 for mtb in new.mutables.difference((old,))]
893 new_mtbs_set = set(new_mtbs_lst)
895 # New mutables must be fresh.
896 # It is OK to replace a mutable with itself or an affine expression of
897 # itself and other fresh mutables, though.
898 if old_mtbs_set.intersection(new_mtbs_set):
899 raise ValueError("Can only replace mutables with fresh mutables "
900 "or affine expressions of all fresh mutables (the old mutable "
901 "may appear in the expression).")
903 # New mutables must be unique.
904 if len(new_mtbs_lst) != len(new_mtbs_set):
905 raise ValueError("Can only replace multiple mutables at once if "
906 "the replacing mutables (and/or the mutables in replacing "
907 "expressions) are all unique.")
909 # Turn the replacement map into a complete map.
910 mapping = {mtb: mtb for mtb in self.mutables}
911 mapping.update(replacement)
913 # Replace recursively and refine the result.
914 return self._replace_mutables(mapping).refined
916 def frozen(self, subset=None):
917 """The expression with valued mutables frozen to their current value.
919 If all mutables of the expression are valued (and in the subset unless
920 ``subset=None``), this is the same as the inversion operation ``~``.
922 If the mutables to be frozen do not appear in the expression, then the
923 expression is not copied but returned as is.
925 :param subset:
926 An iterable of valued :class:`mutables <.mutable.Mutable>` or names
927 thereof that should be frozen. If :obj:`None`, then all valued
928 mutables are frozen to their current value. May include mutables
929 that are not present in the expression, but may not include mutables
930 without a value.
932 :returns Expression:
933 The frozen expression, refined to a more suitable type if possible.
935 :Example:
937 >>> from picos import RealVariable
938 >>> x, y = RealVariable("x"), RealVariable("y")
939 >>> f = x + y; f
940 <1×1 Real Linear Expression: x + y>
941 >>> sorted(f.mutables, key=lambda mtb: mtb.name)
942 [<1×1 Real Variable: x>, <1×1 Real Variable: y>]
943 >>> x.value = 5
944 >>> g = f.frozen(); g # g is f with x frozen at its current value of 5.
945 <1×1 Real Affine Expression: [x] + y>
946 >>> sorted(g.mutables, key=lambda mtb: mtb.name)
947 [<1×1 Real Variable: y>]
948 >>> x.value, y.value = 10, 10
949 >>> f.value # x takes its new value in f.
950 20.0
951 >>> g.value # x remains frozen at [x] = 5 in g.
952 15.0
953 >>> # If an expression is frozen to a constant, this is reversable:
954 >>> f.frozen().equals(~f) and ~f.frozen() is f
955 True
956 """
957 from .mutable import Mutable
959 # Collect mutables to be frozen in the expression.
960 if subset is None:
961 freeze = set(mtb for mtb in self.mutables if mtb.valued)
962 else:
963 if not all(isinstance(mtb, (str, Mutable)) for mtb in subset):
964 raise TypeError("Some element of the subset of mutables to "
965 "freeze is neither a mutable nor a string.")
967 subset_mtbs = set(m for m in subset if isinstance(m, Mutable))
968 subset_name = set(n for n in subset if isinstance(n, str))
970 freeze = set()
971 if subset_mtbs:
972 freeze.update(m for m in subset_mtbs if m in self.mutables)
973 if subset_name:
974 freeze.update(m for m in self.mutables if m.name in subset_name)
976 if not all(mtb.valued for mtb in freeze):
977 raise NotValued(
978 "Not all mutables in the selected subset are valued.")
980 if not freeze:
981 return self
983 if freeze == self.mutables:
984 return ~self # Allow ~self.frozen() to return self.
986 return self._freeze_mutables(freeze).refined
988 @property
989 def certain(self):
990 """Always :obj:`True` for certain expression types.
992 This can be :obj:`False` for Expression types that inherit from
993 :class:`~.uexpression.UncertainExpression` (with priority).
994 """
995 return True
997 @property
998 def uncertain(self):
999 """Always :obj:`False` for certain expression types.
1001 This can be :obj:`True` for Expression types that inherit from
1002 :class:`~.uexpression.UncertainExpression` (with priority).
1003 """
1004 return False
1006 # --------------------------------------------------------------------------
1007 # Python special method implementations.
1008 # --------------------------------------------------------------------------
1010 def __len__(self):
1011 return self.shape[0] * self.shape[1]
1013 def __le__(self, other):
1014 # Try to refine self and see if the operation is then supported.
1015 # This allows e.g. a <= 0 if a is a real-valued complex expression.
1016 refined = self.refined
1017 if type(refined) != type(self):
1018 return refined.__le__(other)
1020 return NotImplemented
1022 def __ge__(self, other):
1023 # Try to refine self and see if the operation is then supported.
1024 # This allows e.g. a >= 0 if a is a real-valued complex expression.
1025 refined = self.refined
1026 if type(refined) != type(self):
1027 return refined.__ge__(other)
1029 return NotImplemented
1031 def __invert__(self):
1032 """Convert between a valued expression and its value.
1034 The value is returned as a constant affine expression whose conversion
1035 returns the original expression.
1036 """
1037 if hasattr(self, "_origin"):
1038 return self._origin
1039 elif self.constant:
1040 return self
1042 from .exp_affine import Constant
1044 A = Constant(glyphs.frozen(self.string), self._get_value(), self.shape)
1045 A._origin = self
1046 return A
1048 def __contains__(self, mutable):
1049 """Whether the expression concerns the given mutable."""
1050 return mutable in self.mutables
1052 def __eq__(self, exp):
1053 raise NotImplementedError("PICOS supports equality comparison only "
1054 "between affine expressions, as otherwise the problem would "
1055 "become non-convex. Choose either <= or >= if possible.")
1057 def __repr__(self):
1058 return str(glyphs.repr2(self._typeStr, self._symbStr))
1060 def __str__(self):
1061 """Return a dynamic string description of the expression.
1063 The description is based on whether the expression is valued. If it is
1064 valued, then a string representation of the value is returned.
1065 Otherwise, the symbolic description of the expression is returned.
1066 """
1067 if self.valued:
1068 return str(self.value).strip()
1069 else:
1070 return str(self._symbStr)
1072 def __format__(self, format_spec):
1073 if self.valued:
1074 return self.value.__format__(format_spec)
1075 else:
1076 return self._symbStr.__format__(format_spec)
1078 def __index__(self):
1079 if len(self) != 1:
1080 raise TypeError("Cannot use multidimensional expression {} as an "
1081 "index.".format(self.string))
1083 if not self.valued:
1084 raise NotValued("Cannot use unvalued expression {} as an index."
1085 .format(self.string))
1087 value = self.safe_value
1089 if value.imag:
1090 raise ValueError("Cannot use {} as an index as its value of {} has "
1091 "a nonzero imaginary part.".format(self.string, value))
1093 value = value.real
1095 if not value.is_integer():
1096 raise ValueError("Cannot use {} as an index as its value of {} is "
1097 "not integral.".format(self.string, value))
1099 return int(value)
1101 def _casting_helper(self, theType):
1102 assert theType in (int, float, complex)
1104 if len(self) != 1:
1105 raise TypeError(
1106 "Cannot cast multidimensional expression {} as {}."
1107 .format(self.string, theType.__name__))
1109 if not self.valued:
1110 raise NotValued("Cannot cast unvalued expression {} as {}."
1111 .format(self.string, theType.__name__))
1113 value = self.value_as_matrix
1115 return theType(value[0])
1117 def __int__(self):
1118 return self._casting_helper(int)
1120 def __float__(self):
1121 return self._casting_helper(float)
1123 def __complex__(self):
1124 return self._casting_helper(complex)
1126 def __round__(self, ndigits=None):
1127 return round(float(self), ndigits)
1129 # Since we define __eq__, __hash__ is not inherited. Do this manually.
1130 __hash__ = object.__hash__
1132 # HACK: This prevents NumPy operators from iterating over PICOS expressions.
1133 __array_priority__ = float("inf")
1135 # --------------------------------------------------------------------------
1136 # Fallback algebraic operations: Try again with converted RHS, refined LHS.
1137 # --------------------------------------------------------------------------
1139 @convert_operands(sameShape=True)
1140 def __add__(self, other):
1141 if type(self.refined) != type(self):
1142 return self.refined.__add__(other)
1143 else:
1144 return NotImplemented
1146 @convert_operands(sameShape=True)
1147 def __radd__(self, other):
1148 if type(self.refined) != type(self):
1149 return self.refined.__radd__(other)
1150 else:
1151 return NotImplemented
1153 @convert_operands(sameShape=True)
1154 def __sub__(self, other):
1155 if type(self.refined) != type(self):
1156 return self.refined.__sub__(other)
1157 else:
1158 return NotImplemented
1160 @convert_operands(sameShape=True)
1161 def __rsub__(self, other):
1162 if type(self.refined) != type(self):
1163 return self.refined.__rsub__(other)
1164 else:
1165 return NotImplemented
1167 @convert_operands(sameShape=True)
1168 def __or__(self, other):
1169 if type(self.refined) != type(self):
1170 return self.refined.__or__(other)
1171 else:
1172 return NotImplemented
1174 @convert_operands(sameShape=True)
1175 def __ror__(self, other):
1176 if type(self.refined) != type(self):
1177 return self.refined.__ror__(other)
1178 else:
1179 return NotImplemented
1181 @convert_operands(rMatMul=True)
1182 def __mul__(self, other):
1183 if type(self.refined) != type(self):
1184 return self.refined.__mul__(other)
1185 else:
1186 return NotImplemented
1188 @convert_operands(lMatMul=True)
1189 def __rmul__(self, other):
1190 if type(self.refined) != type(self):
1191 return self.refined.__rmul__(other)
1192 else:
1193 return NotImplemented
1195 @convert_operands(sameShape=True)
1196 def __xor__(self, other):
1197 if type(self.refined) != type(self):
1198 return self.refined.__xor__(other)
1199 else:
1200 return NotImplemented
1202 @convert_operands(sameShape=True)
1203 def __rxor__(self, other):
1204 if type(self.refined) != type(self):
1205 return self.refined.__rxor__(other)
1206 else:
1207 return NotImplemented
1209 @convert_operands()
1210 def __matmul__(self, other):
1211 if type(self.refined) != type(self):
1212 return self.refined.__matmul__(other)
1213 else:
1214 return NotImplemented
1216 @convert_operands()
1217 def __rmatmul__(self, other):
1218 if type(self.refined) != type(self):
1219 return self.refined.__rmatmul__(other)
1220 else:
1221 return NotImplemented
1223 @convert_operands(scalarRHS=True)
1224 def __truediv__(self, other):
1225 if type(self.refined) != type(self):
1226 return self.refined.__truediv__(other)
1227 else:
1228 return NotImplemented
1230 @convert_operands(scalarLHS=True)
1231 def __rtruediv__(self, other):
1232 if type(self.refined) != type(self):
1233 return self.refined.__rtruediv__(other)
1234 else:
1235 return NotImplemented
1237 @convert_operands(scalarRHS=True)
1238 def __pow__(self, other):
1239 if type(self.refined) != type(self):
1240 return self.refined.__pow__(other)
1241 else:
1242 return NotImplemented
1244 @convert_operands(scalarLHS=True)
1245 def __rpow__(self, other):
1246 if type(self.refined) != type(self):
1247 return self.refined.__rpow__(other)
1248 else:
1249 return NotImplemented
1251 @convert_operands(horiCat=True)
1252 def __and__(self, other):
1253 if type(self.refined) != type(self):
1254 return self.refined.__and__(other)
1255 else:
1256 return NotImplemented
1258 @convert_operands(horiCat=True)
1259 def __rand__(self, other):
1260 if type(self.refined) != type(self):
1261 return self.refined.__rand__(other)
1262 else:
1263 return NotImplemented
1265 @convert_operands(vertCat=True)
1266 def __floordiv__(self, other):
1267 if type(self.refined) != type(self):
1268 return self.refined.__floordiv__(other)
1269 else:
1270 return NotImplemented
1272 @convert_operands(vertCat=True)
1273 def __rfloordiv__(self, other):
1274 if type(self.refined) != type(self):
1275 return self.refined.__rfloordiv__(other)
1276 else:
1277 return NotImplemented
1279 def __neg__(self):
1280 if type(self.refined) != type(self):
1281 return self.refined.__neg__()
1282 else:
1283 return NotImplemented
1285 def __abs__(self):
1286 if type(self.refined) != type(self):
1287 return self.refined.__abs__()
1288 else:
1289 return NotImplemented
1291 # --------------------------------------------------------------------------
1292 # Turn __lshift__ and __rshift__ into a single binary relation.
1293 # This is used for both Loewner order (defining LMIs) and set membership.
1294 # --------------------------------------------------------------------------
1296 def _lshift_implementation(self, other):
1297 return NotImplemented
1299 def _rshift_implementation(self, other):
1300 return NotImplemented
1302 @convert_operands(sameShape=True)
1303 @validate_prediction
1304 @refine_operands()
1305 def __lshift__(self, other):
1306 result = self._lshift_implementation(other)
1308 if result is NotImplemented:
1309 result = other._rshift_implementation(self)
1311 return result
1313 @convert_operands(sameShape=True)
1314 @validate_prediction
1315 @refine_operands()
1316 def __rshift__(self, other):
1317 result = self._rshift_implementation(other)
1319 if result is NotImplemented:
1320 result = other._lshift_implementation(self)
1322 return result
1324 # --------------------------------------------------------------------------
1325 # Backwards compatibility methods.
1326 # --------------------------------------------------------------------------
1328 @deprecated("2.0", useInstead="valued")
1329 def is_valued(self):
1330 """Whether the expression is valued."""
1331 return self.valued
1333 @deprecated("2.0", useInstead="value")
1334 def set_value(self, value):
1335 """Set the value of an expression."""
1336 self.value = value
1338 @deprecated("2.0", "PICOS treats all inequalities as non-strict. Using the "
1339 "strict inequality comparison operators may lead to unexpected results "
1340 "when dealing with integer problems.")
1341 def __lt__(self, exp):
1342 return self.__le__(exp)
1344 @deprecated("2.0", "PICOS treats all inequalities as non-strict. Using the "
1345 "strict inequality comparison operators may lead to unexpected results "
1346 "when dealing with integer problems.")
1347 def __gt__(self, exp):
1348 return self.__ge__(exp)
1351# --------------------------------------
1352__all__ = api_end(_API_START, globals())