Spectral conjugate gradient projection methods for large-scale monotone equations without Lipschitz continuity

Technische Samenvatting: Spectrale Conjugate Gradient-projectiemethoden voor Groot-schalige Monotone Vergelijkingen

Probleemstelling
Het artikel behandelt het probleem van het vinden van een vector $x \in \Gamma$ zodat $G(x) = 0$, waarbij $G: \mathbb{R}^n \to \mathbb{R}^n$ een continue monotone afbeelding is en $\Gamma \subset \mathbb{R}^n$ een niet-lege, gesloten en convexe verzameling is. Deze formulering omvat variatie-ongelijkheidsproblemen, complementariteitsproblemen, berekeningen van chemisch evenwicht, gecomprimeerd waarnemen en geregulariseerde logistische regressie. Hoewel Newton-achtige methoden snelle lokale convergentie bieden voor differentieerbare $G$, zijn ze onpraktisch voor groot-schalige problemen vanwege de opslagvereisten van $O(n^2)$ en de noodzaak om Jacobianen te berekenen. Conjugate gradient (CG) methoden worden preferentieel behandeld voor groot-schalige situaties omdat ze alleen functiewaarden en $O(n)$ opslag vereisen. Het uitbreiden van CG-methoden naar beperkte situaties is echter doorgaans afhankelijk van projectietechnieken, en bestaande methoden vereisen vaak Lipschitz-continuïteit van $G$ of lijden onder suboptimale convergentiesnelheden.

Methodologie
De auteurs stellen twee afgeleide-vrije projectiemethoden voor die een adaptieve spectrale parameter $\lambda_k$ integreren in gevestigde conjugate gradient-kaders. Beide methoden maken gebruik van de Solodov–Svaiter projectietechniek, die het berekenen van een dalingsrichting omvat, het uitvoeren van een lijnzoektocht om een proefpunt te genereren, het construeren van een scheidend hypervlak op basis van de monotonie van $G$, en het projecteren van de huidige iteratie op dit hypervlak.

1. GMOPCGM (Generalized Modified Optimal Perry Conjugate Gradient Method):
   Deze methode generaliseert de Modified Optimal Perry Conjugate Gradient Method (MOPCGM) van Sabi'u et al. De zoekrichting is afgeleid van een gewijzigde optimale Perry-matrix waarbij de schaalparameter wordt vervangen door een adaptieve spectrale parameter $\lambda_k$. De parameter $\lambda_k$ is begrensd binnen $[\alpha_{\min}, \alpha_{\max}]$ en wordt bijgewerkt met Barzilai–Borwein-achtige spectrale verhoudingen gebaseerd op de lokale kromming ($s_{k-1}$ en $v_{k-1}$). De resulterende zoekrichting voldoet aan een voldoende dalingsvoorwaarde die onafhankelijk is van de lijnzoektocht.

2. GCGPM (Generalized Conjugate Gradient Projection Method):
   Deze methode generaliseert de CGPM van Zheng et al., die is gebaseerd op de Hager–Zhang-parameter. De auteurs introduceren een spectrale Dai–Liao-parameter $\lambda_k$ in de updateformule. Net als bij GMOPCGM past de spectrale parameter zich aan aan de lokale geometrie van het probleem. De zoekrichting wordt zo geconstrueerd dat voldoende daling wordt gewaarborgd.

Belangrijkste Bijdragen

• Afleiding van Nieuwe Zoekrichtingen: Het artikel leidt twee nieuwe zoekrichtingen af die bestaande MOPCGM- en CGPM-kaders generaliseren via een spectrale parameter $\lambda_k$.
• Onafhankelijkheid van Voldoende Daling: Het wordt bewezen dat beide voorgestelde methoden voldoen aan een voldoende dalingsvoorwaarde ($G_k^T p_k \leq -c \|G_k\|^2$) die geldt onafhankelijk van de lijnzoektochtstrategie.
• Globale Convergentie onder Zwakkere Aannames:
  • Voor GMOPCGM wordt globale convergentie vastgesteld onder alleen Aannames A1 (niet-lege oplossingsverzameling) en A2 (monotonie). Cruciaal is dat dit resultaat geen Lipschitz-continuïteit van $G$ vereist.
  • Voor GCGPM wordt globale convergentie bewezen onder de standaardaannames A1–A3, die Lipschitz-continuïteit omvatten.
• Praktische Effectiviteit: De methoden zijn getest op 18 benchmarkproblemen met dimensies tot 120.000, evenals toepassingen in gecomprimeerd waarnemen en geregulariseerde logistische regressie.

Numerieke Resultaten
De auteurs hebben uitgebreide numerieke experimenten uitgevoerd waarbij GMOPCGM en GCGPM werden vergeleken met drie bestaande methoden: MOPCGM, CGPM en STTDFPM.

• Benchmarkproblemen: In 5.400 runs (18 problemen, 6 dimensies, 10 startpunten) bereikte GCGPM de hoogste convergentiesnelheid (96,9%) en het laagste mediaan aantal iteraties (10) en functiewaarden (52). GMOPCGM convergeerde in 93,0% van de gevallen met een mediaan van 28 iteraties, een aanzienlijke verbetering ten opzichte van zijn voorganger MOPCGM (160 iteraties).
• Gecomprimeerd Waarnemen: Bij $\ell_1$-geregulariseerde taak voor signaalherstel convergeerden beide voorgestelde methoden op alle 240 testgevallen. GCGPM en GMOPCGM vereisten aanzienlijk minder iteraties en CPU-tijd in vergelijking met MOPCGM, dat faalde op 20 gevallen. Alle methoden bereikten een vergelijkbare gemiddelde kwadratische fout (MSE) bij signaalherstel.
• Geregulariseerde Logistische Regressie: Op real-world datasets voor binaire classificatie convergeerden beide voorgestelde methoden op alle 60 gevallen. GMOPCGM verlaagde het mediaan aantal iteraties van 2.447 (MOPCGM) naar 313, wat het voordeel van de spectrale generalisatie voor niet-lineaire monotone vergelijkingen aantoont. GCGPM was het meest efficiënt en vereiste 184 mediaan iteraties.

Betekenis en Claims
Het artikel beweert dat de integratie van adaptieve spectrale parameters in conjugate gradient-projectiekaders een robuuste aanpak biedt voor het oplossen van groot-schalige monotone vergelijkingen. De primaire theoretische betekenis ligt in het convergentiebewijs voor GMOPCGM, dat de vereiste voor Lipschitz-continuïteit verwijdert – een veelvoorkomende bottleneck in de analyse van afgeleide-vrije methoden voor monotone vergelijkingen. Praktisch tonen de resultaten aan dat de spectrale generalisatie de prestaties consistent verbetert ten opzichte van de basismethodes wat betreft convergentiesnelheid en rekentijd, waardoor de voorgestelde algoritmen geschikt zijn voor hoog-dimensionale toepassingen in signaalverwerking en machine learning. De auteurs merken op dat toekomstig werk de convergentieanalyse van GCGPM kan uitbreiden naar de pseudomonotone setting en inertieversnellings technieken kan verkennen.