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 a parameterization for (random) noise in data.""" 

20 

21from abc import ABC, abstractmethod 

22 

23from ...apidoc import api_end, api_start 

24from ...containers import DetailedType 

25from ..data import load_shape 

26from ..mutable import Mutable 

27from ..vectorizations import FullVectorization 

28from .uexp_affine import UncertainAffineExpression 

29from .uexpression import IntractableWorstCase, UncertainExpression 

30 

31_API_START = api_start(globals()) 

32# ------------------------------- 

33 

34 

35class PerturbationUniverseType(DetailedType): 

36 """Container for a pair of perturbation universe class type and subtype.""" 

37 

38 pass 

39 

40 

41class PerturbationUniverse(ABC): 

42 """Base class for uncertain perturbation sets and distributions. 

43 

44 See :attr:`distributional` for a distinction between perturbation sets, 

45 random distributions and distributional ambiguity sets, all three of which 

46 can be represented by this class. 

47 

48 The naming scheme for implementing classes is as follows: 

49 

50 - Perturbation sets (robust optimization) end in ``PerturbationSet``, 

51 - random distributions (stochastic programming) end in ``Distribution``, 

52 - distributional ambiguity sets (DRO) end in ``AmbiguitySet``. 

53 """ 

54 

55 # -------------------------------------------------------------------------- 

56 # Prediction related. 

57 # -------------------------------------------------------------------------- 

58 

59 @property 

60 def type(self): 

61 """Detailed type of a perturbation parameter universe.""" 

62 return PerturbationUniverseType(self.__class__, self._subtype()) 

63 

64 subtype = property(lambda self: self._subtype()) 

65 

66 @classmethod 

67 def make_type(cls, *args, **kwargs): 

68 """Create a detailed universe type from subtype parameters.""" 

69 return PerturbationUniverseType(cls, cls.Subtype(*args, **kwargs)) 

70 

71 @abstractmethod 

72 def _subtype(self): 

73 """Subtype of the perturbation parameter universe.""" 

74 pass 

75 

76 # -------------------------------------------------------------------------- 

77 # Other. 

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

79 

80 @property 

81 @abstractmethod 

82 def parameter(self): 

83 r"""The perturbation parameter.""" 

84 pass 

85 

86 @property 

87 @abstractmethod 

88 def distributional(self): 

89 r"""Whether this is a distribution or distributional ambiguity set. 

90 

91 If this is :obj:`True`, then this represents a random distribution 

92 (stochastic programming) or an ambiguity set of random distributions 

93 (distributionally robust optimization) and any expression that depends 

94 on its random :attr:`parameter`, when used in a constraint or as an 

95 objective function, is understood as a (worst-case) *expected* value. 

96 

97 If this is :obj:`False`, then this represents a perturbation set (robust 

98 optimization) and any expression that depends on its perturbation 

99 :attr:`parameter`, when used in a constraint or as an objective 

100 function, is understood as a worst-case value. 

101 """ 

102 pass 

103 

104 def _check_worst_case_argument_scalar(self, scalar): 

105 """Support implementations of :meth:`worst_case`.""" 

106 if not isinstance(scalar, UncertainExpression): 

107 raise TypeError("{} can only compute the worst-case value of " 

108 "uncertain expressions, not of {}." 

109 .format(type(self).__name__, type(scalar).__name__)) 

110 

111 if not scalar.scalar: 

112 raise TypeError( 

113 "{} can only compute the worst-case value of a scalar " 

114 "expression.".format(type(self).__name__)) 

115 

116 p = self.parameter 

117 if scalar.mutables != set([p]): 

118 raise ValueError( 

119 "{} can only compute the worst-case value of expressions that " 

120 "depend exactly on its perturbation parameter {}.".format( 

121 type(self).__name__, p.name)) 

122 

123 def _check_worst_case_argument_direction(self, direction): 

124 """Support implementations of :meth:`worst_case`.""" 

125 if not isinstance(direction, str): 

126 raise TypeError("Optimization direction must be given as a string.") 

127 

128 # NOTE: "find" is OK even though it is not documented. 

129 if direction not in ("min", "max", "find"): 

130 raise ValueError( 

131 "Invalid optimization direction '{}'.".format(direction)) 

132 

133 def _check_worst_case_f_and_x(self, f, x): 

134 """Support implementations of :meth:`worst_case`. 

135 

136 :param f: 

137 The certain scalar function to minimize or maximize. 

138 

139 :param x: 

140 The decision variable that replaces the uncertain parameter in f. 

141 """ 

142 assert f.scalar 

143 assert f.mutables == set([x]) 

144 

145 assert not isinstance(f, UncertainExpression), \ 

146 "An instance of {} did not refine to a certain expression type " \ 

147 "after its perturbation parameter was replaced with a real " \ 

148 "variable.".format(type(f).__name__) 

149 

150 def worst_case(self, scalar, direction): 

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

152 

153 :param scalar: 

154 A scalar uncertain expression that depends only on the perturbation 

155 :attr:`parameter`. 

156 :type scalar: 

157 ~picos.expressions.uncertain.uexpression.UncertainExpression 

158 

159 :param str direction: 

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

161 

162 :returns: 

163 A pair where the first element is the worst-case (expeceted) value 

164 as a :obj:`float` and where the second element is a realization of 

165 the perturbation parameter that attains this worst case as a 

166 :obj:`float` or CVXOPT matrix (or :obj:`None` for stochastic 

167 uncertainty). 

168 

169 :raises TypeError: 

170 When the function is not scalar. 

171 

172 :raises ValueError: 

173 When the function depends on other mutables than exactly the 

174 :attr:`parameter`. 

175 

176 :raises picos.uncertain.IntractableWorstCase: 

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

178 particular when it would require solving a nonconvex problem. 

179 

180 :raises RuntimeError: 

181 When the computation is supported but fails. 

182 """ 

183 raise IntractableWorstCase("Computing a worst-case (expected) value is " 

184 "not supported for uncertainty defined through an instance of {}." 

185 .format(self.__class__.__name__)) 

186 

187 

188class Perturbation(Mutable, UncertainAffineExpression): 

189 r"""A parameter that can be used to describe (random) noise in data. 

190 

191 This is the initial building block for an 

192 :class:`~.uexp_affine.UncertainAffineExpression`. In particular, an affine 

193 transformation of this parameter represents uncertain data. 

194 """ 

195 

196 @classmethod 

197 def _get_type_string_base(cls): 

198 # TODO: Make type string depend on the perturbation set/distribution. 

199 # NOTE: It would probably be best to replace Expression._typeStr and 

200 # _symbStr with abstract instance methods and implement them with 

201 # the cached_property decorator. 

202 return "Perturbation" 

203 

204 def __init__(self, universe, name, shape): 

205 """Create a :class:`~.perturbation.Perturbation`. 

206 

207 :param universe: 

208 Either the set that the perturbation parameter lives in or the 

209 distribution according to which the perturbation is distributed. 

210 :type universe: 

211 ~picos.expressions.uncertain.perturbation.PerturbationUniverse 

212 

213 :param str name: 

214 Symbolic string description of the perturbation, similar to a 

215 variable's name. 

216 

217 :param shape: 

218 Algebraic shape of the perturbation parameter. 

219 :type shape: 

220 int or tuple or list 

221 

222 This constructor is meant for internal use. As a user, you will want to 

223 first define a universe (e.g. 

224 :class:`~.pert_conic.ConicPerturbationSet`) for the parameter and obtain 

225 the parameter from it. 

226 """ 

227 shape = load_shape(shape) 

228 vec = FullVectorization(shape) 

229 Mutable.__init__(self, name, vec) 

230 UncertainAffineExpression.__init__( 

231 self, self.name, shape, {self: vec.identity}) 

232 

233 assert isinstance(universe, PerturbationUniverse) 

234 

235 self._universe = universe 

236 

237 def copy(self, new_name=None): 

238 """Return an independent copy of the perturbation.""" 

239 name = self.name if new_name is None else new_name 

240 

241 return self.__class__(self._universe, name, self.shape) 

242 

243 @property 

244 def universe(self): 

245 """The uncertainty universe that the parameter belongs to.""" 

246 return self._universe 

247 

248 

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

250__all__ = api_end(_API_START, globals())