Over-Relaxed Projected-Forward Iterations for Cocoercive Variational Inequalities: Active-Face Spectral Tuning

Technical Summary: Over-Relaxed Projected-Forward Iterations for Cocoercive Variational Inequalities

Problem Statement
The paper addresses the variational inequality (VI) problem: find $p \in X$ such that $\langle f(p), x - p \rangle \geq 0$ for all $x \in X$, where $X$ is a nonempty closed convex set in a real Hilbert space and $f$ is a cocoercive operator. The focus is on the projected-forward iteration (equivalent to forward–backward splitting for the normal cone inclusion), defined by the fixed-point map $G_\gamma = P_X(I - \gamma f)$.

While the global convergence of relaxed iterations $x_{n+1} = x_n + \lambda_n(G_\gamma x_n - x_n)$ is well-established for $\lambda_n$ within a specific averagedness interval, existing theory does not determine the optimal relaxation parameter $\lambda$ once the algorithm has identified the active constraints (the "active face"). The paper investigates how to select $\lambda$ to minimize the local spectral radius after the projection face has stabilized, specifically for box constraints.

Methodology
The authors analyze the asymptotic behavior of the iteration under the assumption of strict complementarity and local differentiability of $f$.

1. Finite Face Identification: Under strict complementarity, the algorithm identifies the active set (variables at lower/upper bounds) and the free set (variables strictly inside bounds) in finite time. Once identified, the projection operator $P_X$ acts as a constant mask on active variables and the identity on free variables.
2. Local Linearization: The paper derives the exact derivative of the relaxed map $R_{\gamma, \lambda}(x) = (1-\lambda)x + \lambda P_X(x - \gamma f(x))$ at the solution $p$. For box constraints, this derivative $M_{\gamma, \lambda}$ takes a block triangular form:
   • The active block has eigenvalues equal to $|1 - \lambda|$.
   • The free block depends on the Jacobian of $f$ restricted to free variables ($J_{FF}$). If $J_{FF}$ is symmetric positive definite with eigenvalues $\theta_j$, the free block eigenvalues are $|1 - \lambda \gamma \theta_j|$.
3. Spectral Minimization: The local convergence rate is governed by the spectral radius $\rho(M_{\gamma, \lambda})$. The authors formulate a scalar minimax problem to minimize $\max(|1-\lambda|, \max_j |1 - \lambda \gamma \theta_j|)$.
4. Safeguarded Selection: To ensure global convergence while exploiting local speed, the authors propose an adaptive algorithm (Algorithm 1). This algorithm:
   • Monitors the active face pattern.
   • Locks the pattern once it remains stable for $K$ iterations.
   • Estimates the spectral extremes of the free block.
   • Computes the optimal $\lambda^*_{loc}$ and clips it to the global averagedness interval $[ \lambda_{min}, 1/\eta_\gamma - \epsilon ]$ to guarantee global safety even if the face identification is premature.

Key Contributions
The paper makes five specific contributions:

1. Global Baseline: It establishes a sharp global linear convergence certificate for the relaxed projected-forward map under strong monotonicity and cocoercivity, serving as a baseline for local analysis.
2. Post-Identification Derivation: It derives the exact derivative of the relaxed map after finite face identification for $C^1$ operators, showing the block triangular structure that separates active and free dynamics.
3. Closed-Form Optimal Relaxation: For box constraints with a symmetric positive definite free Jacobian, the authors derive a closed-form scalar minimizer for the local spectral radius:
   $$\lambda^*_{loc} = \frac{2}{a_\gamma + b_\gamma}$$
   where $a_\gamma$ and $b_\gamma$ are the minimum and maximum of the set $\{1\} \cup \{\gamma \theta_j\}$. They explicitly state the condition for genuine over-relaxation ($\lambda^*_{loc} > 1$) as $a_\gamma + b_\gamma < 2$.
4. Joint Tuning Characterization: The paper characterizes the jointly optimal pair $(\gamma, \lambda)$. A critical finding is that if the forward step $\gamma$ can be freely retuned after face identification, the unrelaxed choice ($\lambda=1$) with an optimal $\gamma$ is already locally optimal. Thus, outer relaxation is most valuable when $\gamma$ is fixed, conservative, or globally constrained.
5. Safeguarded Adaptive Selector: A practical algorithm is proposed that dynamically locks the active face, estimates spectral parameters, and clips the relaxation parameter to the global safe interval, ensuring global convergence is never compromised by local tuning.

Results
Numerical experiments on dense 120-dimensional affine benchmarks and an 80-dimensional nonlinear problem confirm the theoretical findings:

• Constrained Forward Step: In a benchmark where the locally optimal forward step $\gamma$ violates global bounds, the adaptive over-relaxation (with fixed $\gamma$) reduced iteration counts by approximately 33% compared to the unrelaxed method.
• Retunable Forward Step: In a nonlinear test where the optimal $\gamma$ was globally admissible, retuning $\gamma$ (with $\lambda=1$) outperformed over-relaxation with a fixed conservative $\gamma$.
• Safety: The pattern-reset mechanism successfully handled transient face misidentifications without destroying global convergence, as the relaxation parameter was always clipped to the safe interval.

Significance and Claims
The paper modestly positions its contribution not as a replacement for global performance-estimation techniques or a general acceleration heuristic, but as a mechanism-specific analytic rule.

• Scope: The results apply specifically to box-constrained VIs with cocoercive operators where the free-face Jacobian is symmetric positive definite.
• Role of Over-Relaxation: The authors clarify that over-relaxation ($\lambda > 1$) is not universally superior. Its distinct utility arises when the forward step $\gamma$ is fixed in advance or constrained by global stability requirements. In such regimes, $\lambda$ acts as a necessary control variable to compensate for a suboptimal $\gamma$.
• Limitations: The analysis relies on the spectral radius (asymptotic rate) rather than one-step norm contraction, acknowledging that non-normality in the full matrix may cause polynomial transients. The closed-form solution is specific to the geometry of box constraints.

In conclusion, the paper provides a precise criterion for when over-relaxation is beneficial: it is a targeted acceleration tool for fixed-forward-step regimes where the forward step cannot be locally optimized, rather than a generic improvement for all splitting methods.