Coverage for picos/constraints/uncertain/ucon_ball_norm.py: 97.96%
98 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
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# ------------------------------------------------------------------------------
19"""Implements :class:`BallUncertainNormConstraint`."""
21import operator
22from collections import namedtuple
24from ... import glyphs
25from ...apidoc import api_end, api_start
26from ..constraint import Constraint, ConstraintConversion
28_API_START = api_start(globals())
29# -------------------------------
32class BallUncertainNormConstraint(Constraint):
33 """An (uncertain) upper bound on a norm with unit ball uncertainty."""
35 class RobustConversion(ConstraintConversion):
36 """Robust counterpart conversion."""
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
44 if subtype.bound_universe_subtype: # uncertain bound
45 X = subtype.bound_universe_subtype
46 x_dim = X.param_dim
48 K = X.cone_type
49 D = X.dual_cone_type
50 K_dim = K.subtype.dim
52 v = AffineExpression.make_type(
53 shape=(K_dim, 1), constant=False, nonneg=False)
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)
62 k = subtype.dim
63 p = subtype.norm_universe_subtype.param_dim
65 yield ("var", RealVariable.make_var_type(dim=1, bnd=1), 1)
66 yield ("con", LMIConstraint.make_type(diag=(k + p + 1)), 1)
68 @classmethod
69 def convert(cls, con, options):
70 """Implement :meth:`~.constraint.ConstraintConversion.convert`.
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
79 problem = Problem()
81 # a = A(η)y + b(η) is the normed expression, e = η its perturbation.
82 a = con.ne.vec
83 e = con.ne.perturbation
85 # Lz is the uncertain and g = Aⁿy + bⁿ the certain part of a.
86 L, g = a.factor_out(e)
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
96 # sx = σᵀ(y)χ is the uncertain, d = δ(y) the certain part of b.
97 s, d = b.factor_out(x)
99 X = x.universe
100 assert isinstance(X, ConicPerturbationSet)
101 P, Q, p, K = X.A, X.B, X.c, X.K
103 t = RealVariable("__t")
104 v = RealVariable("__v", K.subtype.dim)
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)
112 # Define l = λ.
113 l = RealVariable("__{}".format(glyphs.lambda_()), lower=0)
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))
120 M = block([[t*Ik, L, g ], # noqa
121 [L.T, l*Ip, Op ], # noqa
122 [g.T, Op.T, t-l ]]) # noqa
124 problem.add_constraint(M >> 0)
126 return problem
128 def __init__(self, norm, upper_bound):
129 """Construct a :class:`BallUncertainNormConstraint`.
131 :param norm:
132 Uncertain norm that is bounded from above.
133 :type norm:
134 ~picos.expressions.UncertainNorm
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)
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
155 self.norm = norm
156 self.ub = upper_bound
158 super(BallUncertainNormConstraint, self).__init__("Ball-Uncertain Norm")
160 @property
161 def ne(self):
162 """The uncertain affine expression under the norm."""
163 return self.norm.x
165 Subtype = namedtuple("Subtype", (
166 "dim", "norm_universe_subtype", "bound_universe_subtype"))
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)
172 @classmethod
173 def _cost(cls, subtype):
174 return float("inf")
176 def _expression_names(self):
177 yield "norm"
178 yield "ub"
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
187 return glyphs.forall(
188 glyphs.le(self.norm.string, self.ub.string), params)
190 def _get_size(self):
191 return (1, 1)
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")
199 return ub_value - self.norm.worst_case_value(direction="max")
202# --------------------------------------
203__all__ = api_end(_API_START, globals())