Extended-Krylov-subspace methods for trust-region and norm-regularization subproblems

1. Il Problema

Il lavoro si concentra sulla risoluzione efficiente dei problemi sottomessi (subproblems) che sorgono in molte applicazioni di ottimizzazione non lineare, in particolare nei metodi di Trust-Region e nella regolarizzazione della norma.

Il problema di Trust-Region standard è definito come:
$$x^* = \arg \min_{x \in \mathbb{R}^n} \left( \frac{1}{2}x^T A x - b^T x \right) \quad \text{soggetto a} \quad \|x\| \le \Delta$$
dove $A$ è una matrice Hessiana simmetrica (non necessariamente definita positiva), $b$ è un vettore, e $\Delta$ è il raggio della regione di fiducia.

Un problema correlato è quello della regolarizzazione della norma (es. regolarizzazione cubica):
$$x^* = \arg \min_{x \in \mathbb{R}^n} \left( \frac{1}{2}x^T A x - b^T x + \frac{\rho}{r} \|x\|^r \right)$$

La sfida principale risiede nel fatto che, per grandi dimensioni ($n$), la risoluzione diretta di questi problemi richiede spesso fattorizzazioni multiple della matrice $A$ (o di $A + \sigma I$), che sono computazionalmente costose. I metodi basati su sottospazi di Krylov standard (come GLTR) evitano la fattorizzazione ma possono richiedere molte iterazioni, specialmente quando il parametro di spostamento $\sigma$ è vicino al limite dello spettro di $A$.

2. Metodologia e Approccio Teorico

Gli autori propongono un nuovo metodo basato sull'osservazione fondamentale che le soluzioni $x(\sigma)$ del problema, al variare del parametro di spostamento $\sigma$, giacciono all'interno di un sottospazio a dimensionalità molto bassa.

2.1. Analisi della Rango Basso

Analizzando la matrice delle soluzioni per diversi valori di $\sigma$, gli autori dimostrano che questa può essere approssimata da una matrice di rango basso (circa 35-40 vettori significativi anche per $n=10^4$). Questo è dovuto alla struttura di tipo matrice di Cauchy generalizzata della soluzione, che ammette approssimazioni razionali efficienti.

2.2. Sottospazio di Krylov Esteso (EKS)

Per catturare questa struttura a basso rango senza dover risolvere sistemi lineari multipli, il metodo utilizza un Sottospazio di Krylov Esteso. A differenza del sottospazio di Krylov classico che considera solo potenze positive di $A$ ($span\{b, Ab, A^2b, \dots\}$), il sottospazio esteso include anche le potenze negative (inverses):
$$\mathcal{K}_{2m}(A, b) = \text{span}\{b, A^{-1}b, Ab, A^{-2}b, A^2b, \dots, A^{-m}b\}$$
Questa inclusione permette di approssimare efficacemente sia il comportamento asintotico per grandi $\sigma$ (tramite serie di Laurent) che per piccoli $\sigma$ (tramite serie di Taylor), coprendo l'intero spettro di interesse.

2.3. L'Algoritmo TREK

Gli autori sviluppano l'algoritmo TREK (Trust-Region Extended Krylov) che costruisce una base ortonormale $V_\ell$ per questo sottospazio esteso.

• Costruzione della Base: Utilizza una procedura ricorsiva (simile all'algoritmo di Lanczos ma esteso) che richiede una singola fattorizzazione iniziale di $A$ (o di una versione spostata $A + \sigma_S I$ se $A$ non è definita positiva) per calcolare $A^{-1}b$. Successivamente, richiede solo prodotti matrice-vettore e prodotti vettore-vettore.
• Proiezione: Il problema originale di dimensione $n$ viene proiettato su un sottoproblema di dimensione $\ell$ (dove $\ell \ll n$):
  $$y_\ell = \arg \min_{y \in \mathbb{R}^\ell} \left( \frac{1}{2}y^T P_\ell y - b_\ell^T y \right) \quad \text{s.t.} \quad \|y\| \le \Delta$$
  dove $P_\ell = V_\ell^T A V_\ell$ è una matrice simmetrica pentadiagonale e $b_\ell$ è un vettore molto semplice.
• Risoluzione del Sottoproblema: Grazie alla struttura di $P_\ell$ e alla sua piccola dimensione, il sottoproblema può essere risolto in modo estremamente economico utilizzando metodi di ricerca della radice di alto ordine su una forma diagonalizzata, senza ulteriori fattorizzazioni costose.
• Criterio di Arresto: L'algoritmo monitora il residuo del sistema lineare spostato. Se il residuo è sufficientemente piccolo, la soluzione è accettata. Il metodo gestisce anche i casi "difficili" (hard case) e i casi interni.

2.4. Estensione a Matrici Indefinite e Norme Ellittiche

• Matrici Indefinite: Se $A$ non è definita positiva, il metodo utilizza uno spostamento diagonale $\sigma_S$ (basato sul teorema di Gershgorin) per rendere $A + \sigma_S I$ definita positiva, risolvendo il problema nello spazio trasformato.
• Norme Ellittiche: Il metodo è esteso per gestire vincoli della forma $\|Rx\| \le \Delta$ o $\|x\|_S \le \Delta$, adattando le operazioni di prodotto scalare e inverso.

3. Contributi Chiave

1. Dimostrazione della Bassa Dimensionalità: Prove teoriche ed empiriche che l'insieme delle soluzioni di Trust-Region giace in un sottospazio di dimensione molto ridotta, indipendente dalla dimensione del problema originale.
2. Algoritmo TREK: Un nuovo algoritmo che combina la costruzione di un sottospazio di Krylov esteso (richiedendo una sola fattorizzazione) con la risoluzione efficiente di sottoproblemi proiettati.
3. Efficienza nei "Resolves": Il metodo è particolarmente vantaggioso quando è necessario risolvere una sequenza di problemi con lo stesso $A$ e $b$ ma con raggi $\Delta$ decrescenti (comune nei metodi di ottimizzazione). La base costruita può essere riutilizzata e ampliata, rendendo le risoluzioni successive estremamente rapide.
4. Estensione alla Regolarizzazione: L'approccio è stato adattato per risolvere problemi di regolarizzazione della norma (algoritmo NREK), mostrando versatilità.

4. Risultati Numerici

Gli autori hanno testato TREK su 93 problemi di ottimizzazione non vincolata di grandi dimensioni (da CUTEst) con $n \ge 1000$.

• Confronto: TREK è stato confrontato con:
  • TRS: Un metodo basato su multiple fattorizzazioni (Gold standard per accuratezza ma costoso).
  • GLTR: Un metodo iterativo basato su Lanczos senza fattorizzazioni.
• Performance:
  • Velocità: TREK è spesso competitivo o superiore a TRS, specialmente quando il raggio $\Delta$ è grande (dove $\sigma$ è vicino al limite dello spettro e i metodi standard di Krylov convergono lentamente).
  • Robustezza: TREK richiede una singola fattorizzazione, evitando i costi cumulativi di TRS che ne richiede diverse.
  • Convergenza: In molti casi, TREK converge in meno di 20 iterazioni, confermando l'ipotesi di bassa dimensionalità.
  • Gestione dei "Resolves": Quando il raggio viene ridotto, TREK riutilizza la base esistente, rendendo le iterazioni successive quasi istantanee rispetto ai metodi che devono ricominciare o fattorizzare di nuovo.

5. Significato e Conclusioni

Il lavoro introduce un nuovo strumento efficace nell'arsenale degli ottimizzatori. Colma il divario tra i metodi basati su fattorizzazione multipla (precisi ma lenti) e i metodi senza fattorizzazione (veloci ma talvolta lenti nella convergenza per certi parametri).

La scoperta che le soluzioni giacciono in un sottospazio a bassa dimensionalità e l'uso strategico del sottospazio di Krylov esteso permettono di:

• Ridurre drasticamente il costo computazionale per problemi di Trust-Region su larga scala.
• Gestire efficientemente sequenze di problemi correlati (tipici negli algoritmi di ottimizzazione adattiva).
• Fornire un'alternativa robusta per problemi non convessi e con norme ellittiche.

Il codice è stato implementato nella libreria GALAHAD (disponibile in Fortran con interfacce per C, Python, Julia e Matlab), rendendo queste tecniche immediatamente accessibili alla comunità scientifica e industriale.