Main modules

PEP
Point
Expression
Constraint
Symmetric positive semidefinite matrix
Function

PEP 

class PEPit.PEP[source]

Bases: object

The class PEP is the main class of this framework. A PEP 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 a Function. Typically the initial Point.
list_of_constraints (list) – list of Constraint objects that are defined out of the scope of a Function. Typically the initial Constraint.
list_of_performance_metrics (list) – list of Expression objects. The pep maximizes the minimum of all performance metrics.
list_of_psd (list) – list of PSDMatrix objects. The PEP consider the associated LMI constraints psd_matrix >> 0.
_list_of_constraints_sent_to_cvxpy (list) – a list of all the Constraint objects that are sent to CVXPY for solving the SDP. It should not be updated manually. Only the solve method takes care of it.
_list_of_cvxpy_constraints (list) – a list of all the CVXPY Constraints objects that have been sent by PEPit for solving the SDP. It should not be updated manually. Only the solve method takes care of it.
counter (int) – counts the number of PEP objects. Ideally, only one is defined at a time.

A PEP object can be instantiated without any argument

Example

>>> pep = PEP()

add_constraint(constraint)[source]

Store a new Constraint to the list of constraints of this PEP.

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_of_expressions)[source]

Store a new matrix of Expressions that we enforce to be positive semidefinite.

Parameters

matrix_of_expressions (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.

send_constraint_to_cvxpy(constraint, F, G)[source]

Transform a PEPit Constraint into a CVXPY one and add the 2 formats of the constraints into the tracking lists.

Parameters

constraint (Constraint) – a Constraint object to be sent to CVXPY.
F (CVXPY Variable) – a CVXPY Variable referring to function values.
G (CVXPY Variable) – a CVXPY Variable referring to points and gradients.

:raises ValueError if the attribute equality_or_inequality of the Constraint: :raises is neither equality, nor inequality.:

send_lmi_constraint_to_cvxpy(psd_counter, psd_matrix, F, G, verbose)[source]

Transform a PEPit PSDMatrix into a CVXPY symmetric PSD matrix and add the 2 formats of the constraints into the tracking lists.

Parameters

psd_counter (int) – a counter useful for the verbose mode.
psd_matrix (PSDMatrix) – a matrix of expressions that is constrained to be PSD.
F (CVXPY Variable) – a CVXPY Variable referring to function values.
G (CVXPY Variable) – a CVXPY Variable referring to points and gradients.
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

set_initial_condition(condition)[source]

Store a new Constraint to the list of constraints of this PEP. 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). Set to None to deactivate it (default value). 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.
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 are Point 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 other Point objects). False if self is a linear combination of existing Point objects.
decomposition_dict (dict) – decomposition of self as a linear combination of leaf Point objects. Keys are Point 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 by

Example

>>> point1 = Point()
>>> point2 = Point()
>>> new_point = Point(is_leaf=False, decomposition_dict = {point1: -1/5, point2: 1/5})

eval()[source]

Compute, store and return the value of this Point.

Returns: self._value (np.array) – The value of this Point after the corresponding PEP was solved numerically.
Raises: ValueError("The PEP must be solved to evaluate Points!") if the PEP has not been solved yet. –

get_is_leaf()[source]

Returns: self._is_leaf (bool) – allows to access the protected attribute _is_leaf.

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 2 Point 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 are Expression objects or tuple of 2 Point 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 together

Example

>>> 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 are Expression objects or tuple of 2 Point 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 by

Example

>>> 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!") –

get_is_leaf()[source]

Returns: self._is_leaf (bool) – allows to access the protected attribute _is_leaf.

Constraint 

class PEPit.Constraint(expression, equality_or_inequality)[source]

Bases: object

A Constraint encodes either an equality or an inequality between two Expression 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 two Expression 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 by

Example

>>> 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 this Constraint.

Returns: self._value (np.array) – The value of the underlying Expression of this Constraint 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. –

Symmetric positive semidefinite matrix 

class PEPit.PSDMatrix(matrix_of_expressions)[source]

Bases: object

A PSDMatrix encodes a square matrix of Expression objects that is constrained to be symmetric PSD.

Attributes

matrix_of_expressions (Iterable of Iterable of Expression) – a square matrix of Expression objects.
shape (tuple of ints) – the shape of the underlying matrix of Expression objects.
_value (2D ndarray of floats) – numerical values of Expression objects 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 (2D ndarray of floats) – the associated dual matrix from the numerical solution to the corresponding PEP. Set to None before the call to PEP.solve from the PEP.
entries_dual_variable_value (2D ndarray of floats) – the dual of each correspondence between entries of the matrix and the underlying Expression objects.
counter (int) – counts the number of PSDMatrix objects.

Example

>>> # Defining t <= sqrt(expr) for a given expression expr.
>>> from PEPit import Expression
>>> from PEPit import PSDMatrix
>>> expr = Expression()
>>> t = Expression()
>>> psd_matrix = PSDMatrix(matrix_of_expressions=[[expr, t], [t, 1]])
>>> # The last line means that the matrix [[expr, t], [t, 1]] is constrained to be PSD.
>>> # This is equivalent to det([[expr, t], [t, 1]]) >= 0, i.e. expr - t^2 >= 0.

PSDMatrix objects are instantiated via the following argument.

Parameters: matrix_of_expressions (Iterable of Iterable of Expression) – a square matrix of Expression.

Instantiating the PSDMatrix objects of the first example can be done by

Example

>>> import numpy as np
>>> from PEPit import Expression
>>> from PEPit import PSDMatrix
>>> matrix_of_expressions = np.array([Expression() for i in range(4)]).reshape(2, 2)
>>> psd_matrix = PSDMatrix(matrix_of_expressions=matrix_of_expressions)

Raises

AssertionError – if provided matrix is not a square matrix.
TypeError – if provided matrix does not contain only Expressions and / or scalar values.

eval()[source]

Compute, store and return the value of the underlying matrix of Expression objects.

Returns: self._value (np.array) – The value of the underlying matrix of Expression objects after the corresponding PEP was solved numerically.
Raises: ValueError("The PEP must be solved to evaluate PSDMatrix!") if the PEP has not been solved yet. –

eval_dual()[source]

Compute, store and return the value of the dual variable of this PSDMatrix.

Returns: self._dual_variable_value (ndarray of floats) – The value of the dual variable of this PSDMatrix after the corresponding PEP was solved numerically.
Raises: ValueError("The PEP must be solved to evaluate PSDMatrix 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 the PEPit.functions and PEPit.operators modules.

Some Function objects are defined from scratch as leaf Function 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 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.
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 this Function.
list_of_psd (list) – The list of PSDMatrix objects associated with this Function.
list_of_class_constraints (list) – The list of class interpolation Constraint objects.
list_of_class_psd (list) – The list of PSDMatrix objects associated associated with class interpolation constraints.
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 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.

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 per Point.

Instantiating the Function object of the first example can be done by

Example

>>> 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 this Function.

Raises: NotImplementedError – This method must be overwritten in children classes

add_constraint(constraint)[source]

Store a new Constraint to the list of constraints of this Function.

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

add_psd_matrix(matrix_of_expressions)[source]

Store a new matrix of Expressions that we enforce to be positive semidefinite.

Parameters

matrix_of_expressions (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.

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 this Function 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

subgradient(point)[source]

Return a subgradient of this Function evaluated at point.

Parameters: point (Point) – any point.
Returns: Point – a subgradient (Point) of this Function on point (Point).

Note

the method gradient does the exact same thing.

value(point)[source]

Return the function value of this Function on point.

Parameters: point (Point) – any point.
Returns: Point – the function value (Expression) of this Function on point (Point).

Main modules

PEP

Point

Expression

Constraint

Symmetric positive semidefinite matrix

Function

PEP 

Point 

Expression 

Constraint 

Symmetric positive semidefinite matrix 

Function 