Main modules
PEP
- class PEPit.PEP[source]
Bases:
object
The class
PEP
is the main class of this framework. APEP
object encodes a complete performance estimation problem. It stores the following information.- Attributes
list_of_functions (list) – list of leaf
Function
objects that are defined through the pipeline.list_of_points (list) – list of
Point
objects that are defined out of the scope of aFunction
. Typically the initialPoint
.list_of_constraints (list) – list of
Constraint
objects that are defined out of the scope of aFunction
. Typically the initialConstraint
.list_of_performance_metrics (list) – list of
Expression
objects. The pep maximizes the minimum of all performance metrics.counter (int) – counts the number of
PEP
objects. Ideally, only one is defined at a time.
A
PEP
object can be instantiated without any argumentExample
>>> pep = PEP()
- add_constraint(constraint)[source]
Store a new
Constraint
to the list of constraints of thisPEP
.- Parameters
constraint (Constraint) – typically resulting from a comparison of 2
Expression
objects.- Raises
AssertionError – if provided constraint is not a
Constraint
object.
- add_psd_matrix(matrix)[source]
Store a new matrix of :class:`Expression`s that we enforce to be positive semidefinite.
- Parameters
matrix (Iterable of Iterable of Expression) – a square matrix of
Expression
.- Raises
AssertionError – if provided matrix is not a square matrix.
TypeError – if provided matrix does not contain only Expressions.
- declare_function(function_class, **kwargs)[source]
Instantiate a leaf
Function
and store it in the attribute list_of_functions.- Parameters
function_class (class) – a subclass of
Function
that overwrite the add_class_constraints method.kwargs (dict) – dictionary of parameters that characterize the function class. Can also contains the boolean reuse_gradient, that enforces using only one subgradient per point.
- Returns
f (Function) – the newly created function.
- static get_nb_eigenvalues_and_corrected_matrix(M)[source]
Compute the number of True non zero eigenvalues of M, and recompute M with corrected eigenvalues.
- Parameters
M (nd.array) – a 2 dimensional array, supposedly symmetric.
- Returns
nb_eigenvalues (int) – The number of eigenvalues of M estimated to be strictly positive zero.
eig_threshold (float) – The threshold used to determine whether an eigenvalue is 0 or not.
corrected_S (nd.array) – Updated M with zero eigenvalues instead of small ones.
- set_initial_condition(condition)[source]
Store a new
Constraint
to the list of constraints of thisPEP
. Typically an condition of the form \(\|x_0 - x_\star\|^2 \leq 1\).- Parameters
condition (Constraint) – typically resulting from a comparison of 2
Expression
objects.- Raises
AssertionError – if provided constraint is not a
Constraint
object.
- set_initial_point()[source]
Create a new leaf
Point
and store it in the attribute list_of_points.- Returns
x (Point) – the newly created
Point
.
- set_performance_metric(expression)[source]
Store a performance metric in the attribute list_of_performance_metrics. The objective of the PEP (which is maximized) is the minimum of the elements of list_of_performance_metrics.
- Parameters
expression (Expression) – a new performance metric.
- solve(verbose=1, return_full_cvxpy_problem=False, dimension_reduction_heuristic=None, eig_regularization=0.001, tol_dimension_reduction=1e-05, **kwargs)[source]
Transform the
PEP
under the SDP form, and solve it.- Parameters
verbose (int) – Level of information details to print (Override the CVXPY solver verbose parameter). 0: No verbose at all 1: PEPit information is printed but not CVXPY’s 2: Both PEPit and CVXPY details are printed
return_full_cvxpy_problem (bool) – If True, return the cvxpy Problem object. If False, return the worst case value only. Set to False by default.
dimension_reduction_heuristic (str, optional) –
An heuristic to reduce the dimension of the solution (rank of the Gram matrix). Available heuristics are:
”trace”: minimize \(Tr(G)\)
”logdet{an integer n}”: minimize \(\log\left(\mathrm{Det}(G)\right)\) using n iterations of local approximation problems.
Set to None to deactivate it (default value).
eig_regularization (float, optional) – The regularization we use to make \(G + \mathrm{eig_regularization}I_d \succ 0\). (only used when “dimension_reduction_heuristic” is not None) The default value is 1e-5.
tol_dimension_reduction (float, optional) – The error tolerance in the heuristic minimization problem. Precisely, the second problem minimizes “optimal_value - tol” (only used when “dimension_reduction_heuristic” is not None) The default value is 1e-5.
kwargs (keywords, optional) – Additional CVXPY solver specific arguments.
- Returns
float or cp.Problem – Value of the performance metric of cp.Problem object corresponding to the SDP. The value only is returned by default.
Point
- class PEPit.Point(is_leaf=True, decomposition_dict=None)[source]
Bases:
object
A
Point
encodes an element of a pre-Hilbert space, either a point or a gradient.- Attributes
_is_leaf (bool) – True if self is defined from scratch (not as linear combination of other
Point
objects). False if self is defined as linear combination of other points._value (nd.array) – numerical value of self obtained after solving the PEP via SDP solver. Set to None before the call to the method PEP.solve from the
PEP
.decomposition_dict (dict) – decomposition of self as a linear combination of leaf
Point
objects. Keys arePoint
objects. And values are their associated coefficients.counter (int) – counts the number of leaf
Point
objects.
Point
objects can be added or subtracted together. They can also be multiplied and divided by a scalar value.Example
>>> point1 = Point() >>> point2 = Point() >>> new_point = (- point1 + point2) / 5
As in any pre-Hilbert space, there exists a scalar product. Therefore,
Point
objects can be multiplied together.Example
>>> point1 = Point() >>> point2 = Point() >>> new_expr = point1 * point2
The output is a scalar of type
Expression
.The corresponding squared norm can also be computed.
Example
>>> point = Point() >>> new_expr = point ** 2
Point
objects can also be instantiated via the following arguments- Parameters
is_leaf (bool) – True if self is a
Point
defined from scratch (not as linear combination of otherPoint
objects). False if self is a linear combination of existingPoint
objects.decomposition_dict (dict) – decomposition of self as a linear combination of leaf
Point
objects. Keys arePoint
objects. And values are their associated coefficients.
Note
If is_leaf is True, then decomposition_dict must be provided as None. Then self.decomposition_dict will be set to {self: 1}.
Instantiating the
Point
object of the first example can be done byExample
>>> point1 = Point() >>> point2 = Point() >>> new_point = Point(is_leaf=False, decomposition_dict = {point1: -1/5, point2: 1/5})
Expression
- class PEPit.Expression(is_leaf=True, decomposition_dict=None)[source]
Bases:
object
An
Expression
is a linear combination of functions values, inner products of points and / or gradients (product of 2Point
objects), and constant scalar values.- Attributes
_is_leaf (bool) – True if self is a function value defined from scratch (not as linear combination of other function values). False if self is a linear combination of existing
Expression
objects._value (float) – numerical value of self obtained after solving the PEP via SDP solver. Set to None before the call to the method PEP.solve from the
PEP
.decomposition_dict (dict) – decomposition of self as a linear combination of leaf
Expression
objects. Keys areExpression
objects or tuple of 2Point
objects. And values are their associated coefficients.counter (int) – counts the number of leaf
Expression
objects.
Expression
objects can be added or subtracted together. They can also be added, subtracted, multiplied and divided by a scalar value.Example
>>> expr1 = Expression() >>> expr2 = Expression() >>> new_expr = (- expr1 + expr2 - 1) / 5
Expression
objects can also be compared togetherExample
>>> expr1 = Expression() >>> expr2 = Expression() >>> inequality1 = expr1 <= expr2 >>> inequality2 = expr1 >= expr2 >>> equality = expr1 == expr2
The three outputs inequality1, inequality2 and equality are then
Constraint
objects.Expression
objects can also be instantiated via the following arguments- Parameters
is_leaf (bool) – True if self is a function value defined from scratch (not as linear combination of other function values). False if self is a linear combination of existing
Expression
objects.decomposition_dict (dict) – decomposition of self as a linear combination of leaf
Expression
objects. Keys areExpression
objects or tuple of 2Point
objects. And values are their associated coefficients.
Note
If is_leaf is True, then decomposition_dict must be provided as None. Then self.decomposition_dict will be set to {self: 1}.
Instantiating the
Expression
object of the first example can be done byExample
>>> expr1 = Expression() >>> expr2 = Expression() >>> new_expr = Expression(is_leaf=False, decomposition_dict = {expr1: -1/5, expr2: 1/5, 1: -1/5})
- eval()[source]
Compute, store and return the value of this
Expression
.- Returns
self._value (np.array) – Value of this
Expression
after the corresponding PEP was solved numerically.- Raises
ValueError("The PEP must be solved to evaluate Expressions!") if the PEP has not been solved yet. –
TypeError("Expressions are made of function values, inner products and constants only!") –
Constraint
- class PEPit.Constraint(expression, equality_or_inequality)[source]
Bases:
object
A
Constraint
encodes either an equality or an inequality between twoExpression
objects.A
Constraint
must be understood either as self.expression = 0 or self.expression \(\leqslant\) 0 depending on the value of self.equality_or_inequality.- Attributes
expression (Expression) – The
Expression
that is compared to 0.equality_or_inequality (str) – “equality” or “inequality”. Encodes the type of constraint.
_value (float) – numerical value of self.expression obtained after solving the PEP via SDP solver. Set to None before the call to the method PEP.solve from the
PEP
._dual_variable_value (float) – the associated dual variable from the numerical solution to the corresponding PEP. Set to None before the call to PEP.solve from the
PEP
counter (int) – counts the number of
Constraint
objects.
A
Constraint
results from a comparison between twoExpression
objects.Example
>>> from PEPit import Expression >>> expr1 = Expression() >>> expr2 = Expression() >>> inequality1 = expr1 <= expr2 >>> inequality2 = expr1 >= expr2 >>> equality = expr1 == expr2
Constraint
objects can also be instantiated via the following arguments.- Parameters
expression (Expression) – an object of class Expression
equality_or_inequality (str) – either ‘equality’ or ‘inequality’.
Instantiating the
Constraint
objects of the first example can be done byExample
>>> from PEPit import Expression >>> expr1 = Expression() >>> expr2 = Expression() >>> inequality1 = Constraint(expression=expr1-expr2, equality_or_inequality="inequality") >>> inequality2 = Constraint(expression=expr2-expr1, equality_or_inequality="inequality") >>> equality = Constraint(expression=expr1-expr2, equality_or_inequality="equality")
- Raises
AssertionError – if provided equality_or_inequality argument is neither “equality” nor “inequality”.
- eval()[source]
Compute, store and return the value of the underlying
Expression
of thisConstraint
.- Returns
self._value (np.array) – The value of the underlying
Expression
of thisConstraint
after the corresponding PEP was solved numerically.- Raises
ValueError("The PEP must be solved to evaluate Constraints!") if the PEP has not been solved yet. –
- eval_dual()[source]
Compute, store and return the value of the dual variable of this
Constraint
.- Returns
self._dual_variable_value (float) – The value of the dual variable of this
Constraint
after the corresponding PEP was solved numerically.- Raises
ValueError("The PEP must be solved to evaluate Constraints dual variables!") if the PEP has not been solved yet. –
Function
- class PEPit.Function(is_leaf=True, decomposition_dict=None, reuse_gradient=False)[source]
Bases:
object
A
Function
object encodes a function or an operator.Warning
This class must be overwritten by a child class that encodes some conditions on the
Function
. In particular, the method add_class_constraints must be overwritten. See thePEPit.functions
andPEPit.operators
modules.Some
Function
objects are defined from scratch as leafFunction
objects, and some are linear combinations of pre-existing ones.- Attributes
_is_leaf (bool) – True if self is defined from scratch. False if self is defined as linear combination of leaves.
decomposition_dict (dict) – decomposition of self as linear combination of leaf
Function
objects. Keys areFunction
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.list_of_points (list) – A list of triplets storing the points where this
Function
has been evaluated, as well as the associated subgradients and function values.list_of_stationary_points (list) – The sublist of self.list_of_points of stationary points (characterized by some subgradient=0).
list_of_constraints (list) – The list of
Constraint
objects associated with thisFunction
.counter (int) – counts the number of leaf
Function
objects.
Note
PEPit was initially tough for evaluating performances of optimization algorithms. Operators are represented in the same way as functions, but function values must not be used (they don’t have any sense in this framework). Use gradient to access an operator value.
Function
objects can be added or subtracted together. They can also be multiplied and divided by a scalar value.Example
>>> func1 = Function() >>> func2 = Function() >>> new_func = (- func1 + func2) / 5
Function
objects can also be instantiated via the following arguments.- Parameters
is_leaf (bool) – True if self is defined from scratch. False if self is defined as a linear combination of leaves.
decomposition_dict (dict) – Decomposition of self as linear combination of leaf
Function
objects. Keys areFunction
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.
Note
If is_leaf is True, then decomposition_dict must be provided as None. Then self.decomposition_dict will be set to {self: 1}.
Note
reuse_gradient is typically set to True when this
Function
is differentiable, that is there exists only one subgradient perPoint
.Instantiating the
Function
object of the first example can be done byExample
>>> func1 = Function() >>> func2 = Function() >>> new_func = Function(is_leaf=False, decomposition_dict = {func1: -1/5, func2: 1/5})
- add_class_constraints()[source]
Warning
Needs to be overwritten with interpolation conditions (or necessary conditions for interpolation for obtaining possibly non-tight upper bounds on the worst-case performance).
This method is run by the
PEP
just before solving the problem. It evaluates interpolation conditions for the 2 lists of points that is stored in thisFunction
.- Raises
NotImplementedError – This method must be overwritten in children classes
- add_constraint(constraint)[source]
Store a new
Constraint
to the list of constraints of thisFunction
.- Parameters
constraint (Constraint) – typically resulting from a comparison of 2
Expression
objects.- Raises
AssertionError – if provided constraint is not a
Constraint
object.
- add_point(triplet)[source]
Add a triplet (point, gradient, function_value) to the list of points of this function.
- Parameters
triplet (tuple) – A tuple containing 3 elements: point (
Point
), gradient (Point
), and function value (Expression
).
- fixed_point()[source]
This routine outputs a fixed point of this function, that is \(x\) such that \(x\in\partial f(x)\). If self is an operator \(A\), the fixed point is such that \(Ax = x\).
- Returns
x (Point) – a fixed point of the differential of self.
x (Point) – nabla f(x) = x.
fx (Expression) – a function value (useful only if self is a function).
- get_is_leaf()[source]
- Returns
self._is_leaf (bool) – allows to access the protected attribute _is_leaf.
- gradient(point)[source]
Return the gradient (or a subgradient) of this
Function
evaluated at point.- Parameters
point (Point) – any point.
- Returns
Point – a gradient (
Point
) of thisFunction
on point (Point
).
Note
the method subgradient does the exact same thing.
- oracle(point)[source]
Return a gradient (or a subgradient) and the function value of self evaluated at point.
- Parameters
point (Point) – any point.
- Returns
tuple – a (sub)gradient (
Point
) and a function value (Expression
).
- stationary_point(return_gradient_and_function_value=False)[source]
Create a new stationary point, as well as its zero gradient and its function value.
- Parameters
return_gradient_and_function_value (bool) – if True, return the triplet point (
Point
), gradient (Point
), function value (Expression
). Otherwise, return only the point (Point
).- Returns
Point or tuple – an optimal point