10. Low dimensional worst-cases scenarios
10.1. Inexact gradient
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_inexact_gradient(L, mu, epsilon, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is \(L\)-smooth and \(\mu\)-strongly convex.
This code computes a worst-case guarantee for an inexact gradient method and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee using \(10\) iterations of the logdet heuristic.
That is, it computes the smallest possible \(\tau(n,L,\mu,\varepsilon)\) such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n,L,\mu,\varepsilon) (f(x_0) - f_\star)\]is valid, where \(x_n\) is the output of the gradient descent with an inexact descent direction, and where \(x_\star\) is the minimizer of \(f\). Then, it looks for a low-dimensional nearly achieving this performance.
The inexact descent direction is assumed to satisfy a relative inaccuracy described by (with \(0 \leqslant \varepsilon \leqslant 1\))
\[\|\nabla f(x_t) - d_t\| \leqslant \varepsilon \|\nabla f(x_t)\|,\]where \(\nabla f(x_t)\) is the true gradient, and \(d_t\) is the approximate descent direction that is used.
Algorithm:
The inexact gradient descent under consideration can be written as
\[x_{t+1} = x_t - \frac{2}{L_{\varepsilon} + \mu_{\varepsilon}} d_t\]where \(d_t\) is the inexact search direction, \(L_{\varepsilon} = (1 + \varepsilon)L\) and \(\mu_{\varepsilon} = (1-\varepsilon) \mu\).
Theoretical guarantee:
A tight worst-case guarantee obtained in [1, Theorem 5.3] or [2, Remark 1.6] is
\[f(x_n) - f_\star \leqslant \left(\frac{L_{\varepsilon} - \mu_{\varepsilon}}{L_{\varepsilon} + \mu_{\varepsilon}}\right)^{2n}(f(x_0) - f_\star ),\]with \(L_{\varepsilon} = (1 + \varepsilon)L\) and \(\mu_{\varepsilon} = (1-\varepsilon) \mu\). This guarantee is achieved on one-dimensional quadratic functions.
References:The detailed analyses can be found in [1, 2]. The logdet heuristic is presented in [3].
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
epsilon (float) – level of inaccuracy
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_inexact_gradient(L=1, mu=0.1, epsilon=0.1, n=6, 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 1 function(s) Function 1 : Adding 56 scalar constraint(s) ... Function 1 : 56 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 1 function(s) Function 1 : Adding 6 scalar constraint(s) ... Function 1 : 6 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.13973101296945833 (PEPit) Postprocessing: 3 eigenvalue(s) > 2.99936924706653e-06 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101314530774 (PEPit) Postprocessing: 1 eigenvalue(s) > 7.356394561198437e-08 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101333230654 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101314132523 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101315746582 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 4 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101311324322 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 5 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101297326166 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 6 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101303966996 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.216071300777247e-12 after 7 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101306836934 (PEPit) Postprocessing: 1 eigenvalue(s) > 7.45808567822026e-12 after 8 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101314164972 (PEPit) Postprocessing: 1 eigenvalue(s) > 6.382593300104802e-12 after 9 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101344891796 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 10 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101344891796 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 3.749538388559788e-11 All the primal scalar constraints are verified up to an error of 6.561007293015564e-11 (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.481776410060961e-07 (PEPit) Final upper bound (dual): 0.13973101221655027 and lower bound (primal example): 0.13963101344891796 (PEPit) Duality gap: absolute: 9.999876763230886e-05 and relative: 0.0007161644477277393 *** Example file: worst-case performance of inexact gradient *** PEPit guarantee: f(x_n)-f_* == 0.139731 (f(x_0)-f_*) Theoretical guarantee: f(x_n)-f_* <= 0.139731 (f(x_0)-f_*)
10.2. Non-convex gradient descent
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_gradient_descent(L, gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is \(L\)-smooth.
This code computes a worst-case guarantee for gradient descent with fixed step-size \(\gamma\), and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. That is, it computes the smallest possible \(\tau(n, L, \gamma)\) such that the guarantee
\[\min_{t\leqslant n} \|\nabla f(x_t)\|^2 \leqslant \tau(n, L, \gamma) (f(x_0) - f(x_n))\]is valid, where \(x_n\) is the n-th iterates obtained with the gradient method with fixed step-size. Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm: Gradient descent is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\[x_{t+1} = x_t - \gamma \nabla f(x_t),\]where \(\gamma\) is a step-size and.
Theoretical guarantee: When \(\gamma \leqslant \frac{1}{L}\), an empirically tight theoretical worst-case guarantee is
\[\min_{t\leqslant n} \|\nabla f(x_t)\|^2 \leqslant \frac{4}{3}\frac{L}{n} (f(x_0) - f(x_n)),\]see discussions in [1, page 190] and [2].
References:
- Parameters:
L (float) – the smoothness parameter.
gamma (float) – 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
>>> L = 1 >>> gamma = 1 / L >>> pepit_tau, theoretical_tau = wc_gradient_descent(L=L, gamma=gamma, n=5, 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 6 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 30 scalar constraint(s) ... Function 1 : 30 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.26666666551166657 (PEPit) Postprocessing: 7 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.266566659234068 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.1259768792760665e-07 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.26656666877866464 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.26656666877866464 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 6.201211870048895e-11 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 scalar values associated with inequality constraints are nonnegative up to an error of 4.5045561757111027e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 4.491578307483797e-09 (PEPit) Final upper bound (dual): 0.2666666657156721 and lower bound (primal example): 0.26656666877866464 (PEPit) Duality gap: absolute: 9.99969370074627e-05 and relative: 0.000375129184251059 *** Example file: worst-case performance of gradient descent with fixed step-size *** PEPit guarantee: min_i ||f'(x_i)||^2 == 0.266667 (f(x_0)-f_*) Theoretical guarantee: min_i ||f'(x_i)||^2 <= 0.266667 (f(x_0)-f_*)
10.3. Optimized gradient
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_optimized_gradient(L, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is \(L\)-smooth and convex.
This code computes a worst-case guarantee for optimized gradient method (OGM), and applies the trace heuristic for trying to find a low-dimensional worst-case example on which this guarantee is nearly achieved. That is, it computes the smallest possible \(\tau(n, L)\) such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of OGM and where \(x_\star\) is a minimizer of \(f\). Then, it applies the trace heuristic, which allows obtaining a one-dimensional function on which the guarantee is nearly achieved.
Algorithm: The optimized gradient method is described by
\begin{eqnarray} x_{t+1} & = & y_t - \frac{1}{L} \nabla f(y_t)\\ y_{t+1} & = & x_{t+1} + \frac{\theta_{t}-1}{\theta_{t+1}}(x_{t+1}-x_t)+\frac{\theta_{t}}{\theta_{t+1}}(x_{t+1}-y_t), \end{eqnarray}with
\begin{eqnarray} \theta_0 & = & 1 \\ \theta_t & = & \frac{1 + \sqrt{4 \theta_{t-1}^2 + 1}}{2}, \forall t \in [|1, n-1|] \\ \theta_n & = & \frac{1 + \sqrt{8 \theta_{n-1}^2 + 1}}{2}. \end{eqnarray}Theoretical guarantee: The tight theoretical guarantee can be found in [2, Theorem 2]:
\[f(x_n)-f_\star \leqslant \frac{L\|x_0-x_\star\|^2}{2\theta_n^2}.\]References: The OGM was developed in [1,2]. Low-dimensional worst-case functions for OGM were obtained in [3, 4].
- Parameters:
L (float) – the smoothness parameter.
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_optimized_gradient(L=3, n=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 1 function(s) Function 1 : Adding 30 scalar constraint(s) ... Function 1 : 30 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.0767518265733206 (PEPit) Postprocessing: 6 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.0766518263678761 (PEPit) Postprocessing: 1 eigenvalue(s) > 8.430457643734283e-09 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 5.872825531822352e-11 All the primal scalar constraints are verified up to an error of 1.9493301200643187e-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 2.3578267940913163e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.653093053290753e-08 (PEPit) Final upper bound (dual): 0.0767518302587488 and lower bound (primal example): 0.0766518263678761 (PEPit) Duality gap: absolute: 0.00010000389087269634 and relative: 0.0013046511167619983 *** Example file: worst-case performance of optimized gradient method *** PEPit guarantee: f(y_n)-f_* == 0.0767518 ||x_0 - x_*||^2 Theoretical guarantee: f(y_n)-f_* <= 0.0767518 ||x_0 - x_*||^2
10.4. Frank Wolfe
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_frank_wolfe(L, D, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is \(L\)-smooth and convex and where \(f_2\) is a convex indicator function on \(\mathcal{D}\) of diameter at most \(D\).
This code computes a worst-case guarantee for the conditional gradient method, aka Frank-Wolfe method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee using \(12\) iterations of the logdet heuristic. That is, it computes the smallest possible \(\tau(n, L)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, L) D^2,\]is valid, where x_n is the output of the conditional gradient method, and where \(x_\star\) is a minimizer of \(F\). In short, for given values of \(n\) and \(L\), \(\tau(n, L)\) is computed as the worst-case value of \(F(x_n) - F(x_\star)\) when \(D \leqslant 1\). Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm:
This method was first presented in [1]. A more recent version can be found in, e.g., [2, Algorithm 1]. For \(t \in \{0, \dots, n-1\}\),
\[\begin{split}\begin{eqnarray} y_t & = & \arg\min_{s \in \mathcal{D}} \langle s \mid \nabla f_1(x_t) \rangle, \\ x_{t+1} & = & \frac{t}{t + 2} x_t + \frac{2}{t + 2} y_t. \end{eqnarray}\end{split}\]Theoretical guarantee:
An upper guarantee obtained in [2, Theorem 1] is
\[F(x_n) - F(x_\star) \leqslant \frac{2L D^2}{n+2}.\]References: The algorithm is presented in, among others, [1, 2]. The logdet heuristic is presented in [3].
[1] M .Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2), 95-110.
- Parameters:
L (float) – the smoothness parameter.
D (float) – diameter of \(f_2\).
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_frank_wolfe(L=1, D=1, n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 26x26 (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 (0 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 2 function(s) Function 1 : Adding 132 scalar constraint(s) ... Function 1 : 132 scalar constraint(s) added Function 2 : Adding 325 scalar constraint(s) ... Function 2 : 325 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.07828953904645822 (PEPit) Postprocessing: 15 eigenvalue(s) > 1.6888130186731306e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953725941896 (PEPit) Postprocessing: 11 eigenvalue(s) > 1.1861651266980264e-08 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953903506054 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953903905457 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953893599122 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 4 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953897127347 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 5 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953853593198 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 6 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953853593198 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 4.838754901390161e-10 All the primal scalar constraints are verified up to an error of 9.411701695771768e-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 3.474580080029191e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.2084335345375351e-07 (PEPit) Final upper bound (dual): 0.07828954284798424 and lower bound (primal example): 0.07818953853593198 (PEPit) Duality gap: absolute: 0.00010000431205225979 and relative: 0.0012789986221277267 *** Example file: worst-case performance of the Conditional Gradient (Frank-Wolfe) in function value *** PEPit guarantee: f(x_n)-f_* == 0.0782895 ||x0 - xs||^2 Theoretical guarantee: f(x_n)-f_* <= 0.166667 ||x0 - xs||^2
10.5. Proximal point
- PEPit.examples.low_dimensional_worst_cases_scenarios.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 resolvents of \(A\).
This code computes a worst-case guarantee for the proximal point method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee using the trace heuristic.
That is, 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\). Then, it looks for a low-dimensional nearly achieving this performance.
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.2, n=11, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 13x13 (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 66 scalar constraint(s) ... Function 1 : 66 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.0350493891186265 (PEPit) Postprocessing: 3 eigenvalue(s) > 6.668982718413771e-09 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03494938907009 (PEPit) Postprocessing: 2 eigenvalue(s) > 3.285085131308424e-10 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 4.8548497077664176e-11 All the primal scalar constraints are verified up to an error of 1.1291529170009973e-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 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.034322726414018e-08 (PEPit) Final upper bound (dual): 0.03504939011652487 and lower bound (primal example): 0.03494938907009 (PEPit) Duality gap: absolute: 0.00010000104643487218 and relative: 0.0028613102859773296 *** Example file: worst-case performance of the Proximal Point Method*** PEPit guarantee: ||x(n) - x(n-1)||^2 == 0.0350494 ||x0 - xs||^2 Theoretical guarantee: ||x(n) - x(n-1)||^2 <= 0.0350494 ||x0 - xs||^2
10.6. Halpern iteration
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_halpern_iteration(n, wrapper='cvxpy', solver=None, 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, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. 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\). Then, it looks for a low-dimensional nearly achieving this performance.
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.
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_halpern_iteration(n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 13x13 (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 66 scalar constraint(s) ... Function 1 : 66 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.03305790577349196 (PEPit) Postprocessing: 12 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.033047905727429217 (PEPit) Postprocessing: 1 eigenvalue(s) > 3.494895432655832e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790606633461 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790577532096 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.834729915591876e-13 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790577532096 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.834729915591876e-13 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.3350847983797365e-12 All the primal scalar constraints are verified up to an error of 5.296318938974309e-13 (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 5.146036222356589e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.81631899443615e-07 (PEPit) Final upper bound (dual): 0.03305791391531532 and lower bound (primal example): 0.03304790577532096 (PEPit) Duality gap: absolute: 1.0008139994355236e-05 and relative: 0.00030283734353385173 *** Example file: worst-case performance of Halpern Iterations *** PEPit guarantee: ||xN - AxN||^2 == 0.0330579 ||x0 - x_*||^2 Theoretical guarantee: ||xN - AxN||^2 <= 0.0330579 ||x0 - x_*||^2
10.7. Alternate projections
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_alternate_projections(n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex feasibility problem:
\[\mathrm{Find}\, x\in Q_1\cap Q_2\]where \(Q_1\) and \(Q_2\) are two closed convex sets.
This code computes a worst-case guarantee for the alternate projection method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the alternate projection method, and \(x_\star\in Q_1\cap Q_2\) is a solution to the convex feasibility problem.
In short, for a given value of \(n\), \(\tau(n)\) is computed as the worst-case value of \(\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\). Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm: The alternate projection method can be written as
\[\begin{split}\begin{eqnarray} y_{t+1} & = & \mathrm{Proj}_{Q_1}(x_t), \\ x_{t+1} & = & \mathrm{Proj}_{Q_2}(y_{t+1}). \end{eqnarray}\end{split}\]References: The first results on this method are due to [1]. Its translation in PEPs is due to [2].
- Parameters:
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 (None) – no theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_alternate_projections(n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 24x24 (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 121 scalar constraint(s) ... Function 2 : 121 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.018867679370681505 (PEPit) Postprocessing: 4 eigenvalue(s) > 5.512562645368077e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.018767679335018744 (PEPit) Postprocessing: 2 eigenvalue(s) > 2.7430816238284485e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.018767679335018744 (PEPit) Postprocessing: 2 eigenvalue(s) > 2.7430816238284485e-09 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.543305290992105e-10 All the primal scalar constraints are verified up to an error of 1.6319162687850053e-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 4.6567156492364636e-11 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.056980182671661e-08 (PEPit) Final upper bound (dual): 0.01886768010878965 and lower bound (primal example): 0.018767679335018744 (PEPit) Duality gap: absolute: 0.00010000077377090438 and relative: 0.0053283505107801065 *** Example file: worst-case performance of the alternate projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0188677 ||x0 - x_*||^2
10.8. Averaged projections
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_averaged_projections(n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex feasibility problem:
\[\mathrm{Find}\, x\in Q_1\cap Q_2\]where \(Q_1\) and \(Q_2\) are two closed convex sets.
This code computes a worst-case guarantee for the averaged projection method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the averaged projection method, and \(x_\star\in Q_1\cap Q_2\) is a solution to the convex feasibility problem.
In short, for a given value of \(n\), \(\tau(n)\) is computed as the worst-case value of \(\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\). Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm: The averaged projection method can be written as
\[\begin{eqnarray} x_{t+1} & = & \frac{1}{2} \left(\mathrm{Proj}_{Q_1}(x_t) + \mathrm{Proj}_{Q_2}(x_t)\right). \end{eqnarray}\]- Parameters:
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 (None) – no theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_averaged_projections(n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 25x25 (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 144 scalar constraint(s) ... Function 2 : 144 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.06844885734754097 (PEPit) Postprocessing: 4 eigenvalue(s) > 7.891514481701609e-10 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.06834885735342248 (PEPit) Postprocessing: 2 eigenvalue(s) > 6.225469110482089e-11 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.06834885735342248 (PEPit) Postprocessing: 2 eigenvalue(s) > 6.225469110482089e-11 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.9433797563300196e-12 All the primal scalar constraints are verified up to an error of 1.8770332510520404e-12 (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 9.778816524040534e-13 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.015729320638442e-10 (PEPit) Final upper bound (dual): 0.06844885735573535 and lower bound (primal example): 0.06834885735342248 (PEPit) Duality gap: absolute: 0.0001000000023128611 and relative: 0.0014630822838160252 *** Example file: worst-case performance of the averaged projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0684489 ||x0 - x_*||^2
10.9. Dykstra
- PEPit.examples.low_dimensional_worst_cases_scenarios.wc_dykstra(n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex feasibility problem:
\[\mathrm{Find}\, x\in Q_1\cap Q_2\]where \(Q_1\) and \(Q_2\) are two closed convex sets.
This code computes a worst-case guarantee for the Dykstra projection method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. That is, it computes the smallest possible \(\tau(n)\) such that the guarantee
\[\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]is valid, where \(x_n\) is the output of the Dykstra projection method, and \(x_\star\in Q_1\cap Q_2\) is a solution to the convex feasibility problem.
In short, for a given value of \(n\), \(\tau(n)\) is computed as the worst-case value of \(\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\). Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm: The Dykstra projection method can be written as
\[\begin{split}\begin{eqnarray} y_{t} & = & \mathrm{Proj}_{Q_1}(x_t+p_t), \\ p_{t+1} & = & x_t + p_t - y_t,\\ x_{t+1} & = & \mathrm{Proj}_{Q_2}(y_t+q_t),\\ q_{t+1} & = & y_t + q_t - x_{t+1}. \end{eqnarray}\end{split}\]References: This method is due to [1].
- Parameters:
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 (None) – no theoretical value.
Example
>>> pepit_tau, theoretical_tau = wc_dykstra(n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 24x24 (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 121 scalar constraint(s) ... Function 2 : 121 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.02575645181334978 (PEPit) Postprocessing: 6 eigenvalue(s) > 8.710562863672514e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.025656451810811397 (PEPit) Postprocessing: 3 eigenvalue(s) > 0.009447084376111912 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.025656451810811397 (PEPit) Postprocessing: 3 eigenvalue(s) > 0.009447084376111912 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.721634879362454e-12 All the primal scalar constraints are verified up to an error of 5.100808664337819e-12 (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.7781954429936124e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 9.97201083318334e-08 (PEPit) Final upper bound (dual): 0.025756455102383596 and lower bound (primal example): 0.025656451810811397 (PEPit) Duality gap: absolute: 0.00010000329157219823 and relative: 0.0038977833844529406 *** Example file: worst-case performance of the Dykstra projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0257565 ||x0 - x_*||^2