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

Technische Samenvatting: Over-Relaxed Projected-Forward Iteraties voor Cocoercieve Variatietjes

Probleemstelling
Het artikel behandelt het variatietjesprobleem (VI): vind $p \in X$ zodanig dat $\langle f(p), x - p \rangle \geq 0$ voor alle $x \in X$, waarbij $X$ een niet-lege gesloten convexe verzameling is in een reële Hilbertruimte en $f$ een cocoercieve operator is. De focus ligt op de projected-forward iteratie (equivalent aan forward–backward splitting voor de normaaleklus) gedefinieerd door de vaste-punt afbeelding $G_\gamma = P_X(I - \gamma f)$.

Hoewel de globale convergentie van gerelaxeerde iteraties $x_{n+1} = x_n + \lambda_n(G_\gamma x_n - x_n)$ goed gevestigd is voor $\lambda_n$ binnen een specifiek interval van gemiddeldheid (averagedness), bepaalt de bestaande theorie niet de optimale relaxatieparameter $\lambda$ zodra de actieve restricties (het "actieve gezicht") zijn geïdentificeerd. Het artikel onderzoekt hoe $\lambda$ kan worden gekozen om de lokale spectrale radius te minimaliseren nadat het projectiegezicht is gestabiliseerd, specifiek voor box-restricties.

Methodologie
De auteurs analyseren het asymptotische gedrag van de iteratie onder de aanname van strikte complementariteit en lokale differentieerbaarheid van $f$.

1. Eindige Gezichtidentificatie: Onder strikte complementariteit identificeert het algoritme de actieve verzameling (variabelen bij de onderste/bovenste grenzen) en de vrije verzameling (variabelen strikt binnen de grenzen) in eindige tijd. Zodra deze zijn geïdentificeerd, werkt de projectie-operator $P_X$ als een constante masker op de actieve variabelen en als de identiteit op de vrije variabelen.
2. Lokale Linearisatie: Het artikel leidt de exacte afgeleide af van de gerelaxeerde afbeelding $R_{\gamma, \lambda}(x) = (1-\lambda)x + \lambda P_X(x - \gamma f(x))$ in $p$. Voor box-restricties neemt deze afgeleide $M_{\gamma, \lambda}$ een blok-driehoeksmatrijsvorm aan:
   • Het actieve blok heeft eigenwaarden gelijk aan $|1 - \lambda|$.
   • Het vrije blok hangt af van de Jacobiaan van $f$ beperkt tot de vrije variabelen ($J_{FF}$). Als $J_{FF}$ symmetrisch positief definiet is met eigenwaarden $\theta_j$, zijn de eigenwaarden van het vrije blok $|1 - \lambda \gamma \theta_j|$.
3. Spectrale Minimalisatie: De lokale convergentiesnelheid wordt beheerst door de spectrale radius $\rho(M_{\gamma, \lambda})$. De auteurs formuleren een scalaire minimax-probleem om $\max(|1-\lambda|, \max_j |1 - \lambda \gamma \theta_j|)$ te minimaliseren.
4. Beveiligde Selectie (Safeguarded Selection): Om globale convergentie te garanderen terwijl de lokale snelheid wordt benut, stellen de auteurs een adaptief algoritme voor (Algoritme 1). Dit algoritme:
   • Monitort het patroon van het actieve gezicht.
   • Verankert (locks) het patroon zodra het $K$ iteraties lang stabiel blijft.
   • Schat de spectrale extremen van het vrije blok.
   • Berekent de optimale $\lambda^*_{loc}$ en knipt deze af naar het globale interval van gemiddeldheid $[ \lambda_{min}, 1/\eta_\gamma - \epsilon ]$ om globale veiligheid te garanderen, zelfs als de identificatie van het gezicht voortijdig is.

Belangrijkste Bijdragen
Het artikel levert vijf specifieke bijdragen:

1. Globale Baseline: Het stelt een scherpe globale lineaire convergentie-certificering vast voor de gerelaxeerde geprojecteerde-forward afbeelding onder sterke monotoniciteit en cocoerciviteit, dienend als baseline voor de lokale analyse.
2. Post-Identificatie Afleiding: Het leidt de exacte afgeleide af van de gerelaxeerde afbeelding na eindige gezichtidentificatie voor $C^1$-operatoren, waarbij de blok-driehoeksstructuur wordt getoond die de actieve en vrije dynamiek scheidt.
3. Gesloten Vorm voor Optimale Relaxatie: Voor box-restricties met een symmetrische positief definitieve vrije Jacobiaan, leiden de auteurs een gesloten vorm af voor de scalaire minimizer van de lokale spectrale radius:
   $$\lambda^*_{loc} = \frac{2}{a_\gamma + b_\gamma}$$
   waarbij $a_\gamma$ en $b_\gamma$ de minimum- en maximumwaarden zijn van de verzameling $\{1\} \cup \{\gamma \theta_j\}$. Ze vermelden expliciet de conditie voor echte over-relaxatie ($\lambda^*_{loc} > 1$) als $a_\gamma + b_\gamma < 2$.
4. Gezamenlijke Afstemming Karakterisering: Het artikel karakteriseert het gezamenlijk optimale paar $(\gamma, \lambda)$. Een cruciale bevinding is dat als de forward-stap $\gamma$ na gezichtidentificatie vrij kan worden aangepast, de ongerelaxeerde keuze ($\lambda=1$) met een optimale $\gamma$ al lokaal optimaal is. Hieruit volgt dat externe relaxatie het meest waardevol is wanneer $\gamma$ gefixeerd, conservatief of globaal beperkt is.
5. Beveiligde Adaptieve Selector: Een praktisch algoritme wordt voorgesteld dat het actieve gezicht dynamisch verankert, spectrale parameters schat en de relaxatieparameter afknipt naar het veilige interval, waardoor de globale convergentie nooit in gevaar komt door lokale afstemming.

Resultaten
Numerieke experimenten op dichte 120-dimensionale affine benchmarks en een 80-dimensionale niet-lineaire probleem bevestigen de theoretische bevindingen:

• Beperkte Forward-stap: In een benchmark waar de lokaal optimale forward-stap $\gamma$ de globale grenzen overschrijdt, verminderde de adaptieve over-relaxatie (met vaste $\gamma$) het aantal iteraties met ongeveer 33% vergeleken met de ongerelaxeerde methode.
• Herstelbare Forward-stap: In een niet-lineaire test waar de optimale $\gamma$ globaal toelaatbaar was, presteerde het herafstemmen van $\gamma$ (met $\lambda=1$) beter dan over-relaxatie met een vaste, conservatieve $\gamma$.
• Veiligheid: Het patroon-resetmechanisme handelde tijdelijke foutieve gezichtsidentificaties succesvol af zonder de globale convergentie te verstoren, aangezien de relaxatieparameter altijd naar het veilige interval werd afgeknipt.

Betekenis en Claims
Het artikel positioneert zijn bijdrage bescheiden, niet als een vervanging voor algemene prestatie-estimatietechnieken of een generieke versnellingsheuristiek, maar als een mechanisme-specifieke analytische regel.

• Reikwijdte: De resultaten zijn specifiek van toepassing op box-geconstraineerde VI's met cocoercieve operatoren waarbij de vrije-gezicht Jacobiaan symmetrisch positief definit is.
• Rol van Over-relaxatie: De auteurs verduidelijken dat over-relaxatie ($\lambda > 1$) niet universeel superieur is. De specifieke nut ervan komt voort uit het feit dat het een noodzakelijke controlevariabele is om een suboptimale $\gamma$ te compenseren in regimes waar de forward-stap $\gamma$ vooraf gefixeerd of door globale stabiliteitseisen beperkt is.
• Beperkingen: De analyse steunt op de spectrale radius (asymptotische snelheid) in plaats van een eenstaps-normcontractie, waarbij wordt erkend dat niet-normaliteit in de volledige matrix voor polynomiale transiënten kan zorgen. De oplossing in gesloten vorm is specifiek voor de geometrie van box-restricties.

Concluderend biedt het artikel een precies criterium voor wanneer over-relaxatie voordelig is: het is een doelgerichte versnellingsmethode voor regimes met een vaste forward-stap waar de forward-stap niet lokaal geoptimaliseerd kan worden, in plaats van een generieke verbetering voor alle splitting-methoden.