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) 2018-2019 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"""Affine constraint types.""" 

20 

21from collections import namedtuple 

22 

23from .. import glyphs 

24from ..apidoc import api_end, api_start 

25from ..caching import cached_property 

26from .constraint import ConicConstraint, ConstraintConversion 

27 

28_API_START = api_start(globals()) 

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

30 

31 

32class AffineConstraint(ConicConstraint): 

33 """An equality or inequality between two affine expressions.""" 

34 

35 def __init__(self, lhs, relation, rhs, customString=None): 

36 """Construct an :class:`AffineConstraint`. 

37 

38 :param ~picos.expressions.AffineExpression lhs: 

39 Left hand side expression. 

40 :param str relation: 

41 Constraint relation symbol. 

42 :param ~picos.expressions.AffineExpression rhs: 

43 Right hand side expression. 

44 :param str customString: 

45 Optional string description. 

46 """ 

47 from ..expressions import AffineExpression 

48 

49 assert isinstance(lhs, AffineExpression) 

50 assert isinstance(rhs, AffineExpression) 

51 assert relation in self.LE + self.GE + self.EQ 

52 assert lhs.size == rhs.size 

53 

54 self.lhs = lhs 

55 self.rhs = rhs 

56 self.relation = relation 

57 

58 super(AffineConstraint, self).__init__( 

59 "Affine", customString, printSize=True) 

60 

61 @cached_property 

62 def conic_membership_form(self): 

63 """Implement for :class:`~.constraint.ConicConstraint`.""" 

64 from ..expressions import NonnegativeOrthant, ZeroSpace 

65 

66 element = self.ge0.vec 

67 dim = len(element) 

68 

69 if self.relation == self.EQ: 

70 return element, ZeroSpace(dim=dim) 

71 else: 

72 return element, NonnegativeOrthant(dim=dim) 

73 

74 Subtype = namedtuple("Subtype", ("dim", "eq")) 

75 

76 def _subtype(self): 

77 return self.Subtype(len(self.lhs), self.relation == self.EQ) 

78 

79 @property 

80 def smaller(self): 

81 """Smaller-or-equal side of the constraint. 

82 

83 The smaller-or-equal side expression in case of an inequality, otherwise 

84 the left hand side. 

85 """ 

86 return self.rhs if self.relation == self.GE else self.lhs 

87 

88 @property 

89 def greater(self): 

90 """Greater-or-equal side of the constraint. 

91 

92 The greater-or-equal side expression in case of an inequality, otherwise 

93 the right hand side. 

94 """ 

95 return self.lhs if self.relation == self.GE else self.rhs 

96 

97 @cached_property 

98 def le0(self): 

99 """Expression constrained to be lower than or equal to zero. 

100 

101 The expression posed to be less than or equal to zero in case of an 

102 inequality, otherwise the left hand side minus the right hand side. 

103 """ 

104 if self.relation == self.GE: 

105 return self.rhs - self.lhs 

106 else: 

107 return self.lhs - self.rhs 

108 

109 @cached_property 

110 def ge0(self): 

111 """Expression constrained to be greater than or equal to zero. 

112 

113 The expression posed to be greater than or equal to zero in case of an 

114 inequality, otherwise the left hand side minus the right hand side. 

115 """ 

116 if self.relation == self.LE: 

117 return self.rhs - self.lhs 

118 else: 

119 return self.lhs - self.rhs 

120 

121 @classmethod 

122 def _cost(cls, subtype): 

123 return subtype.dim 

124 

125 def _expression_names(self): 

126 yield "lhs" 

127 yield "rhs" 

128 

129 def _str(self): 

130 if self.relation == self.LE: 

131 return glyphs.le(self.lhs.string, self.rhs.string) 

132 elif self.relation == self.GE: 

133 return glyphs.ge(self.lhs.string, self.rhs.string) 

134 else: 

135 return glyphs.eq(self.lhs.string, self.rhs.string) 

136 

137 def _get_size(self): 

138 return self.lhs.size 

139 

140 def _get_slack(self): 

141 if self.relation == self.LE: 

142 delta = self.rhs.safe_value - self.lhs.safe_value 

143 else: 

144 delta = self.lhs.safe_value - self.rhs.safe_value 

145 

146 return -abs(delta) if self.relation == self.EQ else delta 

147 

148 def bounded_linear_form(self): 

149 """Bounded linear form of the constraint. 

150 

151 Separates the constraint into a linear function on the left hand side 

152 and a constant bound on the right hand side. 

153 

154 :returns: A pair ``(linear, bound)`` where ``linear`` is a pure linear 

155 expression and ``bound`` is a constant expression. 

156 """ 

157 linear = self.lhs - self.rhs 

158 bound = -linear.cst 

159 linear = linear + bound 

160 

161 return (linear, bound) 

162 

163 def sparse_Ab_rows(self, varOffsetMap, indexFunction=None): 

164 """Sparse representation of the constraint's bounded linear form. 

165 

166 A sparse list representation of the constraint, given a mapping of PICOS 

167 variables to column offsets (or alternatively given an index function). 

168 

169 The constraint is brought into a bounded linear form A • b, where • is 

170 one of ≤, ≥, or =, depending on the constraint relation, and the rows 

171 returned correspond to the matrix [A|b]. 

172 

173 :param dict varOffsetMap: Maps variables or variable start indices to 

174 column offsets. 

175 :param indexFunction: Instead of adding the local variable index to the 

176 value returned by varOffsetMap, use the return value of this 

177 function, that takes as argument the variable and its local index, 

178 as the "column index", which need not be an integer. When this 

179 parameter is passed, the parameter varOffsetMap is ignored. 

180 :returns: A list of triples (J, V, c) where J contains column indices 

181 (representing scalar variables), V contains coefficients for each 

182 column index and c is a constant term. Each entry of the list 

183 represents a row in a constraint matrix. 

184 """ 

185 lhs = self.lhs - self.rhs 

186 rows = lhs.sparse_rows(varOffsetMap, indexFunction=indexFunction) 

187 

188 for localConIndex in range(len(lhs)): 

189 rows[localConIndex][2] = -rows[localConIndex][2] 

190 

191 return rows 

192 

193 

194class ComplexAffineConstraint(ConicConstraint): 

195 """An equality between affine expressions, at least one being complex.""" 

196 

197 class RealConversion(ConstraintConversion): 

198 """Complex affine equality to real affine equality conversion.""" 

199 

200 @classmethod 

201 def predict(cls, subtype, options): 

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

203 yield ("con", 

204 AffineConstraint.make_type(dim=2*subtype.dim, eq=True), 1) 

205 

206 @classmethod 

207 def convert(cls, con, options): 

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

209 from ..modeling import Problem 

210 

211 P = Problem() 

212 P.add_constraint((con.lhs.real // con.lhs.imag) 

213 == (con.rhs.real // con.rhs.imag)) 

214 

215 return P 

216 

217 @classmethod 

218 def dual(cls, auxVarPrimals, auxConDuals, options): 

219 """Implement :meth:`~.constraint.ConstraintConversion.dual`.""" 

220 assert len(auxConDuals) == 1 

221 

222 auxConDual = auxConDuals[0] 

223 if auxConDual is None: 

224 return None 

225 else: 

226 n = auxConDual.size[0] // 2 

227 return auxConDual[:n, :] + 1j*auxConDual[n:, :] 

228 

229 def __init__(self, lhs, rhs, customString=None): 

230 """Construct a :class:`ComplexAffineConstraint`. 

231 

232 :param ~picos.expressions.AffineExpression lhs: 

233 Left hand side expression. 

234 :param ~picos.expressions.AffineExpression rhs: 

235 Right hand side expression. 

236 :param str customString: 

237 Optional string description. 

238 """ 

239 from ..expressions import ComplexAffineExpression 

240 

241 assert isinstance(lhs, ComplexAffineExpression) 

242 assert isinstance(rhs, ComplexAffineExpression) 

243 assert lhs.size == rhs.size 

244 

245 self.lhs = lhs 

246 self.rhs = rhs 

247 

248 super(ComplexAffineConstraint, self).__init__( 

249 "Complex Equality", customString, printSize=True) 

250 

251 @cached_property 

252 def conic_membership_form(self): 

253 """Implement for :class:`~.constraint.ConicConstraint`.""" 

254 from ..expressions import ZeroSpace 

255 return self.lhs - self.rhs, ZeroSpace() 

256 

257 Subtype = namedtuple("Subtype", ("dim",)) 

258 

259 def _subtype(self): 

260 return self.Subtype(len(self.lhs)) 

261 

262 @classmethod 

263 def _cost(cls, subtype): 

264 return 2*subtype.dim 

265 

266 def _expression_names(self): 

267 yield "lhs" 

268 yield "rhs" 

269 

270 def _str(self): 

271 return glyphs.eq(self.lhs.string, self.rhs.string) 

272 

273 def _get_size(self): 

274 return self.lhs.size 

275 

276 def _get_slack(self): 

277 return -abs(self.lhs.safe_value - self.rhs.safe_value) 

278 

279 

280# -------------------------------------- 

281__all__ = api_end(_API_START, globals())