Coverage for picos/constraints/uncertain/ucon_ball_norm.py: 97.96%

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 :class:`BallUncertainNormConstraint`.""" 

20 

21import operator 

22from collections import namedtuple 

23 

24from ... import glyphs 

25from ...apidoc import api_end, api_start 

26from ..constraint import Constraint, ConstraintConversion 

27 

28_API_START = api_start(globals()) 

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

30 

31 

32class BallUncertainNormConstraint(Constraint): 

33 """An (uncertain) upper bound on a norm with unit ball uncertainty.""" 

34 

35 class RobustConversion(ConstraintConversion): 

36 """Robust counterpart conversion.""" 

37 

38 @classmethod 

39 def predict(cls, subtype, options): 

40 """Implement :meth:`~.constraint.ConstraintConversion.predict`.""" 

41 from ...expressions import AffineExpression, RealVariable 

42 from .. import AffineConstraint, LMIConstraint 

43 

44 if subtype.bound_universe_subtype: # uncertain bound 

45 X = subtype.bound_universe_subtype 

46 x_dim = X.param_dim 

47 

48 K = X.cone_type 

49 D = X.dual_cone_type 

50 K_dim = K.subtype.dim 

51 

52 v = AffineExpression.make_type( 

53 shape=(K_dim, 1), constant=False, nonneg=False) 

54 

55 yield ("var", RealVariable.make_var_type(dim=1, bnd=0), 1) 

56 yield ("var", RealVariable.make_var_type(dim=K_dim, bnd=0), 1) 

57 yield ("con", AffineConstraint.make_type(dim=1, eq=False), 1) 

58 yield ("con", AffineConstraint.make_type(dim=x_dim, eq=True), 

59 2 if X.has_B else 1) 

60 yield ("con", v.predict(operator.__lshift__, D), 1) 

61 

62 k = subtype.dim 

63 p = subtype.norm_universe_subtype.param_dim 

64 

65 yield ("var", RealVariable.make_var_type(dim=1, bnd=1), 1) 

66 yield ("con", LMIConstraint.make_type(diag=(k + p + 1)), 1) 

67 

68 @classmethod 

69 def convert(cls, con, options): 

70 """Implement :meth:`~.constraint.ConstraintConversion.convert`. 

71 

72 Conversion recipe and variable names based on the book 

73 *Robust Optimization* (Ben-Tal, El Ghaoui, Nemirovski, 2009). 

74 """ 

75 from ...expressions import ( 

76 block, Constant, ConicPerturbationSet, RealVariable) 

77 from ...modeling import Problem 

78 

79 problem = Problem() 

80 

81 # a = A(η)y + b(η) is the normed expression, e = η its perturbation. 

82 a = con.ne.vec 

83 e = con.ne.perturbation 

84 

85 # Lz is the uncertain and g = Aⁿy + bⁿ the certain part of a. 

86 L, g = a.factor_out(e) 

87 

88 # Define t = τ depending on whether the upper bound is uncertain. 

89 if con.ub.certain: 

90 t = con.ub 

91 else: 

92 # b = cᵀ(χ)y + d(χ) is the upper bound, x = χ its perturbation. 

93 b = con.ub 

94 x = con.ub.perturbation 

95 

96 # sx = σᵀ(y)χ is the uncertain, d = δ(y) the certain part of b. 

97 s, d = b.factor_out(x) 

98 

99 X = x.universe 

100 assert isinstance(X, ConicPerturbationSet) 

101 P, Q, p, K = X.A, X.B, X.c, X.K 

102 

103 t = RealVariable("__t") 

104 v = RealVariable("__v", K.subtype.dim) 

105 

106 problem.add_constraint(t + p.T*v <= d) 

107 problem.add_constraint(P.T*v == s.T) 

108 if Q is not None: 

109 problem.add_constraint(Q.T*v == 0) 

110 problem.add_constraint(v << K.dual_cone) 

111 

112 # Define l = λ. 

113 l = RealVariable("__{}".format(glyphs.lambda_()), lower=0) 

114 

115 k, p = len(a), e.dim 

116 Ik = Constant("I", "I", (k, k)) 

117 Ip = Constant("I", "I", (p, p)) 

118 Op = Constant("0", 0, (p, 1)) 

119 

120 M = block([[t*Ik, L, g ], # noqa 

121 [L.T, l*Ip, Op ], # noqa 

122 [g.T, Op.T, t-l ]]) # noqa 

123 

124 problem.add_constraint(M >> 0) 

125 

126 return problem 

127 

128 def __init__(self, norm, upper_bound): 

129 """Construct a :class:`BallUncertainNormConstraint`. 

130 

131 :param norm: 

132 Uncertain norm that is bounded from above. 

133 :type norm: 

134 ~picos.expressions.UncertainNorm 

135 

136 :param upper_bound: 

137 (Uncertain) upper bound on the norm. 

138 :type upper_bound: 

139 ~picos.expressions.AffineExpression or 

140 ~picos.expressions.UncertainAffineExpression 

141 """ 

142 from ...expressions import AffineExpression 

143 from ...expressions.uncertain import (ConicPerturbationSet, 

144 UncertainAffineExpression, UncertainNorm, UnitBallPerturbationSet) 

145 

146 assert isinstance(norm, UncertainNorm) 

147 assert isinstance(norm.x.universe, UnitBallPerturbationSet) 

148 assert isinstance(upper_bound, 

149 (AffineExpression, UncertainAffineExpression)) 

150 assert upper_bound.scalar 

151 if upper_bound.uncertain: 

152 assert isinstance(upper_bound.universe, ConicPerturbationSet) 

153 assert norm.perturbation is not upper_bound.perturbation 

154 

155 self.norm = norm 

156 self.ub = upper_bound 

157 

158 super(BallUncertainNormConstraint, self).__init__("Ball-Uncertain Norm") 

159 

160 @property 

161 def ne(self): 

162 """The uncertain affine expression under the norm.""" 

163 return self.norm.x 

164 

165 Subtype = namedtuple("Subtype", ( 

166 "dim", "norm_universe_subtype", "bound_universe_subtype")) 

167 

168 def _subtype(self): 

169 return self.Subtype(len(self.ne), self.ne.universe.subtype, 

170 self.ub.universe.subtype if self.ub.uncertain else None) 

171 

172 @classmethod 

173 def _cost(cls, subtype): 

174 return float("inf") 

175 

176 def _expression_names(self): 

177 yield "norm" 

178 yield "ub" 

179 

180 def _str(self): 

181 if self.ub.uncertain: 

182 # Perturbations are required to differ. 

183 params = glyphs.comma(self.norm.perturbation, self.ub.perturbation) 

184 else: 

185 params = self.norm.perturbation 

186 

187 return glyphs.forall( 

188 glyphs.le(self.norm.string, self.ub.string), params) 

189 

190 def _get_size(self): 

191 return (1, 1) 

192 

193 def _get_slack(self): 

194 if self.ub.certain: 

195 ub_value = self.ub.safe_value 

196 else: 

197 ub_value = self.ub.worst_case_value(direction="min") 

198 

199 return ub_value - self.norm.worst_case_value(direction="max") 

200 

201 

202# -------------------------------------- 

203__all__ = api_end(_API_START, globals())