12 Low dimensional worst-cases scenarios
12.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.13973101021632428 (PEPit) Postprocessing: 3 eigenvalue(s) > 3.028518178869447e-06 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.1396310103564475 (PEPit) Postprocessing: 1 eigenvalue(s) > 9.047553817195615e-08 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101028561192 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101042304152 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101027602265 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 4 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101034245295 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 5 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.1396310103204911 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 6 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101022486266 (PEPit) Postprocessing: 1 eigenvalue(s) > 9.087483651128653e-13 after 7 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.1396310102399474 (PEPit) Postprocessing: 1 eigenvalue(s) > 8.535000475023181e-12 after 8 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.13963101023133517 (PEPit) Postprocessing: 1 eigenvalue(s) > 4.810079003044157e-13 after 9 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.1396310102275719 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 10 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.1396310102275719 (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 8.83270861025616e-13 All the primal scalar constraints are verified up to an error of 1.0150352780513572e-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 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.4160437804734643e-07 (PEPit) Final upper bound (dual): 0.1397310094213599 and lower bound (primal example): 0.1396310102275719 (PEPit) Duality gap: absolute: 9.999919378800293e-05 and relative: 0.0007161675162632091 *** 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_*)
12.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.2666666655116666 (PEPit) Postprocessing: 7 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.26656665923389067 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.1259924068173275e-07 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.2665666687640418 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.2665666687640418 (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.171828087683806e-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.5045553432130066e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 4.49157760320874e-09 (PEPit) Final upper bound (dual): 0.2666666657156721 and lower bound (primal example): 0.2665666687640418 (PEPit) Duality gap: absolute: 9.999695163032118e-05 and relative: 0.0003751292391279272 *** 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_*)
12.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.07675182658909867 (PEPit) Postprocessing: 6 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07665182638365314 (PEPit) Postprocessing: 1 eigenvalue(s) > 8.430486098367942e-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.872882200186105e-11 All the primal scalar constraints are verified up to an error of 1.9493406411622005e-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.3554960855935635e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.7023258253444443e-08 (PEPit) Final upper bound (dual): 0.07675183030228215 and lower bound (primal example): 0.07665182638365314 (PEPit) Duality gap: absolute: 0.00010000391862900748 and relative: 0.0013046514786023995 *** 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
12.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.07828953896022825 (PEPit) Postprocessing: 15 eigenvalue(s) > 1.6901731014750697e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953827556187 (PEPit) Postprocessing: 11 eigenvalue(s) > 5.259349500958895e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953894898742 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953893021713 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953878629332 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 4 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953886867731 (PEPit) Postprocessing: 11 eigenvalue(s) > 3.5625534521309287e-12 after 5 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953860484489 (PEPit) Postprocessing: 11 eigenvalue(s) > 0 after 6 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.07818953860484489 (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 3.3614813402196086e-10 All the primal scalar constraints are verified up to an error of 6.596046486784246e-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.4682721500621377e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.2155275372348722e-07 (PEPit) Final upper bound (dual): 0.07828954275558239 and lower bound (primal example): 0.07818953860484489 (PEPit) Duality gap: absolute: 0.00010000415073750657 and relative: 0.001278996557875966 *** 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
12.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.03504938911859705 (PEPit) Postprocessing: 3 eigenvalue(s) > 6.66897064282442e-09 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03494938907006561 (PEPit) Postprocessing: 2 eigenvalue(s) > 3.285089843486249e-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.854333827729659e-11 All the primal scalar constraints are verified up to an error of 1.1289407950143548e-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.0333995201109465e-08 (PEPit) Final upper bound (dual): 0.035049390116491635 and lower bound (primal example): 0.03494938907006561 (PEPit) Duality gap: absolute: 0.00010000104642602509 and relative: 0.0028613102857261864 *** 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
12.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.03305790577466909 (PEPit) Postprocessing: 12 eigenvalue(s) > 0 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790575185698 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.8483042527042987e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790606312158 (PEPit) Postprocessing: 1 eigenvalue(s) > 0 after 2 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790577678836 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.2580800749100387e-13 after 3 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.03304790577678836 (PEPit) Postprocessing: 1 eigenvalue(s) > 1.2580800749100387e-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.4946460426395706e-12 All the primal scalar constraints are verified up to an error of 5.708211681110242e-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.146117367966438e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.8163082866886653e-07 (PEPit) Final upper bound (dual): 0.03305791391665664 and lower bound (primal example): 0.03304790577678836 (PEPit) Duality gap: absolute: 1.0008139868282473e-05 and relative: 0.0003028373397055563 *** 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
12.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.018867679370620477 (PEPit) Postprocessing: 4 eigenvalue(s) > 5.512588136340781e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.01876767933486927 (PEPit) Postprocessing: 2 eigenvalue(s) > 2.7426815323822647e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.01876767933486927 (PEPit) Postprocessing: 2 eigenvalue(s) > 2.7426815323822647e-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.5439352243334105e-10 All the primal scalar constraints are verified up to an error of 1.6328691523903593e-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.656486538994397e-11 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.054970099021031e-08 (PEPit) Final upper bound (dual): 0.018867680108727337 and lower bound (primal example): 0.01876767933486927 (PEPit) Duality gap: absolute: 0.0001000007738580673 and relative: 0.005328350515466854 *** Example file: worst-case performance of the alternate projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0188677 ||x0 - x_*||^2
12.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.0684488573474302 (PEPit) Postprocessing: 4 eigenvalue(s) > 7.89314275744705e-10 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.06834885794771604 (PEPit) Postprocessing: 2 eigenvalue(s) > 6.675793636702899e-09 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.06834885794771604 (PEPit) Postprocessing: 2 eigenvalue(s) > 6.675793636702899e-09 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 3.4702057470351053e-10 All the primal scalar constraints are verified up to an error of 2.313877735249381e-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 9.760213634525396e-13 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.0486379622054575e-10 (PEPit) Final upper bound (dual): 0.06844885735562138 and lower bound (primal example): 0.06834885794771604 (PEPit) Duality gap: absolute: 9.99994079053379e-05 and relative: 0.001463073574423631 *** Example file: worst-case performance of the averaged projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0684489 ||x0 - x_*||^2
12.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.025756451962234826 (PEPit) Postprocessing: 6 eigenvalue(s) > 8.663938612734702e-08 before dimension reduction (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.025656451722815107 (PEPit) Postprocessing: 3 eigenvalue(s) > 0.009447129803180574 after 1 dimension reduction step(s) (PEPit) Solver status: optimal (solver: MOSEK); objective value: 0.025656451722815107 (PEPit) Postprocessing: 3 eigenvalue(s) > 0.009447129803180574 after dimension reduction (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.4387615127435673e-10 All the primal scalar constraints are verified up to an error of 4.817901633202837e-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.908644654925377e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 9.751031937655801e-08 (PEPit) Final upper bound (dual): 0.02575645525161499 and lower bound (primal example): 0.025656451722815107 (PEPit) Duality gap: absolute: 0.00010000352879988364 and relative: 0.0038977926441385144 *** Example file: worst-case performance of the Dykstra projection method *** PEPit guarantee: ||Proj_Q1 (xn) - Proj_Q2 (xn)||^2 == 0.0257565 ||x0 - x_*||^2