Ernest K Ryu
email: ernestryu@snu.ac.kr

Adrien B Taylor
email: adrien.taylor@inria.fr

Carolina Bergeling
email: olina.bergeling@control.lth.se

AND Pontus Giselsson
email: pontusg@control.lth.se

OPERATOR SPLITTING PERFORMANCE ESTIMATION: TIGHT CONTRACTION FACTORS AND OPTIMAL PARAMETER SELECTION

We propose a methodology for studying the performance of common splitting methods through semidefinite programming. We prove tightness of the methodology and demonstrate its value by presenting two applications of it. First, we use the methodology as a tool for computerassisted proofs to prove tight analytic contraction factors for Douglas-Rachford splitting that are likely too complicated for a human to find bare-handed. Second, we use the methodology as an algorithmic tool to computationally select the optimal splitting method parameters by solving a series of semidefinite programs.

1. Introduction. Consider the fixed-point iteration in a real Hilbert space H

z k+1 = T z k ,
where T : H → H. We say ρ < 1 is a contraction factor of T if T x -T y ≤ ρ x -y for all x, y ∈ H. We ask the question: given a set of assumptions, what is the best (tight) contraction factor one can prove? In this work, we present the operator splitting performance estimation problem (OSPEP), a methodology for studying contraction factors of forward-backward splitting (FBS), Douglas-Rachford splitting (DRS), and Davis-Yin splitting (DYS).

First, we present the OSPEP problem, the infinite-dimensional non-convex optimization problem of finding the best (smallest) contraction factor given a set of assumptions on the operators. Following the technique of Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF], we reformulate the problem into a finite-dimensional convex semidefinite program (SDP). We then establish tightness (exactness) of this reformulation with interpolation conditions.

Next, we demonstrate the value of OSPEP through two uses. First, we use OSPEP as a tool for computer-assisted proofs to prove tight analytic contraction factors for DRS. The results are tight in that they have exact matching lower bounds. The proofs are computer-assisted in that their discoveries were assisted by a computer, but their verifications do not require a computer. Second, we use OSPEP as an algorithmic tool to automatically select the optimal splitting method parameters.

The tightness guarantee and flexibility make OSPEP a powerful tool. Due to tightness, OSPEP can provide both positive and negative results. The flexibility allows users to pick and choose assumptions from a set of standard assumptions.

1.1. Organization and contribution. Section 2 presents operator interpolation, later used in Section 3 to establish tightness. Section 3 presents the OSPEP methodology, an exact transformation of the problem of finding the best contraction factor into a convex SDP, and provides tightness guarantees. Section 4 presents tight analytic contraction factors for DRS under assumptions considered in [START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF][START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF] using OSPEP as a tool for computer-assisted proofs. Section 5 presents an automatic parameter selection method using OSPEP as an algorithmic tool. Section 6 concludes the paper.

The main contribution of this work is twofold. The first is analyzing the performance of monotone splitting methods using SDPs with tightness guarantees. The overall formulation generally follows from the technique of Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF] and the prior work discussed in Section 1.2. The tightness, established with the operator interpolation results of Sections 2, is a novel theoretical contribution. The second contribution is the techniques of Sections 4 and 5, an illustration of how to use the proposed methodology. Although we do consider the results of Sections 4 and 5 to be interesting and valuable, we view the technique, rather than the result, to be the second major contribution.

The major and minor contributions of this work are, to the best of our knowledge, novel in the following sense. The tightness of Section 3 is new. The technique of Section 4 is the first use of computer-assisted proofs to obtain provably tight rates for monotone operator splitting methods. The tight results of Section 4 improve upon the prior results of [START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF][START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF]. The technique of Section 5 is the first use of automatic parameter selection that is optimal with respect to the algorithm and assumptions.

1.2. Prior work. FBS was first stated in the operator theoretic language in [START_REF] Bruck | On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space[END_REF][START_REF] Passty | Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[END_REF]. The projected gradient method presented in [START_REF] Goldstein | Convex programming in Hilbert space[END_REF][START_REF] Levitin | Constrained minimization methods[END_REF] served as a precursor to FBS. Peaceman-Rachford spitting (PRS) was first presented in [START_REF] Peaceman | The numerical solution of parabolic and elliptic differential equations[END_REF][START_REF] Kellogg | A nonlinear alternating direction method[END_REF][START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF], and DRS was first presented in [START_REF] Douglas | On the numerical solution of heat conduction problems in two and three space variables[END_REF][START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF]. DYS was first presented in [START_REF] Davis | A three-operator splitting scheme and its optimization applications[END_REF]. Forward-Douglas-Rachford splitting of Raguet, Fadili, Peyré, and Brineño-Arias [START_REF] Raguet | A generalized forward-backward splitting[END_REF][START_REF] Briceño-Arias | Forward-Douglas-Rachford splitting and forward-partial inverse method for solving monotone inclusions[END_REF][START_REF] Raguet | A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization[END_REF] served as a precursor to DYS.

What we call interpolation in this work is also called extension. The maximal monotone extension theorem, which we later state as Fact 1, is well known, and it follows from a standard application of Zorn's lemma. Reich [START_REF] Reich | Extension problems for accretive sets in Banach spaces[END_REF], Bauschke [START_REF] Bauschke | Fenchel duality, Fitzpatrick functions and the extension of firmly nonexpansive mappings[END_REF], Reich and Simons [START_REF] Reich | Fitzpatrick functions and the Kirszbraun-Valentine extension theorem[END_REF], Bauschke, Wang, and Yao [START_REF] Bauschke | Firmly nonexpansive and Kirszbraun-Valentine extensions: a constructive approach via monotone operator theory[END_REF][START_REF] Bauschke | General resolvents for monotone operators: characterization and extension[END_REF][START_REF] Wang | Maximally monotone linear subspace extensions of monotone subspaces: explicit constructions and characterizations[END_REF], and Crouzeix and Anaya [START_REF] Crouzeix | A construction of a maximal monotone extension of a monotone map[END_REF][START_REF] Crouzeix | Monotone and maximal monotone affine subspaces[END_REF][START_REF] Crouzeix | Maximality is nothing but continuity[END_REF] have studied more concrete and constructive extension theorems for maximal monotone, nonexpansive, and firmly-nonexpansive operators using tools from monotone operator theory.

Contraction factors and linear convergence for first-order methods have been a subject of intense study. Surprisingly, many of the published contraction factors are not tight. For FBS, Mercier, [51, p. 25], Tseng [START_REF] Tseng | Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[END_REF], Chen and Rockafellar [START_REF] Chen | Convergence rates in forward-backward splitting[END_REF], and Bauschke and Combettes [2, Section 26.5] proved linear rates of convergence, but did not provide exact matching lower bounds. Taylor, Hendrickx, and Glineur showed tight contraction factors and provided exact matching lower bounds [START_REF] Taylor | Exact worst-case convergence rates of the proximal gradient method for composite convex minimization[END_REF]. For DRS, Lions and Mercier [START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF] and Davis and Yin [START_REF] Davis | Faster convergence rates of relaxed Reaceman-Rachford and ADMM under regularity assumptions[END_REF] proved linear rates of convergence, but did not provide exact matching lower bounds. Giselsson and Boyd [START_REF] Giselsson | Diagonal scaling in Douglas-Rachford splitting and ADMM[END_REF][START_REF] Giselsson | Linear convergence and metric selection for Douglas-Rachford splitting and ADMM[END_REF], Giselsson [START_REF] Giselsson | Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM[END_REF][START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF], and Moursi and Vandenberghe [START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF] proved linear rates of convergence and provided exact matching lower bounds for certain cases. ADMM is a splitting method closely related to DRS. Deng and Yin [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF], Giselsson and Boyd [START_REF] Giselsson | Diagonal scaling in Douglas-Rachford splitting and ADMM[END_REF][START_REF] Giselsson | Linear convergence and metric selection for Douglas-Rachford splitting and ADMM[END_REF], Nishihara et al. [START_REF] Nishihara | A general analysis of the convergence of ADMM[END_REF], França and Bento [START_REF] Franc | An explicit rate bound for over-relaxed ADMM[END_REF], Hong and Luo [START_REF] Hong | On the linear convergence of the alternating direction method of multipliers[END_REF], Han, Sun, and Zhang [START_REF] Han | Linear rate convergence of the alternating direction method of multipliers for convex composite programming[END_REF], and Chen et al. [START_REF] Chen | On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming[END_REF] proved linear rates of convergence for ADMM. Matching lower bounds are provided only in [START_REF] Giselsson | Linear convergence and metric selection for Douglas-Rachford splitting and ADMM[END_REF]. Further, [START_REF] Giselsson | Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM[END_REF] provides matching lower bounds to the rates in [START_REF] Giselsson | Diagonal scaling in Douglas-Rachford splitting and ADMM[END_REF]. Ghadimi et al. [START_REF] Ghadimi | On the optimal step-size selection for the alternating direction method of multipliers[END_REF][START_REF] Ghadimi | Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems[END_REF] and Teixeira et al. [START_REF] Teixeira | Optimal scaling of the ADMM algorithm for distributed quadratic programming[END_REF][START_REF] Teixeira | The ADMM algorithm for distributed quadratic problems: Parameter selection and constraint preconditioning[END_REF] proved linear rates of convergence and provided matching lower bounds for ADMM applied to quadratic problems. For DYS, Davis and Yin [START_REF] Davis | A three-operator splitting scheme and its optimization applications[END_REF], Yan [START_REF] Yan | A new primal-dual algorithm for minimizing the sum of three functions with a linear operator[END_REF], Pedregosa and Gidel [START_REF] Pedregosa | Adaptive three operator splitting[END_REF], and Pedregosa, Fatras, and Casotto [START_REF] Pedregosa | Proximal splitting meets variance reduction[END_REF] proved linear rates of convergence, but did not provide exact matching lower bounds. Pedegrosa [START_REF] Pedregosa | On the convergence rate of the three operator splitting scheme[END_REF] analyzed sublinear convergence, but not contraction factors.

Analyzing convex optimization algorithms by formulating the analysis as an SDP has been a rapidly growing area of research in the past 5 years. Past work analyzed convex optimization algorithms, and, to the best of our knowledge, analyzing the performance of monotone operator splitting methods with SDPs or any form of computer-assisted proof is new. (After the initial version of this paper was made public on arXiv, several papers citing our work followed up on our results and used SDPs to analyze other monotone operator splitting methods [START_REF] Gu | On the optimal ergodic sublinear convergence rate of the relaxed proximal point algorithm for variational inequalities[END_REF][START_REF] Gu | On the optimal linear convergence factor of the relaxed proximal point algorithm for monotone inclusion problems[END_REF][START_REF] Gu | Optimal nonergodic sublinear convergence rate of proximal point algorithm for maximal monotone inclusion problems[END_REF][START_REF] Seidman | A control-theoretic approach to analysis and parameter selection of Douglas-Rachford splitting[END_REF][START_REF] Wang | Robust convergence analysis of threeoperator splitting[END_REF][START_REF] Ryu | Finding the forward-Douglas-Rachford-forward method[END_REF].) Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF] and Taylor, Hendrickx, and Glineur [START_REF] Taylor | Exact worst-case performance of first-order methods for composite convex optimization[END_REF][START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF] presented the performance estimation problem (PEP) methodology. Our work generally follows the techniques presented by Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF] while contributing by establishing tightness. Lieder [START_REF] Lieder | On the convergence rate of the Halpern-iteration[END_REF] applied the PEP approach to analyze the Halpern iteration without an a priori guarantee of tightness. Lessard, Recht, and Packard [START_REF] Lessard | Analysis and design of optimization algorithms via integral quadratic constraints[END_REF] leveraged techniques from control theory and used integral quadratic constraints (IQC) for finding Lyapunov functions for analyzing convex optimization algorithms. The IQC and PEP approaches were recently linked by Taylor, Van Scoy, and Lessard [START_REF] Taylor | Lyapunov functions for first-order methods: Tight automated convergence guarantees[END_REF]. Finally, Nishihara et al. [START_REF] Nishihara | A general analysis of the convergence of ADMM[END_REF] and França and Bento [START_REF] Franc | An explicit rate bound for over-relaxed ADMM[END_REF] used IQC to the analyze ADMM.

Finally, both IQC and PEP approaches allowed designing new methods for particular problem settings. For example, the optimized gradient method by Kim and Fessler [35,[START_REF] Kim | On the convergence analysis of the optimized gradient method[END_REF][START_REF] Kim | Adaptive restart of the optimized gradient method for convex optimization[END_REF][START_REF] Kim | Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)[END_REF][START_REF] Kim | Generalizing the optimized gradient method for smooth convex minimization[END_REF][START_REF] Kim | Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions[END_REF] (first numerical version by Drori and Teboulle [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF]) was developed using PEPs and enjoys the best possible worst-case guarantee on the final objective function accuracy after a fixed number of iteration, as showed by Drori [START_REF] Drori | The exact information-based complexity of smooth convex minimization[END_REF]. On the other hand, the IQC framework was used by Van Scoy et al. [START_REF] Van Scoy | The fastest known globally convergent firstorder method for minimizing strongly convex functions[END_REF] for developing the triple momentum method, the first-order method with the fastest known convergence rate for minimizing a smooth strongly convex function.

1.3. Preliminaries. We now quickly review standard results and set up the notation. We follow standard notation [START_REF] Ryu | Primer on monotone operator methods[END_REF][START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]. Write H for a real Hilbert space equipped with a (symmetric) inner product •, • . Write S n + for the set of n × n symmetric positive semidefinite matrices. Write M 0 if and only if M ∈ S n + . We say A is an operator on H and write A : H ⇒ H if A maps a point in H to a subset of H. So A(x) ⊂ H for all x ∈ H. For simplicity, we also write Ax = A(x). Write I : H → H for the identity operator. We say A : H ⇒ H is monotone if Ax -Ay, x -y ≥ 0 for all x, y ∈ H. To clarify, the inequality means u -v, x -y ≥ 0 for all u ∈ Ax and v ∈ Ay. We say A :

H ⇒ H is µ-strongly monotone if Ax -Ay, x -y ≥ µ x -y 2 ,
where µ ∈ (0, ∞). We say a single-valued operator A :

H → H is β-cocoercive if Ax -Ay, x -y ≥ β Ax -Ay 2 ,
where β ∈ (0, ∞). We say a single-valued operator A :

H → H is L-Lipschitz if Ax -Ay ≤ L x -y
where L ∈ (0, ∞). A monotone operator is maximal if it cannot be properly extended to another monotone operator. The resolvent of an operator A is J αA = (I + αA) -1 , where α > 0. We say a single-valued operator T :

H → H is contractive if it is ρ-Lipschitz with ρ < 1. We say x is a fixed point of T if x = T x .
Davis-Yin splitting (DYS) encodes solutions to

find x∈H 0 ∈ (A + B + C)x
where A, B, and C are maximal monotone and C is single-valued, as fixed points of (1.1)

T (z; A, B, C, α, θ) = z -θJ αB z + θJ αA (2J αB -I -αCJ αB )z
where α > 0 and θ = 0. FBS and DRS are special cases of DYS; when C = 0 DYS reduces to DRS, and when B = 0 DYS reduces to FBS. Therefore, our analysis on DYS directly applies to FBS and DRS.

2. Operator interpolation. Let Q be a class of operators, and let I be an arbitrary index set. We say a set of duplets {(x i , q i )} i∈I , where x i , q i ∈ H for all i ∈ I, is Q-interpolable if there is an operator Q ∈ Q such that q i ∈ Qx i for all i ∈ I. In this case, we call Q an interpolation of {(x i , q i )} i∈I . In this section, we present conditions that characterize when a set of duplets is interpolable with respect to the class of operators listed in Table 1 and their intersections.

Class Description

M

maximal monotone operators M µ µ-strongly monotone maximal monotone operators

L L L-Lipschitz operators C β β-cocoercive operators Table 1:
Operator classes for which we analyze interpolation. The parameters µ, L, and β are in (0, ∞). Note that M µ ⊂ M for any µ > 0, C β ⊂ M for any β > 0, but L L ⊂ M for any L > 0.

2.1. Interpolation with one class. We now present interpolation results for the classes M, M µ , L L , and

C β . Fact 1 (Maximal monotone extension theorem [2, Theorem 20.21]). {(x i , q i )} i∈I is M-interpolable if and only if q i -q j , x i -x j ≥ 0 ∀i, j ∈ I. Proposition 1. Let µ ∈ (0, ∞). Then {(x i , q i )} i∈I is M µ -interpolable if and only if q i -q j , x i -x j ≥ µ x i -x j 2 ∀i, j ∈ I.
Proof. With Fact 1, the proof follows from a sequence of equivalences: ∀i, j ∈ I, q i -q j , x i -

x j ≥ µ x i -x j 2 ⇔ ∀i, j ∈ I, (q i -µx i ) -(q j -µx j ), x i -x j ≥ 0 ⇔ ∃R ∈ M, ∀i ∈ I, (q i -µx i ) ∈ Rx i ⇔ ∃Q ∈ M µ , Q = R + µI, ∀i ∈ I, q i ∈ Qx i . Proposition 2. Let β ∈ (0, ∞). Then {(x i , q i )} i∈I is C β -interpolable if and only if q i -q j , x i -x j ≥ β q i -q j 2 ∀i, j ∈ I.
Proof. With Proposition 1, the proof follows from a sequence of equivalences:

∀i, j ∈ I, q i -q j , x i -x j ≥ β q i -q j 2 ⇔ ∃R ∈ M β , ∀i ∈ I, x i ∈ Rq i ⇔ ∃Q ∈ C β , Q = R -1 , ∀i ∈ I, q i ∈ Qx i . Fact 2 (Kirszbraun-Valentine Theorem). Let L ∈ (0, ∞). Then {(x i , q i )} i∈I is L L -interpolable if and only if q i -q j 2 ≤ L 2 x i -x j 2 ∀i, j ∈ I.
Fact 2 is a special case of the Kirszbraun-Valentine theorem [START_REF] Kirszbraun | Über die zusammenziehende und Lipschitzsche transformationen[END_REF][START_REF] Valentine | On the extension of a vector function so as to preserve a Lipschitz condition[END_REF][START_REF] Valentine | A Lipschitz condition preserving extension for a vector function[END_REF]. A direct proof follows from similar arguments.

Failure of interpolation with intersection of classes.

When considering interpolation with intersections of classes such as M∩L L , one might naively expect results as simple as those of Section 2.1. Contrary to this expectation, interpolation can fail.

Proposition 3. {(x i , q i )} i∈I may not be (M ∩ L L )-interpolable for L ∈ (0, ∞) even if q i -q j 2 ≤ L 2 x i -x j 2 , q i -q j , x i -x j ≥ 0 ∀i, j ∈ I.
Proof. Consider the following example in R 2 :

S = 0 0 , 0 0 , 1 0 , 0 0 , 1/2 0 , 0 L/2 .
These points satisfy the inequalities. However, there is no Lipschitz and maximal monotone operator interpolating these points. Assume for contradiction that Q ∈ Proposition 23.39]. This implies Q(1/2, 0) = (0, 0), which is a contradiction.

(M ∩ L L ) is an interpolation of these points. Since Q is Lipschitz, it is single-valued. Since Q is maximal monotone, the set {x | Qx = 0} is convex [2,
The subtlety is that the counterexample has two separate interpolations in M and L L but does not have an interpolation in M ∩ L L . Interpolation with respect to M µ ∩ L L , C β ∩ L L , and M µ ∩ C β can fail in a similar manner.

Two-point interpolation.

We now present conditions for two-point interpolation, i.e., interpolation when |I| = 2. In this case, interpolation conditions become simple, and the difficulty discussed in Section 2.2 disappears. Although the setup |I| = 2 may seem restrictive, it is sufficient for what we need in later sections.

Proposition 4. Assume 0 < µ, µ ≤ L < ∞, and µ ≤ 1/β < ∞. Then {(x 1 , q 1 ), (x 2 , q 2 )} is (M µ ∩ C β ∩ L L )-interpolable if and only if q 1 -q 2 , x 1 -x 2 ≥ µ x 1 -x 2 2 q 1 -q 2 , x 1 -x 2 ≥ β q 1 -q 2 2 (2.1) q 1 -q 2 2 ≤ L 2 x 1 -x 2 2 .
Proof. If the points are (M µ ∩L L ∩C β )-interpolable, then (2.1) holds by definition. Assume (2.1) holds. When dim H = 1 the result is trivial, so we assume, without loss of generality, dim H ≥ 2.

Define q = q 1 -q 2 and x = x 1 -x 2 . If x = 0, then β > 0 or L > 0 implies q = 0, and the operator Q : H → H defined as

Q(y) = µ(y -x 1 ) + q 1 interpolates {(x 1 , q 1 ), (x 2 , q 2 )} and Q ∈ M µ ∩ L L ∩ C β . Assume x = 0. If q = γx for some γ ∈ R, then the operator Q : H → H defined as Q(y) = γ(y -x 1 ) + q 1
interpolates {(x 1 , q 1 ), (x 2 , q 2 )} and Q ∈ M µ ∩ L L ∩ C β . Assume q is linearly independent from x. Define the orthonormal vectors,

e 1 = 1 x
x, e 2 = 1 q 2 -( e 1 , q ) 2 (q -e 1 , q e 1 ), along with an associated bounded linear operator A : H → H such that

A| {e1,e2} ⊥ = µI,
where {e 1 , e 2 } ⊥ ⊂ H is the subspace orthogonal to e 1 and e 2 and I is the identity mapping on {e 1 , e 2 } ⊥ . On span{e 1 , e 2 }, define

Ae 1 = q, e 1 x e 1 + q 2 -( e 1 , q ) 2 x e 2 , Ae 2 = - q 2 -( e 1 , q ) 2 x e 1 + q, e 1 x e 2 .
Note that this definition satisfies Ax = q. Finally, define M to be a 2 × 2 matrix isomorphic to A| span{e1,e2} , i.e.,

A| span{e1,e2} ∼ = 1 x q, e 1 -q 2 -( e 1 , q ) 2 q 2 -( e 1 , q ) 2 q, e 1 =M ∈ R 2×2 .
With direct computations, we can verify that M satisfies

L 2 ≥ λ max (M T M ) = q 2 x 2 , µ ≤ λ min ((1/2)(M + M T )) = q, x x 2 , β ≤ λ min ((1/2)(M -1 + M -T )) = q, x q 2 .
This implies A : H → H is L-Lipschitz, µ-strongly monotone, and β-cocoercive.

Finally, the affine operator Q : H → H defined as

Q(y) = A(y -x 1 ) + q 1 interpolates {(x 1 , q 1 ), (x 2 , q 2 )} and Q ∈ M µ ∩ L L ∩ C β .
Proposition 4 presents conditions for interpolation with 3 classes. Interpolation conditions with 2 of these classes, such as (C β ∩L L ), (M µ ∩C β ), (M µ ∩L L ), (M∩L L ), and are of the same form and follow from the a very similar (identical) proof.

3. Operator splitting performance estimation problems. Consider the operator splitting performance estimation problem (OSPEP) maximize

T (z; A, B, C, α, θ) -T (z ; A, B, C, α, θ) 2 z -z 2 subject to A ∈ Q 1 , B ∈ Q 2 , C ∈ Q 3 z, z ∈ H, z = z (3.1)
where z, z , A, B, and C are the optimization variables. T is the DYS operator defined in (1.1). The scalars α > 0 and θ > 0 and the classes

Q 1 , Q 2 ,
T (z; A, B, C, α, θ) -T (z ; A, B, C, α, θ) 2 z -z 2 .
Therefore, the OSPEP, by definition, computes the square of the best contraction factor of T given the assumptions on A, B, and C, encoded as the classes Q 1 , Q 2 , and Q 3 . In fact, we say a contraction factor (established through a proof) is tight if it is equal to the square root of the optimal value of (3.1). A contraction factor that is not tight can be improved with a better proof without any further assumptions. At first sight, (3.1) seems difficult to solve, as it is posed as an infinite-dimensional non-convex optimization problem. In this section, we present a reformulation of (3.1) into a (finite-dimensional convex) SDP. This reformulation is exact; it performs no relaxations or approximations, and the optimal value of the SDP coincides with that of (3.1).

3.1. Convex formulation of OSPEP. We now formulate (3.1) into a (finitedimensional) convex SDP through a series of equivalent transformations. First, we write (3.1) more explicitly as

maximize z -θ(z B -z A ) -z + θ(z B -z A ) 2 z -z 2 subject to A ∈ Q 1 , B ∈ Q 2 , C ∈ Q 3 z B = J αB z z C = αCz B z A = J αA (2z B -z -z C ) z B = J αB z z C = αCz B z A = J αA (2z B -z -z C ) z, z ∈ H, z = z (3.2)
where z, z ∈ H, A, B, and C are the optimization variables.

3.1.1. Homogeneity. We say a class of operators Q is homogeneous if

A ∈ Q ⇔ (γ -1 I)A(γI) ∈ Q for all γ > 0.
→ γ -1 z, z → γ -1 z , A → (γ -1 I)A(γI), B → (γ -1 I)B(γI), and C → (γ -1 I)C(γI) where γ = z -z to equivalently reformulate (3.2) into maximize z -θ(z B -z A ) -z + θ(z B -z A ) 2 subject to A ∈ Q 1 , B ∈ Q 2 , C ∈ Q 3 z B = J αB z z C = αCz B z A = J αA (2z B -z -z C ) z B = J αB z z C = αCz B z A = J αA (2z B -z -z C ) z -z 2 = 1 (3.3)
where z, z ∈ H, A, B, and C are the optimization variables.

3.1.2. Operator interpolation. For simplicity of exposition, we limit the generality and reformulate the convex SDP under the following operator classes

• A ∈ Q 1 = M µ -µ-strongly maximal monotone • B ∈ Q 2 = C β ∩ L L -β-cocoercive and L-Lipschitz • C ∈ Q 3 = C β C -β C -cocoercive
To clarify, the same analysis can be done in the general setup, and we can freely pick and choose the assumptions. The general result is shown in the supplementary materials, in Section SM1.

We use the interpolation results from Section 2. For operator A, we have

∃A ∈ M µ such that z A = J αA (2z B -z -z C ), z A = J αA (2z B -z -z C ) ⇔ {(z A , α -1 (2z B -z -z C -z A )), (z A , α -1 (2z B -z -z C -z A ))} is M µ -interpolable ⇔ z A -z A , 2z B -z -z C -(2z B -z -z C ) ≥ (1 + αµ) z A -z A 2 .
For operator B, we have

∃B ∈ C β ∩ L L such that z B = J αB z, z B = J αB z ⇔ {(z B , α -1 (z -z B )), (z B , α -1 (z -z B ))} is C β -interpolable {(z B , α -1 (z -z B )), (z B , α -1 (z -z B ))} is L L -interpolable ⇔ z -z -z B + z B , z B -z B ≥ (β/α) z -z -z B + z B 2 α 2 L 2 z B -z B 2 ≥ z -z -z B + z B 2 .
For operator C, we have

∃C ∈ C β C such that z C = αCz B , z C = αCz B ⇔ {(z B , α -1 z C ), (z B , α -1 z C )} is C β C -interpolable ⇔ z B -z B , z C -z C ≥ (β C /α) z C -z C 2 .
Now we can drop the explicit dependence on the operators A, B, and C and reformulate

(3.3) into maximize z -θ(z B -z A ) -z + θ(z B -z A ) 2 subject to z A -z A , 2z B -z -z C -(2z B -z -z C ) ≥ (1 + αµ) z A -z A 3.1.3. Grammian representation.
The optimization problem (3.4) and all other operator classes in Section 2 are specified through inner products and squared norms. This structure allows us to rewrite the problem with a Grammian representation:

(3.5) G =     z 2 z, z A z, z B z, z C z, z A z A 2 z A , z B z A , z C z, z B z A , z B z B 2 z B , z C z, z C z A , z C z B , z C z C 2     . Lemma 3.1. If dim H ≥ 4, then G ∈ S 4 + ⇔ ∃z, z A , z B , z C ∈ H such that G = expression of (3.5).
Proof. (⇐) For any z, z A , z B , z C ∈ H, G is positive semidefinite since

x T Gx = x 1 z + x 2 z A + x 3 z B + x 4 z C 2 ≥ 0 for any x = (x 1 , x 2 , x 3 , x 4 ) ∈ R 4 . (⇒) Let LL T = G be a Cholesky factorization of G. Write L =     zT zT A zT B zT C    
where z, zA , zB , zC ∈ R 4 . We can find orthonormal vectors e 1 , e Write

M I =     1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0     , M O =     1 θ -θ 0 θ θ 2 -θ 2 0 -θ -θ 2 θ 2 0 0 0 0 0     , M A µ =     0 -1/2 0 0 -1/2 -1 -αµ 1 -1/2 0 1 0 0 0 -1/2 0 0     , M C β =     0 0 0 0 0 0 0 0 0 0 0 1/2 0 0 1/2 -β C /α     , M B β =     -β/α 0 1/2 + β/α 0 0 0 0 0 1/2 + β/α 0 -1 -β/α 0 0 0 0 0     , M B L =     -1 0 1 0 0 0 0 0 1 0 -1 + α 2 L 2 0 0 0 0 0     .
When dim H ≥ 4, we can use Lemma 3.1 to reformulate (3.4) into the equivalent SDP maximize Tr(M O G)

subject to Tr(M A µ G) ≥ 0 Tr(M B β G) ≥ 0 Tr(M B L G) ≥ 0 Tr(M C β G) ≥ 0 Tr(M I G) = 1 G 0 (3.6)
where G ∈ S 4 + is the optimization variable. Since (3.6) is a finite-dimensional convex SDP, we can solve it efficiently with standard solvers.

These equivalent reformulations prove Theorem 3.2 for this special case. The general case follows from analogous steps, and we show the fully general SDP in the supplementary materials, in Section SM1.

Theorem 3.2. The OSPEP (3.1) and the SDP of Section SM1 are equivalent if dim H ≥ 4 and

Q 1 = M µ A ∩ C β A ∩ L L A , Q 2 = M µ B ∩ C β B ∩ L L B , and Q 3 = M µ C ∩ C β C ∩ L L C .
To clarify, Theorem 3.2 states that the optimal values of the two problems are equal and that a solution from one problem can be transformed into a solution of another. Given an optimal G of the SDP, we can take its Cholesky factorization as in Lemma 3.1 to get z, z A , z B , z C ∈ H and obtain evaluations of the worst-case operators

A(z A ) α -1 (2z B -z -z C -z A ), A(0) 0, where A ∈ Q 1 B(z B ) α -1 (z -z B ), B(0) 0, where B ∈ Q 2 C(z B ) α -1 z C , C(0) 0, where C ∈ Q 3 .
3.2. Dual OSPEP. The SDP (3.6) has a dual:

(3.7) minimize ρ 2 subject to λ A µ , λ B β , λ B L , λ C β ≥ 0 S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) 0 where ρ 2 , λ A µ , λ B β , λ B L , λ C β ∈ R are the optimization variables and S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) = -M O -λ A µ M A µ -λ B β M B β -λ B L M B L -λ C β M C β + ρ 2 M I (3.8) =        ρ 2 + λ B β β α + λ B L -1 λ A µ 2 -θ -λ B β ( 1 2 + β α ) -λ B L + θ 0 λ A µ 2 -θ λ A µ (1 + αµ) -θ 2 -λ A µ + θ 2 λ A µ 2 -λ B β ( 1 2 + β α ) -λ B L + θ -λ A µ + θ 2 λ B β ( β α -1) + λ B L (1 -α 2 L 2 ) -θ 2 - λ C β 2 0 λ A µ 2 - λ C β 2 λ C β β C α        .
We call (3.7) the dual OSPEP. In contrast, we call the OSPEP (3.1), and equivalently (3.6), the primal OSPEP. Again, this special case illustrates the overall approach. We show the fully general dual OSPEP in the supplementary materials, in Section SM2.

To ensure strong duality between the primal and dual OSPEPs, we enforce Slater's constraint qualification with the following notion of degeneracy. We say the intersections

C β ∩ L L , M µ ∩ C β , M µ ∩ L L , and M µ ∩ C β ∩ L L are respectively degenerate if C β+ε ∩ L L-ε = ∅, M µ+ε ∩ C β+ε = ∅, M µ+ε ∩ L L-ε = ∅, and M µ+ε ∩ C β+ε ∩ L L-ε = ∅ for all ε > 0. For example, M 3 ∩ L 3 = {3I} is a degenerate intersection.
Theorem 3.3. Weak duality holds between the primal and dual OSPEPs of Sections SM1 and SM2. Furthermore, strong duality holds if each class Q 1 , Q 2 , and Q 3 is a non-degenerate intersection of classes of Table 1.

Proof. Weak duality follows from the fact that the SDP of Section SM2 is the Lagrange dual of the SDP of Section SM1. To establish strong duality, we show that the non-degeneracy assumption leads to Slater's constraint qualification [START_REF] Rockafellar | Conjugate Duality and Optimization[END_REF] for the primal OSPEP.

Since the intersections are non-degenerate, there is a small ε > 0 and A, B, and C such that

A ∈ M µ A +ε ∩ C β A +ε ∩ L L A -ε B ∈ M µ B +ε ∩ C β B +ε ∩ L L B -ε C ∈ M µ C +ε ∩ C β C +ε ∩ L L C -ε .
With any inputs z, z ∈ H such that z = z , we can follow the arguments of Section 3.1 and construct a G matrix as defined in (3.5). This G satisfies

Tr(M A µ G) > 0, . . . , Tr(M C L G) > 0, Tr(M I G) = 1, G 0. Define G δ = (1 -δ)G + δI.
There exists a small δ > 0 such that

Tr(M A µ G δ ) > 0, . . . , Tr(M C L G δ ) > 0, Tr(M I G δ ) = 1, G δ 0.
Note that the equality constraint Tr(M I G δ ) = 1 holds since Tr(M I ) = 1. Since G δ is a strictly feasible point, Slater's condition gives us strong duality.

More generally, the strong duality argument of Theorem 3.3 applies if each Q 1 , Q 2 , and Q 3 is a single operator class of Table 1 or is a non-degenerate intersection of those classes.

Primal and dual interpretations and computer-assisted proofs.

A feasible point of the primal OSPEP provides a lower bound on any contraction factor as it corresponds to operator instances that exhibit a contraction corresponding to the objective value. An optimal point of the primal OSPEP corresponds to the worstcase operators. A feasible point of the dual OSPEP provides an upper bound as it corresponds to a proof of a contraction factor. A convergence proof in optimization is a nonnegative combination of known valid inequalities. The nonnegative variables of the dual OSPEP correspond to weights of such a nonnegative combination, and the objective value is the contraction factor the nonnegative combination of inequalities (i.e., the proof) proves.

We can use the OSPEP methodology as a tool for computer-assisted proofs. Given the operator classes, we can choose specific numerical values for the parameters, such as the strong convexity and cocoercivity parameters, and numerically solve the SDP. We do this for many parameter values, observe the pattern of primal and dual solutions, and guess the analytical, parameterized solution to the SDPs. To put it differently, the SDP solver provides a valid and optimal proof for a given choice of parameters, and we use this to infer 3.4. Further remarks. With analogous steps, the OSPEPs for FBS and DRS can be written as smaller 3 × 3 SDPs. Using the smaller SDP is preferred, as formulating these cases into larger 4 × 4 SDPs, as a special case of the 4 × 4 SDP for DYS, can lead to numerical difficulties.

The tightness of the OSPEP methodology relies on the two-point interpolation results of Section 2, which we can use because the operators A, B, and C are evaluated once per iteration. (To analyze the contraction factor, we consider a single evaluation of the operator at two distinct points, which leads to two evaluations of each operator.) For splitting methods without this property, methods that access one of the operators twice or more per iteration, the OSPEP loses the tightness guarantee. Such methods include the extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], FBF [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF], PDFP [START_REF] Chen | A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions[END_REF], Extragradient-Based Alternating Direction Method for Convex Minimization [START_REF] Lin | An extragradient-based alternating direction method for convex minimization[END_REF], FBHF [START_REF] Briceño-Arias | Forward-backward-half forward algorithm for solving monotone inclusions[END_REF], FRB [START_REF] Malitsky | A forward-backward splitting method for monotone inclusions without cocoercivity[END_REF], Golden ratio algorithm [START_REF] Malitsky | Golden ratio algorithms for variational inequalities[END_REF], Shadow-Douglas-Rachford [START_REF] Csetnek | Shadow Douglas-Rachford splitting for monotone inclusions[END_REF], and BFRB/BRFB [START_REF] Rieger | Backward-forward-reflected-backward splitting for three operator monotone inclusions[END_REF]. Nevertheless, the OSPEP is applicable for analyzing these types of methods and, in particular, can be used to find the convergence proofs presented in these references.

Tight analytic contraction factors for DRS.

In this section, we present tight analytic contraction factors for DRS under two sets of assumptions considered in [START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF][START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF]. The primary purpose of this section is to demonstrate the strength of the OSPEP methodology through proving results that are likely too complicated for a human to find bare-handed. The proofs are computer-assisted in that their discoveries were assisted by a computer, but their verifications do not require a computer.

The results below are presented for α = 1. The general rate for α > 0 follows from the scaling µ → αµ, β → β/α, and L → αL. The proofs are presented in the supplementary materials, in Section SM3.

I -θJ B +θJ A (2J B -I) for θ ∈ (0, 2) is ρ =                |1 -θ β β+1 | if µβ -µ + β < 0 and θ ≤ 2 (β+1)(µ-β-µβ) µ+µβ-β-β 2 -2µβ 2 , |1 -θ 1+µβ (µ+1)(β+1) | if µβ -µ -β > 0 and θ ≤ 2 µ 2 +β 2 +µβ+µ+β-µ 2 β 2 µ 2 +β 2 +µ 2 β+µβ 2 +µ+β-2µ 2 β 2 , |1 -θ| if θ ≥ 2 µβ+µ+β 2µβ+µ+β , |1 -θ µ µ+1 | if µβ + µ -β < 0 and θ ≤ 2 (µ+1)(β-µ-µβ) β+µβ-µ-µ 2 -2µ 2 β , ρ 5
otherwise, with

ρ 5 = √ 2-θ 2 ((2-θ)µ(β+1)+θβ(1-µ)) ((2-θ)β(µ+1)+θµ(1-β)) µβ(2µβ(1-θ)+(2-θ)(µ+β+1))
.

(In the first, second, and fourth cases, the former parts of the conditions ensure that there is no division by 0 in the latter parts. We show this in Section SM4.

I -J B + J A (2J B -I) is ρ =            |1 -β β+1 | if β 2 + µβ + β -µ ≤ 0, |1 -1+µβ (µ+1)(β+1) | if µβ -µ -β ≥ 1, |1 -µ µ+1 | if µ 2 + µβ + µ -β ≤ 0, 1 2 β+µ √ βµ(β+µ+1)
otherwise.

Proof. Plug θ = 1 into Theorem 4.1 and simplify. We omit the details.

Theorem 4.3. Let A ∈ M µ and B ∈ M∩L L with µ, L > 0, and assume dim H ≥ 3. The tight contraction factor of the DRS operator

I -θJ B + θJ A (2J B -I) for θ ∈ (0, 2) is ρ =            θ+ (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 L 2 +1 2(µ+1) if (a), |1 -θ L+µ (µ+1)(L+1) | if (b), (2-θ) 4µ(L 2 +1) (θ(L 2 +1)-2µ(θ+L 2 -1))(θ(1+2µ+L 2 )-2(µ+1)(L 2 +1)) 2µ(θ+L 2 -1)-(2-θ)(1-L 2 ) otherwise, with (a) µ -(2(θ-1)µ+θ-2)+L 2 (θ-2(1+µ)) √ (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 ≤ √ L 2 + 1, (b) L < 1, µ > L 2 +1 (L-1) 2 , and θ ≤ 2(µ+1)(L+1)(µ+µL 2 -L 2 -2µL-1) 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 .
(In case (b), the former part of the condition ensures that there is no division by 0 in the latter part. We show this in Section SM4.

-J B + J A (2J B -I) is ρ =            1+ (1-2(µ+1)) 2 L 2 +1 L 2 +1 2(1+µ) if (µ -1)(2µ + 1) 2 L 2 ≥ 2µ 2 -2 √ 2 √ µ + 1µ + µ + 1 or µ ≤ 1, 1+µL (1+µ)(1+L) if L ≤ 2µ 2 (L-1)L 2 +µ(1-2L)-1 (µ+1)(L 2 +L+1) and L < 1, (2µL 2 +L 2 +1)(2µL 2 -L 2 -1) 4µ(L 2 +1)(2µL 2 +L 2 -1)
otherwise.

Proof. Plug θ = 1 into Theorem 4.3 and simplify. We omit the details.

4.1. Proof outline. The discovery of these proofs relied heavily on a computer algebra system (CAS), Mathematica. When symbolically solving the primal problem, we conjectured that the worst-case operators would exist in R 2 . This is equivalent to conjecturing that the solution G ∈ R 3×3 has rank 2 or less, which is reasonable due to complementary slackness. We then formulated the problem of finding this 2-dimensional worst-case as a non-convex quadratic program, rather than an SDP, formulated the KKT system, and solved the stationary points using the CAS. When symbolically solving the dual problem, we conjectured that the optimal solution would correspond to S ∈ R 3×3 with rank 1 or 2, which is reasonable due to complementary slackness. We then chose ρ 2 and the other dual variables so that S would have rank 1 or 2. Finally, we minimized the contraction factor ρ 2 under those rank conditions to obtain the optimum. These two approaches gave us analytic expressions for optimal primal and dual SDP solutions. To verify the solutions, we formulated them into primal and dual feasible points and verified that their optimal values are equal for all parameter choices.

The written proof of Theorems 4.1 and 4.3, are deferred to supplementary materials, to Sections SM3 and SM4. The point we wish to make in this section is that the OSPEP is a powerful tool that enables us to prove incredibly complex results. The length and complexity of the proofs demonstrate this point.

The proofs provided on paper are complete and rigorous. However, we help readers verify the calculations of Sections SM3 and SM4 with code that performs symbolic manipulations. If a reader is willing to trust the CAS's symbolic manipulations, the proofs are not difficult to follow. We also verified the results through the following alternative approach: we finely discretized the parameter space and verified that the upper and lower bounds of Section SM3 are valid and that they match up to machine precision. The link to the code is provided in the conclusion. The optimal α and θ minimizing the contraction factor of Theorems 4.1 and 4.3 can be computed with the algorithm presented in Section 5. However, their analytical expressions seem to be quite complicated.

If we furthermore assume A and B are subdifferential operators of closed convex proper functions, the contraction factors of Theorems 4.1 and 4.3 remain valid but our proof no longer guarantees tightness; with the additional assumptions, it may be possible to obtain a smaller contraction factor. Such setups can be analyzed with the machinery and interpolation results of [START_REF] Taylor | Smooth strongly convex interpolation and exact worst-case performance of first-order methods[END_REF]. By numerically solving the SDP with the added subdifferential operator assumption, we find that Theorem 4.1 remains tight. For subdifferential operators of convex functions, Lipschitz continuity implies cocoercivity by the Baillon-Haddad theorem, so there is no reason to consider Theorem 4. Table 2 lists other commonly considered assumptions providing linear convergence of DRS and the corresponding prior work analyzing them. The results of Theorems 4.1 and 4.3 provide the tight contraction factors for the three cases for which there had not been tight results.

5. Automatic optimal parameter selection. When using FBS, DRS, or DYS, how should one choose the parameters α > 0 and θ ∈ (0, 2)? One option is to find a contraction factor and choose the α and θ that minimizes it. However, this may be suboptimal if the contraction factor is not tight or if no known contraction factors fully utilize a given set of assumptions

In this section, we use the OSPEP to automatically select the optimal algorithm parameters for FBS, DRS, and DYS. Write

ρ 2 (α, θ) =     maximize T (z; A, B, C, α, θ) -T (z ; A, B, C, α, θ) 2 z -z 2 subject to A ∈ Q 1 , B ∈ Q 2 , C ∈ Q 3 z, z ∈ H, z = z    
where z, z , A, B, and C are the optimization variables. This is the tight contraction factor of (3.1), and we make explicit its dependence on α and θ. Define

ρ 2 = inf α>0, θ∈(0,2) ρ 2 (α, θ)
and write α and θ for the optimal parameters that attain the infimum, if they exist. Again, for simplicity of exposition, we limit the generality and consider the operator classes

Q 1 = M µ , Q 2 = C β ∩ L L , and Q 3 = C β C , as in Section 3.1.2. For β ∈ (0, ∞) and L ∈ (0, ∞), the intersection C β ∩ L L is non-degenerate.
ρ 2 (α, θ) =   minimize ρ 2 subject to λ A µ , λ B β , λ B L , λ C β ≥ 0 S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) 0   ,
where ρ 2 , λ A µ , λ B β , λ B L , and λ C β are the optimization variables and S is as in (3.8). Note that

S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) =        ρ 2 + λ B β β α + λ B L -1 λ A µ 2 -λ B β ( 1 2 + β α ) -λ B L 0 λ A µ 2 λ A µ (1 + αµ) -λ A µ λ A µ 2 -λ B β ( 1 2 + β α ) -λ B L -λ A µ λ B β ( β α -1) + λ B L (1 -α 2 L 2 ) - λ C β 2 0 λ A µ 2 - λ C β 2 λ C β β C α        -     1 θ -θ 0         1 θ -θ 0     T is the Schur complement of S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) =          ρ 2 + λ B β β α + λ B L -1 λ A µ 2 -λ B β ( 1 2 + β α ) -λ B L 0 1 λ A µ 2 λ A µ (1 + αµ) -λ A µ λ A µ 2 θ -λ B β ( 1 2 + β α ) -λ B L -λ A µ λ B β ( β α -1) + λ B L (1 -α 2 L 2 ) - λ C β 2 -θ 0 λ A µ 2 - λ C β 2 λ C β β C α 0 1 θ -θ 0 1          ∈ R 5×5 .
Therefore S 0 if and only if S 0. We use S as it depends on θ linearly. Define ρ 2 (α) = inf θ∈(0,2) ρ 2 (α, θ). We evaluate ρ 2 (α) by solving the SDP

ρ 2 (α) =   minimize ρ 2 subject to λ A µ , λ B β , λ B L , λ C β ≥ 0 S(ρ 2 , λ A µ , λ B β , λ B L , λ C β , θ, α) 0   , where ρ 2 , λ A µ , λ B β , λ B L , λ C
β , and θ are the optimization variables. It remains to solve

ρ 2 = inf α>0 ρ 2 (α).
The function ρ 2 (α) is non-convex in α, and it does not seem possible to compute ρ 2 with a single SDP. However, ρ 2 (α) seems to be continuous and unimodal for a wide range of operator classes and parameter choices. Continuity is not surprising. We do not know whether or why ρ 2 (α) is always unimodal.

To minimize the apparently continuous univariate unimodal function, we use Matlab's derivative free optimization (DFO) solver fminunc. We provide a routine that evaluates ρ 2 (α) by solving an SDP, and the DFO solver calls it to evaluate ρ 2 (α) at various values of α. Figure 1 shows an example of the function ρ 2 (α), and its minimizer was approximated with this approach. In Figure 2, we plot ρ 2 (α) under several assumptions. In all cases, ρ 2 (α) is continuous and unimodal.

Conclusion.

In this work, we presented the OSPEP methodology, proved its tightness, and demonstrated its value by presenting two applications of it. The first application was to prove tight analytic contraction factors for DRS and the second was to provide a method for automatic optimal parameter selection.

Code. With this paper, we release the following code: Matlab script implementing OSPEP for FBS, DRS, and DYS; Matlab script used to plot the figures of Section 5; and Mathematica script to help readers verify the algebra of Section SM3. The code uses YALMIP [START_REF] Löfberg | Yalmip : A toolbox for modeling and optimization in matlab[END_REF] and Mosek [START_REF] Mosek Aps | The MOSEK optimization toolbox for MATLAB manual[END_REF] and is available at https://github.com/AdrienTaylor/OperatorSplittingPerformanceEstimation.

For splitting methods applied to convex functions, one can use the Matlab toolbox PESTO [START_REF] Taylor | Performance estimation toolbox (PESTO): automated worst-case analysis of first-order optimization methods[END_REF], available at https://github.com/AdrienTaylor/Performance-Estimation-Toolbox. All operator classes are subsets of M, and only the parameters used in the intersection are specified. For example, subfigure (e) uses the classes

RYU, TAYLOR, BERGELING, AND GISELSSON

Q 1 = M ∩ L L A , Q 2 = M µ B , and
Q 3 = {0}. constraints. maximize Tr(M O G) subject to Tr(M A µ G) ≥ 0, Tr(M A β G) ≥ 0, Tr(M A L G) ≥ 0 Tr(M B µ G) ≥ 0 ,Tr(M B β G) ≥ 0, Tr(M B L G) ≥ 0 Tr(M C µ G) ≥ 0, Tr(M C β G) ≥ 0, Tr(M C L G) ≥ 0 Tr(M I G) = 1 G 0 where G ∈ S 4
+ is the optimization variable and

M I =     1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0     , M O =     1 θ -θ 0 θ θ 2 -θ 2 0 -θ -θ 2 θ 2 0 0 0 0 0     M A µ =     0 -1 2 0 0 -1 2 -αµ A -1 1 -1 2 0 1 0 0 0 -1 2 0 0     , M A β =     -β A α -β A α -1 2 2β A α -β A α -β A α -1 2 -β A α -1 2β A α + 1 -β A α -1 2 2β A α 2β A α + 1 -4β A α 2β A α -β A α -β A α -1 2 2β A α -β A α     , M A L =     -1 -1 2 -1 -1 α 2 L 2 A -1 2 -1 2 2 -4 2 -1 -1 2 -1     , M B µ =     0 0 1 2 0 0 0 0 0 1 2 0 -αµ B -1 0 0 0 0 0     , M B β =     -β B α 0 β B α + 1 2 0 0 0 0 0 β B α + 1 2 0 -β B α -1 0 0 0 0 0     , M B L =     -1 0 1 0 0 0 0 0 1 0 α 2 L 2 B -1 0 0 0 0 0     , M C µ =     0 0 0 0 0 0 0 0 0 0 -αµ C 1 2 0 0 1 2 0     , M C β =     0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 1 2 -β C α     , M C L =     0 0 0 0 0 0 0 0 0 0 α 2 L 2 C 0 0 0 0 -1     .

The objective Tr(M

O G) corresponds to z -θ(z B -z A ) -z + θ(z B -z A ) 2 .
The equality constraint Tr(M I G) = 1 corresponds to z -z 2 = 1. The other 9 inequality constraints correspond to the three assumptions on the three operators. In particular, Tr(M A µ G) ≥ 0, Tr(M A β G) ≥ 0, and Tr(M A L G) ≥ 0 respectively correspond to the µ-strong monotonicity, β-cocoercivity, and L-Lipschitz continuity assumptions on A respectively. The assumptions on B and C have analogous correspondences. SM2. Full dual OSPEP. We state the full dual OSPEP with the same operator classes as in Section SM1. The dual OSPEP with fewer assumptions will be of an analogous form with fewer λ-variables.

minimize ρ 2 subject to λ A µ , λ A β , λ A L ≥ 0 λ B µ , λ B β , λ B L ≥ 0 λ C µ , λ C β , λ C L ≥ 0 S(ρ 2 , λ A µ , λ A β , λ A L , λ B µ , λ B β , λ B L , λ C µ , λ C β , λ C L , θ, α) 0 where ρ 2 , λ A µ , λ A β , λ A L , λ B µ , λ B β , λ B L , λ C µ , λ C β , λ C L ∈ R are the optimization variables and S(ρ 2 , λ A µ , λ A β , λ A L , λ B µ , λ B β , λ B L , λ C µ , λ C β , λ C L , θ, α) = ρ 2 M I -M O -λ A µ M A µ -λ A β M A β -λ A L M A L -λ B µ M B µ -λ B β M B β -λ B L M B L -λ C µ M C µ -λ C β M C β -λ C L M C L
is symmetric. The matrix can also explicitly be written as

S(ρ 2 , λ A µ , λ A β , λ A L , λ B µ , λ B β , λ B L , λ C µ , λ C β , λ C L , θ, α) =     S 1,1 S 2,1 S 3,1 S 4,1 S 2,1 S 2,2 S 3,2 S 4,2 S 3,1 S 3,2 S 3,3 S 4,3 S 4,1 S 4,2 S 4,3 S 4,4     with S 1,1 = ρ 2 -1 + β A α λ A β + β B α λ B β + λ A L + λ B L , S 2,1 = 1 2 (2 β A α λ A β -2θ + λ A β + 2λ A L + λ A µ ), S 3,1 = -2 β A α λ A β -β B α λ B β + θ -2λ A L - λ B β 2 -λ B L - λ B µ 2 , S 4,1 = β A α λ A β + λ A L , S 2,2 = β A α λ A β -θ 2 + λ A β + λ A L + λ A µ αµ A + λ A µ -λ A L α 2 L 2 A , S 3,2 = -(2 β A α + 1)λ A β + θ 2 -2λ A L -λ A µ , S 4,2 = 1 2 (2 β A α λ A β + λ A β + 2λ A L + λ A µ ), S 3,3 = 4 β A α λ A β + β B α λ B β -θ 2 + 4λ A L + λ B β + λ B L + λ B µ αµ B + λ B µ + λ C µ αµ C -λ B L α 2 L 2 B -λ C L α 2 L 2 C , S 4,3 = 1 2 (-4 β A α λ A β -4λ A L -λ C β -λ C µ ), S 4,4 = β A α λ A β + β C α λ C β + λ A L + λ C L .
SM3. Proofs of results in Section 4. We now prove Theorems 4.1 and 4.3. The approach is to provide an upper bound and a lower bound for each case (5 cases for Theorem 4.1 and 3 cases for Theorem 4.3). Since the upper and lower bounds match, weak duality tells us that the bounds are optimal, i.e., the contraction factors are tight.

In the language of the SDPs, the upper and lower bounds correspond to primal and dual feasible points, and their optimality is certified since they match (0 duality gap). Note that the strong duality result of Theorem 3.3 guarantees the existence of lower bounds matching the optimal upper bounds. Here, we explicitly provide lower bounds to certify the upper bounds are indeed optimal.

The proofs rely on inequalities that we assert by saying "It is possible to verify that ...." Whenever we do so, we provide a rigorous (and arduous) verification separately in Section SM4. We make this separation because the verifications are purely algebraic and do not illuminate the main proof. As an alternative means of verification, we provide code that uses symbolic manipulation to verify the inequalities.

SM3.1. Proof of Theorem

4.1. Define R (a) = (µ, β, θ) µβ -µ + β < 0, θ ≤ 2 (β+1)(µ-β-µβ) µ+µβ-β-β 2 -2µβ 2 , µ > 0, β > 0, θ ∈ (0, 2) R (b) = (µ, β, θ) µβ -µ -β > 0, θ ≤ 2 µ 2 +β 2 +µβ+µ+β-µ 2 β 2 µ 2 +β 2 +µ 2 β+µβ 2 +µ+β-2µ 2 β 2 , µ > 0, β > 0, θ ∈ (0, 2) R (c) = (µ, β, θ) θ ≥ 2 µβ+µ+β 2µβ+µ+β , µ > 0, β > 0, θ ∈ (0, 2) R (d) = (µ, β, θ) µβ + µ -β < 0, θ ≤ 2 (µ+1)(β-µ-µβ) β+µβ-µ-µ 2 -2µ 2 β , µ > 0, β > 0, θ ∈ (0, 2) R (e) = (µ, β, θ) µ > 0, β > 0, θ ∈ (0, 2) \R (a) \R (b) \R (c) \R (d)
which correspond to the 5 cases of Theorem 4.1.

SM3.1.1. Upper bounds. By weak duality between the primal and dual OS-PEP, ρ is a valid contraction factor if there exists ρ, λ A µ ≥ 0, and λ B β ≥ 0 such that

S =    ρ 2 + βλ B β -1 -θ + λ A µ 2 θ -( 1 2 + β)λ B β -θ + λ A µ 2 -θ 2 + (1 + µ)λ A µ θ 2 -λ A µ θ -( 1 2 + β)λ B β θ 2 -λ A µ -θ 2 + (1 + β)λ B β    0.
For each of the 5 cases, we establish an upper bound by providing values for ρ, λ A µ ≥ 0, and λ B β ≥ 0 such that S 0. We establish S 0 with a sum-of-squares factorization

(SM3.1) Tr(SG(z, z A , z B )) = K 1 m 1 z A + m 2 z B + m 3 z 2 + K 2 m 4 z B + m 5 z 2 ,
for some m 1 , m 2 , m 3 , m 4 , m 5 ∈ R and K 1 , K 2 ≥ 0, where

(SM3.2) G(z, z A , z B ) =   z 2 z, z A z, z B z, z A z A 2 z A , z B z, z B z A , z B z B 2   ∈ S 3 +
for z, z A , z B ∈ H. By arguments similar to that of Lemma 3.1, G(z, z A , z B ) ∈ S 3 + can be any 3 × 3 positive semidefinite matrix. Therefore Tr(SG(z, z A , z B )) ≥ 0, ∀z, z A , z A ∈ H ⇔ Tr(SM ) ≥ 0, ∀M 0 ⇔ S 0, i.e., the sum-of-squares factorization proves S 0. (We only need 2 terms in the sum-of-squares factorization, because it turns out that the optimal S has rank at most 2.)

Case (a). When (µ, β, θ) ∈ R (a) , we use

ρ 2 = 1 -θ β β+1 2 , λ A µ = 2θ 1+β 1-β 1 -θ β β+1 , λ B β = 2θ 1 -θ β β+1 .
This gives us the sum-of-square factorization (SM3.1) with

m 1 = -1, m 2 = (2-θ)(β+1) (2-θ)(β+1)+2µ(1+β-θβ) , m 3 = - (2-θ)β (2-θ)(β+1)+2µ(1+β-θβ) , m 4 = -β+1 β , m 5 = 1, K 1 = θ (2-θ)(β+1)+2µ(1+β-θβ) 1-β , K 2 = 2β 2 θ 1+β-θβ (1-β)(β+1) 2 (β-1)µ(2β(θ-1)+θ-2)-(2-θ)β(β+1) (2-θ)(β+1)+2µ(1+β-θβ)
.

It is possible to verify that there is no division by 0 in the definitions and that

λ A µ , λ B β , K 1 , K 2 ≥ 0 when (µ, β, θ) ∈ R (a) .
Case (b). When (µ, β, θ) ∈ R (b) , we use

ρ 2 = 1 -θ 1+µβ (µ+1)(β+1) 2 , λ A µ = 2θ β+1 β-1 1 -θ 1+µβ (µ+1)(β+1) , λ B β = 2θ µ-1 µ+1 1 -θ 1+µβ (µ+1)(β+1) .
This gives us the sum-of-square factorization (SM3.1) with

m 1 = -1, m 2 = 2 µ+1 - (2-θ)(β+1) (2-θ)(β+1)+2µ(1+β-θβ) , m 3 = -1 µ+1 + (2-θ)β (2-θ)(β+1)+2µ(1+β-θβ) , m 4 = -β+1 β , m 5 = 1, K 1 = θ (2-θ)(β+1)+2µ(1+β-θβ) β-1 , K 2 = 2θβ 2 (β+1)(µ+1)-θ(1+µβ) (µ+1) 2 (β-1)(β+1) 2 µβ 2 (-2θµ+θ+2µ)+θβ 2 +(θ-2)µ(µ+1)+β(θµ 2 +θ-2µ-2)-2β 2 (2-θ)(β+1)+2µ(1+β-θβ)
.

It is possible to verify that there is no division by 0 in the definitions and that

λ A µ , λ B β , K 1 , K 2 ≥ 0 when (µ, β, θ) ∈ R (b) .
Case (c). When (µ, β, θ) ∈ R (c) , we use

ρ 2 = (θ -1) 2 , λ A µ = 2θ(θ -1), λ B β = 2θ(θ -1)
This gives us the sum-of-square factorization (SM3.1) with

m 1 = -1, m 2 = - 2-θ 2(θ-1)µ+θ-2 , m 3 = 2-θ 2(θ-1)µ+θ-2 , m 4 = -1, m 5 = 1, K 1 = θ(2(θ -1)µ + θ -2), K 2 = 2(θ -1)θ θβ+θµ(1+2β)-2(µ+β+µβ) 2(θ-1)µ+θ-2 .
It is possible to verify that there is no division by 0 in the definitions and that

λ A µ , λ B β , K 1 , K 2 ≥ 0 when (µ, β, θ) ∈ R (c) .
Case (d). When (µ, β, θ) ∈ R (d) , we use

ρ 2 = 1 -θ µ µ+1 2 , λ A µ = 2θ 1 -θ µ µ+1 , λ B β = 2θ 1-µ 1+µ 1 -θ µ µ+1 .
This gives us the sum-of-square factorization (SM3.1) with

m 1 = -1, m 2 = 2-θ 2(θ-1)µ+θ-2 + 2 µ+1 , m 3 = - θµ (µ+1)(2(θ-1)µ+θ-2) , m 4 = -1, m 5 = 1, K 1 = -θ(2(θ -1)µ + θ -2), K 2 = 2θ((θ -1)µ -1) -θ(β-µ 2 (1+2β)-µ(1-β))-2(µ+1)(µβ+µ-β) (µ+1) 2 (2(θ-1)µ+θ-2)
.

It is possible to verify that there is no division by 0 in the definitions and that

λ A µ , λ B β , K 1 , K 2 ≥ 0 when (µ, β, θ) ∈ R (d) .
Case (e). When (µ, β, θ) ∈ R (e) , we use

ρ 2 = 2-θ 4 ((2-θ)µ(β+1)+θβ(1-µ)) ((2-θ)β(µ+1)+θµ(1-β)) µβ(2µβ(1-θ)+(2-θ)(µ+β+1)) , λ A µ = θ (2-θ)µ(β+1)+θβ(1-µ) β , λ B β = θ(2-θ) β (2-θ)µ(β+1)+θβ(1-µ) 2µβ(1-θ)+(2-θ).(µ+β+1) .
This gives us the sum-of-square factorization (SM3.1) with

m 1 = -2µ 2(θ-1)µβ+θβ+(θ-2)(µ+1)-2β β , m 2 = 2µ (β+1)(θ-2)+βθ β , m 3 = (θ -2) -µ (β+1)(θ-2)+βθ β m 4 = 0, m 5 = 0, K 1 = β 4µ θ 2µβ(1-θ)+(2-θ)(µ+β+1) , K 2 = 0.
It is possible to verify that there is no division by 0 in the definitions and that

ρ 2 , λ A µ , λ B β , K 1 , K 2 ≥ 0 when (µ, β, θ) ∈ R (e) .
Remark 1 (Constructing a classical proof with a dual solution). Given ρ 2 , λ A µ ≥ 0, and λ B β ≥ 0 such that S 0, one can construct a classical proof establishing ρ 2 as a valid contraction factor without relying on the OSPEP methodology. With G defined as in (SM3.2), we have

Tr(SG(z, z A , z B )) = ρ 2 z 2 -z -θ(z B -z A ) 2 -λ A µ ∆A, z A -µ z A 2 -λ B β ∆B, z B -β ∆B 2 , with ∆A = 2z b -z -z A and ∆B = z -z B .
The sum-of-square factorization gives us

ρ 2 z 2 -z -θ(z B -z A ) 2 -λ A µ ∆A, z A -µ z A 2 -λ B β ∆B, z B -β ∆B 2 = K 1 m 1 z A + m 2 z B + m 3 z 2 + K 2 m 4 z B + m 5 z 2 .
Reorganizing, we get

z -θ(z B -z A ) 2 = ρ 2 z 2 -λ A µ ∆A, z A -µ z A 2 -λ B β ∆B, z B -β ∆B 2 -(sum of squares).

Now revert the change of variables of Section 3.1 by substituting

z → z -z , z -θ(z B - z A ) → T DRS (z)-T DRS (z ), z B → J B z-J B z , and z A → J A (2J B z-z)-J A (2J B z -z )
to get a classical proof of the form

T DRS (z; A, B, 1, θ) -T DRS (z ; A, B, 1, θ) 2 = ρ 2 z -z 2 -λ A µ ∆A, J A (2J B z -z) -J A (2J B z -z ) -µ J A (2J B z -z) -J A (2J B z -z ) 2 -λ B β ∆B, J B z -J B z -β ∆B 2 -(sum of squares) where now ∆A = 2J B z -z -J A (2J B z -z) -2J B z + z + J A (2J B z -z ) and ∆B = z -J B z -z + J B z . Since A is µ-strong monotone, we have ∆A, J A (2J B z -z) -J A (2J B z -z ) -µ J A (2J B z -z) -J A (2J B z -z ) 2 ≥ 0. Since B is β-cocoercive, we have ∆B, J B z -J B z -β ∆B 2 ≥ 0.
Since λ A µ ≥ 0 and λ B β ≥ 0, we have a valid proof establishing

T DRS (z; A, B, 1, θ) -T DRS (z ; A, B, 1, θ) 2 ≤ ρ 2 z -z 2 .
SM3.1.2. Lower bounds. We now show that for the five cases, there are operators A ∈ M µ and B ∈ C β and inputs z 1 , z 2 ∈ H such that

T z 1 -T z 2 ≥ ρ z 1 -z 2 ,
where T = I -θJ B + θJ A (2J B -I) and ρ is given by Theorem 4.1. We construct the lower bounds for R 2 , since the construction can be embedded into the higher dimensional space H. Case (e). Define

K = ((2-θ)µ(µ+1)+β(µ-1)(2-θ+2µ(1-θ))) ((2-θ)µ+β(2(1-θ)µ-θ+2)) β 2 (θ-2)µ(2β(θ-2)-θ-2)+β 2 (2β+1)(θ-2) 2 +(2β-1)µ 3 (2β(θ-1)+θ-2) 2 -(2β-1)µ 2 (2β-θ+2)(2β(θ-1)+θ-2) .
It is possible to verify that there is no division by 0 in the definition of K and that 0 < K < 1/β 2 when (µ, β, θ) ∈ R (e) . Let

A = µ -a a µ , B = βK -K -K 2 β 2 K -K 2 β 2 βK ,
where

a = 2θµ+θ-2βθKµ-θK+2Kµ+2K-2µ-2+ √ 4(θ-2) 2 (µ+1) 2 (K-β 2 K 2 )+((θ-2)(K-1)-2µ(θ-βθK+K-1)) 2 2(θ-2) √ K-β 2 K 2 .
Since 1 2 (A+A T ) has two eigenvalues equal to µ and 1 2 (B -T +B -1 ) has two eigenvalues equal to β, we have A ∈ M µ and B ∈ C β . Then

T = T 1 -T 2 T 2 T 1 with T 1 = -θ(a 2 (βK+1)+(µ+1)(K(βµ+β+1)+µ))+(a 2 +(µ+1) 2 )(2βK+K+1)-2aθ √ K-β 2 K 2 (a 2 +(µ+1) 2 )(2βK+K+1) , T 2 = θ a 2 √ K-β 2 K 2 +a(K-1)+(µ 2 -1) √ K-β 2 K 2 (a 2 +(µ+1) 2 )(2βK+K+1)
, and

T T T = T 2 1 + T 2 2 0 0 T 2 1 + T 2 2 .
So this construction provides the lower bound ρ 2 = T 2 1 + T 2 2 . Under the assumption θ < 2 βµ+β+µ 2βµ+β+µ (i.e., when (µ, β, θ) / ∈ R (c) ), the lower bound simplifies to

ρ = √ 2-θ 2 ((2-θ)µ(β+1)-θβ(µ-1)) ((2-θ)β(µ+1)-θµ(β-1)) µβ(2µβ(1-θ)+(2-θ)(µ+β+1))
, and it is valid when (µ, β, θ) ∈ R (e) .

Case (b). When (µ, L, θ) ∈ R (b) , we use

ρ 2 = 1 -θ L+µ (µ+1)(L+1) 2 λ A µ = 2θ 1+L 1-L 1 -θ µ+L (µ+1)(L+1) , λ B L = θ L µ-1 µ+1 1 -θ µ+L (µ+1)(L+1) , λ B µ = 0.
This gives us the sum-of-square factorization (SM3.3) with

K 1 = θ 2(µ+1)(L+1)-θ(2µ+L+1) 1-L , K 2 = θ (L+1)(µ+1)-θ(L+µ) (µ+1) 2 (1-L)L(L+1) 2 2(µ+1)(L+1)(µ(1-L) 2 -(L 2 +1))+θ(µ(1+L+3L 2 -L 3 )+(1+L+L 2 +L 3 )+2µ 2 (L-1)) 2(µ+1)(L+1)-θ(2µ+L+1) m 1 = -1, m 2 = 2 µ+1 - (2-θ)(L+1) 2(µ+1)(L+1)-θ(2µ+L+1) , m 3 = 1 1+µ θ(µ+L)-2L(µ+1) 2(µ+1)(L+1)-θ(2µ+L+1) , m 4 = -(1 + L), m 5 = 1.
It is possible to verify that there is no division by 0 in the definitions and that

λ A µ , λ B L , λ B µ , K 1 , K 2 ≥ 0 when (µ, L, θ) ∈ R (b) . Case (c). When (µ, L, θ) ∈ R (c) , we use ρ 2 = (2-θ) 4µ(L 2 +1) (θ(L 2 +1)-2µ(θ+L 2 -1))(θ(1+2µ+L 2 )-2(µ+1)(L 2 +1)) 2µ(θ+L 2 -1)-(2-θ)(1-L 2 ) λ A µ = θ θ - 2µ(θ+L 2 -1) L 2 +1 , λ B L = (2-θ)θ (L 2 +1) θ(L 2 +1)-2µ(θ+L 2 -1) (2-θ)(1-L 2 )-2µ(θ+L 2 -1) , λ B µ = 0.
This gives us the sum-of-square factorization (SM3.3) with

K 1 = θ 4µ(L 2 +1)((2-θ)(1-L 2 )-2µ(θ+L 2 -1)) , m 1 = 4µ 2 1 -L 2 -θ + 2µ(2 -θ) 1 -L 2 , m 2 = 4µ L 2 + θ -1 , m 3 = 2µ 1 -L 2 -θ -(2 -θ) L 2 + 1 , K 2 = 0, m 4 = 0, m 5 = 0.
It is possible to verify that there is no division by 0 in the definitions and that

ρ 2 , λ A µ , λ B L , λ B µ , K 1 , K 2 ≥ 0 when (µ, L, θ) ∈ R (c) . SM3.2.
2. Lower bounds. We now show that for the three cases, there are operators A ∈ M µ and B ∈ L L ∩ M and inputs z 1 , z 2 ∈ H such that

T z 1 -T z 2 ≥ ρ z 1 -z 2 ,
where T = I -θJ B + θJ A (2J B -I) and ρ is given by Theorem 4.3. We construct the lower bounds for R 2 , since the construction can be embedded into the higher dimensional space H.

Case (a). Let

A = µ Id + N {0}×R , B = L 0 1 -1 0 . Then J A = 1 µ+1 0 0 0 1 , J B = 1 L 2 +1 1 -L L 1 ,
and

T = 1 -θ L 2 +1 Lθ L 2 +1
-Lθ(µ-1)

(L 2 +1)(µ+1) (-θ+µ+1)L 2 -θµ+µ+1 (L 2 +1)(µ+1)
.

The eigenvalues of T T T are given by

θ± (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 L 2 +1 2 4(µ+1) 2
.

This construction provides the lower bound

ρ = θ+ (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 L 2 +1 2(µ+1)
, and it is valid when (µ, L, θ) ∈ R (a) . (In fact, it is always valid.) This construction was inspired by Example 5.3 of [START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF].

Case (b). A = µI, B = LI, and T = 1 -θ L+µ (L+1)(µ+1) . This construction provides the lower bound ρ = |1 -θ L+µ (µ+1)(L+1) |, and it is valid when (µ, L, θ) ∈ R (b) . (In fact, it is always valid.)

Case (c). Define

K = L 2 +1 2L (µ-1)(L 2 (θ-2(µ+1))-(2(θ-1)µ+θ-2)) 2 -4(θ-2) 2 (µ+1)L 2 4µ 2 (θ+L 2 -1)((1-θ)(L 2 -µ)+L 2 µ-1)+(θ-2) 2 (µ+1)(L 2 +1) 2 .
It is possible to verify that there is no division by 0 in the definition of K and that 0

≤ K ≤ 1 when (µ, L, θ) ∈ R (c) . Let A = µ Id + N R×{0} , B = L K - √ 1 -K 2 √ 1 -K 2 K .
Since the eigenvalues of B T B and 1 2 (B T + B) are respectively both equal to L 2 and KL, we have B ∈ M ∩ L L . Then

J A = 1 µ+1 1 0 0 0 , J B = KL+1 L 2 +2KL+1 √ 1-K 2 L L 2 +2KL+1 - √ 1-K 2 L L 2 +2KL+1 KL+1 L 2 +2KL+1
, and

T = 1 -KLθ+θ L 2 +2KL+1 - √ 1-K 2 Lθ L 2 +2KL+1 √ 1-K 2 Lθ(µ-1) (L 2 +2KL+1)(µ+1) (-θ+µ+1)L 2 -K(θ-2)(µ+1)L-θµ+µ+1 (L 2 +2KL+1)(µ+1)
.

The eigenvalues of T T T are

T1±θ √ T2 2(µ+1) 2 (2KL+L 2 +1)
with

T 1 = θ 2 2KµL + 2µ(µ + 1) + L 2 + 1 -2θ(µ + 1) 2K(µ + 1)L + 2µ + L 2 + 1 + 2(µ + 1) 2 2KL + L 2 + 1 , T 2 = -2KL + L 2 + 1 (2(θ -1)µ + θ -2) 2 + 2KL(θ -2(µ + 1))(2(θ -1)µ + θ -2) + L 2 (θ -2µ -2) 2 .
This construction provides the lower bound

ρ 2 = T1+θ √ T2 2(µ+1) 2 (2KL+L 2 +1) .
Under the assumption

µ(-2(θ-1)µ-θ+L 2 (θ-2(µ+1))+2) √ (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 > L 2 + 1,
(i.e., when (µ, L, θ) / ∈ R (a) ), the lower bound simplifies to

ρ = (2-θ) 4µ(L 2 +1) (θ(L 2 +1)-2µ(θ+L 2 -1))(θ(1+2µ+L 2 )-2(µ+1)(L 2 +1)) 2µ(θ+L 2 -1)-(2-θ)(1-L 2 )
, and it is valid when (µ, L, θ) ∈ R (c) .

SM4. Algebraic verification of inequalities. We now provide the algebraic verifications of the inequalities asserted in Section SM3. The proofs of this section are based on elementary arguments and arduous algebra. To help readers follow and verify the basic but tedious computation, we provide code that uses symbolic manipulation to verify the steps.

A µ , λ B β , K 1 , K 2 ≥ 0 in each case. Case (a). Assume 0 < µ, 0 < β, 0 < θ < 2, and µ -µβ -β > 0 (a1) θ ≤ 2 (β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2
(no division by 0 implied, see (ii) below) (a2) Then:

(i) From (a1) it is direct to note that 1 -β > βµ -1 > 0 and hence also β < 1.

(ii) As the numerator of (a2) is positive (from β > 0 and (a1)) and as θ > 0, the denominator of (a2) is positive, i.e., µ + µβ -β -β 2 -2µβ 2 ≥ 0. To prove strict positivity, assume for contradiction that µ + µβ -β -β 2 -2µβ 2 = 0. This implies

β(β + 2(β -1)µ) = µ -µβ -β (a1)
> 0, and hence

0 < β + 2(β -1)µ (a1) < µ -µβ + 2(β -1)µ = µ(β -1) (i) < 0,
which is a contradiction. Therefore, we conclude

µ + µβ -β -β 2 -2µβ 2 > 0.
(iii) Multiply both sides of (a2) by β, reorganize, and use (a1) to get

1 + β -θβ (a2) ≥ (1-β 2 )(µ-β) µ+µβ-β-β 2 -2µβ 2 (a1) > µβ(1-β 2 ) µ+µβ-β-β 2 -2µβ 2 > 0.
(iv) Multiply both sides of (a2) by the denominator of (a2) (which is positive by (ii)) and reorganize to get

(β -1)µ(2β(θ -1) + θ -2) -(2 -θ)β(β + 1) ≥ 0.
(v) Multiply both sides of (a2) by β/(1 + β) and reorganize to get

1 -θ β β+1 ≥ (1-β)(µ-β) µ+µβ-β-β 2 -2µβ 2 > 0.
(v) shows λ A µ and λ B β are nonnegative. (i) shows the denominator of K 1 is positive. (iii) shows the numerator of K 1 is nonnegative. (i) and (iii) show the denominator of K 2 is positive. (iii) and (iv) show the numerator of K 2 is nonnegative. (iii) shows the denominator of m 2 and m 3 are positive.

Case (b). Assume 0 < µ, 0 < β, 0 < θ < 2, and

µβ -µ -β > 0 (b1) θ ≤ 2(µ+1)(µ+β+β 2 -µβ 2 ) µ 2 +β 2 +µ 2 β+µβ 2 +µ+β-2µ 2 β 2
(no division by 0 implied, see (ii) below)) (b2) Then:

(i) From (b1), we have µβ > µ+β. Therefore µ > 1+µ/β > 1 and

β > 1+β/µ > 1. (ii) The numerator of (b2) is negative since µ + β + β 2 -µβ 2 = (1 + β)(µ -µβ + β) (b1)
< 0. Since θ > 0, the denominator of (b2) is nonpositive. To prove strict negativity, we view the denominator of (b2) as a quadratic function of µ:

φ β (µ) = µ 2 + β 2 + µ 2 β + µβ 2 + µ + β -2µ 2 β 2 = (1 + β -2β 2 )
<0 by (i)

µ 2 + (1 + β 2 )µ + β + β 2 .
This quadratic is nonnegative only between its roots and

φ β (0) = β + β 2 > 0, φ β (β/(β -1)) = -β 2 β-1 < 0.
Therefore φ β (µ) < 0 for any µ > β/(β -1), which holds by (b1). Therefore we conclude denominator of (b2) is strictly negative. (iii) Multiply both sides of (b2) by (1 + β + 2µβ) and reorganize to get

(2 -θ)(β + 1) + 2µ(1 + β -θβ) ≥ - 2µ 2 (µ+1)(β 2 -1) µ 2 +β 2 +µ 2 β+µβ 2 +µ+β-2µ 2 β 2 > 0.
The latter inequality follows from (i) and (ii). (iv) Multiply both sides of (b2) by (1 + µβ) and reorganize to get

(β + 1)(µ + 1) -θ(1 + µβ) ≥ - (µ 2 -1)(β 2 -1)(µ+β) µ 2 +β 2 +µ 2 β+β 2 µ+µ+β-2µ 2 β > 0.
The latter inequality follows from (i) and (ii). (v) Multiply both sides of (b2) by -(µ 2 + β 2 + µ 2 β + µβ 2 + µ + β -2µ 2 β 2 ) (which is positive by (ii)) and reorganize to get Case (d). Assume 0 < µ, 0 < β, 0 < θ < 2, and

µβ 2 (-2θµ + θ + 2µ) + θβ 2 + (θ -2)µ(µ + 1) + β θµ 2 + θ -2µ -2 -2β 2 ≥ 0.
µ + µβ -β < 0 (d1) θ ≤ 2(µ+1)(β-µ-µβ) β+βµ-µ-µ 2 -2βµ 2
(no division by 0 implied, see (ii) below)) (d2) Then:

(i) From (d1) it is direct to note that µ < β β+1 < 1 and β > µ 1-µ > µ. (ii) As the numerator of (d2) is positive (from µ > 0 and (d1)) and as θ > 0, the denominator of (d2) is nonnegative. To prove strict positivity of the of the denominator, assume for contradiction that β + βµ -µ -µ 2 -2βµ 2 = 0. This implies that

-2βµ 2 + 2βµ -µ 2 = βµ -β + µ (d1)
< 0, and hence

0 > 2β(1 -µ) -µ (i) > µ > 0,
which is a contradiction. Therefore we conclude

β + βµ -µ -µ 2 -2βµ 2 > 0.
(iii) Multiply both sides of (d2) by (1 + 2µ) and reorganize to get

2(θ -1)µ + θ -2 ≤ - 2µ 2 (µ+1) β+βµ-µ-µ 2 -2βµ 2 < 0.
(iv) Multiply both sides of (d2) by µ and reorganize to get

(θ -1)µ -1 ≤ -(1-µ 2 )(β-µ) β+βµ-µ-µ 2 -2βµ 2 < 0,
where the latter inequality follows from (i) and (ii). (v) Multiply both sides of (d2) by the denominator of (d2) (which is positive by (ii)) and reorganize to get

-θ(β -µ 2 (1 + 2β) -µ(1 -β)) -2(µ + 1)(µβ + µ -β) ≥ 0.
(vi) Multiply both sides of (d2) by µ/(1 + µ) and reorganize to get

1 -θ µ µ+1 ≥ (1-µ)(β-µ) β+βµ-µ-µ 2 -2βµ 2 > 0,
where the latter inequality follows from (i) and (ii). (vi) shows λ A µ is nonnegative. (i) and (vi) show λ B β is nonnegative. (iii) shows K 1 is nonnegative. (iv) and (v) show the numerator of K 2 is nonpositive. (iii) shows the denominator of K 2 is negative. (iii) shows the denominators of m 2 and m 3 are negative.

Case (e). Assume 0 < µ, 0 < β, and 0 < θ < 2. First, we show that if (µ, β, θ) ∈ R (e) , then

θ < 2(µ+1)(1+β) 2µβ+µ+β+1 (e1)
If (e1) does not hold, i.e., θ ≥ 2 µ+β+µβ+1 µ+β+2µβ+1 , then > -2(µ+1)(β+1) µ+β+2µβ+1 (µ + β + 2µβ + 1) + 2(µ + 1)(β + 1) = 0, where the inequality follows from plugging in (e1). (iii) We have

θ(µ + β + 2µβ) -2(µ + β + µβ) ≥ 2 µ+β+µβ+1 µ+β+2µβ+1 (µ + β + 2µβ) -2(µ + β + µβ) = 2µβ µ+β+2µβ+1 > 0, which implies (c1). So (µ, β, θ) ∈ R (e) ⇒ (µ, β, θ) / ∈ R (c) ⇒ (e1).
(2 -θ)(1 + µ)β -θµ(β -1) = 2(µ + 1)β + θ(µ(1 -2β) -β) > 0,
because either µ(1 -2β) -β ≥ 0 and the inequality immediately follows or µ(1 -2β) -β < 0 and we use

2(µ + 1)β + θ(µ(1 -2β) -β) > 2(µ + 1)β + 2(µ+1)(1+β) 2µβ+µ+β+1 (µ(1 -2β) -β) = 2µ(µ+1) 2µβ+µ+β+1 > 0.
(ii) shows that the denominator of ρ 2 is positive. (i) and (iii) show that the numerator of ρ 2 is nonnegative. (i) shows that λ A µ is nonnegative. (i) shows that the numerator of λ B β is nonnegative. (ii) shows that the denominator of λ B β is positive. (ii) shows that the denominator of K 1 is positive. Hence we arrive to ρ, λ A µ , λ B β , K 1 , K 2 ≥ 0 in the region of interest. SM4.1.2. Lower bounds. It remains to show that (µ, β, θ) ∈ R (e) ⇒ 0 < K < 1/β 2 . In what follows, we first show 0 < K in part I, and we then show K < 1/β 2 in part II.

Before we proceed, let us introduce the symbol ¬ that denotes the logical negation, and point out the following elementary fact. If f (θ) = aθ + b is an affine function of θ, then either

f (θ) < max{f (θ min ), f (θ max )} for all θ ∈ (θ min , θ max ) or f (θ) = f (θ min ) = f (θ max ).
The two cases respectively correspond to a = 0 and a = 0. Part I. We now prove 0 < K. Define

a 1 = -θ(2βµ + β + µ) + 2(βµ + β + µ) a 2 = θ -(2β + 1)µ 2 + (β -1)µ + β + 2(µ + 1)(β(µ -1) + µ)
and

K den =θ 2 8β 3 µ 3 + 2β 3 µ + 2β 3 + 4β 2 µ 3 + 4β 2 µ 2 -β 2 µ + β 2 -2βµ 3 -µ 3 -µ 2 -4θ 4β 3 µ 3 + 2β 3 µ 2 + 2β 3 µ + 2β 3 + 4β 2 µ 3 + 3β 2 µ 2 + β 2 -βµ 3 -µ 3 -µ 2 + 4(µ + 1) 2β 3 µ 2 + 2β 3 + 3β 2 µ 2 + β 2 -µ 2 so that K = a 1 a 2 K den .
We have a 1 > 0 since (µ, β, θ) / ∈ R (c) , i.e., θ < 2 βµ+β+µ 2βµ+β+µ . We now show a 2 > 0. Since (µ, β, θ) / ∈ R (d) , we have 2 cases:

(i) Assume ¬(d1). Since a 2 is an affine function of θ and θ ∈ 0, 2 βµ+β+µ 2βµ+β+µ , either

a 2 > min a 2 θ=0 , a 2 θ=2 βµ+β+µ 2βµ+β+µ = min 2(µ + 1)(βµ -β + µ), 4βµ 2 2βµ+β+µ ≥ 0,
where the first term is nonnegative by ¬(d1), or

a 2 = 2(µ + 1)(βµ -β + µ) = 4βµ 2 2βµ+β+µ > 0.
In both cases, a 2 > 0. (ii) Assume (d1) and ¬(d2). In Section SM4.1.1 case (d) part (ii), we proved that (d1) implies -2βµ 2 + βµ + β -µ 2 -µ > 0. Since a 2 is an affine function of

θ and θ ∈ 2(µ+1)(β(-µ)+β-µ) -2βµ 2 +βµ+β-µ 2 -µ , 2 βµ+β+µ 2βµ+β+µ , either a 2 > min a 2 θ= 2(µ+1)(β(-µ)+β-µ) -2βµ 2 +βµ+β-µ 2 -µ , a 2 θ=2 βµ+β+µ 2βµ+β+µ = min 0, 4βµ 2 2βµ+β+µ = 0, or a 2 = 0 = 4βµ 2 2βµ+β+µ
. The latter case is impossible and we conclude a 2 > 0.

We now show K den > 0. We will use the following elementary fact. Let f (θ) = aθ 2 + bθ + c be a quadratic function. If a ≤ 0, f (θ min ) > 0, and f (θ max ) > 0, then f (θ) > 0 for all θ ∈ (θ min , θ max ). If a > 0, f (θ min ) > 0, f (θ max ) > 0, and f (θ max ) < 0, then f (θ) > 0 for all θ ∈ (θ min , θ max ). Consider the 2 cases: (i) Assume ¬(a1). Under this case, θ ∈ 0, 2 βµ+β+µ 2βµ+β+µ . We view K den as a quadratic function of θ. First, note

K den θ=0 = 4(µ + 1)((2β + 1)β 2 + (β + 1) 2 (2β -1)µ 2 )
and define φ µ (β) = (2β + 1)β 2 + (β + 1) 2 (2β -1)µ 2 . Since

φ µ µ µ+1 = 4µ 5 (µ+1) 3 > 0 dφµ dβ (β) = 2β 3(β + 1)µ 2 + 3β + 1 > 0
and β ≥ µ µ+1 by ¬(a1), we have φ µ (β) > 0 and K den θ=0 > 0. We have

K den θ=2 βµ+β+µ 2βµ+β+µ = 16β 3 µ 2 (β + µ) (2βµ + β + µ) 2 > 0.
Finally, note Therefore, the quadratic function satisfies K den > 0 for θ ∈ 0, 2 βµ+β+µ 2βµ+β+µ . (ii) Assume (a1) and ¬(a2). Under this case, θ ∈ 2(β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2 , 2 βµ+β+µ 2βµ+β+µ , and, in Section SM4.1.1 case (a) part (ii), we proved that (a1) implies µ + µβ -β -β 2 -2µβ 2 > 0. We first show µ > β. The fact that θ is in the interval implies

dK den dθ θ=2 βµ+β+µ 2βµ+β+µ = - 4βµ 4β 3 µ + 2β 3 + 4β 2 µ 2 + 2β 2 + βµ -µ 2 2βµ + β + µ and define φ µ (β) = 4β 3 µ + 2β 3 + 4β 2 µ 2 + 2β 2 + βµ -µ 2 . Since φ µ µ µ+1 = µ 2 (3µ(µ+1) 2 +2) (µ+1) 3
2(β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2 < 2 βµ+β+µ 2βµ+β+µ ⇔ 4β 2 µ β 2 (2µ + 1) + β(1 -µ) -µ = (2βµ + β + µ) 2(β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2 -2(βµ + β + µ) < 0 ⇔ β 2 (2µ + 1) + β(1 -µ) -µ < 0. Define φ µ (β) = β 2 (2µ + 1) >0 +β(1 -µ) -µ.
Since the coefficient of the quadratic term is positive, φ µ (0) = -µ < 0, and φ µ (µ) = 2µ 3 > 0, we conclude that φ µ (β) < 0 is only possible when β < µ, i.e., φ µ (β) < 0 ⇒ µ > β.

Now we view K den as a quadratic function of θ. We have

K den θ= 2(β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2 = 16β 5 µ 2 (µ-β) (µ-β(2βµ+β-µ+1)) 2 > 0 (since µ > β) K den θ=2 βµ+β+µ 2βµ+β+µ = 16β 3 µ 2 (β+µ) (2βµ+β+µ) 2 > 0. (SM4.1) Define φ(β, µ) = 8β 3 µ 3 + 2β 3 µ + 2β 3 + 4β 2 µ 3 + 4β 2 µ 2 -β 2 µ + β 2 -2βµ 3 -µ 3 -µ 2 ,
which is the coefficient for the quadratic term of K den . If φ(β, µ) ≤ 0 (i.e., the curvature K den of is nonpositive), then the two inequalities (SM4.1) implies

K den > 0 for θ ∈ 2(β+1)(µ-µβ-β) µ+µβ-β-β 2 -2µβ 2 , 2 βµ+β+µ
2βµ+β+µ . Now assume φ(β, µ) > 0. In this case, we have

dK den dθ θ=2 βµ+β+µ 2βµ+β+µ = - 4βµ(β 3 (4µ+2)+β 2 (4µ 2 +2)+βµ-µ 2 ) 2βµ+β+µ < -4βµ 2βµ+β+µ β 3 4µ + β 2 4µ 2 -µ 2 = -4βµ 2 2βµ+β+µ 4β 2 (β + µ) -µ If 4β 2 (β + µ) -µ > 0, then dK den dθ θ=2 βµ+β+µ 2βµ+β+µ
< 0, and we conclude that

K den > 0. We now show 4β 2 (β + µ) -µ > 0. Assume for contradiction that 4β 2 (β + µ) -µ ≤ 0, or equivalently, 4β 2 (β + µ) -µ ≤ 0 ⇔ 4β 3 ≤ µ(1 -4β 2 ),
which implies β < 1/2 and hence

4β 2 (β + µ) -µ ≤ 0 ⇔ 4β 3 ≤ µ(1 -4β 2 ) ⇔ µ ≥ 4β 3 1-4β 2 , and also dφ dµ (β, µ) = (2β -1) β 2 + 4βµ + 3(2βµ + µ) 2 + 2µ < 0.
We have assumed for contradiction that µ ≥ 4β 3 1-4β 2 , and on the other hand, (a1) and

β < 1/2 imply µ > β 1-β . If φ β, max 4β 3 1-4β 2 , β 1-β < 0, then φ(β, µ) < 0, the contradiction forces us to conclude 4β 2 (β + µ) -µ > 0. (A) If 4β 3 1-4β 2 ≥ β 1-β ⇔ -4β 3 + 8β 2 -1 ≥ 0, then φ β, 4β 3 1-4β 2 = - β 2 (64β 7 -16β 5 -16β 4 +4β 3 +8β 2 -1) (2β-1) 2 (2β+1) < 0, since 64β 7 -16β 5 -16β 4 + 4β 3 + 8β 2 -1 ≥ 64β 7 -16β 5 -16β 4 + 8β 3 (since -4β 3 + 8β 2 -1 ≥ 0) = 8β 3 (2β -1) 2 2β 2 + 2β + 1 > 0 (using β < 1 2 ). (B) If 4β 3 1-4β 2 < β 1-β ⇔ -4β 3 + 8β 2 -1 < 0), then φ β, β 1-β = β 3 (8β 3 +3β-2) (1-β) 3 < 0, since -4β 3 + 8β 2 -1 < 0 and β ∈ (0, 1/2) ⇒ 8β 3 + 3β -2 < 0.
This final point can be verified with simple plotting or with the following algebraic argument. Define χ(β) = -4β 3 + 8β 2 -1 and ψ(β) = 8β 3 + 3β -2. Since χ (β) = 4(4 -3β)β and ψ (β) = 3 8β 2 + 1 , the functions χ and ψ are increasing on β ∈ (0, 1/2). We have χ(0) < 0 and ψ(0) < 0. Furthermore,

χ 3 √ 2(3 √ 2+4) 2/3 -2 2/3 4 3 √ 3 √ 2+4 = 1 4 3 √ 2(48 √ 2+67) (3 √ 2+4) 5/3 + 6 √ 2(62 √ 2+87) (3 √ 2+4) 4/3 -16 ≈ 0.207156 > 0 and ψ 3 √ 2(3 √ 2+4) 2/3 -2 2/3 4 3 √ 3 √ 2+4 = 0.
So χ and ψ are increasing functions and χ hits its first positive root before ψ. Therefore χ(β) < 0 ⇒ ψ(β) < 0 on β ∈ (0, 1 2 ). Part II. We now prove K < 1/β 2 . Define

a 3 = θ β 2 2µ 2 -µ -1 -β µ 2 + 1 -µ(µ + 1) + 2(β + 1)(µ + 1)(β + µ -µβ), a 4 = θ β 2 (2µ + 1) -βµ + β -µ -2(β + 1)(βµ + β -µ).
Then β 2 K -1/β 2 K den = a 3 a 4 , where we know K den > 0 from part I. Now verifying K < 1 β 2 is equivalent to verifying a 3 a 4 < 0. Given 0 < µ, 0 < β, and 0 < θ < 2, we have

= max -2(β + 1)(βµ + β -µ), -4β 2 µ 2βµ+β+µ ≤ 0,
where the first term is nonpositive by the assumption βµ + β -µ ≥ 0, or

a 4 = -2(β + 1)(βµ + β -µ) = -4β 2 µ
2βµ+β+µ < 0. In both cases, a 4 < 0.

(i) Since a 3 is an affine function of θ and θ ∈ 0, 2 βµ+β+µ 2βµ+β+µ , either

a 3 > min a 3 θ=0 , a 3 θ=2 βµ+β+µ 2βµ+β+µ = min 2(β + 1)(µ + 1)(β + µ -βµ), 4βµ(β+µ) 2βµ+β+µ ≥ 0,
where the first term is nonnegative by ¬(b2), which is βµ -β -µ ≤ 0, or a 3 = 2(β + 1)(µ + 1)(β + µ -βµ) = 4βµ(β+µ) 2βµ+β+µ > 0. In both cases, we have a 3 > 0.

(ii) As we had shown in Section SM4.1.1 case (b) part (ii), we have

(b1) ⇒ -2β 2 µ 2 + β 2 µ + β 2 + βµ 2 + β + µ 2 + µ < 0,
and we have no division by 0 in considering ¬(b2).

Since a 3 is an affine function of θ and θ ∈

2(β 2 +βµ+β+µ 2 +µ-µ 2 β 2 ) -2β 2 µ 2 +β 2 µ+β 2 +βµ 2 +β+µ 2 +µ , 2 βµ+β+µ 2βµ+β+µ , either a 3 > min    a 3 θ= 2(β 2 +βµ+β+µ 2 +µ-µ 2 β 2 ) -2β 2 µ 2 +β 2 µ+β 2 +βµ 2 +β+µ 2 +µ , a 3 θ=2 βµ+β+µ 2βµ+β+µ    = min 0, 4βµ(β+µ) 2βµ+β+µ = 0, or a 3 = 0 = 4βµ(β+µ)
2βµ+β+µ . The latter case is impossible, and we conclude a 3 > 0.

(iii) As we had shown in Section SM4.1.1 case (a) part (ii), we have

(a1) ⇒ µ + βµ -β -β 2 -2β 2 µ > 0,
and we have no division by 0 in considering ¬(a2).

Since a 4 is an affine function of θ and θ ∈ 2 (β+1)(µ-βµ-β) µ+βµ-β-β 2 -2β 2 µ , 2 βµ+β+µ 2βµ+β+µ , either

a 4 < max a 4 θ=2 (β+1)(µ-βµ-β) µ+βµ-β-β 2 -2β 2 µ , a 4 θ=2 βµ+β+µ 2βµ+β+µ = max 0, -4β 2 µ 2βµ+β+µ = 0. or a 4 = 0 = -4β 2 µ 2βµ+β+µ
The latter case is impossible, and we conclude a 4 < 0. Since a 3 is an affine function of θ and θ ∈ (2

(β+1)(µ-βµ-β) µ+βµ-β-β 2 -2β 2 µ , 2 βµ+β+µ 2βµ+β+µ ), either a 3 > min a 3 θ=2 (β+1)(µ-βµ-β) µ+βµ-β-β 2 -2β 2 µ , a 3 θ=2 βµ+β+µ 2βµ+β+µ = min 4β(1-β 2 )µ 2 µ+βµ-β-β 2 -2β 2 µ , 4βµ(β+µ) 2βµ+β+µ > 0,
where the first term is positive since 1 > β follows from (a1), or

a 3 = 4β(1-β 2 )µ 2 µ+βµ-β-β 2 -2β 2 µ = 4βµ(β+µ) 2βµ+β+µ > 0.
In both cases, we have a 3 > 0.

SM4.2. Inequalities for Theorem 4.3. SM4.2.1. Upper bounds. It remains to show that there is no division by 0 and λ A µ , λ B L , K 1 , K 2 ≥ 0 in each case. Case (a). Since the quantities in Section SM3.2.1 Case (a) are simple, we verify by inspection that there is no division by 0 and λ A µ , λ B L , K 1 , K 2 ≥ 0. Case (b). Assume 0 < µ, 0 < L, 0 < θ < 2, and

L < 1 (SM4.2) µ > L 2 +1
(L-1) 2 (SM4.3) θ ≤ 2(µ + 1)(L + 1)

µ+µL 2 -L 2 -2µL-1 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 (SM4.4)
(no division by 0 implied by (ii) below) (i) From (SM4.2) and (SM4.3), it is direct to obtain µ > 1.

(ii) The numerator of (SM4.4) is positive since, by (SM4.3), we have

µ + µL 2 -L 2 -2µL -1 = µ(1 -L) 2 -L 2 + 1 > 0.
Since θ > 0, the denominator of (SM4.4) is nonnegative. To prove strict positivity, we view the denominator of (SM4.4) as a quadratic function of µ:

φ L,θ (µ) = 2µ 2 -µ + µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L -µL -L -1 = 2(1 -L) >0 by (SM4.2) µ 2 + (L 3 -3L 2 -L -1)µ -(1 + L)(1 + L 2 ).
This quadratic is nonpositive only between its roots and Therefore φ L,θ (µ) > 0 for all µ > L 2 +1 (L-1) 2 , which holds by (SM4.3). Therefore we conclude the denominator of (SM4.4) is strictly positive. (iii) Multiply both sides of (SM4.4) by (µ + L)/(µ + 1)(L + 1) and reorganize to get 1 -θ µ+L (µ+1)(L+1) ≥ 1 -2(µ + L)

µ+µL 2 -L 2 -2µL-1 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 = (µ-1)(1-L)(1+2µL+L 2 ) 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 > 0,
where the latter inequality follows from (SM4.2), (i), and (ii). (iv) Multiply both sides of (SM4.4) by (2µ + L + 1) and reorganize to get 2(µ + 1)(L + 1) -θ(2µ + L + 1) ≥ 4µ 2 (µ+1)L(1-L 2 ) 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 > 0, where the latter inequality follows from (SM4.2) and (ii). (v) Multiply both sides of (SM4.4) by the denominator of (SM4.4) (which is positive by (ii)) and reorganize to get 2(µ + 1)(L + 1) µ(1 -L) 2 -L 2 + 1 + θ µ 1 + L + 3L 2 -L 3 + 1 + L + L 2 + L 3 + 2µ 2 (L -1) ≥ 0.

(vi) Multiply both sides of (SM4.4) by L + µ and reorganize to get (L + 1)(µ + 1) -θ(L + µ) ≥ (µ 2 -1)(1-L 2 )(1+L 2 +2µL) 2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1 .

Since µ > 1 by (i), L < 1 by (SM4.2), and the denominator is positive by (ii), we have (L + 1)(µ + 1) -θ(L + µ) > 0.

(iv) shows λ A µ is nonnegative.

θ(L 2 + 1) -2µ(θ + L 2 -1) > θ(L 2 + 1) -(2 -θ)(1 -L 2 ) = 2 θ + L 2 -1 ≥ 0,
where the first inequality follows from (ii). (iv) We prove θ 1 + 2µ + L 2 -2(µ + 1) L 2 + 1 < 0. Note that (SM4.5), the main inequality from (i), can be reformulated as

0 < (2 -θ) 1 -L 2 -2µ θ + L 2 -1 = θ -2µ + L 2 -1 <0 by (i) -2(µ + 1) L 2 -1 . Therefore, θ < 2(µ+1)(1-L 2 ) 2µ-L 2 +1
and plugging this into θ gives us θ 1 + 2µ + L 2 -2(µ + 1) L 2 + 1 < -8µ(µ+1)L 2 2µ+1-L 2 < 0.

Let us view K den as a quadratic function of θ. From (ii) of case (c) of Section SM4.2.1, we have (2-θ) 1 -L 2 -2µ θ + L 2 -1 > 0, which we can reformulate as θ < 2(µ+1)(1-L 2 )

1-L 2 +2µ using to L < 1. Basic computation gives us

K den θ=0 = 4(µ + 1) µ 2 L 2 -1 2 + L 2 + 1 2 > 0, K den θ= 2(µ+1)(1-L 2 ) 1-L 2 +2µ = 16µ 2 (µ+1)L 2 (L 2 +1) 2
(1-L 2 +2µ) 2 > 0,

dK den dθ θ= 2(µ+1)(1-L 2 ) 1-L 2 +2µ = - 4µ(L 2 +1) 2 (2µ+L 2 +1) 1-L 2 +2µ
< 0.

If the quadratic term of K den is negative, K den is positive when θ is between the roots, and the interval θ ∈ 0, 2(µ+1)(1-L 2 )

1-L 2 +2µ
lies between the roots. If the quadratic term of K den is nonnegative, then the roots (if they exist) would lie in ( 2(µ+1)(1-L 2 ) 1-L 2 +2µ , ∞) because of the sign of the derivative. Therefore we conclude K den > 0 in both cases.

Part II. We now show K = L Remember that in Section SM4.2.1 case (c) part (ii) we had shown 2µ θ + L 2 -1 < (2 -θ) 1 -L 2 . Plugging this inequality into the first term of a 1 gives us

a 1 ≤ (2 -θ)(1 -L) 1 -L 2 -(2 -θ)(L + 1) L 2 + 1 = -2(2 -θ)L(L + 1) < 0.
Finally, we show a 2 ≥ 0. Remember that (µ, L, θ) ∈ R (b) ⇔ (SM4.2) and (SM4.3) and (SM4.4) so we divide (µ, L, θ) / ∈ R (b) into the following three cases: (i) Case ¬(SM4.2). This case corresponds to L ≥ 1, but this cannot happen as (µ, L, θ) / ∈ R (a) implies L < 1. (ii) Case (SM4.2) and ¬(SM4.3). This case corresponds to µ ≤ L 2 +1 (L-1) 2 . Plug L 2 + 1 ≥ µ(L -1) 2 into the second term of a 2 to get

a 2 ≥ 2µ µ(1 -L) θ + L 2 -1 + L 2 + 1 (1 + L -θ) ≥ µ(1 -L) θ + L 2 -1 + L 2 + 1 (1 + L -θ),
which we further split in two cases: either 1 + L -θ ≥ 0 and we use L 2 + 1 ≥ µ(L -1) 2 again to get a 2 ≥ θµL(1 -L) > 0, or 1 + L -θ < 0 and we use 0 < θ -L -1 ≤ θ + L 2 -1 and hence from the previous inequality on a 2 and µ > 1:

a 2 ≥ (1 -L) θ + L 2 -1 + L 2 + 1 (1 + L -θ) = (2 -θ)L(L + 1) > 0,
where the last inequality follows from θ < 2. (iii) Case (SM4.2) and (SM4.3) and ¬(SM4.4). Remember that in Section SM4.2.1 case (b) part (ii), we have shown that (SM4.2) and (SM4.3) implies

2µ 2 -µ + µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L -µL -L -1 > 0.
So there is no division by 0 in ¬(SM4.4) and we have θ(2µ 2 -µ+µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L-µL-L-1) > 2(µ+1)(L+1) µ + µL 2 -L 2 -2µL -1 .

We conclude by noting

Theorem 4 . 1 .

 41 Let A ∈ M µ and B ∈ C β with µ, β > 0, and assume dim H ≥ 3. The tight contraction factor of the DRS operator

  1.1 case (a) part (ii), case (b) part (ii), and case (d) part (ii).) Corollary 4.2. Let A ∈ M µ and B ∈ C β with µ, β > 0, and assume dim H ≥ 3. The tight contraction factor of the DRS operator

  2.1 case (b) part (ii).) Corollary 4.4. Let A ∈ M µ and B ∈ M ∩ L L with µ, L > 0, and assume dim H ≥ 3. The tight contraction factor of the DRS operator I

4. 2 .

 2 Further remarks. The third contraction factor of Theorem 4.1, the factor |1 -θ|, matches the contraction factor of Theorem 5.6 of[START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF]. The contraction factor for the other 4 cases do not match. This implies, Theorem 5.6 of[START_REF] Giselsson | Tight global linear convergence rate bounds for DouglasRachford splitting[END_REF] is tight when θ ≥ 2 µβ+µ+β 2µβ+µ+β but not in the other cases. The first contraction factor of Corollary 4.4, but not the second and third, matches the contraction factor of Theorem 5.2 of[START_REF] Moursi | Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator[END_REF] which instead assumes B is a skew symmetric L-Lipschitz linear operator, a stronger assumption than B ∈ M ∩ L.One can show that the contraction factors of Theorems 4.1 and 4.3 are symmetric in the assumptions. Specifically, if we swap the assumptions and instead assume [B ∈ M µ and A ∈ C β ] and [B ∈ M µ and A ∈ M ∩ L L ], the contraction factors of Theorems 4.1 and 4.3 remain valid and tight. The proof follows from using the "scaled relative graph" developed in the concurrent work by Ryu, Hannah, and Yin [67, Theorem 7].

Fig. 1 :

 1 Fig. 1: Plot of ρ 2 (α) under the assumptions A ∈ M µ , B ∈ C β ∩ L L , and C ∈ C β C with µ = 1, β = 0.01, L = 5, and β C = 9.The optimal parameters are α ≈ 0.131 and θ ≈ 1.644, and they produce the optimal contraction factor ρ 2 ≈ 0.737. We used Matlab's fminunc for the minimization.

  So strong duality holds by Theorem 3.3, and we use the dual OSPEP (3.7) to write

69 Fig. 2 :

 692 Fig.2: Plots of ρ 2 (α) under various assumptions. The plots are unimodal in all cases. All operator classes are subsets of M, and only the parameters used in the intersection are specified. For example, subfigure (e) uses the classesQ 1 = M ∩ L L A , Q 2 = M µ B , and Q 3 = {0}.

  Case (a). A = N {0} , B = 1 β I, and T = 1 -θ β 1+β I. This construction provides the lower bound ρ = |1 -θ β β+1 |, and it is valid when (µ, β, θ) ∈ R (a) . (In fact, it is always valid.) Case (b). A = µI, B = 1 β I, and T = 1 -θ 1+βµ (β+1)(µ+1) I. This construction provides the lower bound ρ = |1 -θ 1+µβ (µ+1)(β+1) |, and it is valid when (µ, β, θ) ∈ R (b) . (In fact, it is always valid.) Case (c). A = N {0} , B = 0, and T = (1 -θ)I. This construction provides the lower bound ρ = |1 -θ|, and it is valid when (µ, β, θ) ∈ R (c) . (In fact, it is always valid.) Case (d). A = µI, B = 0, and T = 1 -θ µ µ+1 I. This construction provides the lower bound ρ = |1 -θ µ µ+1 |, and it is valid when (µ, β, θ) ∈ R (d) . (In fact, it is always valid.)

SM4. 1 .

 1 Inequalities for Theorem 4.1. SM4.1.1. Upper bounds. It remains to show that there is no division by 0 and λ

2 µ+β+2µβ

 2 (i) and (iv) show λ A µ and λ B β are nonnegative. (i) shows the denominator of K 1 is positive. (iii) shows the numerator of K 1 is nonnegative. (i) and (iii) show the denominator of K 2 is positive. (iv) and (v) show the numerator of K 2 is nonnegative. (iii) shows the denominators of m 2 and m 3 are positive. Case (c). Assume 0 < µ, 0 < β, 0 < θ < 2Multiply both sides of (c1) by (1 + 2µ) and reorganize to get 2(θ -1)µ + θ -2 ≥ 2µ Multiply both sides of (c1) by (µ + β + 2µβ) to get θβ + θµ(1 + 2β) -2(µ + β + µβ) ≥ 0. (ii) shows λ A µ and λ B β are nonnegative. (i) shows K 1 is nonnegative. (i) shows the denominator of K 2 is positive. (ii) and (iii) show the numerator of K 2 is nonnegative. (i) shows the denominators of m 2 and m 3 are positive.

  (i) We have (2 -θ)µ(β + 1) + θβ(1 -µ) = θ(β -(2β + 1)µ) + 2(β + 1)µ > 0, because either β -(2β + 1)µ ≥ 0 and the inequality immediately follows or β -(2β + 1)µ < 0 and we use (e1) to get θ(β -(2β + 1)µ) + 2(β + 1)µ > 2(µ+1)(1+β) 2µβ+µ+β+1 (β -(2β + 1)µ) + 2(β + 1)µ = 2β(β+1) µ+β+2µβ+1 > 0. (ii) We have 2µβ(1 -θ) + (2 -θ)(µ + β + 1) > 0, because 2µβ(1 -θ) + (2 -θ)(µ + β + 1) = -θ(µ + β + 2µβ + 1) + 2(µ + 1)(β + 1)

  ) = 2β β(6µ + 3) + 4µ 2 + 2 + µ > 0 and β ≥ µ µ+1 by ¬(a1), we have φ µ (β) > 0 and dK den

  (µ, β, θ) ∈ R (a) ⇔ (a1) and (a2) and (µ, β, θ) ∈ R (b) ⇔ (b1) and (b2), where (a1), (a2), (b1), and (b2) are defined as in Section SM4.1.1. We show (µ, β, θ) ∈ R (e) ⇒ (µ, β, θ) / ∈ R (a) and (µ, β, θ) / ∈ R (b) and (µ, β, θ) / ∈ R (c) ⇒ a 3 a 4 < 0 by considering the following 3 cases: (i) ¬(a1) and ¬(b1) and (µ, β, θ) / ∈ R (c) ⇒ a 3 a 4 < 0 (ii) ¬(a1) and (b1) and ¬(b2) and (µ, β, θ) / ∈ R (c) ⇒ a 3 a 4 < 0 (iii) (a1) and ¬(a2) and (µ, β, θ) / ∈ R (c) ⇒ a 3 a 4 < 0 (i) & (ii) Since a 4 is an affine function of θ and θ ∈ 0, 2 βµ+β+µ 2βµ+β+µ , either a 4 < max a 4 θ=0 , a 4 θ=2 βµ+β+µ 2βµ+β+µ

φ

  L,θ (0) = -(1 + L)(1 + L 2 ) < 0, φ L,θ L 2 +1 (L-1) 2 = 2L (L 2 +1) 2 (1-L) 3 > 0.

  (i) and (iv) show λ B L is nonnegative. (v) shows the numerator of K 1 is nonnegative. (v) and (vi) show the numerator of K 2 is nonnegative. (v) shows the denominator of K 2 is positive. (v) shows the denominators of m 2 and m 3 are positive.Case (c). Assume (µ, L, θ) ∈ R (c) . Then:(i) We show L < 1. Since (µ, L, θ) / ∈ R (a) , we have 0 < L 2 + 1 < µ -(2(θ-1)µ+θ-2)+L 2 (θ-2(1+µ)) √ (2(θ-1)µ+θ-2) 2 +L 2 (θ-2(µ+1)) 2 .This implies the numerator of the right-most-side is positive:(SM4.5) 0 < -(2(θ -1)µ + θ -2) + L 2 (θ -2(1 + µ))<0 by µ>0, θ<2.Therefore L 2 < 2(θ -1)µ + θ -2 θ -2(1 + µ) = 1 + 2θµ θ -2(1 + µ) <0 by µ>0, θ<2< 1, and we conclude L < 1.(ii) We have (2 -θ) 1 -L 2 -2µ θ + L 2 -1 > 0, since it is a simple reformulation of (SM4.5). (iii) We have θ(L 2 + 1) -2µ(θ + L 2 -1) > 0, because either θ + L 2 -1 < 0 and θ(L 2 + 1) -2µ(θ + L 2 -1) > 0 or θ + L 2 -1 ≥ 0 and

2 1 a 2 = 2µ 2 ( 1 -

 21221 +1 2L Knum K den ≤ 1. Since K den > 0, we can equivalently show (SM4.6) L 2 + 1 K num -2LK den = a 1 a 2 ≤ 0 with a 1 = 2µ(1 -L) θ + L 2 -1 -(2 -θ)(L + 1) L 2 + L) θ + L 2 -1 + (2 -θ)(L + 1) L 2 + 1 + θµ (L-1) 3 -4L + 4µL(L + 1).

a 2 =

 2 θ(2µ 2 -µ + µL 3 -L 3 -3µL 2 -L 2 -2µ 2 L -µL -L -1) -2(µ + 1)(L + 1) µ + µL 2 -L 2 -2µL -1 ≥ 0.SM5. Visualization. In this section, we visualize the cases for Theorems 4.1 and 4.3 and the contraction factors for Corollaries 4.2 and 4.4.

Fig. 3 :

 3 Fig. 3: Parameter regions for the 5 cases of Theorem 4.1 in the µ-β-θ plane.

Fig. 4 :

 4 Fig. 4: Parameter regions for the 3 cases of Theorem 4.3 in the µ-L-θ plane.

Fig. 5 :

 5 Fig. 5: Contraction factor for Corollary 4.2 (when θ = 1) in the µ-β plane.

Fig. 6 :

 6 Fig. 6: Contraction factor for Corollary 4.4 (when θ = 1) in the µ-L plane.

  and Q 3 are problem data. Assume each class Q 1 , Q 2 , and Q 3 is a single operator class of Table1or is an intersection of classes of Table1. (So the reader can freely pick the assumptions; the minimal assumptions are that Q 1 , Q 2 , and Q 3 are monotone).

	By definition, ρ is a valid contraction factor if and only if
	ρ 2 ≥	sup
		A∈Q1,B∈Q2,C∈Q3,
		z,z ∈H, z =z

  All operator classes of Table 1 are homogeneous. Since Q 1 , Q 2 , and Q 3 are homogeneous, we can use the change of variables z

  2 , e 3 , e 4 ∈ H since dim H ≥ 4. Define z = z1 e 1 + z2 e 2 + z3 e 3 + z4 e 4 , z A = (z A ) 1 e 1 + (z A ) 2 e 2 + (z A ) 3 e 3 + (z A ) 4 e 4 . Define z B , z C ∈ H similarly. Then G is as given by (3.5) with the constructed z, z A , z B , z C ∈ H.

Table 2 :

 2 3. Indeed, numerical solutions of the SDP indicate Theorem 4.3 is not tight in this setup. Prior results on contraction factors of Douglas-Rachford splitting.

	Properties for A	Properties for B Reference Tight
	∂f , f : str. cvx & smooth	∂g	[26, 27]	Y
	∂f , f : str. cvx	∂g, g: smooth	[25]	N
	str. mono. & cocoercive	-	[25]	Y
	str. mono. & Lipschitz	-	[25]	Y
	str. mono.	cocoercive	[25]	N
	str. mono.	Lipschitz	[53]	N

RYU, TAYLOR, BERGELING, AND GISELSSON

Acknowledgements. Collaborations between the authors started during the LCCC Focus Period on Large-Scale and Distributed Optimization organized by the Automatic Control Department of Lund University. The authors thank the organizers and the other participants. Among others, we thank Laurent Lessard for insightful discussions on the topics of DRS and computer-assisted proofs. Ernest Ryu was supported in part by NSF grant DMS-1720237 and ONR grant N000141712162. Adrien Taylor was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement 724063). Pontus Giselsson was supported by the Swedish Foundation for Strategic Research and the Swedish Research Council.

Appendix

SM1. Full primal OSPEP. We state the full primal OSPEP with the operator classes

The primal OSPEP with fewer assumptions will be of an analogous form with fewer SM3.2. Proof of Theorem 4.3. Define R (a) = (µ, L, θ) µ -(2(θ-1)µ+θ-2)+L 2 (θ-2(1+µ))

which correspond to the 3 cases of Theorem 4.3.

SM3.2.1. Upper bounds.

The approach is similar to that of Section SM3.1.1. By weak duality between the primal and dual OSPEP, ρ is a valid contraction factor if there exists ρ, λ A µ ≥ 0, λ B L ≥ 0, and λ B µ ≥ 0 such that

We establish S 0 with a sum-of-squares factorization

Remark 2. As before, the dual matrix S satisfies

with ∆A = 2z b -z -z A and ∆B = z -z B . One can use this to construct a classical proof establishing ρ 2 as a valid contraction factor without relying on the OSPEP methodology, given ρ, λ A µ ≥ 0, λ B L ≥ 0, and λ B µ ≥ 0 such that S 0. Case (a). When (µ, L, θ) ∈ R (a) , we define

, which satisfies C > 0 for all values of L, µ, θ > 0, and we use

.

This gives us the sum-of-square factorization (SM3.3) with

When µ, L > 0 and θ ∈ (0, 2), we have

, which is immediately equivalent to the main condition defining R (a) .

(v) Finally, we show µ > 1. (We use this later in Section SM4.2.2.) Since (µ, L, θ) / ∈ R (a) we have

which, in turn, implies

where we used θ < 2 < 2(1 + µ) for the last inequality. Finally, using the implied µ (-

(iii) and (iv) shows the numerator of ρ 2 is nonpositive. (ii) shows the denominator of ρ 2 is negative. (iii) shows that λ A µ is nonnegative. (iii) shows that the numerator of λ B L is nonnegative. (ii) shows that the denominator of λ B L is positive. (ii) shows that the denominator of K 1 is positive.

2L Knum K den . In part I, we show K den > 0 and K num ≥ 0 using (µ, L, θ) / ∈ R (a) . In part I, we show K ≤ 1 using (µ, L, θ) / ∈ R (a) and (µ, L, θ) / ∈ R (b) . Part I. We now show K den > 0 and K num ≥ 0. First, we quickly recall (µ, L, θ) / ∈ R (a) ⇒ µ > 1 and (µ, L, θ) / ∈ R (a) ⇒ L < 1 by respectively (v) and (i) of case (c) of Section SM4.2.1.

Next we move on to the main proof. Note Reorganizing the last inequality gives us (µ + 1)K num > 0, which proves K num > 0.