6. Fixed point
6.1. Halpern iteration
- PEPit.examples.fixed_point_problems.wc_halpern_iteration(n, verbose=1)[source]
Consider the fixed point problem
\[\mathrm{Find}\, x:\, x = Ax,\]where \(A\) is a non-expansive operator, that is a \(L\)-Lipschitz operator with \(L=1\).
This code computes a worst-case guarantee for the Halpern Iteration. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|x_n - Ax_n\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the Halpern iteration, and \(x_\star\) the fixed point of \(A\).
In short, for a given value of \(n\), \(\tau(n)\) is computed as the worst-case value of \(\|x_n - Ax_n\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: The Halpern iteration can be written as
\[x_{t+1} = \frac{1}{t + 2} x_0 + \left(1 - \frac{1}{t + 2}\right) Ax_t.\]Theoretical guarantee: A tight worst-case guarantee for Halpern iteration can be found in [1, Theorem 2.1]:
\[\|x_n - Ax_n\|^2 \leqslant \left(\frac{2}{n+1}\right)^2 \|x_0 - x_\star\|^2.\]References: The detailed approach and tight bound are available in [1].
- Parameters
n (int) – number of iterations.
verbose (int) –
Level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + CVXPY details.
- Returns
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> pepit_tau, theoretical_tau = wc_halpern_iteration(n=25, verbose=1) (PEPit) Setting up the problem: size of the main PSD matrix: 28x28 (PEPit) Setting up the problem: performance measure is minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) function 1 : Adding 702 scalar constraint(s) ... function 1 : 702 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: SCS); optimal value: 0.005933984368783424 *** Example file: worst-case performance of Halpern Iterations *** PEPit guarantee: ||xN - AxN||^2 <= 0.00593398 ||x0 - x_*||^2 Theoretical guarantee: ||xN - AxN||^2 <= 0.00591716 ||x0 - x_*||^2
6.2. Optimal Contractive Halpern iteration
- PEPit.examples.fixed_point_problems.wc_optimal_contractive_halpern_iteration(n, gamma, verbose=1)[source]
Consider the fixed point problem
\[\mathrm{Find}\, x:\, x = Ax,\]where \(A\) is a \(1/\gamma\)-contractive operator, i.e. a \(L\)-Lipschitz operator with \(L=1/\gamma\).
This code computes a worst-case guarantee for the Optimal Contractive Halpern Iteration. That is, it computes the smallest possible \(\tau(n, \gamma)\) such that the guarantee
\[\|x_n - Ax_n\|^2 \leqslant \tau(n, \gamma) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the Optimal Contractive Halpern iteration, and \(x_\star\) is the fixed point of \(A\). In short, for a given value of \(n, \gamma\), \(\tau(n, \gamma)\) is computed as the worst-case value of \(\|x_n - Ax_n\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: The Optimal Contractive Halpern iteration can be written as
\[x_{t+1} = \left(1 - \frac{1}{\varphi_{t+1}} \right) Ax_t + \frac{1}{\varphi_{t+1}} x_0.\]where \(\varphi_k = \sum_{i=0}^k \gamma^{2i}\) and \(x_0\) is a starting point.
Theoretical guarantee: A tight worst-case guarantee for the Optimal Contractive Halpern iteration can be found in [1, Corollary 3.3, Theorem 4.1]:
\[\|x_n - Ax_n\|^2 \leqslant \left(1 + \frac{1}{\gamma}\right)^2 \left( \frac{1}{\sum_{k=0}^n \gamma^k} \right)^2 \|x_0 - x_\star\|^2.\]References: The detailed approach and tight bound are available in [1].
- Parameters
n (int) – number of iterations.
gamma (float) – \(\gamma \ge 1\). \(A\) will be \(1/\gamma\)-contractive.
verbose (int) –
Level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + CVXPY details.
- Returns
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> pepit_tau, theoretical_tau = wc_optimal_contractive_halpern_iteration(n=10, gamma=1.1, verbose=1) (PEPit) Setting up the problem: size of the main PSD matrix: 13x13 (PEPit) Setting up the problem: performance measure is minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) function 1 : Adding 132 scalar constraint(s) ... function 1 : 132 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: SCS); optimal value: 0.010613882599724987 *** Example file: worst-case performance of Optimal Contractive Halpern Iterations *** PEPit guarantee: ||xN - AxN||^2 <= 0.0106139 ||x0 - x_*||^2 Theoretical guarantee: ||xN - AxN||^2 <= 0.0106132 ||x0 - x_*||^2
6.3. Krasnoselskii-Mann with constant step-sizes
- PEPit.examples.fixed_point_problems.wc_krasnoselskii_mann_constant_step_sizes(n, gamma, verbose=1)[source]
Consider the fixed point problem
\[\mathrm{Find}\, x:\, x = Ax,\]where \(A\) is a non-expansive operator, that is a \(L\)-Lipschitz operator with \(L=1\).
This code computes a worst-case guarantee for the Krasnolselskii-Mann (KM) method with constant step-size. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\frac{1}{4}\|x_n - Ax_n\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the KM method, and \(x_\star\) is some fixed point of \(A\) (i.e., \(x_\star=Ax_\star\)).
Algorithm: The constant step-size KM method is described by
\[x_{t+1} = \left(1 - \gamma\right) x_{t} + \gamma Ax_{t}.\]Theoretical guarantee: A theoretical upper bound is provided by [1, Theorem 4.9]
\[\begin{split}\tau(n) = \left\{ \begin{eqnarray} \frac{1}{n+1}\left(\frac{n}{n+1}\right)^n \frac{1}{4 \gamma (1 - \gamma)}\quad & \text{if } \frac{1}{2}\leqslant \gamma \leqslant \frac{1}{2}\left(1+\sqrt{\frac{n}{n+1}}\right) \\ (\gamma - 1)^{2n} \quad & \text{if } \frac{1}{2}\left(1+\sqrt{\frac{n}{n+1}}\right) < \gamma \leqslant 1. \end{eqnarray} \right.\end{split}\]Reference:
- Parameters
n (int) – number of iterations.
gamma (float) – step-size between 1/2 and 1
verbose (int) –
Level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + CVXPY details.
- Returns
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> pepit_tau, theoretical_tau = wc_krasnoselskii_mann_constant_step_sizes(n=3, gamma=3 / 4, verbose=1) (PEPit) Setting up the problem: size of the main PSD matrix: 6x6 (PEPit) Setting up the problem: performance measure is minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) function 1 : Adding 20 scalar constraint(s) ... function 1 : 20 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: SCS); optimal value: 0.14062586461718285 *** Example file: worst-case performance of Kranoselskii-Mann iterations *** PEPit guarantee: 1/4||xN - AxN||^2 <= 0.140626 ||x0 - x_*||^2 Theoretical guarantee: 1/4||xN - AxN||^2 <= 0.140625 ||x0 - x_*||^2
6.4. Krasnoselskii-Mann with increasing step-sizes
- PEPit.examples.fixed_point_problems.wc_krasnoselskii_mann_increasing_step_sizes(n, verbose=1)[source]
Consider the fixed point problem
\[\mathrm{Find}\, x:\, x = Ax,\]where \(A\) is a non-expansive operator, that is a \(L\)-Lipschitz operator with \(L=1\).
This code computes a worst-case guarantee for the Krasnolselskii-Mann method. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\frac{1}{4}\|x_n - Ax_n\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the KM method, and \(x_\star\) is some fixed point of \(A\) (i.e., \(x_\star=Ax_\star\)).
Algorithm: The KM method is described by
\[x_{t+1} = \frac{1}{t + 2} x_{t} + \left(1 - \frac{1}{t + 2}\right) Ax_{t}.\]Reference: This scheme was first studied using PEPs in [1].
- Parameters
n (int) – number of iterations.
verbose (int) –
Level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + CVXPY details.
- Returns
pepit_tau (float) – worst-case value
theoretical_tau (None) – no theoretical value
Example
>>> pepit_tau, theoretical_tau = wc_krasnoselskii_mann_increasing_step_sizes(n=3, verbose=1) (PEPit) Setting up the problem: size of the main PSD matrix: 6x6 (PEPit) Setting up the problem: performance measure is minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) function 1 : Adding 20 scalar constraint(s) ... function 1 : 20 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: SCS); optimal value: 0.11963406474148795 *** Example file: worst-case performance of Kranoselskii-Mann iterations *** PEPit guarantee: 1/4 ||xN - AxN||^2 <= 0.119634 ||x0 - x_*||^2