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:

  • counter (int) – counts the number of PEP objects. Ideally, only one is defined at a time.

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

  • wrapper_name (str) – name of the used wrapper.

  • wrapper (Wrapper) – Wrapper object that interfaces between the PEP and the solver.

  • _list_of_prepared_constraints (list) – list of Constraint objects ready to be sent to the wrapper.

  • _list_of_prepared_psd (list) – list of PSDMatrix objects ready to be sent to the wrapper.

  • _list_of_constraints_sent_to_wrapper (list) – list of Constraint objects actually sent to the wrapper.

  • _list_of_psd_sent_to_wrapper (list) – list of PSDMatrix objects actually sent to the wrapper.

  • objective (Expression) – the expression to be maximized by the solver. It is set by the method solve. And should not be updated otherwise.

  • G_value (ndarray) – the value of the Gram matrix G that the solver found.

  • F_value (ndarray) – the value of the vector of Expression F that the solver found.

  • residual (ndarray) – the dual value found by the solver to the lmi constraints G >> 0.

A PEP object can be instantiated without any argument

Example

>>> pep = PEP()
add_constraint(constraint, name=None)[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.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Raises:

AssertionError – if provided constraint is not a Constraint object.

add_psd_matrix(matrix_of_expressions, name=None)[source]

Store a new matrix of Expressions that we enforce to be positive semi-definite.

Parameters:

  • matrix_of_expressions (Iterable of Iterable of Expression) – a square matrix of Expression.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Returns:

(PSDMatrix) the :class:`PSDMatrix` to be added to the :class:`PEP`.

Raises:

  • AssertionError – if provided matrix is not a square matrix.

  • TypeError – if provided matrix does not contain only Expressions.

check_feasibility(wc_value, verbose=1)[source]

Check primal feasibility and display precision. Check dual feasibility and display precision. Compute and display primal-dual gap.

Parameters:

  • wc_value (float) – the primal value of the PEP objective returned by the solver.

  • verbose (int, optional) – If larger or equal than 1, print intermediate information.

Returns:

(float) – the dual value of the PEP objective.

Notes

The dual feasibility consists in

  • verifying that the dual values associated to inequality constraints are nonnegative,

  • and verifying that the residual corresponds to the right linear combination of the constraints.

The second point essentially means that verifying the dual feasibility consists in reconstructing the proof.

static declare_block_partition(d)[source]

Instantiate a BlockPartition and store it in the attribute list_of_partitions.

Parameters:

d (int) – number of blocks in the BlockPartition.

Returns:

block_partition (BlockPartition) – the newly created partition.

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 contain 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, name=None)[source]

Store a new Constraint to the list of constraints of this PEP. Typically, a condition of the form \(\|x_0 - x_\star\|^2 \leq 1\).

Parameters:

  • condition (Constraint) – typically resulting from a comparison of 2 Expression objects.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Raises:

AssertionError – if provided constraint is not a Constraint object.

set_initial_point(name=None)[source]

Create a new leaf Point and store it in the attribute list_of_points.

Parameters:

name (str, optional) – name of the object. Not overwriting is None. None by default.

Returns:

x (Point) – the newly created Point.

set_performance_metric(expression, name=None)[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.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

solve(wrapper='cvxpy', return_primal_or_dual='dual', safe_mode=True, verbose=1, dimension_reduction_heuristic=None, eig_regularization=0.001, tol_dimension_reduction=0.0001, **kwargs)[source]

Transform the PEP under the SDP form, and solve it. Parse the options for solving the SDPs, instantiate the concerning wrappers and call the main internal solve option for solving the PEP.

Parameters:

  • wrapper (str, optional) – Reference to a solver, interfaced by a PEPit.Wrapper. Default is “cvxpy”, other native option include “mosek”.

  • return_primal_or_dual (str, optional) – If “dual”, it returns a worst-case upper bound of the PEP (dual value of the objective). If “primal”, it returns a worst-case lower bound of the PEP (primal value of the objective). Default is “dual”. Note both value should be almost the same by strong duality.

  • safe_mode (bool, optional) – Enable safe mode that includes basic checks such as appropriate packages being installed or not, or licenses. Deactivating might lead to codes that are harder to debug.

  • verbose (int, optional) –

    Level of information details to print (Override the solver verbose parameter).

    • 0: No verbose at all

    • 1: PEPit information is printed but not solver’s

    • 2: Both PEPit and solver details are printed

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

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

  • kwargs (keywords, optional) – Additional solver-specific arguments.

Returns:

float – Worst case guarantee of the PEP.

Point

class PEPit.Point(is_leaf=True, decomposition_dict=None, name=None)[source]

Bases: object

A Point encodes an element of a pre-Hilbert space, either a point or a gradient.

Attributes:

  • name (str) – A name set through the set_name method. None is no name is given.

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

  • name (str) – name of the object. None by default. Can be updated later through the method set_name.

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.

get_name()[source]

Returns (str): the attribute name.

set_name(name)[source]

Assign a name to self for easier identification purpose.

Parameters:

name (str) – a name to be given to self.

Block partition

class PEPit.BlockPartition(d)[source]

Bases: object

A BlockPartition encodes an abstract block partitioning (of \(d\) blocks of variables) of the ambient space.

Attributes:

  • blocks_dict (dict) – dictionary describing the decomposition of Point objects. Keys are Point objects. Values are lists of Point objects corresponding to the decompositions of the key in blocks.

  • list_of_constraints (list) – The list of Constraint objects associated with this BlockPartition.

  • d (int) – encodes the number of blocks (\(d \geq 1\)).

  • counter (int) – counts the number of BlockPartition objects.

Example

>>> from PEPit import PEP
>>> pep = PEP()
>>> block_partition = pep.declare_block_partition(d=5)

BlockPartition objects can also be instantiated via the following arguments

Parameters:

d (int) – encodes the number of blocks (\(d \geq 1\)).

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

Raises:

AssertionError – if provided \(d\) is not a positive integer.

Example

>>> block_partition = BlockPartition(d=5)
add_constraint(constraint)[source]

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

Parameters:

constraint (Constraint) – typically resulting from a comparison of 2 Expression objects.

Raises:

AssertionError – if provided constraint is not a Constraint object.

add_partition_constraints()[source]

Formulate the list of orthogonality constraints induced by the partitioning.

get_block(point, block_number)[source]

Decompose a Point as a sum of into \(d\) orthogonal Point according to the partitioning.

Parameters:

  • point (Point) – any Point object.

  • block_number (int) – an integer between 0 and the number of blocks (corresponding to the block index, between 0 and d-1)

Returns:

point (Point) – a Point corresponding to the projection of point onto the block block_number of the partitioning.

Raises:

AssertionError – if provided point is not a Point or block_number is not a valid integer (which should be nonnegative and strictly smaller than the number of blocks)

get_nb_blocks()[source]

Return the number of blocks of this partition.

Expression

class PEPit.Expression(is_leaf=True, decomposition_dict=None, name=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:

  • name (str) – A name set through the set_name method. None is no name is given.

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

  • name (str) – name of the object. None by default. Can be updated later through the method set_name.

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.

get_name()[source]

Returns (str): the attribute name.

set_name(name)[source]

Assign a name to self for easier identification purpose.

Parameters:

name (str) – a name to be given to self.

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:

  • name (str) – A name set through the set_name method. None is no name is given.

  • activated (bool) – A boolean flag used to activate/deactivate the Constraint in the PEP.

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

activate()[source]

Activate the use of the Constraint.

deactivate()[source]

Deactivate the use of the Constraint.

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

get_name()[source]

Returns (str): the attribute name.

set_name(name)[source]

Assign a name to self for easier identification purpose.

Parameters:

name (str) – a name to be given to self.

Symmetric positive semi-definite matrix

class PEPit.PSDMatrix(matrix_of_expressions, name=None)[source]

Bases: object

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

Attributes:

  • name (str) – A name set through the set_name method. None is no name is given.

  • activated (bool) – A boolean flag used to activate/deactivate the LMI constraint in the PEP.

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

  • name (str) – name of the object. None by default. Can be updated later through the method set_name.

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.

activate()[source]

Activate the use of the LMI constraint.

deactivate()[source]

Deactivate the use of the LMI constraint.

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

get_name()[source]

Returns (str): the attribute name.

set_name(name)[source]

Assign a name to self for easier identification purpose.

Parameters:

name (str) – a name to be given to self.

Function

class PEPit.Function(is_leaf=True, decomposition_dict=None, reuse_gradient=False, name=None)[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:

  • name (str) – A name set through the set_name method. None is no name is given.

  • _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 with a class interpolation constraints.

  • tables_of_constraints (dict) – A dictionary containing all the constraints, sorted by table.

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

  • name (str, optional) – name of the object. None by default. Can be updated later through the method set_name.

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, name=None)[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.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Raises:

AssertionError – if provided constraint is not a Constraint object.

add_constraints_from_one_list_of_points(list_of_points, constraint_name, set_class_constraint_i)[source]

Add a class constraint of one input on all the points of list_of_points. Creates a table corresponding to this set of constraints.

Parameters:

  • list_of_points (list) – the list of points the constraint apply on.

  • constraint_name (str) – generic name for this constraint.

  • set_class_constraint_i (Callable) – a function that takes a point in input and returns a Constraint.

add_constraints_from_two_lists_of_points(list_of_points_1, list_of_points_2, constraint_name, set_class_constraint_i_j, symmetry=False)[source]

Add a class constraint of two inputs on all the couple of points of list_of_points_1 \(\times\) list_of_points_2. Creates a table corresponding to this set of constraints.

Parameters:

  • list_of_points_1 (list) – the first list of points the grid is generated from.

  • list_of_points_2 (list) – the second list of points the grid is generated from.

  • constraint_name (str) – generic name for this constraint.

  • set_class_constraint_i_j (Callable) – a function that takes two points in input and returns a Constraint.

  • symmetry (bool, optional) – A boolean specifying if the constraint function is symmetric or not. If so, the number of constraints is divided by 2. Set to False by default.

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, name=None)[source]

Store a new matrix of Expressions that we enforce to be positive semi-definite.

Parameters:

  • matrix_of_expressions (Iterable of Iterable of Expression) – a square matrix of Expression.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Raises:

  • AssertionError – if provided matrix is not a square matrix.

  • TypeError – if provided matrix does not contain only Expressions.

fixed_point(name=None)[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\).

Parameters:

name (str, optional) – name of the object. Not overwriting is None. None by default.

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_class_constraints_duals()[source]

This method browses all the tables of Constraint`s generated by the `add_class_constraints method, grab the dual variables values associated with the constraints and return a dictionary with all the dual tables.

Returns:

dict – a dictionary which keys are the names of the generic constraints provided to the methods add_constraints_from_one_list_of_points and add_constraints_from_two_lists_of_points, and the keys are pandas.DataFrames containing the dual values associated with the constraints.

get_interpolator()[source]

Warning

Needs to be overwritten with an appropriate interpolator for the class.

Raises:

NotImplementedError – This method must be overwritten in children classes

get_is_leaf()[source]
Returns:

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

get_name()[source]

Returns (str): the attribute name.

gradient(point, name=None)[source]

Return the gradient (or a subgradient) of this Function evaluated at point.

Parameters:

  • point (Point) – any point.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

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

set_class_constraints()[source]

This method is run by the PEP just before solving the problem. It reinitializes the list_of_class_constraints attributes before filling it.

set_name(name)[source]

Assign a name to self for easier identification purpose.

Parameters:

name (str) – a name to be given to self.

stationary_point(return_gradient_and_function_value=False, name=None)[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).

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Returns:

Point or tuple – an optimal point

subgradient(point, name=None)[source]

Return a subgradient of this Function evaluated at point.

Parameters:

  • point (Point) – any point.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Returns:

Point – a subgradient (Point) of this Function on point (Point).

Note

the method gradient does the exact same thing.

value(point, name=None)[source]

Return the function value of this Function on point.

Parameters:

  • point (Point) – any point.

  • name (str, optional) – name of the object. Not overwriting is None. None by default.

Returns:

Point – the function value (Expression) of this Function on point (Point).

Wrapper

class PEPit.Wrapper(verbose=1)[source]

Bases: object

A Wrapper object interfaces PEPit with an SDP solver (or modelling language).

Warning

This class must be overwritten by a child class that encodes all particularities of the solver. In particular, the methods send_constraint_to_solver, send_lmi_constraint_to_solver, generate_problem, get_dual_variables, get_primal_variables, eval_constraint_dual_values, solve, prepare_heuristic, and heuristic must be overwritten.

Attributes:

  • _list_of_constraints_sent_to_solver (list) – list of Constraint and PSDMatrix objects associated to the PEP. This list does not contain constraints due to internal representation of the problem by the solver.

  • optimal_F (numpy.array) – Elements of F after solving.

  • optimal_G (numpy.array) – Gram matrix of the PEP after solving.

  • objective (Expression) – The objective expression that must be maximized. This is an additional Expression created by the PEP to deal with cases where the user wants to maximize a minimum of several expressions.

  • dual_values (list) – Optimal dual variables after solving (same ordering as that of _list_of_constraints_sent_to_solver).

  • residual (Iterable of Iterables of floats) – The residual of the problem, i.e. the dual variable of the Gram.

  • prob – instance of the problem (whose type depends on the solver).

  • solver_name (str) – The name of the solver the wrapper interact with.

  • verbose (int) – Level of information details to print (Override the solver verbose parameter).

    • 0: No verbose at all.

    • 1: PEPit information is printed but not solver’s.

    • 2: Both PEPit and solver details are printed.

Wrapper object should not be instantiated as such: only children class should. This function initializes all internal variables of the class.

Parameters:

verbose (int) –

Level of information details to print (Override the solver verbose parameter).

  • 0: No verbose at all.

  • 1: PEPit information is printed but not solver’s.

  • 2: Both PEPit and solver details are printed.

assign_dual_values()[source]

Recover all dual variables and store them in associated Constraint and PSDMatrix objects.

Returns:

residual (ndarray) – main dual PSD matrix (dual to the PSD constraint on the Gram matrix).

Raises:

TypeError – if the attribute _list_of_constraints_sent_to_solver of this object is neither a Constraint object, nor a PSDMatrix one.

check_license()[source]

Check that there is a valid available license for the solver.

Returns:

license (bool) – is there a valid license?

generate_problem(objective)[source]

Instantiate an optimization model using the solver format, whose objective corresponds to a PEPit Expression object.

Parameters:

objective (Expression) – the objective function of the PEP (to be maximized).

Returns:

prob – the PEP in the solver’s format.

get_dual_variables()[source]

Output the list of dual variables.

Returns:

  • optimal_dual (list) – numerical values of the dual variables (same ordering as that of _list_of_constraints_sent_to_solver).

  • dual_residual (ndarray) – dual variable corresponding to the main (primal) Gram matrix.

get_primal_variables()[source]

Output the optimal value of primal variables.

Returns:

  • optimal_G (ndarray) – numerical Gram matrix of the PEP after solving.

  • optimal_F (ndarray) – numerical elements of F after solving.

heuristic(weight)[source]

Change the objective of the PEP, specifically for finding low-dimensional examples. We specify a matrix \(W\) (weight), which will allow minimizing \(\mathrm{Tr}(G\,W)\).

Parameters:

weight (np.array) – weights that will be used in the heuristic.

prepare_heuristic(wc_value, tol_dimension_reduction)[source]

Add the constraint that the objective stay close to its actual value before using dimension-reduction heuristics. That is, we constrain

\[\tau \leqslant \text{wc value} + \text{tol dimension reduction}\]
Parameters:

  • wc_value (float) – the optimal value of the original PEP.

  • tol_dimension_reduction (float) – tolerance on the objective for finding low-dimensional examples.

send_constraint_to_solver(constraint)[source]

Transfer a PEPit Constraint to the solver and add the Constraint into the tracking lists.

Parameters:

constraint (Constraint) – a Constraint object to be sent to the solver.

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

send_lmi_constraint_to_solver(psd_matrix)[source]

Transfer a PEPit PSDMatrix (LMI constraint) to the solver and add it the tracking lists.

Parameters:

psd_matrix (PSDMatrix) – a matrix of expressions that is constrained to be PSD.

solve(**kwargs)[source]

Solve the PEP with solver options.

Parameters:

kwargs (keywords, optional) – solver specific arguments.

Returns:

  • status (string) – status of the solution / problem.

  • name (string) – name of the solver.

  • value (float) – value of the performance metric after solving.

  • problem () – solver-specific model of the PEP.