Coverage for picos/constraints/constraint.py: 86.75%

1# ------------------------------------------------------------------------------ 

2# Copyright (C) 2018 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"""Backend for constraint type implementations.""" 

20 

21import random 

22import threading 

23from abc import ABC, abstractmethod 

24from copy import copy as pycopy 

25 

26import cvxopt 

27 

28from .. import glyphs 

29from ..apidoc import api_end, api_start 

30from ..caching import cached_property, empty_cache 

31from ..containers import DetailedType 

32 

33_API_START = api_start(globals()) 

34# ------------------------------- 

35 

36 

37# The constraint IDs start at a random value to prevent a clash if constraints 

38# are are pickled and loaded in another python session. 

39_LAST_CONSTRAINT_ID = int(random.getrandbits(31)) 

40 

41# A lock for _LAST_CONSTRAINT_ID, if the user threads to create constraints. 

42_CONSTRAINT_ID_LOCK = threading.Lock() 

43 

44 

45def _make_constraint_id(): 

46 """Create a unique ID for a new constraint.""" 

47 with _CONSTRAINT_ID_LOCK: 

48 global _LAST_CONSTRAINT_ID 

49 _LAST_CONSTRAINT_ID += 1 

50 return _LAST_CONSTRAINT_ID 

51 

52 

53class ConstraintType(DetailedType): 

54 """Container for a pair of constraint class type and constraint subtype.""" 

55 

56 pass 

57 

58 

59class Constraint(ABC): 

60 """Abstract base class for optimization constraints. 

61 

62 Implementations 

63 

64 * need to implement at least the abstract methods ``_str``, 

65 ``_expression_names``, and ``_get_slack``, 

66 * need to implement ``_get_size``, unless duals are not supported, and 

67 * are supposed to call :meth:`Constraint.__init__` from within their own 

68 implementation of ``__init__``. 

69 """ 

70 

71 LE = "<" 

72 GE = ">" 

73 EQ = "=" 

74 

75 def __init__(self, typeTerm, customString=None, printSize=False): 

76 """Perform basic initialization for :class:`Constraint` instances. 

77 

78 :param str typeTerm: Short string denoting the constraint type. 

79 :param str customString: Optional string description. 

80 :param bool printSize: Whether to include the constraint's shape in its 

81 representation string. 

82 """ 

83 self.typeTerm = typeTerm 

84 self.customString = customString 

85 self.printSize = printSize 

86 

87 self._id = _make_constraint_id() 

88 

89 self.name = None 

90 self._dual = None 

91 

92 @property 

93 def type(self): 

94 """Detailed type of the constraint. 

95 

96 The detailed type of the constraint, which is suffcient to predict the 

97 outcome (detailed types and quantities of auxilary variables and 

98 constraints) of any constraint conversion. 

99 """ 

100 return ConstraintType(self.__class__, self._subtype()) 

101 

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

103 

104 @classmethod 

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

106 """Create a detailed constraint type from subtype parameters.""" 

107 return ConstraintType(cls, cls.Subtype(*args, **kwargs)) 

108 

109 @abstractmethod 

110 def _subtype(self): 

111 """Subtype of the constraint. 

112 

113 :returns: A hashable object that, together with the constraint class, 

114 is sufficient to predict the outcome (detailed types and quantities 

115 of auxilary variables and constraints) of any constraint conversion. 

116 """ 

117 pass 

118 

119 @classmethod 

120 @abstractmethod 

121 def _cost(cls, subtype): 

122 r"""Report an estimate number of real constraint matrix rows occupied. 

123 

124 Given the subtype of a constraint, returns an estimate on the number of 

125 rows that a constraint with this subtype would occupy in the constraint 

126 matrix of a (hypothetical) solver that supports direct input of such a 

127 constraint. 

128 

129 Some conventions: 

130 

131 - For a conic constraint, this is the cone's dimensionality. 

132 - For a (complex) affine equality :math:`A = B`, this is the number of 

133 elements in the matrix :math:`A - B` (times two). 

134 - For a constraint that poses a bound on a scalar function on an 

135 :math:`n`-dimensional vector space, this is :math:`n + 1` (:math:`1` 

136 for the affine bound). 

137 - In particular, a bound on a function of symmetric (hermitian) matrices 

138 occupies :math:`\frac{n(n + 1)}{2} + 1` (:math:`n^2 + 1`) rows. 

139 - For a quadratic constraint, this is the number of coefficients in the 

140 simplified quadratic form, plus one (for the affine part). 

141 """ 

142 pass 

143 

144 def __hash__(self): 

145 """Return the unique ID.""" 

146 return self._id 

147 

148 def __eq__(self, other): 

149 """Whether the unique IDs equal.""" 

150 return self._id == other._id 

151 

152 def __repr__(self): 

153 if self.printSize: 

154 return glyphs.repr2("{} {} Constraint".format( 

155 glyphs.size(*self.size), self.typeTerm), self.__str__()) 

156 else: 

157 return glyphs.repr2("{} Constraint".format(self.typeTerm), 

158 self.__str__()) 

159 

160 def __str__(self): 

161 return "{}{}".format( 

162 self.customString if self.customString else self._str(), 

163 " ({})".format(self.name) if self.name else "") 

164 

165 def __len__(self): 

166 """Return number of scalar Lagrange dual variables.""" 

167 return self.size[0] * self.size[1] 

168 

169 @property 

170 def id(self): 

171 """The unique ID of the constraint, assigned at creation. 

172 

173 The ID is kept when the constraint is copied via 

174 :meth:`replace_mutables`, so that the copy can be identified with the 

175 original despite pointing to different expressions and mutable objects. 

176 """ 

177 return self._id 

178 

179 @abstractmethod 

180 def _expression_names(self): 

181 """Attribute names of the expressions stored in the constraint.""" 

182 pass 

183 

184 @abstractmethod 

185 def _str(self): 

186 """Algebraic representation of the constraint.""" 

187 pass 

188 

189 def _get_size(self): 

190 """Langrange dual variable shape. 

191 

192 The dimensionality of the constraint, more precisely the dimensionality 

193 of its Lagrange dual variable, as a pair. 

194 """ 

195 # TODO: This seems to be associated with the size of the slack vector 

196 # as well (the test bench checks against this) and therefor should 

197 # probably be abstract as well. 

198 raise NotImplementedError( 

199 "{} does not define a constraint (dual value) dimensionality." 

200 .format(self.__class__.__name__)) 

201 

202 @abstractmethod 

203 def _get_slack(self): 

204 """Value of a slack variable or of the negative constraint violation. 

205 

206 A negative value whose absolute value corresponds to the amount of 

207 violation, if the constraint is violated, or a non-negative value that 

208 corresponds to the value of a slack variable, otherwise. 

209 """ 

210 pass 

211 

212 def _wrap_get_slack(self): 

213 """Convert a scalar slack value to float. 

214 

215 A wrapper retrieving the slack in a consistent manner: If it is a scalar 

216 value, it is returned as a float, otherwise as a 

217 :class:`CVXOPT matrix <cvxopt.matrix>`. 

218 """ 

219 slack = self._get_slack() 

220 

221 if isinstance(slack, float): 

222 return slack 

223 

224 assert isinstance(slack, cvxopt.matrix), "Constraints need to return " \ 

225 "the slack as either a float or a CVXOPT matrix." 

226 

227 if slack.size == (1, 1): 

228 return float(slack[0]) 

229 else: 

230 return slack 

231 

232 def _get_dual(self): 

233 return self._dual 

234 

235 def _set_dual(self, value): 

236 """Store a constraint's dual value. 

237 

238 Stores a dual solution value for the dual variable corresponding to the 

239 constraint in a consistent manner. 

240 

241 Duals for multidmensional constraints are stored as a CVXOPT (sparse) 

242 matrix while duals for scalar constraints are stored as a Python scalar. 

243 """ 

244 from ..expressions.data import load_data 

245 

246 if value is None: 

247 self._dual = None 

248 else: 

249 dual = load_data(value, self.size)[0] 

250 self._dual = dual[0] if dual.size == (1, 1) else dual 

251 

252 size = property(lambda self: self._get_size(), doc=_get_size.__doc__) 

253 slack = property(lambda self: self._wrap_get_slack(), 

254 doc=_get_slack.__doc__) 

255 dual = property(lambda self: self._get_dual(), _set_dual) 

256 """Value of the constraint's Lagrange dual variable.""" 

257 

258 def delete(self): 

259 """Raise a :exc:`NotImplementedError`. 

260 

261 Formerly this would remove the constraint from the single problem it is 

262 assigned to, if any. 

263 

264 .. deprecated:: 2.0 

265 

266 Both variables and constraints have been decoupled from problems: 

267 Both may safely appear in multiple problems but at the same time 

268 they do not know which problems they were added to. To remove a 

269 constraint from a problem, you have to call its 

270 :meth:`~picos.modeling.problem.Problem.remove_constraint` method. 

271 """ 

272 raise NotImplementedError("Telling a constraint to remove itself from " 

273 "problems is not possible anymore, use Problem.remove_constraint " 

274 "on selected problems instead.") 

275 

276 # TODO: Solve this with inspection instead of _expression_names? 

277 # TODO: Is this even needed for anything apart from mutables and 

278 # replace_mutables? If not, maybe just implement those two with 

279 # every constraint just like for expressions? 

280 # Idea: Could add a MutableRegister abstract base class used by Expression 

281 # and Constraint. 

282 @property 

283 def expressions(self): 

284 """Yield expressions stored with the constraint.""" 

285 for name in self._expression_names(): 

286 yield getattr(self, name) 

287 

288 @cached_property 

289 def mutables(self): 

290 """All mutables referenced by the constraint.""" 

291 mtbs = frozenset() 

292 for expression in self.expressions: 

293 mtbs = mtbs.union(expression.mutables) 

294 return mtbs 

295 

296 @cached_property 

297 def variables(self): 

298 """All decision variables referenced by the constraint.""" 

299 from ..expressions.variables import BaseVariable 

300 

301 return frozenset(mutable for mutable in self.mutables 

302 if isinstance(mutable, BaseVariable)) 

303 

304 @cached_property 

305 def parameters(self): 

306 """All parameters referenced by the constraint.""" 

307 from ..expressions.variables import BaseVariable 

308 

309 return frozenset(mutable for mutable in self.mutables 

310 if not isinstance(mutable, BaseVariable)) 

311 

312 def replace_mutables(self, new_mutables): 

313 """Make the constraint concern a different set of mutables. 

314 

315 See :meth:`~.expression.Expression.replace_mutables` for more. 

316 """ 

317 the_copy = pycopy(self) 

318 

319 # Clear the cache of the copy as it can reference old mutables. 

320 empty_cache(the_copy) 

321 

322 # Rewrite expressions. 

323 for name in the_copy._expression_names(): 

324 expression = getattr(self, name) 

325 new_expression = expression.replace_mutables(new_mutables) 

326 setattr(the_copy, name, new_expression) 

327 

328 # HACK: Delete a custom string because it can contain old mutable names. 

329 # In particular Norm uses it when creating a SOCConstraint. 

330 # TODO: Get rid of custom strings. 

331 the_copy.customString = None 

332 

333 # TODO: Reset a dual value assigned to the constraint? 

334 # theCopy._dual = None 

335 

336 return the_copy 

337 

338 # TODO: Evaluate uses of this method. 

339 def constring(self): 

340 """Return an algebraic string representation of the constraint.""" 

341 return self._str() 

342 

343 # TODO: Re-implement pretty printing for problems. 

344 def keyconstring(self): 

345 """Return the regular string representation.""" 

346 return self.__str__() 

347 

348 def _assure_lhs_rhs_relation(self): 

349 if not hasattr(self, "relation") or not hasattr(self, "lhs") \ 

350 or not hasattr(self, "rhs"): 

351 raise TypeError("{} does not explicitly define a relation " 

352 "between a left hand side and a right hand side expression." 

353 .format(self.__class__.__name__)) 

354 

355 def is_equality(self): 

356 """Whether the constraints states an equality.""" 

357 self._assure_lhs_rhs_relation() 

358 return self.relation == self.EQ 

359 

360 def is_inequality(self): 

361 """Whether the constraints states an inequality.""" 

362 self._assure_lhs_rhs_relation() 

363 return self.relation != self.EQ 

364 

365 def is_increasing(self): 

366 """Whether the left side is posed smaller or equal than the right.""" 

367 self._assure_lhs_rhs_relation() 

368 return self.relation == self.LE 

369 

370 def is_decreasing(self): 

371 """Whether the left side is posed greater or equal than the right.""" 

372 self._assure_lhs_rhs_relation() 

373 return self.relation == self.GE 

374 

375 

376class ConicConstraint(Constraint): 

377 """Base class for constraints with an immediate conic representation.""" 

378 

379 @property 

380 @abstractmethod 

381 def conic_membership_form(self): 

382 r"""The constraint in conic membership form. 

383 

384 For a conic constraint 

385 :math:`Ax \succeq_C b \Leftrightarrow Ax - b \in C` this is the pair 

386 :math:`(Ax - b, C)` where :math:`Ax - b` is an affine expression and 

387 :math:`C` a basic cone supported by PICOS. 

388 """ 

389 pass 

390 

391 @cached_property 

392 def conic_standard_form(self): 

393 r"""The constraint in conic standard form. 

394 

395 For a conic constraint :math:`Ax \succeq_C b` this is the triple 

396 :math:`(Ax, b, C)` where :math:`Ax` is a linear expression, :math:`b` is 

397 a constant, and :math:`C` a basic cone supported by PICOS. 

398 """ 

399 member, cone = self.conic_membership_form 

400 return member.lin, -member.cst, cone 

401 

402 @cached_property 

403 def inverse_conic_standard_form(self): 

404 r"""The constraint in inverse conic standard form. 

405 

406 For a conic constraint 

407 :math:`Ax \succeq_C b \Leftrightarrow -Ax \preceq_C -b` this is the 

408 triple :math:`(-Ax, -b, C)` where :math:`Ax` is a linear expression, 

409 :math:`b` is a constant, and :math:`C` a basic cone supported by PICOS. 

410 """ 

411 member, cone = self.conic_membership_form 

412 return -member.lin, member.cst, cone 

413 

414 

415class ConstraintConversion(ABC): 

416 """Recipe for conversion from one constraint to a set of other constraints. 

417 

418 Implementations of this class are defined within the class body of a 

419 Constraint implementation to tell PICOS' reformulation framework how that 

420 constraint can be reformulated into a number of other constraints and 

421 auxiliary variables. 

422 

423 Implementation class names must end in ``Conversion``, and in particular may 

424 be called just ``Conversion``. If for instance 

425 :class:`AbsoluteValueConstraint <.con_absolute.AbsoluteValueConstraint>` 

426 defines :class:`AffineConversion 

427 <.con_absolute.AbsoluteValueConstraint.AffineConversion>`, then the 

428 reformulation will be coined ``AbsoluteValueToAffineReformulation``. If the 

429 conversions was just named ``Conversion``, the result would be a class named 

430 ``AbsoluteValueReformulation``. 

431 """ 

432 

433 @classmethod 

434 @abstractmethod 

435 def predict(cls, subtype, options): 

436 """Predict the outcome of a constraint conversion. 

437 

438 :param object subtype: A hashable object as could be returned by the 

439 ``_subtype`` method of the parent constraint implementation. 

440 :param ~picos.Options options: Solution options to assume used. 

441 :yields: Records to be added to a problem footprint when an instance of 

442 the parent constraint with the given subtype is converted according 

443 to this conversion. 

444 """ 

445 pass 

446 

447 # TODO: Make this yield variables and constraints instad of returning a 

448 # Problem instance (this was not possible with the old expressions). 

449 @classmethod 

450 @abstractmethod 

451 def convert(cls, constraint, options): 

452 """Convert a given constraint. 

453 

454 Returns a temporary problem instance that contains auxilary constraints 

455 and variables replacing the given constraint. 

456 """ 

457 pass 

458 

459 @classmethod 

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

461 """Convert back the dual value of a constraint that was converted. 

462 

463 Given a mapping of auxilary variable names (as named in :meth:`convert`) 

464 to primals and a list of auxilary constraint duals (in the order as the 

465 constraints were added in :meth:`convert`), returns a dual value for the 

466 converted constraint. 

467 

468 :raises NotImplementedError: When dual format not decided upon or not 

469 known. This will be caught by the reformulation's backward method. 

470 """ 

471 raise NotImplementedError( 

472 "{} does not describe how to convert back the dual.".format( 

473 cls.__qualname__ if hasattr(cls, "__qualname__") else cls.__name__)) 

474 

475 def __init__(self): 

476 """Raise a :exc:`TypeError` on instanciation.""" 

477 raise TypeError("Constraint conversion classes are not supposed to be " 

478 "instanciated.") 

479 

480 

481# -------------------------------------- 

482__all__ = api_end(_API_START, globals())