Operators

Monotone 

class PEPit.operators.MonotoneOperator(is_leaf=True, decomposition_dict=None, reuse_gradient=False, name=None)[source]

Bases: Function

The MonotoneOperator class overwrites the add_class_constraints method of Function, implementing interpolation constraints for the class of maximally monotone operators.

Note

Operator values can be requested through gradient and function values should not be used.

General maximally monotone operators are not characterized by any parameter, hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import MonotoneOperator
>>> problem = PEP()
>>> h = problem.declare_function(function_class=MonotoneOperator)

References

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

Parameters:

is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

add_class_constraints()[source]: Formulates the list of interpolation constraints for self (maximally monotone operator), see, e.g., [1, Theorem 20.21].

static set_monotonicity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set monotonicity constraint for operators.

Strongly monotone 

class PEPit.operators.StronglyMonotoneOperator(mu, is_leaf=True, decomposition_dict=None, reuse_gradient=False, name=None)[source]

Bases: Function

The StronglyMonotoneOperator class overwrites the add_class_constraints method of Function, implementing interpolation constraints of the class of strongly monotone (maximally monotone) operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: mu (float) – strong monotonicity parameter

Strongly monotone (and maximally monotone) operators are characterized by the parameter \(\mu\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import StronglyMonotoneOperator
>>> problem = PEP()
>>> h = problem.declare_function(function_class=StronglyMonotoneOperator, mu=.1)

References

Discussions and appropriate pointers for the problem of interpolation of maximally monotone operators 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.

Parameters:

mu (float) – Strong monotonicity parameter.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

add_class_constraints()[source]: Formulates the list of necessary conditions for interpolation of self (Lipschitz strongly monotone and maximally monotone operator), see, e.g., discussions in [1, Section 2].

set_strong_monotonicity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set strong monotonicity constraint for operators.

Lipschitz continuous 

class PEPit.operators.LipschitzOperator(L, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The LipschitzOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints of the class of Lipschitz continuous operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: L (float) – Lipschitz parameter

Cocoercive operators are characterized by the parameter \(L\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import LipschitzOperator
>>> problem = PEP()
>>> func = problem.declare_function(function_class=LipschitzOperator, L=1.)

Notes

By setting L=1, we define a non-expansive operator.

By setting L<1, we define a contracting operator.

References

[1] M. Kirszbraun (1934). Uber die zusammenziehende und Lipschitzsche transformationen. Fundamenta Mathematicae, 22 (1934).

[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.

Parameters:

L (float) – Lipschitz continuity parameter.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Lipschitz continuous operators are necessarily continuous, hence reuse_gradient is set to True.

add_class_constraints()[source]: Formulates the list of interpolation constraints for self (Lipschitz operator), see [1, 2, 3] or e.g., [4, Fact 2].

set_lipschitz_continuity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set Lipschitz continuity constraint for operators.

Nonexpansive 

class PEPit.operators.NonexpansiveOperator(is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The NonexpansiveOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints of the class of (possibly inconsistent) nonexpansive operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: v (Point) – infimal displacement vector.

Nonexpansive operators are not characterized by any parameter, hence can be initiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import NonexpansiveOperator
>>> problem = PEP()
>>> func = problem.declare_function(function_class=NonexpansiveOperator)

Notes

Any nonexpansive operator has a unique vector called 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, a nonexpansive operator is inconsistent, i.e., does not have a fixed point.

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.

Parameters:

is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Nonexpansive continuous operators are necessarily continuous, hence reuse_gradient is set to True.

Setting self.v = None corresponds to case when a nonexpansive operator is consistent.

add_class_constraints()[source]: Formulates the list of interpolation constraints for self (Nonexpansive operator), see [2, Theorem 10].

set_infimal_displacement_vector_constraint_i(xi, gi, fi)[source]: Set infimal displacement vector constraint of nonexpansive operators.

static set_nonexpansiveness_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set Lipschitz continuity constraint for operators.

Strongly monotone and Lipschitz continuous 

class PEPit.operators.LipschitzStronglyMonotoneOperator(mu, L, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The LipschitzStronglyMonotoneOperator class overwrites the add_class_constraints method of Function, implementing some constraints (which are not necessary and sufficient for interpolation) for the class of Lipschitz continuous strongly monotone (and maximally monotone) operators.

Note

Operator values can be requested through gradient and function values should not be used.

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]).

Attributes:

mu (float) – strong monotonicity parameter
L (float) – Lipschitz parameter

Lipschitz continuous strongly monotone operators are characterized by parameters \(\mu\) and L, hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import LipschitzStronglyMonotoneOperator
>>> problem = PEP()
>>> h = problem.declare_function(function_class=LipschitzStronglyMonotoneOperator, mu=.1, L=1.)

References

[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.

Parameters:

mu (float) – The strong monotonicity parameter.
L (float) – The Lipschitz continuity parameter.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Lipschitz continuous strongly monotone operators are necessarily continuous, hence reuse_gradient is set to True.

add_class_constraints()[source]: Formulates the list of necessary conditions for interpolation of self (Lipschitz strongly monotone and maximally monotone operator), see, e.g., discussions in [1, Section 2].

set_lipschitz_continuity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set Lipschitz continuity constraint for operators.

set_strong_monotonicity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set strong monotonicity constraint for operators.

Cocoercive 

class PEPit.operators.CocoerciveOperator(beta, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The CocoerciveOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints of the class of cocoercive (and maximally monotone) operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: beta (float) – cocoercivity parameter

Cocoercive operators are characterized by the parameter \(\beta\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import CocoerciveOperator
>>> problem = PEP()
>>> func = problem.declare_function(function_class=CocoerciveOperator, beta=1.)

References:

[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.

Parameters:

beta (float) – The cocoercivity parameter.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Cocoercive operators are necessarily continuous, hence reuse_gradient is set to True.

add_class_constraints()[source]: Formulates the list of interpolation constraints for self (cocoercive maximally monotone operator), see, e.g., [1, Proposition 2].

set_cocoercivity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Set cocoercivity constraint for operator.

Cocoercive and strongly monotone 

class PEPit.operators.CocoerciveStronglyMonotoneOperator(mu, beta, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The CocoerciveStronglyMonotoneOperator class overwrites the add_class_constraints method of Function, implementing some necessary constraints verified by the class of cocoercive and strongly monotone (maximally) operators.

Warning

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

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:

mu (float) – strong monotonicity parameter
beta (float) – cocoercivity parameter

Cocoercive operators are characterized by the parameters \(\mu\) and \(\beta\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import CocoerciveStronglyMonotoneOperator
>>> problem = PEP()
>>> func = problem.declare_function(function_class=CocoerciveStronglyMonotoneOperator, mu=.1, beta=1.)

References:

[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.

Parameters:

mu (float) – The strong monotonicity parameter.
beta (float) – The cocoercivity parameter.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Cocoercive operators are necessarily continuous, hence reuse_gradient is set to True.

add_class_constraints()[source]: Add interpolation constraints for self (cocoercive strongly monotone operator).

set_cocoercivity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Formulates the list of interpolation constraints for self (cocoercive strongly monotone operators).

set_strong_monotonicity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Formulates the list of interpolation constraints for self (cocoercive strongly monotone operators).

Negatively comonotone 

class PEPit.operators.NegativelyComonotoneOperator(rho, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The NegativelyComonotoneOperator class overwrites the add_class_constraints method of Function, implementing some necessary constraints of the class of negatively comonotone operators.

Warning

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

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: rho (float) – comonotonicity parameter (>0)

Negatively comonotone operators are characterized by the parameter \(\rho\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import NegativelyComonotoneOperator
>>> problem = PEP()
>>> func = problem.declare_function(function_class=NegativelyComonotoneOperator, rho=1.)

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.

Parameters:

rho (float) – The comonotonicity parameter (>0).
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

add_class_constraints()[source]: Add negative comonotonicity constraints.

set_negative_comonotonicity_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Formulates the list of interpolation constraints for self (negatively comonotone operator).

Linear Operator 

class PEPit.operators.LinearOperator(L, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The LinearOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints of the class of linear operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:

L (float) – singular values upper bound
T (Function) – the adjunct linear operator

Linear operators are characterized by the parameter \(L\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import LinearOperator
>>> problem = PEP()
>>> M = problem.declare_function(function_class=LinearOperator, L=1.)

References:

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

Parameters:

L (float) – The singular values upper bound.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

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

add_class_constraints()[source]: Formulates the list of necessary and sufficient conditions for interpolation of self (Linear operator), see [1, Theorem 3.1].

Skew Symmetric Linear Operator 

class PEPit.operators.SkewSymmetricLinearOperator(L, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The SkewSymmetricLinearOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints for the class of skew-symmetric linear operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:: L (float) – singular values upper bound

Skew-Symmetric Linear operators are characterized by parameters \(L\), hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import SkewSymmetricLinearOperator
>>> problem = PEP()
>>> M = problem.declare_function(function_class=SkewSymmetricLinearOperator, L=1.)

References:

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

Parameters:

L (float) – The singular values upper bound.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

Skew-Symmetric Linear operators are necessarily continuous, hence reuse_gradient is set to True.

add_class_constraints()[source]: Formulates the list of necessary and sufficient conditions for interpolation of self (Skew-Symmetric Linear operator), see [1, Corollary 3.2].

static set_antisymmetric_linear_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Formulates the list of interpolation constraints for self (Skew-symmetric linear operator).

Symmetric Linear Operator 

class PEPit.operators.SymmetricLinearOperator(mu, L, is_leaf=True, decomposition_dict=None, reuse_gradient=True, name=None)[source]

Bases: Function

The SymmetricLinearOperator class overwrites the add_class_constraints method of Function, implementing the interpolation constraints for the class of symmetric linear operators.

Note

Operator values can be requested through gradient and function values should not be used.

Attributes:

mu (float) – eigenvalues lower bound
L (float) – eigenvalues upper bound

Symmetric Linear operators are characterized by parameters \(\mu\) and L, hence can be instantiated as

Example

>>> from PEPit import PEP
>>> from PEPit.operators import SymmetricLinearOperator
>>> problem = PEP()
>>> M = problem.declare_function(function_class=SymmetricLinearOperator, mu=.1, L=1.)

References:

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

Parameters:

mu (float) – The eigenvalues lower bound.
L (float) – The eigenvalues upper bound.
is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaf .
decomposition_dict (dict) – Decomposition of self as linear combination of leaf Function objects. Keys are Function objects and values are their associated coefficients.
reuse_gradient (bool) – If True, the same subgradient is returned when one requires it several times on the same Point. If False, a new subgradient is computed each time one is required.
name (str) – name of the object. None by default. Can be updated later through the method set_name.

Note

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

add_class_constraints()[source]: Formulates the list of necessary and sufficient conditions for interpolation of self (Symmetric Linear operator), see [1, Theorem 3.3].

static set_symmetric_linear_constraint_i_j(xi, gi, fi, xj, gj, fj)[source]: Formulates the list of interpolation constraints for self (Symmetric linear operator).