Operator classes

Operator classes use the same oracle infrastructure as function classes, but their interpolation constraints describe set-valued or single-valued operators such as monotone, cocoercive, Lipschitz, or nonexpansive maps.

PEPit.LipschitzOperator — Type

LipschitzOperator(param; reuse_gradient=true)

Interpolation class of $L$-Lipschitz continuous operators.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["L"]: Lipschitz continuity parameter $L$.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$ (see [1, 2, 3], or e.g. [4, Fact 2]):

\[\|g_i - g_j\|^2 \leqslant L^2 \|x_i - x_j\|^2.\]

Julia usage

problem = PEP()
param = OrderedDict("L" => 1.0)
op = declare_function!(problem, LipschitzOperator, param)

Note

Setting $L = 1$ models a nonexpansive operator, and $L < 1$ a contracting operator. With L == Inf the class adds no constraint (it contains all multi-valued mappings); the constructor emits a warning in that case.

Fields

L::Float64: Lipschitz continuity parameter $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] M. Kirszbraun (1934). Über die zusammenziehende und Lipschitzsche Transformationen. Fundamenta Mathematicae, 22.

[2] F.A. Valentine (1943). On the extension of a vector function so as to preserve a Lipschitz condition. Bulletin of the American Mathematical Society, 49(2).

[3] F.A. Valentine (1945). A Lipschitz condition preserving extension for a vector function. American Journal of Mathematics, 67(1).

Discussions and appropriate pointers for the interpolation problem can be found in:

[4] E. Ryu, A. Taylor, C. Bergeling, P. Giselsson (2020). Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3), 2251-2271.

PEPit.LinearOperator — Type

LinearOperator(param; reuse_gradient=true)

Interpolation class of linear operators $M$ with singular values bounded by $L$.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used. The adjoint operator $M^\ast$ is available as the field T: calling gradient!(M.T, u) evaluates $M^\ast u$.

Class parameters

param["L"]: upper bound $L$ on the singular values of the operator.

Interpolation conditions

Denoting by $(x_i, y_i)$ the oracle pairs of $M$ (with $y_i = M x_i$) and by $(u_j, v_j)$ the oracle pairs of the adjoint $M^\ast$ (with $v_j = M^\ast u_j$), the following constraints are added (see [1]):

\[\langle x_i, v_j \rangle = \langle y_i, u_j \rangle \qquad \text{for all pairs } (i, j),\]

together with the two PSD constraints $T^{(1)} \succeq 0$ and $T^{(2)} \succeq 0$, where

\[T^{(1)}_{ij} = L^2 \langle x_i, x_j \rangle - \langle y_i, y_j \rangle, \qquad T^{(2)}_{ij} = L^2 \langle u_i, u_j \rangle - \langle v_i, v_j \rangle.\]

Julia usage

problem = PEP()
param = OrderedDict("L" => 1.0)
M = declare_function!(problem, LinearOperator, param)
y = gradient!(M, x)    # evaluates M * x
v = gradient!(M.T, u)  # evaluates M' * u

Note

Linear operators are necessarily continuous, hence reuse_gradient is set to true.

Fields

L::Float64: singular value bound $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.
T::PEPFunction: the adjoint linear operator $M^\ast$ (created automatically by the constructor).

References

[1] N. Bousselmi, J. Hendrickx, F. Glineur (2023). Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems. arXiv preprint.

PEPit.NonexpansiveOperator — Type

NonexpansiveOperator(param=OrderedDict(); reuse_gradient=true)

Interpolation class of (possibly inconsistent) nonexpansive operators.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["v"] (optional, default nothing): infimal displacement vector $v$, given as a Point.

Nonexpansive operators are not otherwise characterized by any parameter. Omitting "v" corresponds to the consistent case.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i = T(x_i)$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$:

\[\|g_i - g_j\|^2 \leqslant \|x_i - x_j\|^2.\]

When the infimal displacement vector $v$ is provided, the following constraint is also added for every $i$ (see [2]):

\[\|v\|^2 \leqslant \langle x_i - g_i, v \rangle.\]

Julia usage

problem = PEP()
op = declare_function!(problem, NonexpansiveOperator, OrderedDict())

Note

Any nonexpansive operator $T$ has a unique vector called the infimal displacement vector, which we denote by $v$. If a nonexpansive operator is consistent, i.e., has a fixed point, then $v = 0$. If $v$ is nonzero, the operator is inconsistent, i.e., does not have a fixed point.

Fields

v::Union{Point,Nothing}: infimal displacement vector $v$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

Discussions and appropriate pointers for the interpolation problem can be found in:

[1] E. Ryu, A. Taylor, C. Bergeling, P. Giselsson (2020). Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3), 2251-2271.

[2] J. Park, E. Ryu (2023). Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations. arXiv preprint:2303.15876.

PEPit.MonotoneOperator — Type

MonotoneOperator(param=OrderedDict(); reuse_gradient=false)

Interpolation class of maximally monotone operators (see, e.g., [1] for an extensive discussion of maximal monotonicity).

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

General maximally monotone operators are not characterized by any parameter, so param may be left empty.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$:

\[\langle g_i - g_j, x_i - x_j \rangle \geqslant 0.\]

Maximality guarantees that any monotone set of pairs can be extended to a maximally monotone operator, so these conditions are interpolation conditions for the class.

Julia usage

problem = PEP()
op = declare_function!(problem, MonotoneOperator, OrderedDict())

Fields

_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] H. H. Bauschke and P. L. Combettes (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer New York.

PEPit.StronglyMonotoneOperator — Type

StronglyMonotoneOperator(param; reuse_gradient=false)

Interpolation class of $\mu$-strongly monotone (and maximally monotone) operators.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: strong monotonicity parameter $\mu$.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$:

\[\langle g_i - g_j, x_i - x_j \rangle \geqslant \mu \|x_i - x_j\|^2.\]

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1)
op = declare_function!(problem, StronglyMonotoneOperator, param)

Fields

mu::Float64: strong monotonicity parameter $\mu$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

Discussions and appropriate pointers for the problem of interpolation of maximally monotone operators can be found in:

PEPit.NegativelyComonotoneOperator — Type

NegativelyComonotoneOperator(param; reuse_gradient=true)

Class of $\rho$-negatively comonotone operators, modeled through necessary constraints (see, e.g., [1] for a discussion of this class of nonmonotone operators).

Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.

Warning

Those constraints might not be sufficient, thus the characterized class might contain more operators.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["rho"]: comonotonicity parameter $\rho$ ($> 0$).

Necessary conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$:

\[\langle g_i - g_j, x_i - x_j \rangle \geqslant -\rho \|g_i - g_j\|^2.\]

Julia usage

problem = PEP()
param = OrderedDict("rho" => 0.1)
op = declare_function!(problem, NegativelyComonotoneOperator, param)

Note

With rho == 0 the class reduces to monotone operators; the constructor emits a warning suggesting MonotoneOperator in that case.

Fields

rho::Float64: comonotonicity parameter $\rho$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] E. Gorbunov, A. Taylor, S. Horváth, G. Gidel (2023). Convergence of proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity. International Conference on Machine Learning.

PEPit.CocoerciveOperator — Type

CocoerciveOperator(param; reuse_gradient=true)

Interpolation class of $\beta$-cocoercive (and maximally monotone) operators.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["beta"]: cocoercivity parameter $\beta$.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraint is added for every pair $i \neq j$ (see [1]):

\[\langle g_i - g_j, x_i - x_j \rangle \geqslant \beta \|g_i - g_j\|^2.\]

Julia usage

problem = PEP()
param = OrderedDict("beta" => 1.0)
op = declare_function!(problem, CocoerciveOperator, param)

Note

Cocoercive operators are necessarily continuous, hence reuse_gradient is set to true. With beta == 0 the class reduces to monotone operators; the constructor emits a warning suggesting MonotoneOperator in that case.

Fields

beta::Float64: cocoercivity parameter $\beta$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

PEPit.CocoerciveStronglyMonotoneOperatorCheap — Type

CocoerciveStronglyMonotoneOperatorCheap(param; reuse_gradient=true)

Class of $\beta$-cocoercive and $\mu$-strongly monotone (maximally monotone) operators, modeled through a cheap set of necessary constraints.

Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.

Warning

Those constraints might not be sufficient, thus the characterized class might contain more operators.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: strong monotonicity parameter $\mu$.
param["beta"]: cocoercivity parameter $\beta$.

Necessary conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraints are added for every pair $i \neq j$ (see [1]):

\[\begin{aligned} \langle g_i - g_j, x_i - x_j \rangle & \geqslant \beta \|g_i - g_j\|^2, \\ \langle g_i - g_j, x_i - x_j \rangle & \geqslant \mu \|x_i - x_j\|^2. \end{aligned}\]

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1, "beta" => 1.0)
op = declare_function!(problem, CocoerciveStronglyMonotoneOperatorCheap, param)

Note

With mu == 0 the class reduces to CocoerciveOperator, and with beta == 0 to StronglyMonotoneOperator; the constructor emits a warning in those cases.

Fields

mu::Float64: strong monotonicity parameter $\mu$.
beta::Float64: cocoercivity parameter $\beta$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

PEPit.CocoerciveStronglyMonotoneOperatorExpensive — Type

CocoerciveStronglyMonotoneOperatorExpensive(param; reuse_gradient=true)

Class of $\beta$-cocoercive and $\mu$-strongly monotone (maximally monotone) operators, modeled through the strengthened necessary constraints of [1, Appendix F], which are stronger than those used in [2] (and in CocoerciveStronglyMonotoneOperatorCheap) but significantly more expensive (two $7 \times 7$ PSD blocks per ordered triplet of oracle points).

Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.

Warning

Those constraints might not be sufficient, thus the characterized class might contain more operators.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: strong monotonicity parameter $\mu$.
param["beta"]: cocoercivity parameter $\beta$.

Necessary conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the implementation considers, for every ordered triplet of oracle points $(i, j, k)$ (not all equal), the pairwise strong-monotonicity residuals and cocoercivity residuals

\[A_{pq} = -\langle g_p - g_q, x_p - x_q \rangle + \mu \|x_p - x_q\|^2, \qquad B_{pq} = -\langle g_p - g_q, x_p - x_q \rangle + \beta \|g_p - g_q\|^2,\]

over the pairs $(p, q) \in \{(i,j), (i,k), (j,k)\}$. Two $7 \times 7$ matrices are built from these residuals together with nine free slack Expressions (the two matrices differ by swapping the roles of the two residual families), and both are constrained to be PSD through PSDMatrix objects, following [1, Appendix F]. See the implementation of add_class_constraints! in this file for the exact entries.

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1, "beta" => 1.0)
op = declare_function!(problem, CocoerciveStronglyMonotoneOperatorExpensive, param)

Note

With mu == 0 the class reduces to CocoerciveOperator, and with beta == 0 to StronglyMonotoneOperator; the constructor emits a warning in those cases.

Fields

mu::Float64: strong monotonicity parameter $\mu$.
beta::Float64: cocoercivity parameter $\beta$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] A. Rubbens, J.M. Hendrickx, A. Taylor (2025). A constructive approach to strengthen algebraic descriptions of function and operator classes.

[2] E. Ryu, A. Taylor, C. Bergeling, P. Giselsson (2020). Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3), 2251-2271.

PEPit.LipschitzStronglyMonotoneOperatorCheap — Type

LipschitzStronglyMonotoneOperatorCheap(param; reuse_gradient=true)

Class of $L$-Lipschitz continuous and $\mu$-strongly monotone (maximally monotone) operators, modeled through a cheap set of necessary constraints.

Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.

Warning

Lipschitz strongly monotone operators do not enjoy known interpolation conditions. The conditions implemented in this class are necessary but a priori not sufficient for interpolation. Hence, the numerical results obtained when using this class might be non-tight upper bounds (see Discussions in [1, Section 2]).

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: strong monotonicity parameter $\mu$.
param["L"]: Lipschitz continuity parameter $L$.

Necessary conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the following constraints are added for every pair $i \neq j$ (see [1]):

\[\begin{aligned} \langle g_i - g_j, x_i - x_j \rangle & \geqslant \mu \|x_i - x_j\|^2, \\ \|g_i - g_j\|^2 & \leqslant L^2 \|x_i - x_j\|^2. \end{aligned}\]

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
op = declare_function!(problem, LipschitzStronglyMonotoneOperatorCheap, param)

Note

With L == Inf the Lipschitz bound adds no constraint, so the class reduces to StronglyMonotoneOperator; the constructor emits a warning in that case.

Fields

mu::Float64: strong monotonicity parameter $\mu$.
L::Float64: Lipschitz continuity parameter $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

PEPit.LipschitzStronglyMonotoneOperatorExpensive — Type

LipschitzStronglyMonotoneOperatorExpensive(param; reuse_gradient=true)

Class of $L$-Lipschitz continuous and $\mu$-strongly monotone (maximally monotone) operators, modeled through the strengthened necessary constraints of [1, Proposition 3.15] (details in [1, Appendix E]), which are stronger than those used in [2] (and in LipschitzStronglyMonotoneOperatorCheap) but significantly more expensive (two $7 \times 7$ PSD blocks per ordered triplet of oracle points).

Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.

Warning

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: strong monotonicity parameter $\mu$.
param["L"]: Lipschitz continuity parameter $L$.

Necessary conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i$ denotes the operator value at $x_i$, the implementation considers, for every ordered triplet of oracle points $(i, j, k)$ (not all equal), the pairwise Lipschitz residuals and scaled strong-monotonicity residuals

\[A_{pq} = \|g_p - g_q\|^2 - L^2 \|x_p - x_q\|^2, \qquad B_{pq} = 2L \left( -\langle g_p - g_q, x_p - x_q \rangle + \mu \|x_p - x_q\|^2 \right),\]

over the pairs $(p, q) \in \{(i,j), (i,k), (j,k)\}$. Two $7 \times 7$ matrices are built from these residuals together with nine free slack Expressions (the two matrices differ by swapping the roles of the two residual families), and both are constrained to be PSD through PSDMatrix objects, following [1, Proposition 3.15]. See the implementation of add_class_constraints! in this file for the exact entries.

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
op = declare_function!(problem, LipschitzStronglyMonotoneOperatorExpensive, param)

Note

With L == Inf the Lipschitz bound adds no constraint, so the class reduces to StronglyMonotoneOperator; the constructor emits a warning in that case.

Fields

mu::Float64: strong monotonicity parameter $\mu$.
L::Float64: Lipschitz continuity parameter $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] A. Rubbens, J.M. Hendrickx, A. Taylor (2025). A constructive approach to strengthen algebraic descriptions of function and operator classes.

PEPit.SymmetricLinearOperator — Type

SymmetricLinearOperator(param; reuse_gradient=true)

Interpolation class of symmetric linear operators $M = M^\ast$ with eigenvalues in $[\mu, L]$.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["mu"]: lower bound $\mu$ on the eigenvalues.
param["L"]: upper bound $L$ on the eigenvalues.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i = M x_i$ denotes the operator value at $x_i$, the following symmetry constraints are added (see [1]):

\[\langle x_i, g_j \rangle = \langle x_j, g_i \rangle \qquad \text{for all } i < j,\]

together with the PSD constraint $T \succeq 0$, where

\[T_{ij} = L \langle g_i, x_j \rangle - \langle g_i, g_j \rangle - \mu L \langle x_i, x_j \rangle + \mu \langle x_i, g_j \rangle,\]

which is the Gram-space formulation of $(L I - M)(M - \mu I) \succeq 0$.

Julia usage

problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
M = declare_function!(problem, SymmetricLinearOperator, param)

Note

Symmetric linear operators are necessarily continuous, hence reuse_gradient is set to true.

Fields

mu::Float64: eigenvalue lower bound $\mu$.
L::Float64: eigenvalue upper bound $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] N. Bousselmi, J. Hendrickx, F. Glineur (2023). Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems. arXiv preprint.

PEPit.SkewSymmetricLinearOperator — Type

SkewSymmetricLinearOperator(param; reuse_gradient=true)

Interpolation class of skew-symmetric linear operators $M = -M^\ast$ with singular values bounded by $L$.

Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.

Note

Operator values are requested through gradient!; function values should not be used.

Class parameters

param["L"]: upper bound $L$ on the singular values of the operator.

Interpolation conditions

Associating with each oracle call $i$ the pair $(x_i, g_i)$, where $g_i = M x_i$ denotes the operator value at $x_i$, the following skew-symmetry constraints are added (see [1]):

\[\begin{aligned} \langle x_i, g_j \rangle & = -\langle x_j, g_i \rangle && \text{for all } i < j, \\ \langle x_i, g_i \rangle & = 0 && \text{for all } i, \end{aligned}\]

together with the PSD constraint $T \succeq 0$, where

\[T_{ij} = L^2 \langle x_i, x_j \rangle - \langle g_i, g_j \rangle.\]

Julia usage

problem = PEP()
param = OrderedDict("L" => 1.0)
M = declare_function!(problem, SkewSymmetricLinearOperator, param)

Note

Skew-symmetric linear operators are necessarily continuous, hence reuse_gradient is set to true.

Fields

L::Float64: singular value bound $L$.
_PEPit_func: internal PEPFunction storing oracle calls and constraints.

References

[1] N. Bousselmi, J. Hendrickx, F. Glineur (2023). Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems. arXiv preprint.