Skip to content

Constraints

Constraints are equalities and inequalities over linear expressions, used to encode assumptions on the problem data and the initial conditions.

Constraint

A symbolic relation between two expressions (or an expression and a vector), of the form:

\[ \text{lhs} \;\mathrm{op}\; \text{rhs}, \]

where op is one of "==", "<=", or ">=". Instances are typically created by using comparison operators on expression object(s) (e.g., expr1 <= expr2) rather than by calling the constructor directly.

Attributes:

Name Type Description
lhs LinearExpression

Left-hand side linear expression in the constraint definition.
rhs LinearExpression, np.ndarray, or list

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.
operator str {'<=', '>=', '=='}

The relational operator defining the constraint.
ndim int

The dimension of underlying space, i.e., the size of each coefficient matrix in the linear expressions.
is_linear bool

True for ordinary (in)equality constraints, which are linear and safe to forward to the OBBT handler's LP. Non-convex subclasses (e.g. ComplementarityConstraint) override this to False.
Source code in fomtools/constraint.py 
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class Constraint:
    r"""
    A symbolic relation between two expressions (or an expression and a vector),
    of the form:

    $$
        \text{lhs} \;\mathrm{op}\; \text{rhs},
    $$

    where ``op`` is one of ``"=="``, ``"<="``, or ``">="``. Instances are
    typically created by using comparison operators on expression object(s)
    (e.g., ``expr1 <= expr2``) rather than by calling the constructor directly.

    Attributes
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.
    rhs: LinearExpression, np.ndarray, or list
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.
    operator: str {'<=', '>=', '=='}
        The relational operator defining the constraint.
    ndim: int
        The dimension of underlying space, i.e., the size of each coefficient matrix
        in the linear expressions.
    is_linear: bool
        ``True`` for ordinary (in)equality constraints, which are linear and safe to
        forward to the OBBT handler's LP. Non-convex subclasses (e.g.
        `ComplementarityConstraint`) override this to ``False``.
    """

    is_linear = True

    def __init__(
        self, lhs: "LinearExpression", rhs: Union["LinearExpression", np.ndarray, list], operator
    ):
        """
        Initialize an instance of `Constraint` class.

        Parameters
        ----------
        lhs: LinearExpression
            Left-hand side linear expression in the constraint definition.

        rhs: LinearExpression
            Right-hand side linear expression in the constraint definition. Scalars are
            broadcast to the shape of the `lhs` expression. Arrays or expressions must
            be of same shape with `self`.

        operator: str {'<=', '>=', '=='}
            The relational operator defining the constraint.

        Raises
        ------
        ValueError
            If the expressions `lhs` and `rhs` are not of the same shape.

        TypeError
            If `rhs` is not a LinearExpression object, NumPy array or a list.
        """
        try:
            # If rhs is a scalar, broadcast it to the dimension of the lhs expression
            rhs = np.full(lhs.ndim, float(rhs))
        except TypeError:
            try:
                # Check to see if rhs is of type list or a numpy array
                if len(rhs) == lhs.ndim:
                    rhs = np.array(rhs)
                else:
                    raise ValueError("Cannot have a constraint of mismatched dimensions. ")
            except TypeError:
                try:
                    # Check to see if other is of type LinearExpression
                    if lhs.ndim != rhs.ndim:
                        raise ValueError("Cannot have a constraint of mismatched dimensions. ")
                except AttributeError:
                    raise TypeError(
                        f"""Can only create a constraint of a LinearExpression object,"
                         with a scalar, numpy array, list, or another LinearExpression object got type {type(rhs)}."""
                    )

        self.lhs = lhs - rhs
        self.rhs = np.zeros_like(self.lhs.ndim)
        self.operator = operator
        self.ndim = lhs.ndim

    def __str__(self):
        return f"{self.lhs} {self.operator} {self.rhs}"

    def __repr__(self):
        return f"<{self.__class__.__name__}, dim={self.ndim}>"

__init__ 

__init__(lhs: LinearExpression, rhs: Union[LinearExpression, ndarray, list], operator)

Parameters:

Name Type Description Default
lhs LinearExpression

Left-hand side linear expression in the constraint definition.

 required
rhs Union[LinearExpression, ndarray, list]

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.

 required
operator

The relational operator defining the constraint.

 required

Raises:

Type Description
ValueError

If the expressions lhs and rhs are not of the same shape.
TypeError

If rhs is not a LinearExpression object, NumPy array or a list.
Source code in fomtools/constraint.py 
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
def __init__(
    self, lhs: "LinearExpression", rhs: Union["LinearExpression", np.ndarray, list], operator
):
    """
    Initialize an instance of `Constraint` class.

    Parameters
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.

    rhs: LinearExpression
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.

    operator: str {'<=', '>=', '=='}
        The relational operator defining the constraint.

    Raises
    ------
    ValueError
        If the expressions `lhs` and `rhs` are not of the same shape.

    TypeError
        If `rhs` is not a LinearExpression object, NumPy array or a list.
    """
    try:
        # If rhs is a scalar, broadcast it to the dimension of the lhs expression
        rhs = np.full(lhs.ndim, float(rhs))
    except TypeError:
        try:
            # Check to see if rhs is of type list or a numpy array
            if len(rhs) == lhs.ndim:
                rhs = np.array(rhs)
            else:
                raise ValueError("Cannot have a constraint of mismatched dimensions. ")
        except TypeError:
            try:
                # Check to see if other is of type LinearExpression
                if lhs.ndim != rhs.ndim:
                    raise ValueError("Cannot have a constraint of mismatched dimensions. ")
            except AttributeError:
                raise TypeError(
                    f"""Can only create a constraint of a LinearExpression object,"
                     with a scalar, numpy array, list, or another LinearExpression object got type {type(rhs)}."""
                )

    self.lhs = lhs - rhs
    self.rhs = np.zeros_like(self.lhs.ndim)
    self.operator = operator
    self.ndim = lhs.ndim

EqualityConstraint

Bases: Constraint

An equality relation between two expressions (or an expression and a vector), of the form.

\[ \text{lhs} \;=\; \text{rhs}, \]

and is typically created via the == operator on expression objects (e.g., expr1 == expr2) rather than by calling the constructor directly.

Attributes:

Name Type Description
lhs LinearExpression

Left-hand side linear expression in the constraint definition.
rhs LinearExpression, np.ndarray, or list

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.
operator str {'<=', '>=', '=='}

The relational operator defining the constraint.
ndim int

The dimension of underlying space, i.e., the size of each coefficient matrix in the linear expressions.
Source code in fomtools/constraint.py 
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
class EqualityConstraint(Constraint):
    r"""
    An equality relation between two expressions (or an expression and a vector),
    of the form.

    $$
        \text{lhs} \;=\; \text{rhs},
    $$

    and is typically created via the ``==`` operator on expression objects
    (e.g., ``expr1 == expr2``) rather than by calling the constructor directly.

    Attributes
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.
    rhs: LinearExpression, np.ndarray, or list
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.
    operator: str {'<=', '>=', '=='}
        The relational operator defining the constraint.
    ndim: int
        The dimension of underlying space, i.e., the size of each coefficient matrix
        in the linear expressions.
    """

    def __init__(self, lhs, rhs):
        """
        Initialize an instance of `EqualityConstraint` class.

        Parameters
        ----------
        lhs: LinearExpression
            Left-hand side linear expression in the constraint definition.

        rhs: LinearExpression
            Right-hand side linear expression in the constraint definition. Scalars are
            broadcast to the shape of the `lhs` expression. Arrays or expressions must
            be of same shape with `self`.
        """
        operator = "="
        super().__init__(lhs, rhs, operator)

__init__ 

__init__(lhs, rhs)

Parameters:

Name Type Description Default
lhs

Left-hand side linear expression in the constraint definition.

 required
rhs

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.

 required
Source code in fomtools/constraint.py 
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
def __init__(self, lhs, rhs):
    """
    Initialize an instance of `EqualityConstraint` class.

    Parameters
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.

    rhs: LinearExpression
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.
    """
    operator = "="
    super().__init__(lhs, rhs, operator)

InequalityConstraint

Bases: Constraint

An non-strict inequality relation between two expressions (or an expression and a vector), of the form.

\[ \text{lhs} \;<=\; \text{rhs}, \]

and is typically created via the <= operator on expression objects (e.g., expr1 <= expr2) rather than by calling the constructor directly.

Attributes:

Name Type Description
lhs LinearExpression

Left-hand side linear expression in the constraint definition.
rhs LinearExpression, np.ndarray, or list

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.
operator str {'<=', '>=', '=='}

The relational operator defining the constraint.
ndim int

The dimension of underlying space, i.e., the size of each coefficient matrix in the linear expressions.
Source code in fomtools/constraint.py 
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
class InequalityConstraint(Constraint):
    r"""
    An non-strict inequality relation between two expressions (or an expression and a vector),
    of the form.

    $$
        \text{lhs} \;<=\; \text{rhs},
    $$

    and is typically created via the ``<=`` operator on expression objects
    (e.g., ``expr1 <= expr2``) rather than by calling the constructor directly.

    Attributes
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.
    rhs: LinearExpression, np.ndarray, or list
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.
    operator: str {'<=', '>=', '=='}
        The relational operator defining the constraint.
    ndim: int
        The dimension of underlying space, i.e., the size of each coefficient matrix
        in the linear expressions.
    """

    def __init__(self, lhs, rhs):
        """
        Initialize an instance of `InequalityConstraint` class.

        Parameters
        ----------
        lhs: LinearExpression
            Left-hand side linear expression in the constraint definition.

        rhs: LinearExpression
            Right-hand side linear expression in the constraint definition. Scalars are
            broadcast to the shape of the `lhs` expression. Arrays or expressions must
            be of same shape with `self`.
        """
        operator = "<="
        super().__init__(lhs, rhs, operator)

__init__ 

__init__(lhs, rhs)

Parameters:

Name Type Description Default
lhs

Left-hand side linear expression in the constraint definition.

 required
rhs

Right-hand side linear expression in the constraint definition. Scalars are broadcast to the shape of the lhs expression. Arrays or expressions must be of same shape with self.

 required
Source code in fomtools/constraint.py 
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
def __init__(self, lhs, rhs):
    """
    Initialize an instance of `InequalityConstraint` class.

    Parameters
    ----------
    lhs: LinearExpression
        Left-hand side linear expression in the constraint definition.

    rhs: LinearExpression
        Right-hand side linear expression in the constraint definition. Scalars are
        broadcast to the shape of the `lhs` expression. Arrays or expressions must
        be of same shape with `self`.
    """
    operator = "<="
    super().__init__(lhs, rhs, operator)

Objective atoms

ft.norm and ft.sum_squares build the objective passed to Verifier.maximize, for example vp.maximize(ft.norm(z - z_prev, np.inf)).

norm 

norm(expr, p) -> Norm

Build a norm atom \|expr\|_p to maximize with Verifier.maximize::

vp.maximize(ft.norm(z - z_prev, np.inf))

Parameters:

Name Type Description Default
expr LinearExpression or Sequence[LinearExpression]

The expression, or a list of expressions whose stacked vector is taken.

 required
p (1, inf, inf)

The norm order. For the squared two-norm, maximize ft.sum_squares(expr).

 1

Returns:

Type Description
Norm

The atom.

Raises:

Type Description
ValueError

If p is not 1 or infinity.
Source code in fomtools/constraint.py 
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
def norm(expr, p) -> Norm:
    r"""
    Build a norm atom ``\|expr\|_p`` to maximize with `Verifier.maximize`::

        vp.maximize(ft.norm(z - z_prev, np.inf))

    Parameters
    ----------
    expr : LinearExpression or Sequence[LinearExpression]
        The expression, or a list of expressions whose stacked vector is taken.
    p : {1, np.inf, 'inf'}
        The norm order. For the squared two-norm, maximize ``ft.sum_squares(expr)``.

    Returns
    -------
    Norm
        The atom.

    Raises
    ------
    ValueError
        If ``p`` is not ``1`` or infinity.
    """
    if p == 2:
        raise ValueError(
            "The two-norm objective is squared: maximize ft.sum_squares(expr) instead "
            "(with method='mip' it is an MIQP and needs solver='gurobi')."
        )
    if p == "inf":
        p = np.inf
    if p not in (1, np.inf):
        raise ValueError(f"Unsupported norm order: {p}. Use 1 or np.inf.")
    exprs = tuple(expr) if isinstance(expr, (list, tuple)) else (expr,)
    return Norm(exprs, p)

sum_squares 

sum_squares(expr: LinearExpression) -> SumSquares

Build a sum-of-squares atom \sum_i (a_i^\top x + b_i)^2 for use in a quadratic constraint.

Compare the returned object against a nonnegative scalar to form a QuadraticConstraint::

vp.add_constraint(ft.sum_squares(expr) <= r**2)   # ||A x + b||_2^2 <= r^2
vp.add_constraint(ft.sum_squares(expr) >= r**2)   # nonconvex shell
vp.add_constraint(ft.sum_squares(expr) == r**2)   # nonconvex sphere

Parameters:

Name Type Description Default
expr LinearExpression

The expression whose squared two-norm is taken.

 required

Returns:

Type Description
SumSquares

The atom; compare it with <= / >= / == to obtain a constraint.
Source code in fomtools/constraint.py 
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
def sum_squares(expr: "LinearExpression") -> SumSquares:
    r"""
    Build a sum-of-squares atom ``\sum_i (a_i^\top x + b_i)^2`` for use in a quadratic
    constraint.

    Compare the returned object against a nonnegative scalar to form a
    `QuadraticConstraint`::

        vp.add_constraint(ft.sum_squares(expr) <= r**2)   # ||A x + b||_2^2 <= r^2
        vp.add_constraint(ft.sum_squares(expr) >= r**2)   # nonconvex shell
        vp.add_constraint(ft.sum_squares(expr) == r**2)   # nonconvex sphere

    Parameters
    ----------
    expr : LinearExpression
        The expression whose squared two-norm is taken.

    Returns
    -------
    SumSquares
        The atom; compare it with ``<=`` / ``>=`` / ``==`` to obtain a constraint.
    """
    return SumSquares(expr)