tvopt package
Submodules
tvopt.costs module
Cost template definition and examples.
- class tvopt.costs.AbsoluteValue(weight=1)
Bases:
Cost
Scalar absolute value function.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Constant(dom, c)
Bases:
Cost
Constant cost.
This class defines a constant, whose value is stored in the attribute c. The gradient and hessian methods return 0, while the proximal acts as an identity.
- c
The constant value.
- Type
float
- smooth
The smoothness degree, set to 2.
- Type
int
- function(*args, **kwargs)
An evaluation of the cost.
Returns the costant value.
- gradient(*args, **kwargs)
An evaluation of the cost’s gradient.
Returns 0.
- hessian(*args, **kwargs)
An evaluation of the cost’s Hessian.
Returns 0.
- proximal(x, *args, **kwargs)
An evaluation of the cost’s proximal.
Acts as the identity, returning x.
- class tvopt.costs.Cost(dom, time=None, prox_solver=None)
Bases:
object
Template for a cost function.
This class defines the template for a cost function
\[f : \mathbb{R}^{n_1 \times n_2 \times \ldots} \times \mathbb{R}_+ \to \mathbb{R} \cup \{ +\infty \}\]which depends on the unknown \(\pmb{x} \in \mathbb{R}^{n_1 \times n_2 \times \ldots}\) and, optionally, on the time \(t \in \mathbb{R}_+\).
Cost objects support the following operations:
negation
sum (by another cost or with a scalar),
product (by another cost or with a scalar),
division and power with a scalar.
A Cost object should expose, compatibly with the smoothness degree, the methods function, gradient, hessian, proximal. The convention for these methods is that the first positional argument is \(\pmb{x}\), and only a second positional argument is allowed, for \(t\). Any other argument should be passed as a keyword argument.
If the cost is time-varying, then it should expose the methods time_derivative and sample, as well; see methods’ documentation for the default behavior.
- is_dynamic
Attribute to check if the cost is static or dynamic.
- Type
bool
- smooth
This attribute stores the smoothness degree of the cost, for example it is \(0\) if the cost is continuous, \(1\) if the cost is differentiable, etc. By convention it is \(-1\) if the cost is discontinuous.
- Type
int
- _prox_solver
This attribute specifies the method (gradient or Newton) that should be used to compute the proximal
\[\text{prox}_{\rho f(\cdot; t)}(\pmb{x}) = \text{argmin}_{\pmb{y}} \left\{ f(\pmb{y};t) + \frac{1}{2 \rho} \| \pmb{y} - \pmb{x} \|^2 \right\}\]of the cost, if a closed form is not available. See also the auxiliary function compute_proximal.
- Type
str or None
Notes
Not all operations preserve convexity.
- function(x, *args, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, *args, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, *args, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, *args, penalty=1, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- sample(t)
Sample the cost.
This method returns a SampledCost object which exposes the same methods of the cost but fixing the time argument to t.
If the cost is static, the cost itself is returned.
- Parameters
t (float) – The time at which the cost should be sampled.
- Returns
The sampled cost or, if static, the cost itself.
- Return type
- time_derivative(x, t, der='tx', **kwargs)
A derivative w.r.t. time of the cost.
This method computes derivatives w.r.t. time of the cost, or mixed derivatives w.r.t. both time and x (e.g. the derivative in time of the gradient).
If this method is not overwritten, it computes the derivative by default using backward finite differences. See backward_finite_difference for details.
If the cost is static, \(0\) is returned.
- Parameters
x (array_like) – The x where the derivative should be evaluated.
t (float) – The time at which the derivative should be evaluated.
der (str, optional) – A sequence of “x” and “t” that chooses which derivative should be computed. For example, the default “tx” denotes the derivative w.r.t. time of the cost’s (sub-)gradient.
**kwargs – Any other required argument.
- Raises
ValueError – If the number of “x” characters in der exceeds \(2\).
- Returns
The required derivative or \(0\).
- Return type
array_like
- class tvopt.costs.DiscreteDynamicCost(costs, t_s=1)
Bases:
Cost
Dynamic cost from a sequence of static costs.
This class creates a dynamic cost from a list of static costs. That is, given a sampling time \(T_\mathrm{s}\), the cost at time \(t_k = k T_\mathrm{s}\) is:
\[f(\pmb{x}; t_k) = f_k(\pmb{x})\]with \(f_k\) the k-th static cost in the list.
- function(x, t, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, t, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, t, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, t, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.DynamicExample_1D(t_s, t_max, omega=0.06283185307179587, kappa=7.5, mu=1.75)
Bases:
Cost
Scalar benchmark dynamic cost.
The dynamic cost was propposed in 2 and is defined as:
\[f(x; t) = \frac{1}{2} (x - \cos(\omega t))^2 + \kappa \log(1 + \exp(\mu x))\]with default parameters \(\omega = 0.02 \pi\), \(\kappa = 7.5\) and \(\mu = 1.75\).
- 2
A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, and A. Ribeiro, “A Class of Prediction-Correction Methods for Time-Varying Convex Optimization,” IEEE Transactions on Signal Processing, vol. 64, no. 17, pp. 4576–4591, Sep. 2016.
- approximate_time_derivative(x, t, der='tx')
- function(x, t)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, t)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, t=None)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- time_derivative(x, t, der='tx')
A derivative w.r.t. time of the cost.
This method computes derivatives w.r.t. time of the cost, or mixed derivatives w.r.t. both time and x (e.g. the derivative in time of the gradient).
If this method is not overwritten, it computes the derivative by default using backward finite differences. See backward_finite_difference for details.
If the cost is static, \(0\) is returned.
- Parameters
x (array_like) – The x where the derivative should be evaluated.
t (float) – The time at which the derivative should be evaluated.
der (str, optional) – A sequence of “x” and “t” that chooses which derivative should be computed. For example, the default “tx” denotes the derivative w.r.t. time of the cost’s (sub-)gradient.
**kwargs – Any other required argument.
- Raises
ValueError – If the number of “x” characters in der exceeds \(2\).
- Returns
The required derivative or \(0\).
- Return type
array_like
- class tvopt.costs.DynamicExample_2D(t_s, t_max)
Bases:
Cost
Bi-dimensional benchmark dynamic cost.
The dynamic cost was proposed in 3 and is defined as:
\[f(\pmb{x}; t) = \frac{1}{2} (x_1 - \exp(\cos(t)))^2 + \frac{1}{2} (x_2 - x_1 \tanh(t))^2\]where we used the notation \(\pmb{x} = [x_1, x_2]^\top\).
- 3
Y. Zhang, Z. Qi, B. Qiu, M. Yang, and M. Xiao, “Zeroing Neural Dynamics and Models for Various Time-Varying Problems Solving with ZLSF Models as Minimization-Type and Euler-Type Special Cases [Research Frontier],” IEEE Computational Intelligence Magazine, vol. 14, no. 3, pp. 52–60, Aug. 2019.
- approximate_time_derivative(x, t, der='tx')
- function(x, t)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, t)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x=None, t=None)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- time_derivative(x, t, der='tx')
A derivative w.r.t. time of the cost.
This method computes derivatives w.r.t. time of the cost, or mixed derivatives w.r.t. both time and x (e.g. the derivative in time of the gradient).
If this method is not overwritten, it computes the derivative by default using backward finite differences. See backward_finite_difference for details.
If the cost is static, \(0\) is returned.
- Parameters
x (array_like) – The x where the derivative should be evaluated.
t (float) – The time at which the derivative should be evaluated.
der (str, optional) – A sequence of “x” and “t” that chooses which derivative should be computed. For example, the default “tx” denotes the derivative w.r.t. time of the cost’s (sub-)gradient.
**kwargs – Any other required argument.
- Raises
ValueError – If the number of “x” characters in der exceeds \(2\).
- Returns
The required derivative or \(0\).
- Return type
array_like
- class tvopt.costs.Huber(n, threshold)
Bases:
Cost
Vector Huber loss.
The cost is defined as
\[\begin{split}f(\pmb{x}) = \begin{cases} \|\pmb{x}\|^2 / 2 & \text{if} \ \|\pmb{x}\| \leq \theta \\ \theta (\|\pmb{x}\| - \theta / 2) & \text{otherwise} \end{cases}\end{split}\]where \(\theta > 0\) is a given threshold.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Huber_1D(threshold)
Bases:
Cost
Huber loss.
The cost is defined as
\[\begin{split}f(x) = \begin{cases} x^2 / 2 & \text{if} \ |x| \leq \theta \\ \theta (|x| - \theta / 2) & \text{otherwise} \end{cases}\end{split}\]where \(\theta > 0\) is a given threshold.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Indicator(s)
Bases:
Cost
Indicator function of a given set.
This objects implements the indicator function of a given Set object. That is, given the set \(\mathbb{S}\) we define:
\[\begin{split}f(\pmb{x}) = \begin{cases} 0 & \text{if} \ \pmb{x} \in \mathbb{S} \\ +\infty & \text{otherwise}. \end{cases}\end{split}\]The proximal operator of the cost is the projection onto the set.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- projection(x, **kwargs)
- proximal(x, *args, penalty=1, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Linear(b, c=0)
Bases:
Cost
Linear cost.
The function is defined as
\[f(x) = \langle \pmb{x}, \pmb{b} \rangle + c.\]
- class tvopt.costs.LinearRegression(A, b)
Bases:
Cost
Cost for linear regression.
The cost is defined as
\[f(\pmb{x}) = \frac{1}{2} \| \pmb{A} \pmb{x} - \pmb{b} \|^2.\]
- class tvopt.costs.Logistic
Bases:
Cost
Logistic function.
The function is defined as
\[f(x) = \log\left( 1 + \exp(x) \right).\]- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1, max_iter=50, tol=1e-08)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.LogisticRegression(A, b, weight=0)
Bases:
Cost
Cost for logistic regression.
The cost is defined as
\[f(\pmb{x}) = \sum_{i = 1}^m \log\left( 1 + \exp\left( - b_i \langle \pmb{a}_i, \pmb{x} \rangle + x_0 \right) \right)\]where \(b_i \in \{ -1, 1 \}\), \(\pmb{a}_i\) are classifier and feature vector, and \(x_0\) is the intercept. An optional \(\ell_2\) regularization can be added defining its weight penalty.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1, tol=1e-05, max_iter=100)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Norm_1(n=1, weight=1)
Bases:
Cost
Class for \(\ell_1\) norm.
The function is defined as
\[f(\pmb{x}) = w \| \pmb{x} \|_1\]for \(\pmb{x} \in \mathbb{R}^n\) and \(w > 0\).
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
Proximal evaluation of \(\ell_1\) norm, a.k.a. soft-thresholding.
See also
utils.soft_thresholding
- class tvopt.costs.Norm_inf(n=1, weight=1)
Bases:
Cost
Class for \(\ell_\infty\) norm.
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- class tvopt.costs.PowerCost(cost, p)
Bases:
Cost
Power cost.
This class defines a cost as the given power of a cost. It is used for implementing the * operation.
- function(*args, **kwargs)
An evaluation of the power cost.
- gradient(*args, **kwargs)
An evaluation of the power cost (sub-)gradient.
- hessian(*args, **kwargs)
An evaluation of the power cost Hessian.
- class tvopt.costs.ProductCost(c_1, c_2)
Bases:
Cost
Product of two costs.
This class defines a cost from the product of two given costs. Derivatives are computed using the chain rule.
- function(x, *args, **kwargs)
An evaluation of the product cost.
- gradient(x, *args, **kwargs)
An evaluation of the product cost (sub-)gradient.
- hessian(x, *args, **kwargs)
An evaluation of the product cost Hessian.
- class tvopt.costs.Quadratic(A, b, c=0)
Bases:
Cost
Quadratic cost.
The function is defined as
\[f(x) = \frac{1}{2} \pmb{x}^\top \pmb{A} \pmb{x} + \langle \pmb{x}, \pmb{b} \rangle + c\]with the given matrix \(\pmb{A} \in \mathbb{R}^{n \times n}\) and vector \(\pmb{b} \in \mathbb{R}^n\).
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x=None)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.Quadratic_1D(a, b, c=0)
Bases:
Cost
Scalar quadratic cost.
The cost is defined as
\[f(x) = a x^2 / 2 + b x + c.\]- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x=None)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.RobustLinearRegression(A, b, threshold)
Bases:
Cost
Cost for robust linear regression.
Let \(h : \mathbb{R} \to \mathbb{R}\) be the Huber loss, then the cost is defined as:
\[f(\pmb{x}) = \sum_{i = 1}^m h(a_i \pmb{x} - b_i)\]where \(a_i \in \mathbb{R}^{1 \times n}\) are the rows of the data matrix \(\pmb{A} \in \mathbb{R}^{m \times n}\), and \(b_i\) the elements of the data vector \(\pmb{b}\).
- function(x)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- class tvopt.costs.SampledCost(cost, t)
Bases:
Cost
Sampled cost.
This class defines a static cost by sampling a dynamic cost at a given time.
- function(x, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.ScaledCost(cost, s)
Bases:
Cost
Scaled cost.
This class defines a cost scaled by a constant. That is, given the cost \(f : \mathbb{R}^n \times \mathbb{R}_+ \to \mathbb{R} \cup \{ +\infty \}\) and \(c \in \mathbb{R}\) it defines:
\[g(\pmb{x}; t) = c f(\pmb{x}; t).\]The class is used for the product and division by a constant.
- function(*args, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(*args, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(*args, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(*args, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- class tvopt.costs.SeparableCost(costs)
Bases:
Cost
Separable cost function.
This class defines a separable cost, that is
\[f(\pmb{x}; t) = \sum_{i = 1}^N f_i(x_i; t)\]where \(x_i \in \mathbb{R}^{n_1 \times n_2 \times \ldots}\) for each \(i = 1, \ldots, N\). Each of the component functions \(f_i\) can be either static or dynamic. This is useful for defining distributed optimization problems.
The overall dimension of the domain is \(n_1 \times n_2 \times \ldots \times N\), meaning that the last dimension indexes the components.
The class exposes the same methods as any Cost, with the difference that the keyword argument i can be used to evaluate only a single component. If all components are evaluated, an ndarray is returned with the last dimension indexing the components.
The class has the Cost attributes, with the following additions or differences.
- costs
The component costs.
- Type
list
- N
The number of components.
- Type
int
- is_dynamic
True if at least one component is dynamic.
- Type
bool
- smooth
This is the minimum of the smoothness degrees of all components.
- Type
int
- function(x, *args, i=None, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, *args, i=None, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, *args, i=None, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, *args, penalty=1, i=None, **kwargs)
An evaluation of the cost(s) proximal(s).
This is the same as calling _evaluate with “proximal”, with the difference that is customized to handle the penalty parameter. In particular, the penalty can either be a scalar, in which case the same penalty is used for all components, or a list of component-wise penalties.
- class tvopt.costs.SumCost(*costs)
Bases:
Cost
Sum of costs.
This class defines a cost as the sum of an arbitrary number of costs. That is, given the costs \(f_i : \mathbb{R}^n \times \mathbb{R}_+ \to \mathbb{R} \cup \{ +\infty \}\) with \(i = 1, \ldots, N\), the class defines:
\[f(\pmb{x}; t) = \sum_{i = 1}^N f_i(\pmb{x}; t)\]The function, gradient and hessian are defined from the components’ methods using the sum rule, while the proximal by default is computed recursively.
- function(x, *args, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, *args, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, *args, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- tvopt.costs.backward_finite_difference(signal, t, order=1, step=1)
Compute the backward finite difference of a signal.
This function computes an approximate derivative of a given signal using backward finite differences. Given the signal \(s(t)\), it computes:
\[s^o(t) = \sum_{i = 0}^o (-1)^i {o \choose i} s(t - i T_s) / T_s^o\]where \(o \in \mathbb{N}\) is the derivative order and \(T_s\) is the sampling time, see 5 for more details.
Notice that if samples before \(t = 0\) are required, they are set to zero.
- Parameters
signal – A function of a single scalar argument that represents the signal.
t (float) – The time where the derivative should be evaluated.
order (int, optional) – The derivative order, defaults to 1.
step (float, optional) – The sampling time, defaults to 1.
- Raises
ValueError – For invalid order or step arguments.
- Returns
The approximate derivative.
- Return type
ndarray
References
- 5
A. Quarteroni, R. Sacco, and F. Saleri, Numerical mathematics, 2nd ed. Berlin; New York: Springer, 2007.
- tvopt.costs.compute_proximal(f, x, penalty, solver=None, **kwargs)
Compute the proximal of a cost.
This function (approximately) computes the proximal of a given cost if there is no closed form solution. The function uses either a Newton method or a gradient method, both with backtracking line search.
- Parameters
f (Cost) – The static cost whose proximal is required.
x (array_like) – Where the proximal has to be evaluated.
penalty (float) – The penalty of the proximal.
solver (str, optional) – The method to use for computing the proximal, Newton or gradient. If not specified, Newton is used for twice differentiable function, gradient otherwise.
**kwargs (dict) – Parameters for the Newton or gradient method.
- Returns
y – The proximal.
- Return type
ndarray
See also
solvers.backtracking_gradient
,solvers.newton
tvopt.distributed_solvers module
Distributed solvers.
- tvopt.distributed_solvers.admm(problem, penalty, rel, w_0=0, num_iter=100)
Distributed relaxed alternating direction method of multipliers (ADMM).
This function implements the distributed ADMM, see 6 and references therein. The algorithm is characterized by the following updates
\[x_i^\ell = \operatorname{prox}_{f_i / (\rho d_i)} ([\pmb{A}^\top z^\ell]_i / (\rho d_i))\]\[z_{ij}^{\ell+1} = (1-\alpha) z_{ij}^\ell - \alpha z_{ji}^\ell + 2 \alpha \rho x_j^\ell\]for \(\ell = 0, 1, \ldots\), where \(d_i\) is node \(i\)’s degree, \(\rho\) and \(\alpha\) are the penalty and relaxation parameters, and \(\pmb{A}\) is the arc incidence matrix. The algorithm is guaranteed to converge to the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the cost describing the problem.
penalty (float) – The penalty parameter \(\rho\) of the algorithm (convergence is guaranteed for any positive value).
rel (float) – The relaxation parameter \(\alpha\) of the algorithm (convergence is guaranteed for values in \((0,1)\)).
w_0 (ndarray, optional) – The initial value of the dual nodes’ states. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x (ndarray) – The nodes’ states after num_iter iterations.
w (ndarray) – The dual variables of the nodes after num_iter iterations.
References
- 6
N. Bastianello, R. Carli, L. Schenato, and M. Todescato, “Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence,” IEEE Transactions on Automatic Control.
- tvopt.distributed_solvers.aug_dgm(problem, step, x_0=0, num_iter=100)
Augmented distributed gradient method (Aug-DGM).
This function implements the Aug-DGM algorithm (see 7). The algorithm is characterized by the following updates
\[\begin{split}\begin{align} \pmb{y}^\ell &= \pmb{W} \left( \pmb{y}^{\ell-1} + \nabla f(\pmb{x}^\ell) - \nabla f(\pmb{x}^{\ell-1}) \right) \\ \pmb{x}^{\ell+1} &= \pmb{W} \left( \pmb{x}^\ell - \pmb{A} \pmb{y}^\ell \right) \end{align}\end{split}\]for \(\ell = 0, 1, \ldots\) where \(\pmb{A}\) is a diagonal matrix of uncoordinated step-sizes. The algorithm is guaranteed to converge to the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the cost describing the problem.
step (float) – A common step-size or a list of local step-sizes, one for each node.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 7
J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in 2015 54th IEEE Conference on Decision and Control (CDC), Osaka, Japan, Dec. 2015, pp. 2055–2060.
- tvopt.distributed_solvers.average_consensus(net, x_0, num_iter=100)
Average consensus.
Compute the average consensus over the network net with initial states x_0.
- Parameters
net (networks.Network) – The network describing the multi-agent system.
x_0 (ndarray) – The initial states in a ndarray, with the last dimension indexing the nodes.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
- tvopt.distributed_solvers.dpgm(problem, step, x_0=0, num_iter=100)
Distributed proximal gradient method (DPGM).
This function implements the DPGM algorithm proposed in 8 (see also 9 for the gradient-only version). The algorithm is characterized by the following updates
\[\begin{split}\begin{align} \pmb{y}^\ell &= \pmb{W} \pmb{x}^\ell - \alpha \nabla f(\pmb{x}^\ell) \\ \pmb{x}^{\ell+1} &= \operatorname{prox}_{\alpha g}(\pmb{y}^\ell) \end{align}\end{split}\]for \(\ell = 0, 1, \ldots\). The algorithm is guaranteed to converge to a neighborhood of the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the costs describing the (possibly composite) problem. The dictionary should contain \(f\) and the network, and optionally \(g\).
step (float) – The step-size.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 8
Bastianello, N., Ajalloeian, A., & Dall’Anese, E. (2020). Distributed and Inexact Proximal Gradient Method for Online Convex Optimization. arXiv preprint arXiv:2001.00870.
- 9
Yuan, K., Ling, Q., & Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3), 1835-1854.
- tvopt.distributed_solvers.dual_ascent(problem, step, w_0=0, num_iter=100)
Distributed dual ascent a.k.a. dual decomposition (DD).
This function implements the DD algorithm 10. The algorithm is characterized by the following updates
\[\pmb{x}^\ell = \operatorname{arg\,min}_{\pmb{x}} \left\{ f(\pmb{x}) - \langle (\pmb{I} - \pmb{W}) \pmb{x}, \pmb{w}^\ell \rangle\right\}\]\[\pmb{w}^{\ell+1} = \pmb{w}^\ell - \alpha (\pmb{I} - \pmb{W}) \pmb{x}^\ell\]for \(\ell = 0, 1, \ldots\), where \(\pmb{w}\) is the vector of Lagrange multipliers. The algorithm is guaranteed to converge to the optimal solution.
- Parameters
system (A dictionary containing the network describing the multi-agent) – and the cost describing the problem.
step (float) – The step-size.
w_0 (ndarray, optional) – The initial value of the dual nodes’ states. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x (ndarray) – The nodes’ states after num_iter iterations.
w (ndarray) – The dual variables of the nodes after num_iter iterations.
References
- 10
Simonetto, A. (2018). Dual Prediction–Correction Methods for Linearly Constrained Time-Varying Convex Programs. IEEE Transactions on Automatic Control, 64(8), 3355-3361.
- tvopt.distributed_solvers.gossip_consensus(net, x_0, num_iter=100, q=0.5)
Average consensus.
Compute the average consensus over the network net with initial states x_0 using the symmetric gossip protocol.
- Parameters
net (networks.Network) – The network describing the multi-agent system.
x_0 (ndarray) – The initial states in a ndarray, with the last dimension indexing the nodes.
num_iter (int, optional) – The number of iterations to be performed.
q (float, optional) – The weight used in the convex combination of the nodes that communicate at each iteration.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
- tvopt.distributed_solvers.max_consensus(net, x_0, num_iter=100)
Max consensus.
Compute the maximum of the nodes’ states x_0.
- Parameters
net (networks.Network) – The network describing the multi-agent system.
x_0 (ndarray) – The initial states in a ndarray, with the last dimension indexing the nodes.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
- tvopt.distributed_solvers.nids(problem, step, x_0=0, num_iter=100)
Network InDependent Step-size algorithm (NIDS).
This function implements the NIDS algorithm proposed in 11. The algorithm is characterized by the following updates
\[\begin{split}\begin{align} \pmb{y}^\ell &= \pmb{y}^{\ell-1} - \pmb{x}^\ell - \tilde{\pmb{W}} (2 \pmb{x}^\ell - \pmb{x}^{\ell-1} - \operatorname{diag}(\pmb{\alpha}) (\nabla f(\pmb{x}^\ell) - \nabla f(\pmb{x}^{\ell-1}))) \\ \pmb{x}^{\ell+1} &= \operatorname{prox}_{\pmb{\alpha} g}(\pmb{y}^\ell) \end{align}\end{split}\]for \(\ell = 0, 1, \ldots\), where \(\pmb{\alpha}\) is a column vector containing the independent step-sizes of the nodes, and
\[\tilde{\pmb{W}} = \pmb{I} + c \operatorname{diag}(\pmb{\alpha}) (\pmb{W} - \pmb{I})\]with \(c = 0.5 / \max_i \{ \alpha_i \}\). The algorithm is guaranteed to converge to the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the costs describing the (possibly composite) problem. The dictionary should contain \(f\) and the network, and optionally \(g\).
step (float or list) – A common step-size or a list of local step-sizes, one for each node.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 11
Li, Z., Shi, W., & Yan, M. (2019). A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67(17), 4494-4506.
- tvopt.distributed_solvers.pg_extra(problem, step, x_0=0, num_iter=100)
Proximal gradient exact first-order algorithm (PG-EXTRA).
This function implements the PG-EXTRA algorithm proposed in 12 (see also 13 for the gradient-only version, EXTRA). The algorithm is characterized by the following updates
\[\begin{split}\begin{align} \pmb{y}^\ell &= \pmb{y}^{\ell-1} + \pmb{W} \pmb{x}^\ell - \tilde{\pmb{W}} \pmb{x}^{\ell-1} - \alpha (\nabla f(\pmb{x}^\ell) - \nabla f(\pmb{x}^{\ell-1})) \\ \pmb{x}^{\ell+1} &= \operatorname{prox}_{\alpha g}(\pmb{y}^\ell) \end{align}\end{split}\]for \(\ell = 0, 1, \ldots\), where \(\tilde{\pmb{W}} = (\pmb{I} + \pmb{W}) /2\). The algorithm is guaranteed to converge to the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the costs describing the (possibly composite) problem. The dictionary should contain \(f\) and the network, and optionally \(g\).
step (float) – The step-size.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 12
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015). A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing, 63(22), 6013-6023.
- 13
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015). Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2), 944-966.
- tvopt.distributed_solvers.prox_aac(problem, step, x_0=0, num_iter=100, consensus_steps=[True, True, True])
Proximal adapt-and-combine (Prox-AAC).
This function implements the Prox-AAC algorithm (see 1 for the gradient only version). The algorithm is characterized by the following updates
\[\pmb{z}^\ell = \pmb{W}_1 \pmb{x}^\ell\]\[\pmb{y}^\ell = \pmb{z}^\ell - \alpha \nabla f(\pmb{z}^\ell)\]\[\pmb{x}^{\ell+1} = \pmb{W}_3 \operatorname{prox}_{\alpha g}(\pmb{W}_2 \pmb{y}^\ell)\]for \(\ell = 0, 1, \ldots\), where \(\pmb{W}_1\), \(\pmb{W}_2\) and \(\pmb{W}_3\) are doubly stochastic matrices (or the identity).
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the costs describing the (possibly composite) problem. The dictionary should contain \(f\) and the network, and optionally \(g\).
step (float or list) – A common step-size or a list of local step-sizes, one for each node.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
consensus_steps (list) – A list specifying which consensus steps to perform; the list must have three elements that can be interpreted as bools.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 1
Chen, J., & Sayed, A. H. (2013). Distributed Pareto optimization via diffusion strategies. IEEE Journal of Selected Topics in Signal Processing, 7(2), 205-220.
- tvopt.distributed_solvers.prox_ed(problem, step, x_0=0, num_iter=100)
Proximal exact diffusion (Prox-ED).
This function implements the Prox-ED algorithm 14. The algorithm is characterized by the following updates
\[\begin{split}\begin{align} \pmb{y}^\ell &= \pmb{x}^\ell - \alpha \nabla f(\pmb{x}^\ell) \\ \pmb{u}^\ell &= \pmb{z}^{\ell-1} + \pmb{y}^\ell - \pmb{y}^{\ell-1} \\ \pmb{z}^\ell &= \tilde{\pmb{W}} \pmb{u}^\ell \\ \pmb{x}^{\ell+1} &= \operatorname{prox}_{\alpha g}(\pmb{z}^\ell) \end{align}\end{split}\]for \(\ell = 0, 1, \ldots\), where \(\tilde{\pmb{W}} = (\pmb{I} + \pmb{W}) /2\). The algorithm is guaranteed to converge to the optimal solution.
- Parameters
problem (dict) – A dictionary containing the network describing the multi-agent system and the costs describing the (possibly composite) problem. The dictionary should contain \(f\) and the network, and optionally \(g\).
step (float) – The step-size.
x_0 (ndarray, optional) – The initial states of the nodes. This can be either an ndarray of suitable size with the last dimension indexing the nodes, or a scalar. If it is a scalar then the same initial value is used for all components of the states.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
References
- 14
S. A. Alghunaim, E. Ryu, K. Yuan, and A. H. Sayed, “Decentralized Proximal Gradient Algorithms with Linear Convergence Rates,” IEEE Transactions on Automatic Control, 2020.
- tvopt.distributed_solvers.ratio_consensus(net, x_0, num_iter=100)
Ratio consensus.
Compute the average consensus over the network net with initial states x_0 using the ratio consensus protocol.
- Parameters
net (networks.Network) – The network describing the multi-agent system.
x_0 (ndarray) – The initial states in a ndarray, with the last dimension indexing the nodes.
num_iter (int, optional) – The number of iterations to be performed.
- Returns
x – The nodes’ states after num_iter iterations.
- Return type
ndarray
tvopt.networks module
Network tools.
- class tvopt.networks.DynamicNetwork(nets, t_s=1)
Bases:
Network
Time-varying network.
This class creates a time-varying network from a list of network objects, and possibly a sampling time that specifies how often the network changes.
- broadcast(t, *args, **kwargs)
Broadcast transmission.
This method implements a broadcast transmission in which a node sends the same packet to all its neighbors. The packet is also transmitted to the node itself. The method is implemented using the send method.
- Parameters
sender (int) – The index of the transmitting node.
packet (array_like) – The packet to ne communicated.
- consensus(t, *args, **kwargs)
Consensus mixing.
This method implements a consensus step over the network, mixing the given nodes’ states using the weight matrix of the network or a different one.
- Parameters
x (array_like) – The nodes’ local states in an array with the last dimension indexing the nodes.
weights (ndarray, optional) – The consensus weight matrix to be used instead of the one created at initialization.
- Returns
y – The local states after a consensus step.
- Return type
ndarray
- max_consensus(t, *args, **kwargs)
Max-consensus.
This method implements a step of max-consensus, where each node selects the (element-wise) maximum between the packets received from its neighbors and its own state. See 15 for a reference on max-consensus.
- Parameters
x (array_like) – The nodes’ local states in an array with the last dimension indexing the nodes.
- Returns
x – The local states after a max-consensus step.
- Return type
ndarray
References
- 15
F. Iutzeler, P. Ciblat, and J. Jakubowicz, “Analysis of Max-Consensus Algorithms in Wireless Channels,” IEEE Transactions on Signal Processing, vol. 60, no. 11, pp. 6103–6107, Nov. 2012.
- sample(t)
Sample the dynamic network.
This method returns the network object that is active at time t.
- Parameters
t (float) – The time when the network should be sampled.
- Returns
The sampled network.
- Return type
- send(t, *args, **kwargs)
Node-to-node transmission (sender phase).
This method simulates a node-to-node transmission by storing the packet to be communicated in the buffer. In particular, if \(i\) is the sender and \(j\) the receiver, then the packet is introduced in buffer with keyword \((j,i)\).
Note that older information (if any) in the buffer is overwritten whenever send is called.
- Parameters
sender (int) – The index of the transmitting node.
receiver (int) – The index of the recipient.
packet (array_like) – The packet to ne communicated.
- class tvopt.networks.LossyNetwork(adj_mat, loss_prob, weights=None)
Bases:
Network
Network with random communication failures.
Representation of a connected, undirected network, whose communication protocol is subject to packet losses. Packet sent from a node to another may be lost with a certain probability.
- send(sender, receiver, packet)
Node-to-node transmission (sender phase).
This method simulates a node-to-node transmission by storing the packet to be communicated in the buffer. In particular, if \(i\) is the sender and \(j\) the receiver, then the packet is introduced in buffer with keyword \((j,i)\).
Note that older information (if any) in the buffer is overwritten whenever send is called.
- Parameters
sender (int) – The index of the transmitting node.
receiver (int) – The index of the recipient.
packet (array_like) – The packet to ne communicated.
- class tvopt.networks.Network(adj_mat, weights=None)
Bases:
object
Representation of an undirected network.
The class implements an undirected network defined from the adjacency matrix. The class provides methods for different communication protocols, such as node-to-node and broadcast.
Transmissions are implemented via the buffer attribute of the network: the sender stores the packet to be transmitted in the buffer dictionary, specifying the recipient, which can then access the packet.
By convention, the nodes in the network are indexed from \(0\) to \(N-1\), where \(N\) is the total number of nodes.
- adj_mat
The adjacency matrix of the network.
- Type
ndarray
- N
The number of nodes in the network.
- Type
ndarray
- weights
The consensus weight matrix, if not specified in the constructor this is the Metropolis-Hastings weight matrix.
- Type
ndarray
- neighbors
A list whose \(i\)-th element is a list of node \(i\)’s neighors.
- Type
list
- degrees
The number of neighbors of each node.
- Type
list
- buffer
The dictionary used for node-to-node transmissions.
- Type
dict
- broadcast(sender, packet)
Broadcast transmission.
This method implements a broadcast transmission in which a node sends the same packet to all its neighbors. The packet is also transmitted to the node itself. The method is implemented using the send method.
- Parameters
sender (int) – The index of the transmitting node.
packet (array_like) – The packet to ne communicated.
- consensus(x, weights=None)
Consensus mixing.
This method implements a consensus step over the network, mixing the given nodes’ states using the weight matrix of the network or a different one.
- Parameters
x (array_like) – The nodes’ local states in an array with the last dimension indexing the nodes.
weights (ndarray, optional) – The consensus weight matrix to be used instead of the one created at initialization.
- Returns
y – The local states after a consensus step.
- Return type
ndarray
- max_consensus(x)
Max-consensus.
This method implements a step of max-consensus, where each node selects the (element-wise) maximum between the packets received from its neighbors and its own state. See 16 for a reference on max-consensus.
- Parameters
x (array_like) – The nodes’ local states in an array with the last dimension indexing the nodes.
- Returns
x – The local states after a max-consensus step.
- Return type
ndarray
References
- 16
F. Iutzeler, P. Ciblat, and J. Jakubowicz, “Analysis of Max-Consensus Algorithms in Wireless Channels,” IEEE Transactions on Signal Processing, vol. 60, no. 11, pp. 6103–6107, Nov. 2012.
- receive(receiver, sender, default=0, destructive=True)
Node-to-node transmission (receiver phase).
This method simulates the reception of a packet previously transmitted using the send method. In patricular, the method accesses the packet in the buffer dictionary. If the packet is not present, a default value is returned.
Reads from the buffer can be destructive, meaning that the packet is read and removed, which is the default, or not.
- Parameters
receiver (int) – The index of the recipient.
sender (int) – The index of the transmitting node.
default (array_like, optional) – The value returned when a packet from sender to receiver is not found in the buffer.
destructive (bool, optional) – Specifies if the packet should be removed from the buffer after being read (which is the default) or not.
- Returns
The packet or a default value.
- Return type
array_like
- send(sender, receiver, packet)
Node-to-node transmission (sender phase).
This method simulates a node-to-node transmission by storing the packet to be communicated in the buffer. In particular, if \(i\) is the sender and \(j\) the receiver, then the packet is introduced in buffer with keyword \((j,i)\).
Note that older information (if any) in the buffer is overwritten whenever send is called.
- Parameters
sender (int) – The index of the transmitting node.
receiver (int) – The index of the recipient.
packet (array_like) – The packet to ne communicated.
- class tvopt.networks.NoisyNetwork(adj_mat, noise_var, weights=None)
Bases:
Network
Network with Gaussian communication noise.
Representation of a connected, undirected network, whose communication protocol is subject to additive white Gaussian noise. The network’s transmission methods add normal noise to all packets (unless they are sent from a node to itself).
- send(sender, receiver, packet)
Node-to-node transmission (sender phase).
This method simulates a node-to-node transmission by storing the packet to be communicated in the buffer. In particular, if \(i\) is the sender and \(j\) the receiver, then the packet is introduced in buffer with keyword \((j,i)\).
Note that older information (if any) in the buffer is overwritten whenever send is called.
- Parameters
sender (int) – The index of the transmitting node.
receiver (int) – The index of the recipient.
packet (array_like) – The packet to ne communicated.
- class tvopt.networks.QuantizedNetwork(adj_mat, step, thresholds=None, weights=None)
Bases:
Network
Network with quantized communications.
Representation of a connected, undirected network, whose communications are quantized. The network’s transmission methods quantize all packets (unless they are sent from a node to itself).
- send(sender, receiver, packet)
Node-to-node transmission (sender phase).
This method simulates a node-to-node transmission by storing the packet to be communicated in the buffer. In particular, if \(i\) is the sender and \(j\) the receiver, then the packet is introduced in buffer with keyword \((j,i)\).
Note that older information (if any) in the buffer is overwritten whenever send is called.
- Parameters
sender (int) – The index of the transmitting node.
receiver (int) – The index of the recipient.
packet (array_like) – The packet to ne communicated.
- tvopt.networks.circle_graph(N)
Generate a circle graph.
- Parameters
N (int) – Number of nodes in the graph.
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
See also
circulant_graph
Circulant graph generator
- tvopt.networks.circulant_graph(N, num_conn)
Generate a circulant graph.
- Parameters
N (int) – Number of nodes in the graph.
num_conn (int) – Number of neighbors on each side of a node.
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
Notes
If num_conn is larger than N / 2 a complete graph is returned.
- tvopt.networks.complete_graph(N)
Generate a complete graph.
- Parameters
N (int) – Number of nodes in the graph.
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
See also
circulant_graph
Circulant graph generator
- tvopt.networks.erdos_renyi(N, prob)
Generate a random Erdos-Renyi graph.
- Parameters
N (int) – Number of nodes in the graph.
prob (float) – The probability of adding an edge between any two nodes.
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
- Raises
ValueError. –
- tvopt.networks.incidence_matrix(adj_mat, n=1)
Build the incidence matrix.
The edges \(e = (i,j)\) are ordered with \(i \leq j\), so that in the \(e\)-th column the \(i\)-th element is \(1\) and the \(j\)-th is \(-1\) (the remaining are of course \(0\)).
- Parameters
adj_mat (ndarray) – Adjacency matrix describing the graph.
n (int, optional) – Size of the local states.
- Returns
incid_mat – The incidence matrix.
- Return type
ndarray
- tvopt.networks.is_connected(adj_mat)
Verify if a graph is connected.
- Parameters
adj_mat (ndarray) – Adjacency matrix describing the graph.
- Returns
True if the graph is connected, False otherwise.
- Return type
bool
Notes
The connectedness of the graph is checked by verifying whether the \(N\)-th power of the adjacency matrix plus the identity is a full matrix (no zero elements), with \(N\) the number of nodes.
- tvopt.networks.metropolis_hastings(adj_mat)
Compute a consensus matrix based on the Metropolis-Hastings rule.
The Metropolis-Hastings rule generates a matrix \(W\) with off-diagonal elements equal to:
\[w_{ij} = \frac{1}{1 + \max\{ d_i, d_j \}}\]where \(i\) is a node index and \(j \neq i\) the index of one of its neighbors, and \(d_i\), \(d_j\) are their respective degrees. The diagonal elements are assigned as:
\[w_{ii} = 1 - \sum_{j \in \mathcal{N}_i} w_{ij}\]to guarantee double stochasticity.
- Parameters
adj_mat (ndarray) – Adjacency matrix describing the graph.
- Returns
mh_mat – Metropolois-Hastings consensus matrix.
- Return type
ndarray
- tvopt.networks.random_graph(N, radius)
Generate a random geometric graph.
- Parameters
N (int) – Number of nodes in the graph.
radius (float) – Radius of each node’s neighborhood, must be in \([0,1)\).
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
- Raises
ValueError. –
Notes
The function recursively generates random positions for the nodes on the \([0,1] \times [0,1]\) square, and then builds the graph by setting as neighbors each pair of nodes within a distance no larger than radius. The process is repeated until the result is a connected graph. For this reason, combinations of small N and radius can yield exceedingly long computation times. If the computation does not succeed after 2500 iterations, an error is raised.
- tvopt.networks.star_graph(N)
Generate a star graph.
- Parameters
N (int) – Number of nodes in the graph.
- Returns
adj_mat – Adjacency matrix of the generated graph.
- Return type
ndarray
tvopt.prediction module
Cost prediction tools.
- class tvopt.prediction.ExtrapolationPrediction(cost, order=2)
Bases:
Prediction
Extrapolation-based prediction.
This prediction strategy, proposed in 17, predicts the cost at time \(t_{k+1}\) as:
\[\hat{f}(\pmb{x};t_{k+1}) = \sum_{i = 1}^I \ell_i f(\pmb{x}; t_{k - i + 1})\]where \(I \in \mathbb{N}\) denotes the order, that is, the number of past functions to use, and with coefficients:
\[\ell_i = \prod_{1 \leq j \leq I, \ j \neq i} \frac{j}{j - i}.\]- 17
N. Bastianello, A. Simonetto, and R. Carli, “Primal and Dual Prediction-Correction Methods for Time-Varying Convex Optimization,” arXiv:2004.11709 [cs, math], Oct. 2020. Available: http://arxiv.org/abs/2004.11709.
- update(t)
Update the current prediction.
This method updates the current prediction by building a new predicted cost using the samples observed up to time t. By default this method samples the dynamic cost, and should be overwritten when implementing a custom prediction strategy.
- Parameters
t (float) – The time of the last sampled cost.
- class tvopt.prediction.Prediction(cost)
Bases:
Cost
Prediction of a dynamic cost.
This class creates a cost object that predicts a given dynamic function. The object stores a dynamic cost and a predicted cost, which can be modified using new information through the method update.
- function(x, **kwargs)
An evaluation of the cost. Implement if needed.
- Parameters
x (array_like) – The x where the cost should be evaluated.
*args – The time at which the cost should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- gradient(x, **kwargs)
An evaluation of the cost’s gradient or sub-gradient. Implement if needed.
- Parameters
x (array_like) – The x where the (sub-)gradient should be evaluated.
*args – The time at which the (sub-)gradient should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- hessian(x, **kwargs)
An evaluation of the cost’s Hessian. Implement if needed.
- Parameters
x (array_like) – The x where the Hessian should be evaluated.
*args – The time at which the Hessian should be evaluated. Not required if the cost is static.
**kwargs – Any other required argument.
- proximal(x, penalty=1, **kwargs)
An evaluation of the cost’s proximal.
If this method is not overwritten, the default behavior is to recursively compute the proximal via a gradient or Newton backtracking algorithm. See compute_proximal for the function that is used for this purpose.
- Parameters
x (array_like) – The x where the proximal should be evaluated.
*args – The time at which the proximal should be evaluated. Not required if the cost is static.
penalty (float, optional) – The penalty parameter \(\rho\) for the proximal evaluation. Defaults to \(1\).
**kwargs – Any other required argument.
- update(t, *args, **kwargs)
Update the current prediction.
This method updates the current prediction by building a new predicted cost using the samples observed up to time t. By default this method samples the dynamic cost, and should be overwritten when implementing a custom prediction strategy.
- Parameters
t (float) – The time of the last sampled cost.
- class tvopt.prediction.TaylorPrediction(cost)
Bases:
Prediction
Taylor expansion-based prediction.
This prediction strategy, proposed in 18 and see also 19, predicts the cost at time \(t_{k+1}\) using its Taylor expansion around \(t_k\) and a given \(\pmb{x}_k\):
\[\begin{split}\begin{split} \hat{f}(\pmb{x}; t_{k+1}) &= f(\pmb{x}_k;t_k) + \langle \nabla_x f(\pmb{x}_k;t_k), \pmb{x} - \pmb{x}_k \rangle + T_s \nabla_t f(\pmb{x}_k;t_k) + (T_s^2 / 2) \nabla_{tt} f(\pmb{x}_k;t_k) +\\ &+ T_s \langle \nabla_{tx} f(\pmb{x}_k;t_k), \pmb{x} - \pmb{x}_k \rangle + \frac{1}{2} (\pmb{x} - \pmb{x}_k)^\top \nabla_{xx} f(\pmb{x}_k;t_k) (\pmb{x} - \pmb{x}_k) \end{split}\end{split}\]where \(T_s\) is the sampling time.
References
- 18
A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, and A. Ribeiro, “A Class of Prediction-Correction Methods for Time-Varying Convex Optimization,” IEEE Transactions on Signal Processing, vol. 64, no. 17, pp. 4576–4591, Sep. 2016.
- 19
N. Bastianello, A. Simonetto, and R. Carli, “Primal and Dual Prediction-Correction Methods for Time-Varying Convex Optimization,” arXiv:2004.11709 [cs, math], Oct. 2020. Available: http://arxiv.org/abs/2004.11709.
- update(t, x, gradient_only=True, **kwargs)
Update the current prediction.
This method updates the current prediction by building a new predicted cost using the samples observed up to time t. By default this method samples the dynamic cost, and should be overwritten when implementing a custom prediction strategy.
- Parameters
t (float) – The time of the last sampled cost.
tvopt.sets module
Set template and examples.
- class tvopt.sets.AffineSet(A, b)
Bases:
Set
Affine set.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ A x = b \}\]for given matrix \(A \in \mathbb{R}^{m \times n}\) and vector \(b \in \mathbb{R}^{m}\).
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.Ball(center, radius)
Bases:
Set
Ball set.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ \| x - c \| \leq r \}\]for a center \(c\) and radius \(r > 0\).
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.Ball_l1(center, radius)
Bases:
Set
\(\ell_1\)-ball set.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ \| x - c \|_1 \leq r \}\]for a center \(c\) and radius \(r > 0\).
- contains(x)
Check if the input belongs to the set.
- projection(x, tol=1e-05)
Project the input onto the set.
- class tvopt.sets.Box(l, u, n=1)
Bases:
Set
Box set.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ l \leq x \leq u \}\]with bounds \(l, u\) either scalar (applied element-wise) or vectors.
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.Halfspace(a, b)
Bases:
Set
Halfspace.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ \langle a, x \rangle \leq b \}\]for given vetor \(a \in \mathbb{R}^{n}\) and scalar \(b \in \mathbb{R}\).
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.IntersectionSet(*sets)
Bases:
Set
Intersection of sets.
Given the sets \(\mathbb{S}_i\), \(i = 1, \ldots, N\) this class implements
\[\bigcap_{i = 1}^N \mathbb{S}_i.\]- contains(x)
Check if the input belongs to the set.
- projection(x, *args, **kwargs)
Projection onto the intersection.
This method returns an approximate projection onto the intersection of sets, computed using the method of alternating projections.
See also
alternating_projections
method of alternating projection
- class tvopt.sets.NonnegativeOrthant(n)
Bases:
Set
Non-negative orthant.
This class implements:
\[\{ x \in \mathbb{R}^n \ | \ x \geq 0 \}\]where \(x \geq 0\) if \(x\) is component-wise non-negative.
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.R(*dims)
Bases:
Set
The underlying space.
This class implements the underlying space \(\mathbb{R}^{n_1 \times n_2 \times \ldots}\).
- contains(x)
Check if the input belongs to the set.
- projection(x)
Project the input onto the set.
- class tvopt.sets.ScaledSet(s, c)
Bases:
Set
Scaled set.
Given a set \(\mathbb{S}\) and a scalar \(c\), this class defines
\[\{ c x \ \forall x \in \mathbb{S} \}.\]- contains(x)
Check if the input belongs to the set.
- projection(x, *args, **kwargs)
Project the input onto the set.
- class tvopt.sets.Set(*dims)
Bases:
object
Template for a set.
This class defines a non-empty, closed, convex set in \(\mathbb{R}^{n_1 \times n_2 \times \ldots}\). These objects are defined by a contains method (to check if an input belongs to the set) and a projection method.
Sets can be translated and scaled (via the respective methods). The contains method can also be accessed via the built-in in operator. Using + it is possible to intersect sets.
- shape
The dimensions of the underlying space.
- Type
tuple
- ndim
The number of dimensions of the underlying space.
- Type
int
- size
The product of each dimension’s size.
- Type
int
- check_input(x)
Check dimension of input.
This method verifies if the argument x belong to the space underlying the set, possibly reshaping it. If it is not compatible or cannot be reshaped (using numpy’s broadcasting rules), and exception is raised.
- Parameters
x (array_like) – The input to be checked.
- Returns
The (possibly reshaped) input if it is compatible with the space.
- Return type
ndarray
- contains(x)
Check if the input belongs to the set.
- projection(x, *args, **kwargs)
Project the input onto the set.
- scale(c)
Scale the set.
- translate(x)
Translate the set.
- class tvopt.sets.T(t_s, t_min=0, t_max=inf)
Bases:
Set
Set of sampling times.
This class implements the set of sampling times:
\[\{ t_k \geq 0, \ k \in \mathbb{N} \}\]with \(t_{k+1} - t_k = T_\mathrm{s}\) for a sampling time \(T_\mathrm{s}\).
- check_input(t)
Check dimension of input.
This method verifies if the argument x belong to the space underlying the set, possibly reshaping it. If it is not compatible or cannot be reshaped (using numpy’s broadcasting rules), and exception is raised.
- Parameters
x (array_like) – The input to be checked.
- Returns
The (possibly reshaped) input if it is compatible with the space.
- Return type
ndarray
- contains(t)
Check if the input belongs to the set.
- projection(t)
Project the input onto the set.
- scale(c)
Scale the set.
- translate(t)
Translate the set.
- class tvopt.sets.TranslatedSet(s, t)
Bases:
Set
Translated set.
Given a set \(\mathbb{S}\) and a vector \(t\), this class defines
\[\{ x + t \ \forall x \in \mathbb{S} \}.\]- contains(x)
Check if the input belongs to the set.
- projection(x, *args, **kwargs)
Project the input onto the set.
- tvopt.sets.alternating_projections(sets, x, tol=1e-10, num_iter=10)
Method of alternating projections.
This function returns a point in the intersection of the given convex sets, computed using the method of alternating projections (MAP) 20.
- Parameters
sets (list) – The list of sets.
x (array_like) – The starting point.
tol (float, optional) – The stopping condition. If the difference between consecutive iterates is smaller than or equal to tol, then the function returns. Defaults to \(10^{-10}\).
num_iter (int, optional) – The maximum number of iterations of the projection algorithm. Defaults to \(1000\). This stopping condition is enacted if the algorithm does not reach tol.
- Returns
x – A point in the intersection.
- Return type
ndarray
References
- 20
H. Bauschke and V. Koch, “Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces,” in Contemporary Mathematics, vol. 636, S. Reich and A. Zaslavski, Eds. Providence, Rhode Island: American Mathematical Society, 2015, pp. 1–40.
tvopt.solvers module
Solvers.
- tvopt.solvers.admm(problem, penalty, rel=1, w_0=0, num_iter=100, tol=None)
Alternating direction method of multipliers (ADMM).
This function implements the ADMM to solve the constrained problem
\[\begin{split}\begin{align} &\min_{\pmb{x},\pmb{y}} \left\{ f(\pmb{x}) + g(\pmb{y}) \right\} \\ &\text{s.t.} \ \pmb{A} \pmb{x} + \pmb{B} \pmb{y} = \pmb{c}. \end{align}\end{split}\]The algorithm is characterized by the updates:
\[\begin{split}\begin{align} \pmb{x}^\ell &= \operatorname{arg\,min}_{\pmb{x}} \left\{ f(\pmb{x}) - \langle \pmb{z}^\ell, \pmb{A} \pmb{x} \rangle + \frac{\rho}{2} \| \pmb{A} \pmb{x} - \pmb{c} \|^2 \right\} \\ \pmb{w}^\ell &= \pmb{z}^\ell - \rho (\pmb{A} \pmb{x}^\ell - \pmb{c}) \\ \pmb{y}^\ell &= \operatorname{arg\,min}_{\pmb{y}} \left\{ g(\pmb{y}) - \langle 2 \pmb{w}^\ell - \pmb{z}^\ell, \pmb{B} \pmb{y} \rangle + \frac{\rho}{2} \| \pmb{B} \pmb{y} \|^2 \right\} \\ \pmb{u}^\ell &= 2 \pmb{w}^\ell - \pmb{z}^\ell - \rho \pmb{B} \pmb{y}^\ell \\ \pmb{z}^{\ell+1} &= \pmb{z}^\ell + 2 \alpha (\pmb{u}^\ell - \pmb{w}^\ell) \end{align}\end{split}\]for a given penalty \(\rho > 0\) and \(\alpha \in (0,1]\) is the relaxation constant.
- Parameters
problem (dict) – Problem dictionary defining the costs \(f\) and \(g\), and the constraints \(A\), \(B\) and \(c\).
penalty (float) – The algorithm’s penalty.
rel (float, optional) – The relaxation constant.
w_0 (array_like, optional) – The dual initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{w}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the dual stopping condition \(\| \pmb{w}^{\ell+1} - \pmb{w}^\ell \| \leq t\).
- Returns
x (ndarray) – The approximate primal solution \(\pmb{x}\) after num_iter iterations.
y (ndarray) – The approximate primal solution \(\pmb{y}\) after num_iter iterations.
w (ndarray) – The approximate dual solution after num_iter iterations.
- tvopt.solvers.backtracking_gradient(problem, r=0.2, c=0.5, x_0=0, num_iter=100, tol=None)
Gradient method with backtracking line search.
This function implements the gradient method
\[\pmb{x}^{\ell+1} = \pmb{x}^\ell - \alpha^\ell \nabla f(\pmb{x}^\ell)\]where \(\alpha^\ell\) is chosen via a backtracking line search. In particular, at each iteration we start with \(\alpha^\ell = 1\) and, while
\[f(\pmb{x}^\ell - \alpha^\ell \nabla f(\pmb{x}^\ell)) > f(\pmb{x}^\ell) - c \alpha^\ell \| \nabla f(\pmb{x}^\ell) \|^2\]we set \(\alpha^\ell = r \alpha^\ell\) until a suitable step is found.
Note that the backtracking line search does not stop until a suitable step-size si found; this means that large r parameters may result in big computation times.
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\).
r (float, optional) – The value by which a candidate step-size is multiplied if it does not satisfy the descent condition. r should be in \((0,1)\).
c (float, optional) – The parameter defining the descent condition that a candidate step must satisfy.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.dual_ascent(problem, penalty, w_0=0, num_iter=100, tol=None)
Dual ascent.
This function implements the dual ascent to solve the constrained problem
\[\min_{\pmb{x}} f(\pmb{x}) \ \text{s.t.} \ \pmb{A} \pmb{x} = \pmb{c}.\]The algorithm is characterized by the updates:
\[\begin{split}\begin{align} \pmb{x}^\ell &= \operatorname{arg\,min}_{\pmb{x}} \left\{ f(\pmb{x}) - \langle \pmb{w}^\ell, \pmb{A} \pmb{x} \rangle \right\} \\ \pmb{w}^{\ell+1} &= \pmb{w}^\ell - \rho (\pmb{A} \pmb{x}^\ell - \pmb{c}) \end{align}\end{split}\]for a given penalty \(\rho > 0\).
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\), and the constraints \(A\) and \(c\).
penalty (float) – The algorithm’s penalty.
w_0 (array_like, optional) – The dual initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{w}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the dual stopping condition \(\| \pmb{w}^{\ell+1} - \pmb{w}^\ell \| \leq t\).
- Returns
x (ndarray) – The approximate primal solution after num_iter iterations.
w (ndarray) – The approximate dual solution after num_iter iterations.
- tvopt.solvers.dual_fbs(problem, penalty, rel=1, w_0=0, num_iter=100, tol=None)
Dual forward-backward splitting.
This function implements the dual FBS to solve the constrained problem
\[\begin{split}\begin{align} &\min_{\pmb{x},\pmb{y}} \left\{ f(\pmb{x}) + g(\pmb{y}) \right\} \\ &\text{s.t.} \ \pmb{A} \pmb{x} + \pmb{B} \pmb{y} = \pmb{c}. \end{align}\end{split}\]The algorithm is characterized by the updates:
\[\begin{split}\begin{align} \pmb{x}^\ell &= \operatorname{arg\,min}_{\pmb{x}} \left\{ f(\pmb{x}) - \langle \pmb{w}, \pmb{A} \pmb{x} \rangle \right\} \\ \pmb{u}^\ell &= \pmb{w}^\ell - \rho (\pmb{A} \pmb{x}^\ell - \pmb{c}) \\ \pmb{y}^\ell &= \operatorname{arg\,min}_{\pmb{y}} \left\{ g(\pmb{y}) - \langle \pmb{u}^\ell, \pmb{B} \pmb{y} \rangle + \frac{\rho}{2} \| \pmb{B} \pmb{y} \|^2 \right\} \\ \pmb{w}^{\ell+1} &= (1-\alpha) \pmb{w}^\ell + \alpha (\pmb{u}^\ell - \rho \pmb{B} \pmb{y}^\ell) \end{align}\end{split}\]for a given penalty \(\rho > 0\) and \(\alpha \in (0,1]\) is the relaxation constant.
- Parameters
problem (dict) – Problem dictionary defining the costs \(f\) and \(g\), and the constraints \(A\), \(B\) and \(c\).
penalty (float) – The algorithm’s penalty.
rel (float, optional) – The relaxation constant.
w_0 (array_like, optional) – The dual initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{w}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the dual stopping condition \(\| \pmb{w}^{\ell+1} - \pmb{w}^\ell \| \leq t\).
- Returns
x (ndarray) – The approximate primal solution \(\pmb{x}\) after num_iter iterations.
y (ndarray) – The approximate primal solution \(\pmb{y}\) after num_iter iterations.
w (ndarray) – The approximate dual solution after num_iter iterations.
- tvopt.solvers.fbs(problem, step, rel=1, x_0=0, num_iter=100, tol=None)
Forward-backward splitting (FBS).
This function implements the forward-backward splitting (a.k.a. proximal gradient method) to solve the composite problem
\[\min_{\pmb{x}} \{ f(\pmb{x}) + g(\pmb{x}) \}.\]The algorithm is characterized by the update:
\[\pmb{x}^{\ell+1} = (1-\alpha) \pmb{x}^\ell + \alpha \operatorname{prox}_{\rho g}(\pmb{x}^\ell - \rho \nabla f(\pmb{x}^\ell))\]where \(\rho > 0\) is the step-size and \(\alpha \in (0,1]\) is the relaxation constant.
- Parameters
problem (dict) – Problem dictionary defining the costs \(f\) and \(g\).
step (float) – The algorithm’s step-size.
rel (float, optional) – The relaxation constant.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.gradient(problem, step, x_0=0, num_iter=100, tol=None)
Gradient method.
This function implements the gradient method
\[\pmb{x}^{\ell+1} = \pmb{x}^\ell - \alpha \nabla f(\pmb{x}^\ell)\]for a given step-size \(\alpha > 0\).
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\).
step (float) – The algorithm’s step-size.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.mm(problem, penalty, w_0=0, num_iter=100, tol=None)
Method of multipliers (MM).
This function implements the method of multipliers to solve the constrained problem
\[\min_{\pmb{x}} f(\pmb{x}) \ \text{s.t.} \ \pmb{A} \pmb{x} = \pmb{c}.\]The algorithm is characterized by the updates:
\[\begin{split}\begin{align} \pmb{x}^\ell &= \operatorname{arg\,min}_{\pmb{x}} \left\{ f(\pmb{x}) - \langle \pmb{w}^\ell, \pmb{A} \pmb{x} \rangle + \frac{\rho}{2} \| \pmb{A} \pmb{x} - \pmb{c} \|^2 \right\} \\ \pmb{w}^{\ell+1} &= \pmb{w}^\ell - \rho (\pmb{A} \pmb{x}^\ell - \pmb{c}) \end{align}\end{split}\]for a given penalty \(\rho > 0\).
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\), and the constraints \(A\) and \(c\).
penalty (float) – The algorithm’s penalty.
w_0 (array_like, optional) – The dual initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{w}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the dual stopping condition \(\| \pmb{w}^{\ell+1} - \pmb{w}^\ell \| \leq t\).
- Returns
x (ndarray) – The approximate primal solution after num_iter iterations.
w (ndarray) – The approximate dual solution after num_iter iterations.
- tvopt.solvers.newton(problem, r=0.2, c=0.5, x_0=0, num_iter=100, tol=None)
Newton method with backtracking line search.
This function implements the Newton method
\[\pmb{x}^{\ell+1} = \pmb{x}^\ell - \alpha^\ell \nabla^2 f(\pmb{x}^\ell)^{-1} \nabla f(\pmb{x}^\ell)\]where \(\alpha^\ell\) is chosen via a backtracking line search. In particular, at each iteration we start with \(\alpha^\ell = 1\) and, while
\[f(\pmb{x}^\ell - \alpha^\ell \nabla^2 f(\pmb{x}^\ell)^{-1} \nabla f(\pmb{x}^\ell)) > f(\pmb{x}^\ell) - c \alpha^\ell \| \nabla f(\pmb{x}^\ell) \|^2\]we set \(\alpha^\ell = r \alpha^\ell\) until a suitable step is found.
Note that the backtracking line search does not stop until a suitable step-size si found; this means that large r parameters may result in big computation times.
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\).
r (float, optional) – The value by which a candidate step-size is multiplied if it does not satisfy the descent condition. r should be in \((0,1)\).
c (float, optional) – The parameter defining the descent condition that a candidate step must satisfy.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.ppa(problem, penalty, x_0=0, num_iter=100, tol=None)
Proximal point algorithm (PPA).
This function implements the proximal point algorithm
\[\pmb{x}^{\ell+1} = \operatorname{prox}_{\rho f}(\pmb{x}^\ell)\]where \(\rho > 0\) is the penalty parameter and we recall that
\[\operatorname{prox}_{\rho f}(\pmb{x}) = \operatorname{arg\,min}_{\pmb{y}} \left\{ f(\pmb{y}) + \frac{1}{2\rho} \| \pmb{y} - \pmb{x} \|^2 \right\}.\]- Parameters
problem (dict) – Problem dictionary defining the cost \(f\).
penalty (float) – The penalty parameter for the proximal evaluation.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.prs(problem, penalty, rel=1, x_0=0, num_iter=100, tol=None)
Peaceman-Rachford splitting (PRS).
This function implements the Peaceman-Rachford splitting to solve the composite problem
\[\min_{\pmb{x}} \{ f(\pmb{x}) + g(\pmb{x}) \}.\]The algorithm is characterized by the updates:
\[\begin{split}\begin{align} \pmb{x}^\ell &= \operatorname{prox}_{\rho f}(\pmb{z}^\ell) \\ \pmb{y}^\ell &= \operatorname{prox}_{\rho g}(2 \pmb{x}^\ell - \pmb{z}^\ell) \\ \pmb{z}^{\ell+1} &= \pmb{z}^\ell + 2 \alpha (\pmb{y}^\ell - \pmb{x}^\ell) \end{align}\end{split}\]where \(\rho > 0\) is the penalty and \(\alpha \in (0,1]\) is the relaxation constant.
- Parameters
problem (dict) – Problem dictionary defining the costs \(f\) and \(g\).
penalty (float) – The algorithm’s penalty parameter.
rel (float, optional) – The relaxation constant.
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
- tvopt.solvers.stop(x, x_old, tol=None)
Stopping condition.
This function checks the stopping condition
\[\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\]if t is specified.
- Parameters
x (ndarray) – The current iterate.
x_old (ndarray) – The previous iterate.
tol (float, optional) – The tolerance in the stopping condition.
- Returns
True if tol is given and the stopping condition is verified, False otherwise.
- Return type
bool
- tvopt.solvers.subgradient(problem, x_0=0, num_iter=100, tol=None)
Sub-gradient method.
This function implements the sub-gradient method
\[\pmb{x}^{\ell+1} = \pmb{x}^\ell - \alpha^\ell \tilde{\nabla} f(\pmb{x}^\ell)\]where \(\tilde{\nabla} f(\pmb{x}^\ell) \in \partial f(\pmb{x}^\ell)\) is a sub-differential and \(\alpha^\ell = 1 / (\ell + 1)\).
- Parameters
problem (dict) – Problem dictionary defining the cost \(f\).
x_0 (array_like, optional) – The initial condition. This can be either an ndarray of suitable size, or a scalar. If it is a scalar then the same initial value is used for all components of \(\pmb{x}\).
num_iter (int, optional) – The number of iterations to be performed.
tol (float, optional) – If given, this argument specifies the tolerance \(t\) in the stopping condition \(\| \pmb{x}^{\ell+1} - \pmb{x}^\ell \| \leq t\).
- Returns
x – The approximate solution after num_iter iterations.
- Return type
ndarray
tvopt.utils module
Utility tools.
- tvopt.utils.bisection_method(f, a, b, tol=1e-05)
Minimize using the bisection method.
This function minimizes a function f using the bisection method, stopping when \(a - b \leq t\) for some threshold \(t\).
- Parameters
f – The scalar function to be minimized.
a (float) – The lower bound of the initial interval.
b (float) – the upper bound of the initial interval.
tol (float, optional) – The stopping condition, defaults to 1e-5.
- Returns
x – The approximate minimizer.
- Return type
float
- tvopt.utils.dist(s, r, ord=2)
Distance of a signal from a reference.
This function computes the distance of a signal s from a reference r. The reference can be either constant or a signal itself. Different norm orders can be used, that can be specified using the numpy.linalg.norm argument ord.
- Parameters
s (array_like) – The signal, with the last dimension indexing time.
r (array_like) – The reference, either a single array or a signal with the last dimension indexing time.
ord (optional) – Norm order, see numpy.linalg.norm.
- Raises
ValueError – For incompatible dimensions of signal and reference.
- Returns
The distance of the signal from the reference as an array with length equal to the last dimension of s.
- Return type
ndarray
- tvopt.utils.fpr(s, ord=2)
Fixed point residual.
This function computes the fixed point residual of a signal s, that is
\[\{ \| s^\ell - s^{\ell-1} \|_i \}_{\ell \in \mathbb{N}}.\]Different norm orders can be used, that can be specified using the numpy.linalg.norm argument ord.
- Parameters
s (array_like) – The signal, with the last dimension indexing time.
ord (optional) – Norm order, see numpy.linalg.norm.
- Returns
The fixed point residual.
- Return type
ndarray
- tvopt.utils.initialize_trajectory(x_0, shape, num_iter)
- tvopt.utils.is_scalar(c)
Check if scalar.
- tvopt.utils.is_square(mat)
Check if the matrix is 2-D and square.
- Parameters
mat (ndarray) – The given matrix.
- Returns
True if the matrix is 2-D and square, False otherwise.
- Return type
bool
- tvopt.utils.is_stochastic(mat, row=True, col=True)
Verify if a given matrix is row, column or doubly stochastic.
- Parameters
mat (ndarray) – The given matrix.
row (bool, optional) – Check for row stochasticity, default True.
col (bool, optional) – Check for column stochasticity, default True.
- Returns
True if the matrix is stochastic (row, column or doubly, as specified by the arguments).
- Return type
bool
- Raises
ValueError – If neither row nor col are True.
- tvopt.utils.norm(x)
Compute the norm of the given vector.
- Parameters
x (array_like) – The vector array.
- Returns
The square norm.
- Return type
ndarray
See also
square_norm
Square norm
Notes
The function reshapes x to a column vector, so it does not correctly handle n-dimensional arrays. For n-dim arrays use numpy.linalg.norm.
- tvopt.utils.normalize(x)
Normalize a vector to unit vector.
- Parameters
x (array_like) – The vector array.
- Returns
The normalized vector.
- Return type
ndarray
Notes
The function reshapes x to a column vector, so it does not correctly handle n-dimensional arrays. For n-dim arrays use numpy.linalg.norm.
- tvopt.utils.orthonormal_matrix(dim)
Generate a random orthonormal matrix.
This function generates uniformly distributed random orthonormal matrices using Householder reflections (see Section 7 of this paper).
- Parameters
dim (int) – Size of the matrix.
- Returns
orth_mat – The random orthonormal matrix.
- Return type
ndarray
- Raises
ValueError – For invalid dim.
- tvopt.utils.positive_semidefinite_matrix(dim, max_eig=None, min_eig=None)
Generate a random positive semi-definite matrix.
The matrix is generated as
\[M = O \mathrm{diag}\{ \lambda_i \} O^\top\]where \(O\) is a random orthonormal matrix and \(\lambda_i\) are random eigenvalues uniformly drawn between min_eig and max_eig. If dim is larger than or equal to two, min_eig and max_eig are included in the eigenvalues list.
- Parameters
dim (int) – Size of the matrix.
eigs (array-like, optional) – The list of eigenvalues for the matrix; if None, the eigenvalues are uniformly drawn from \([10^{-2}, 10^2]\).
- Returns
The random positive semi-definite matrix.
- Return type
ndarray
- Raises
ValueError. –
See also
random_matrix
Random matrix generator.
- tvopt.utils.print_progress(i, num_iter, bar_length=80, decimals=2)
Print the progresso to command line.
- Parameters
i (int) – Current iteration.
num_iter (int) – Total number of iterations.
bar_length (int, optional) – Length of progress bar.
decimals (int, optional) – Decimal places of the progress percent.
Notes
Adapted from here.
- tvopt.utils.random_matrix(eigs)
Generate a random matrix.
The matrix is generated as
\[M = O \mathrm{diag}\{ \lambda_i \} O^\top\]where \(O\) is a random orthonormal matrix and \(\lambda_i\) are the specified eigenvalues.
- Parameters
eigs (array-like) – The list of eigenvalues for the matrix.
- Returns
The random positive semi-definite matrix.
- Return type
ndarray
See also
orthonormal_matrix
Orthonormal matrix generator.
- tvopt.utils.regret(f, s, r=None)
Cost over time or regret.
This function computes the cost evaluated using f incurred by an approximate minimizer s
\[\{ \frac{1}{\ell} \sum_{j = 1}^\ell f(s^j) \}_{\ell \in \mathbb{N}}\]or, if a reference r is specified, then the function computes the regret
\[\{ \frac{1}{\ell} \sum_{j = 1}^\ell f(s^j) - f(r^j) \}_{\ell \in \mathbb{N}}\]where r is either a constant array or a signal.
- Parameters
f (costs.Cost) – The cost to evaluate in the signal.
s (array_like) – The sequence of approximate minimizers.
r (array_like, optional) – The reference, either a single array or a signal with the last dimension indexing time.
- Returns
The sequence of cost evaluations or regret.
- Return type
ndarray
- tvopt.utils.soft_thresholding(x, penalty)
Soft-thresholding.
The function computes the element-wise soft-trhesholding defined as
\[\operatorname{sign}(x) \max\{ |x| - \rho, 0 \}\]where \(\rho\) is a positive penalty parameter.
- Parameters
x (array_like) – Where to evaluate the soft-thresholding.
penalty (float) – The positive penalty parameter \(\rho\).
- Returns
The soft-thresolding of x.
- Return type
ndarray
- tvopt.utils.solve(a, b)
- tvopt.utils.square_norm(x)
Compute the square norm of the given vector.
- Parameters
x (array_like) – The vector array.
- Returns
The square norm.
- Return type
ndarray
Notes
The function reshapes x to a column vector, so it does not correctly handle n-dimensional arrays. For n-dim arrays use numpy.linalg.norm.
- tvopt.utils.uniform_quantizer(x, step, thresholds=None)
Function to perform uniform quantization.
The function applies the uniform quantization
\[q(x) = \Delta \operatorname{floor} \left( \frac{x}{\Delta} + \frac{1}{2} \right)\]where \(\Delta\) is the given step. Moreover, a saturation to upper and lower thresholds is peformed if given as argument.
- Parameters
x (ndarray) – The array to be quantized.
step (float) – The step of the quantizer.
thresholds (list, optional) – The upper and lower saturation thresholds.
- Returns
The quantized array.
- Return type
ndarray