5 Monotone inclusions and variational inequalities
5.1 Proximal point
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_proximal_point(alpha, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax,\]where \(A\) is maximally monotone. We denote \(J_A = (I + A)^{-1}\) the resolvent of \(A\).
This code computes a worst-case guarantee for the proximal point method. That, it computes the smallest possible \(\tau(n, \alpha)\) such that the guarantee
\[\|x_n - x_{n-1}\|^2 \leqslant \tau(n, \alpha) \|x_0 - x_\star\|^2,\]is valid, where \(x_\star\) is such that \(0 \in Ax_\star\).
Algorithm: The proximal point algorithm for monotone inclusions is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\[x_{t+1} = J_{\alpha A}(x_t),\]where \(\alpha\) is a step-size.
Theoretical guarantee: A tight theoretical guarantee can be found in [1, section 4].
\[\|x_n - x_{n-1}\|^2 \leqslant \frac{\left(1 - \frac{1}{n}\right)^{n - 1}}{n} \|x_0 - x_\star\|^2.\]Reference:
- Parameters:
alpha (float) – the step-size.
n (int) – number of iterations.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (float) – theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_proximal_point(alpha=2, n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 12x12 (PEPit) Setting up the problem: performance measure is the 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 55 scalar constraint(s) ... Function 1 : 55 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.03874204628793616 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.9056550408154925e-09 All the primal scalar constraints are verified up to an error of 5.786269234586694e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 5.069583051964255e-08 (PEPit) Final upper bound (dual): 0.03874204889858147 and lower bound (primal example): 0.03874204628793616 (PEPit) Duality gap: absolute: 2.610645304101933e-09 and relative: 6.738532303377218e-08 *** Example file: worst-case performance of the Proximal Point Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 <= 0.038742 ||x0 - xs||^2 Theoretical guarantee: ||x(n) - x(n-1)||^2 <= 0.038742 ||x0 - xs||^2
5.2 Accelerated proximal point
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_accelerated_proximal_point(alpha, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax,\]where \(A\) is maximally monotone. We denote \(J_A = (I + A)^{-1}\) the resolvent of \(A\).
This code computes a worst-case guarantee for the accelerated proximal point method proposed in [1]. That, it computes the smallest possible \(\tau(n, \alpha)\) such that the guarantee
\[\|x_n - y_n\|^2 \leqslant \tau(n, \alpha) \|x_0 - x_\star\|^2,\]is valid, where \(x_\star\) is such that \(0 \in Ax_\star\).
Algorithm: Accelerated proximal point is described as follows, for \(t \in \{ 0, \dots, n-1\}\)
\[\begin{split}\begin{eqnarray} x_{t+1} & = & J_{\alpha A}(y_t), \\ y_{t+1} & = & x_{t+1} + \frac{t}{t+2}(x_{t+1} - x_{t}) - \frac{t}{t+2}(x_t - y_{t-1}), \end{eqnarray}\end{split}\]where \(x_0=y_0=y_{-1}\)
Theoretical guarantee: A tight theoretical worst-case guarantee can be found in [1, Theorem 4.1], for \(n \geqslant 1\),
\[\|x_n - y_{n-1}\|^2 \leqslant \frac{1}{n^2} \|x_0 - x_\star\|^2.\]Reference:
- Parameters:
alpha (float) – the step-size
n (int) – number of iterations.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> pepit_tau, theoretical_tau = wc_accelerated_proximal_point(alpha=2, n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 12x12 (PEPit) Setting up the problem: performance measure is the 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 55 scalar constraint(s) ... Function 1 : 55 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.010000025590611602 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.5895117470294495e-09 All the primal scalar constraints are verified up to an error of 7.4593002417217e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 4.728277936710436e-08 (PEPit) Final upper bound (dual): 0.01000002789002249 and lower bound (primal example): 0.010000025590611602 (PEPit) Duality gap: absolute: 2.2994108873908292e-09 and relative: 2.2994050030727943e-07 *** Example file: worst-case performance of the Accelerated Proximal Point Method*** PEPit guarantee: ||x_n - y_n||^2 <= 0.01 ||x_0 - x_s||^2 Theoretical guarantee: ||x_n - y_n||^2 <= 0.01 ||x_0 - x_s||^2
5.3 Optimal Strongly-monotone Proximal Point
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_optimal_strongly_monotone_proximal_point(n, mu, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax,\]where \(A\) is maximally \(\mu\)-strongly monotone. We denote by \(J_{A}\) the resolvent of \(A\).
For any \(x\) such that \(x = J_{A} y\) for some \(y\), define the resolvent residual \(\tilde{A}x = y - J_{A}y \in Ax\).
This code computes a worst-case guarantee for the Optimal Strongly-monotone Proximal Point Method (OS-PPM). That is, it computes the smallest possible \(\tau(n, \mu)\) such that the guarantee
\[\|\tilde{A}x_n\|^2 \leqslant \tau(n, \mu) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the Optimal Strongly-monotone Proximal Point Method, and \(x_\star\) is a zero of \(A\). In short, for a given value of \(n, \mu\), \(\tau(n, \mu)\) is computed as the worst-case value of \(\|\tilde{A}x_n\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: The Optimal Strongly-monotone Proximal Point Method can be written as
\begin{eqnarray} x_{t+1} & = & J_{A} y_t,\\ y_{t+1} & = & x_{t+1} + \frac{\varphi_{t} - 1}{\varphi_{t+1}} (x_{t+1} - x_t) - \frac{2 \mu \varphi_{t}}{\varphi_{t+1}} (y_t - x_{t+1}) \\ & & + \frac{(1+2\mu) \varphi_{t-1}}{\varphi_{t+1}} (y_{t-1} - x_t). \end{eqnarray}where \(\varphi_k = \sum_{i=0}^k (1+2\mu)^{2i}\) with \(\varphi_{-1}=0\) and \(x_0 = y_0 = y_{-1}\) is a starting point.
This method is equivalent to the Optimal Contractive Halpern iteration.
Theoretical guarantee: A tight worst-case guarantee for the Optimal Strongly-monotone Proximal Point Method can be found in [1, Theorem 3.2, Corollary 4.2]:
\[\|\tilde{A}x_n\|^2 \leqslant \left( \frac{1}{\sum_{k=0}^{N-1} (1+2\mu)^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.
mu (float) – \(\mu \ge 0\). \(A\) will be maximal \(\mu\)-strongly monotone.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (float) – theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_optimal_strongly_monotone_proximal_point(n=10, mu=0.05, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 12x12 (PEPit) Setting up the problem: performance measure is the 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 55 scalar constraint(s) ... Function 1 : 55 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.003936989547264896 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.0607852269985061e-09 All the primal scalar constraints are verified up to an error of 3.535184401522195e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.8038520857887303e-08 (PEPit) Final upper bound (dual): 0.0039369906212799455 and lower bound (primal example): 0.003936989547264896 (PEPit) Duality gap: absolute: 1.0740150496388323e-09 and relative: 2.728010924959076e-07 *** Example file: worst-case performance of Optimal Strongly-monotone Proximal Point Method *** PEPit guarantee: ||AxN||^2 <= 0.00393699 ||x0 - x_*||^2 Theoretical guarantee: ||AxN||^2 <= 0.00393698 ||x0 - x_*||^2
5.4 Douglas Rachford Splitting
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_douglas_rachford_splitting(L, mu, alpha, theta, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax + Bx,\]where \(A\) is \(L\)-Lipschitz and maximally monotone and \(B\) is (maximally) \(\mu\)-strongly monotone. We denote by \(J_{\alpha A}\) and \(J_{\alpha B}\) the resolvents of respectively \(\alpha A\) and \(\alpha B\).
This code computes a worst-case guarantee for the Douglas-Rachford splitting (DRS). That is, given two initial points \(w^{(0)}_t\) and \(w^{(1)}_t\), this code computes the smallest possible \(\tau(L, \mu, \alpha, \theta)\) (a.k.a. “contraction factor”) such that the guarantee
\[\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2 \leqslant \tau(L, \mu, \alpha, \theta) \|w^{(0)}_{t} - w^{(1)}_{t}\|^2,\]is valid, where \(w^{(0)}_{t+1}\) and \(w^{(1)}_{t+1}\) are obtained after one iteration of DRS from respectively \(w^{(0)}_{t}\) and \(w^{(1)}_{t}\).
In short, for given values of \(L\), \(\mu\), \(\alpha\) and \(\theta\), the contraction factor \(\tau(L, \mu, \alpha, \theta)\) is computed as the worst-case value of \(\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2\) when \(\|w^{(0)}_{t} - w^{(1)}_{t}\|^2 \leqslant 1\).
Algorithm: One iteration of the Douglas-Rachford splitting is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} x_{t+1} & = & J_{\alpha B} (w_t),\\ y_{t+1} & = & J_{\alpha A} (2x_{t+1}-w_t),\\ w_{t+1} & = & w_t - \theta (x_{t+1}-y_{t+1}). \end{eqnarray}Theoretical guarantee: Theoretical worst-case guarantees can be found in [1, section 4, Theorem 4.3]. Since the results of [2] tighten that of [1], we compare with [2, Theorem 4.3] below. The theoretical results are complicated and we do not copy them here.
References: The detailed PEP methodology for studying operator splitting is provided in [2].
- Parameters:
L (float) – the Lipschitz parameter.
mu (float) – the strongly monotone parameter.
alpha (float) – the step-size in the resolvent.
theta (float) – algorithm parameter.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (float) – theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_douglas_rachford_splitting(L=1, mu=.1, alpha=1.3, theta=.9, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 6x6 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 2 scalar constraint(s) ... Function 1 : 2 scalar constraint(s) added Function 2 : Adding 1 scalar constraint(s) ... Function 2 : 1 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.9287707078375604 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 3.297222217534066e-09 All the primal scalar constraints are verified up to an error of 1.6497672117310458e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.485426757210419e-07 (PEPit) Final upper bound (dual): 0.9287707057276714 and lower bound (primal example): 0.9287707078375604 (PEPit) Duality gap: absolute: -2.109889041257418e-09 and relative: -2.271700672138803e-09 *** Example file: worst-case performance of the Douglas Rachford Splitting*** PEPit guarantee: ||w_(t+1)^0 - w_(t+1)^1||^2 <= 0.928771 ||w_(t)^0 - w_(t)^1||^2 Theoretical guarantee: ||w_(t+1)^0 - w_(t+1)^1||^2 <= 0.928771 ||w_(t)^0 - w_(t)^1||^2
5.5 Douglas Rachford Splitting 2
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_douglas_rachford_splitting_2(beta, mu, alpha, theta, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax + Bx,\]where \(A\) is \(\beta\)-cocoercive and maximally monotone and \(B\) is (maximally) \(\mu\)-strongly monotone. We denote by \(J_{\alpha A}\) and \(J_{\alpha B}\) the resolvents of respectively \(\alpha A\) and \(\alpha B\).
This code computes a worst-case guarantee for the Douglas-Rachford splitting (DRS). That is, given two initial points \(w^{(0)}_t\) and \(w^{(1)}_t\), this code computes the smallest possible \(\tau(\beta, \mu, \alpha, \theta)\) (a.k.a. “contraction factor”) such that the guarantee
\[\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2 \leqslant \tau(\beta, \mu, \alpha, \theta) \|w^{(0)}_{t} - w^{(1)}_{t}\|^2,\]is valid, where \(w^{(0)}_{t+1}\) and \(w^{(1)}_{t+1}\) are obtained after one iteration of DRS from respectively \(w^{(0)}_{t}\) and \(w^{(1)}_{t}\).
In short, for given values of \(\beta\), \(\mu\), \(\alpha\) and \(\theta\), the contraction factor \(\tau(\beta, \mu, \alpha, \theta)\) is computed as the worst-case value of \(\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2\) when \(\|w^{(0)}_{t} - w^{(1)}_{t}\|^2 \leqslant 1\).
Algorithm: One iteration of the Douglas-Rachford splitting is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} x_{t+1} & = & J_{\alpha B} (w_t),\\ y_{t+1} & = & J_{\alpha A} (2x_{t+1}-w_t),\\ w_{t+1} & = & w_t - \theta (x_{t+1}-y_{t+1}). \end{eqnarray}Theoretical guarantee: Theoretical worst-case guarantees can be found in [1, section 4, Theorem 4.1].
References: The detailed PEP methodology for studying operator splitting is provided in [1].
- Parameters:
beta (float) – the Lipschitz parameter.
mu (float) – the strongly monotone parameter.
alpha (float) – the step-size in the resolvent.
theta (float) – algorithm parameter.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (float) – theoretical value.
Example
>>> beta, mu, alpha, theta = 1.2, 0.1, 0.3, 1.5 >>> pepit_tau, theoretical_tau = wc_douglas_rachford_splitting_2(beta=beta, mu=mu, alpha=alpha, theta=theta, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 6x6 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 1 scalar constraint(s) ... Function 1 : 1 scalar constraint(s) added Function 2 : Adding 1 scalar constraint(s) ... Function 2 : 1 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.9145301164750972 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 5.115160308023067e-10 All the primal scalar constraints are verified up to an error of 1.8039681970449806e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.2557649586852904e-08 (PEPit) Final upper bound (dual): 0.9145301167694716 and lower bound (primal example): 0.9145301164750972 (PEPit) Duality gap: absolute: 2.9437441373403317e-10 and relative: 3.218859701074142e-10 *** Example file: worst-case performance of the Douglas Rachford Splitting*** PEPit guarantee: ||w_(t+1)^0 - w_(t+1)^1||^2 <= 0.91453 ||w_(t)^0 - w_(t)^1||^2 Theoretical guarantee: ||w_(t+1)^0 - w_(t+1)^1||^2 <= 0.91453 ||w_(t)^0 - w_(t)^1||^2
5.6 Three operator splitting
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_three_operator_splitting(L, mu, beta, alpha, theta, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax + Bx + Cx,\]where \(A\) is maximally monotone, \(B\) is \(\beta\)-cocoercive and C is the gradient of some \(L\)-smooth \(\mu\)-strongly convex function. We denote by \(J_{\alpha A}\) and \(J_{\alpha B}\) the resolvents of respectively \(\alpha A\) and \(\alpha B\).
This code computes a worst-case guarantee for the three operator splitting (TOS). That is, given two initial points \(w^{(0)}_t\) and \(w^{(1)}_t\), this code computes the smallest possible \(\tau(L, \mu, \beta, \alpha, \theta)\) (a.k.a. “contraction factor”) such that the guarantee
\[\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2 \leqslant \tau(L, \mu, \beta, \alpha, \theta) \|w^{(0)}_{t} - w^{(1)}_{t}\|^2,\]is valid, where \(w^{(0)}_{t+1}\) and \(w^{(1)}_{t+1}\) are obtained after one iteration of TOS from respectively \(w^{(0)}_{t}\) and \(w^{(1)}_{t}\).
In short, for given values of \(L\), \(\mu\), \(\beta\), \(\alpha\) and \(\theta\), the contraction factor \(\tau(L, \mu, \beta, \alpha, \theta)\) is computed as the worst-case value of \(\|w^{(0)}_{t+1} - w^{(1)}_{t+1}\|^2\) when \(\|w^{(0)}_{t} - w^{(1)}_{t}\|^2 \leqslant 1\).
Algorithm: One iteration of the algorithm is described in [1]. For \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} x_{t+1} & = & J_{\alpha B} (w_t),\\ y_{t+1} & = & J_{\alpha A} (2x_{t+1} - w_t - C x_{t+1}),\\ w_{t+1} & = & w_t - \theta (x_{t+1} - y_{t+1}). \end{eqnarray}References: The TOS was proposed in [1], the analysis of such operator splitting methods using PEPs was proposed in [2].
- Parameters:
L (float) – smoothness constant of C.
mu (float) – strong convexity of C.
beta (float) – cocoercivity of B.
alpha (float) – step-size (in the resolvents).
theta (float) – overrelaxation parameter.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (None) – no theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_three_operator_splitting(L=1, mu=.1, beta=1, alpha=.9, theta=1.3, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 8x8 (PEPit) Setting up the problem: performance measure is the 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 3 function(s) Function 1 : Adding 1 scalar constraint(s) ... Function 1 : 1 scalar constraint(s) added Function 2 : Adding 1 scalar constraint(s) ... Function 2 : 1 scalar constraint(s) added Function 3 : Adding 2 scalar constraint(s) ... Function 3 : 2 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.7796890707911133 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.0624581227994185e-08 All the primal scalar constraints are verified up to an error of 4.036798317841317e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.038567561950643e-06 (PEPit) Final upper bound (dual): 0.7796890635199042 and lower bound (primal example): 0.7796890707911133 (PEPit) Duality gap: absolute: -7.271209079284802e-09 and relative: -9.325780431816304e-09 *** Example file: worst-case contraction factor of the Three Operator Splitting *** PEPit guarantee: ||w_(t+1)^0 - w_(t+1)^1||^2 <= 0.779689 ||w_(t)^0 - w_(t)^1||^2
5.7 Optimistic gradient
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_optimistic_gradient(n, gamma, L, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone variational inequality
\[\mathrm{Find}\, x_\star \in C\text{ such that } \left<F(x_\star);x-x_\star\right> \geqslant 0\,\,\forall x\in C,\]where \(C\) is a closed convex set and \(F\) is maximally monotone and Lipschitz.
This code computes a worst-case guarantee for the optimistic gradient method. That, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\tilde{x}_n - \tilde{x}_{n-1}\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2,\]is valid, where \(\tilde{x}_n\) is the output of the optimistic gradient method and \(x_0\) its starting point.
Algorithm: The optimistic gradient method is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} \tilde{x}_{t} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t-1})], \\ {x}_{t+1} & = & \tilde{x}_t + \gamma (F(\tilde{x}_{t-1}) - F(\tilde{x}_t)). \end{eqnarray}where \(\gamma\) is some step-size.
Theoretical guarantee: The method and many variants of it are discussed in [1] and a PEP formulation suggesting a worst-case guarantee in \(O(1/n)\) can be found in [2, Appendix D].
References:
- Parameters:
n (int) – number of iterations.
gamma (float) – the step-size.
L (float) – the Lipschitz constant.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (None) – no theoretical bound.
Example
>>> pepit_tau, theoretical_tau = wc_optimistic_gradient(n=5, gamma=1/4, L=1, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 15x15 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 49 scalar constraint(s) ... Function 1 : 49 scalar constraint(s) added Function 2 : Adding 42 scalar constraint(s) ... Function 2 : 42 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.06631412717626445 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All the primal scalar constraints are verified up to an error of 2.911285089737814e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 2.0187221108482403e-08 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 9.533233993629353e-08 (PEPit) Final upper bound (dual): 0.06631413218999846 and lower bound (primal example): 0.06631412717626445 (PEPit) Duality gap: absolute: 5.013734011294346e-09 and relative: 7.560582073210024e-08 *** Example file: worst-case performance of the Optimistic Gradient Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 <= 0.0663141 ||x0 - xs||^2
5.8 Optimistic gradient (more expensive/less conservative version)
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_optimistic_gradient_refined(n, gamma, L, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone variational inequality
\[\mathrm{Find}\, x_\star \in C\text{ such that } \left<F(x_\star);x-x_\star\right> \geqslant 0\,\,\forall x\in C,\]where \(C\) is a closed convex set and \(F\) is maximally monotone and Lipschitz. In this example, we use the characterization of Lipschitz monotone operators provided in [3, Proposition 3.15] (which results in more computationnaly expensive PEPs to be solved).
This code computes a worst-case guarantee for the optimistic gradient method. That, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\tilde{x}_n - \tilde{x}_{n-1}\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2,\]is valid, where \(\tilde{x}_n\) is the output of the optimistic gradient method and \(x_0\) its starting point.
Algorithm: The optimistic gradient method is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} \tilde{x}_{t} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t-1})], \\ {x}_{t+1} & = & \tilde{x}_t + \gamma (F(\tilde{x}_{t-1}) - F(\tilde{x}_t)). \end{eqnarray}where \(\gamma\) is some step-size.
Theoretical guarantee: The method and many variants of it are discussed in [1] and a PEP formulation suggesting a worst-case guarantee in \(O(1/n)\) can be found in [2, Appendix D].
References:
- Parameters:
n (int) – number of iterations.
gamma (float) – the step-size.
L (float) – the Lipschitz constant.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (None) – no theoretical bound.
Example
>>> pepit_tau, theoretical_tau = wc_optimistic_gradient_refined(n=1, gamma=1/4, L=1, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 7x7 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 9 scalar constraint(s) ... Function 1 : 9 scalar constraint(s) added Function 2 : Adding 0 scalar constraint(s) ... Function 2 : 0 scalar constraint(s) added Function 2 : Adding 48 lmi constraint(s) ... Size of PSD matrix 1: 7x7 Size of PSD matrix 2: 7x7 Size of PSD matrix 3: 7x7 Size of PSD matrix 4: 7x7 Size of PSD matrix 5: 7x7 Size of PSD matrix 6: 7x7 Size of PSD matrix 7: 7x7 Size of PSD matrix 8: 7x7 Size of PSD matrix 9: 7x7 Size of PSD matrix 10: 7x7 Size of PSD matrix 11: 7x7 Size of PSD matrix 12: 7x7 Size of PSD matrix 13: 7x7 Size of PSD matrix 14: 7x7 Size of PSD matrix 15: 7x7 Size of PSD matrix 16: 7x7 Size of PSD matrix 17: 7x7 Size of PSD matrix 18: 7x7 Size of PSD matrix 19: 7x7 Size of PSD matrix 20: 7x7 Size of PSD matrix 21: 7x7 Size of PSD matrix 22: 7x7 Size of PSD matrix 23: 7x7 Size of PSD matrix 24: 7x7 Size of PSD matrix 25: 7x7 Size of PSD matrix 26: 7x7 Size of PSD matrix 27: 7x7 Size of PSD matrix 28: 7x7 Size of PSD matrix 29: 7x7 Size of PSD matrix 30: 7x7 Size of PSD matrix 31: 7x7 Size of PSD matrix 32: 7x7 Size of PSD matrix 33: 7x7 Size of PSD matrix 34: 7x7 Size of PSD matrix 35: 7x7 Size of PSD matrix 36: 7x7 Size of PSD matrix 37: 7x7 Size of PSD matrix 38: 7x7 Size of PSD matrix 39: 7x7 Size of PSD matrix 40: 7x7 Size of PSD matrix 41: 7x7 Size of PSD matrix 42: 7x7 Size of PSD matrix 43: 7x7 Size of PSD matrix 44: 7x7 Size of PSD matrix 45: 7x7 Size of PSD matrix 46: 7x7 Size of PSD matrix 47: 7x7 Size of PSD matrix 48: 7x7 Function 2 : 48 lmi constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 1.062499619318542 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All required PSD matrices are indeed positive semi-definite up to an error of 2.6762453073848446e-09 All the primal scalar constraints are verified up to an error of 4.417966050890063e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual matrices to lmi are positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 3.522728191736381e-08 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.5494369449556818e-05 (PEPit) Final upper bound (dual): 1.0624996259179762 and lower bound (primal example): 1.062499619318542 (PEPit) Duality gap: absolute: 6.599434110299285e-09 and relative: 6.211234329224494e-09 *** Example file: worst-case performance of the Optimistic Gradient Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 <= 1.0625 ||x0 - xs||^2
5.9 Optimistic gradient, cocoercive problem (more expensive/less conservative version)
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_optimistic_gradient_refined_cocoercive(n, gamma, beta, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone variational inequality
\[\mathrm{Find}\, x_\star \in C\text{ such that } \left<F(x_\star);x-x_\star\right> \geqslant 0\,\,\forall x\in C,\]where \(C\) is a closed convex set and \(F\) is maximally monotone and cocoercive. In this example, we use the characterization of cocoercive strongly monotone operators provided in [3, Proposition F.3] (which results in more computationnaly expensive PEPs to be solved).
This code computes a worst-case guarantee for the optimistic gradient method. That, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\tilde{x}_n - \tilde{x}_{n-1}\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2,\]is valid, where \(\tilde{x}_n\) is the output of the optimistic gradient method and \(x_0\) its starting point.
Algorithm: The optimistic gradient method is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} \tilde{x}_{t} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t-1})], \\ {x}_{t+1} & = & \tilde{x}_t + \gamma (F(\tilde{x}_{t-1}) - F(\tilde{x}_t)). \end{eqnarray}where \(\gamma\) is some step-size.
Theoretical guarantee: The method and many variants of it are discussed in [1] and a PEP formulation suggesting a worst-case guarantee in \(O(1/n)\) (when \(\mu=0\)) can be found in [2, Appendix D].
References:
- Parameters:
n (int) – number of iterations.
gamma (float) – the step-size.
mu (float) – strong monotonicity.
beta (float) – the cocoercivity constant.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (None) – no theoretical bound.
Example
>>> pepit_tau, theoretical_tau = wc_optimistic_gradient_refined_cocoercive(n=1, gamma=1/4, beta=1/4, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 7x7 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 9 scalar constraint(s) ... Function 1 : 9 scalar constraint(s) added Function 2 : Adding 0 scalar constraint(s) ... Function 2 : 0 scalar constraint(s) added Function 2 : Adding 48 lmi constraint(s) ... Size of PSD matrix 1: 7x7 Size of PSD matrix 2: 7x7 Size of PSD matrix 3: 7x7 Size of PSD matrix 4: 7x7 Size of PSD matrix 5: 7x7 Size of PSD matrix 6: 7x7 Size of PSD matrix 7: 7x7 Size of PSD matrix 8: 7x7 Size of PSD matrix 9: 7x7 Size of PSD matrix 10: 7x7 Size of PSD matrix 11: 7x7 Size of PSD matrix 12: 7x7 Size of PSD matrix 13: 7x7 Size of PSD matrix 14: 7x7 Size of PSD matrix 15: 7x7 Size of PSD matrix 16: 7x7 Size of PSD matrix 17: 7x7 Size of PSD matrix 18: 7x7 Size of PSD matrix 19: 7x7 Size of PSD matrix 20: 7x7 Size of PSD matrix 21: 7x7 Size of PSD matrix 22: 7x7 Size of PSD matrix 23: 7x7 Size of PSD matrix 24: 7x7 Size of PSD matrix 25: 7x7 Size of PSD matrix 26: 7x7 Size of PSD matrix 27: 7x7 Size of PSD matrix 28: 7x7 Size of PSD matrix 29: 7x7 Size of PSD matrix 30: 7x7 Size of PSD matrix 31: 7x7 Size of PSD matrix 32: 7x7 Size of PSD matrix 33: 7x7 Size of PSD matrix 34: 7x7 Size of PSD matrix 35: 7x7 Size of PSD matrix 36: 7x7 Size of PSD matrix 37: 7x7 Size of PSD matrix 38: 7x7 Size of PSD matrix 39: 7x7 Size of PSD matrix 40: 7x7 Size of PSD matrix 41: 7x7 Size of PSD matrix 42: 7x7 Size of PSD matrix 43: 7x7 Size of PSD matrix 44: 7x7 Size of PSD matrix 45: 7x7 Size of PSD matrix 46: 7x7 Size of PSD matrix 47: 7x7 Size of PSD matrix 48: 7x7 Function 2 : 48 lmi constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 1.333333140563453 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All required PSD matrices are indeed positive semi-definite up to an error of 3.5890351499672374e-09 All the primal scalar constraints are verified (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual matrices to lmi are positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 1.221621779541138e-08 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 4.5245921878695306e-06 (PEPit) Final upper bound (dual): 1.3333331393149042 and lower bound (primal example): 1.333333140563453 (PEPit) Duality gap: absolute: -1.2485488198876737e-09 and relative: -9.364117502997411e-10 *** Example file: worst-case performance of the Optimistic Gradient Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 <= 1.33333 ||x0 - xs||^2
5.10 Past extragradient
- PEPit.examples.monotone_inclusions_variational_inequalities.wc_past_extragradient(n, gamma, L, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the monotone variational inequality
\[\mathrm{Find}\, x_\star \in C\text{ such that } \left<F(x_\star);x-x_\star\right> \geqslant 0\,\,\forall x\in C,\]where \(C\) is a closed convex set and \(F\) is maximally monotone and Lipschitz.
This code computes a worst-case guarantee for the past extragradient method. That, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|x_n - x_{n-1}\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the past extragradient method and \(x_0\) its starting point.
Algorithm: The past extragradient method is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} \tilde{x}_{t} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t-1})], \\ {x}_{t+1} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t})]. \end{eqnarray}where \(\gamma\) is some step-size.
Theoretical guarantee: The method and many variants of it are discussed in [1]. A worst-case guarantee in \(O(1/n)\) can be found in [2, 3].
References:
- Parameters:
n (int) – number of iterations.
gamma (float) – the step-size.
L (float) – the Lipschitz constant.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
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 + solver details.
- Returns:
pepit_tau (float) – worst-case value.
theoretical_tau (None) – no theoretical bound.
Example
>>> pepit_tau, theoretical_tau = wc_past_extragradient(n=5, gamma=1 / 4, L=1, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 20x20 (PEPit) Setting up the problem: performance measure is the 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 2 function(s) Function 1 : Adding 144 scalar constraint(s) ... Function 1 : 144 scalar constraint(s) added Function 2 : Adding 42 scalar constraint(s) ... Function 2 : 42 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.06026638366058837 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.0022302278988268e-09 All the primal scalar constraints are verified up to an error of 8.796389172616159e-10 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 6.659076198893817e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.8117161796698436e-08 (PEPit) Final upper bound (dual): 0.060266385363880064 and lower bound (primal example): 0.06026638366058837 (PEPit) Duality gap: absolute: 1.7032916951875698e-09 and relative: 2.8262716156659814e-08 *** Example file: worst-case performance of the Past Extragradient Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 <= 0.0602664 ||x0 - xs||^2