Main modules

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

  • 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()
declare_function(function_class, param, reuse_gradient=None)[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.

  • param (dict) – dictionary of parameters that characterize the function class.

  • reuse_gradient (bool) – whether the function only admit one gradient on a given Point. Typically True when the function is assumed differentiable.

Returns

f (Function) – the newly created function.

set_initial_condition(condition)[source]

Store a Constraint in the attribute list_of_conditions. Typically an initial condition.

Parameters

condition (Constraint) – the given constraint.

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(solver=None, verbose=1, tracetrick=False, return_full_cvxpy_problem=False)[source]

Transform the PEP under the SDP form, and solve it.

Parameters

  • solver (str or None) – The name of the underlying solver.

  • verbose (int) – Level of information details to print (0 or 1)

  • tracetrick (bool) – Apply trace heuristic as a proxy for minimizing the dimension of the solution (rank of the Gram matrix).

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

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

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

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

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