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 the :class:`UncertainExpression` base class.""" 

20 

21import cvxopt 

22 

23from ... import glyphs 

24from ...apidoc import api_end, api_start 

25from ...caching import cached_property 

26from ..expression import NotValued 

27 

28_API_START = api_start(globals()) 

29# ------------------------------- 

30 

31 

32class IntractableWorstCase(RuntimeError): 

33 """Computing a worst-case (expected) value is hard and not supported. 

34 

35 Raised by :meth:`~.uexpression.UncertainExpression.worst_case` and methods 

36 that depend on it. 

37 """ 

38 

39 

40class UncertainExpression: 

41 """Primary base class for uncertainty affected expression types. 

42 

43 The secondary base class must be :class:`~.expression.Expression` or a 

44 subclass thereof. 

45 

46 Uncertain expressions have a distinct behavior when used to form a 

47 constraint or when posed as an objective function. The exact behavior 

48 depends on the type of uncertainty involved. If the perturbation parameter 

49 that describes the uncertainty is confied to a perturbation set, then the 

50 worst-case realization of the parameter is assumed when determining 

51 feasibility and optimality. If the perturbation parameter is a random 

52 variable (whose distribution may itself be ambiguous), then the constraint 

53 or objective implicitly considers the expected value of the uncertain 

54 expression (under the worst-case distribution). Uncertain expressions are 

55 thus used in the contexts of robust optimization, stochastic programming and 

56 distributionally robust optimization. 

57 """ 

58 

59 @cached_property 

60 def perturbation(self): 

61 """The parameter controlling the uncertainty, or :obj:`None`.""" 

62 from .perturbation import Perturbation 

63 

64 perturbations = tuple( 

65 prm for prm in self.parameters if isinstance(prm, Perturbation)) 

66 

67 if len(perturbations) > 1: 

68 raise NotImplementedError("Uncertain expressions may depend " 

69 "on at most one perturbation parameter. Found {}." 

70 .format(" and ".join(prt.name for prt in perturbations))) 

71 

72 return perturbations[0] if perturbations else None 

73 

74 @property 

75 def random(self): 

76 """Whether the uncertainty is of stochastic nature. 

77 

78 See also :attr:`~.perturbation.PerturbationUniverse.distributional`. 

79 """ 

80 if self.certain: 

81 return False 

82 else: 

83 return self.universe.distributional 

84 

85 @cached_property 

86 def universe(self): 

87 """Universe that the perturbation parameter lives in, or :obj:`None`. 

88 

89 If this is not :obj:`None`, then this is the same as 

90 :attr:`perturbation`.:attr:`~.perturbation.Perturbation.universe`. 

91 """ 

92 return self.perturbation.universe if self.perturbation else None 

93 

94 @property 

95 def certain(self): 

96 """Whether the uncertain expression is actually certain.""" 

97 return not self.perturbation 

98 

99 @property 

100 def uncertain(self): 

101 """Whether the uncertain expression is in fact uncertain.""" 

102 return bool(self.perturbation) 

103 

104 def worst_case(self, direction): 

105 """Find a worst-case realization of the uncertainty for the expression. 

106 

107 Expressions that are affected by uncertainty are only partially valued 

108 once an optimization solution has been applied. While their decision 

109 values are populated with a robust optimal solution, the parameter that 

110 controls the uncertainty is not valued unless the user assigned it a 

111 particular realization by hand. This method computes a worst-case 

112 (expected) value of the expression and returns it together with a 

113 realization of the perturbation parameter for which the worst case is 

114 attained (or :obj:`None` in the case of stochastic uncertainty). 

115 

116 For multidimensional expressions, this method computes the entrywise 

117 worst case and returns an attaining realization for each entry. 

118 

119 :param str direction: 

120 Either ``"min"`` or ``"max"``, denoting the worst-case direction. 

121 

122 :returns: 

123 A pair ``(value, realization)``. For a scalar expression, ``value`` 

124 is its worst-case (expected) value as a :obj:`float` and 

125 ``realization`` is a realization of the :attr:`perturbation` 

126 parameter that attains this worst case as a :obj:`float` or CVXOPT 

127 matrix. For a multidimensional expression, ``value`` is a CVXOPT 

128 dense matrix denoting the entrywise worst-case values and 

129 ``realization`` is a :obj:`tuple` of attaining realizations 

130 corresponding to the expression vectorized in in column-major order. 

131 Lastly, ``realization`` is :obj:`None` if the expression is 

132 :attr:`certain` or when its uncertainty is of stochastic nature. 

133 

134 :raises picos.NotValued: 

135 When the decision variables that occur in the expression are not 

136 fully valued. 

137 

138 :raises picos.uncertain.IntractableWorstCase: 

139 When computing the worst-case (expected) value is not supported, in 

140 particular when it would require solving a nonconvex problem. 

141 

142 :raises RuntimeError: 

143 When the computation is supported but fails. 

144 """ 

145 if not all(var.valued for var in self.variables): 

146 raise NotValued("Not all decision variables that occur in the " 

147 "uncertain expression {} are valued, so PICOS cannot compute " 

148 "its worst-case (expected) value.".format(self.string)) 

149 

150 if self.certain: 

151 return self.safe_value, None 

152 

153 outcome = self.frozen(self.variables) 

154 assert outcome.mutables == set([self.perturbation]) 

155 

156 if self.scalar: 

157 return self.universe.worst_case(outcome, direction) 

158 else: 

159 values, realizations = zip(*( 

160 self.universe.worst_case(outcome[i], direction) 

161 for i in range(len(self)))) 

162 

163 return cvxopt.matrix(values, self.shape), realizations 

164 

165 def worst_case_value(self, direction): 

166 """A shorthand for the first value returned by :meth:`worst_case`.""" 

167 return self.worst_case(direction)[0] 

168 

169 def worst_case_string(self, direction): 

170 """A string describing the expression within a worst-case context. 

171 

172 :param str direction: 

173 Either ``"min"`` or ``"max"``, denoting the worst-case direction. 

174 """ 

175 # NOTE: The following distinguishes only RO and DRO and needs to be 

176 # extended when SP models are supported. 

177 if self.random: 

178 over = glyphs.probdist(self.perturbation.string) 

179 base = glyphs.exparg(self.perturbation.string, self.string) 

180 else: 

181 over = self.perturbation.string 

182 base = self.string 

183 

184 if direction == "min": 

185 return glyphs.minarg(over, base) 

186 elif direction == "max": 

187 return glyphs.maxarg(over, base) 

188 else: 

189 raise ValueError("Invalid direction.") 

190 

191 

192# -------------------------------------- 

193__all__ = api_end(_API_START, globals())