3.2 L’algoritmo primale-duale Newton-gradiente coniugato
3.2.2 Riformulazione primale-duale
dove D è una matrice diagonale, la cui dipendenza da x sarà omessa per semplicità di notazione, con elementi
Dii= (µ2+ x2i)−
1
2 ∀i ∈ [N ]. (3.27)
Chiameremo le variabili x variabili primali, mentre le variabili y variabili duali. L’idea di questa riformulazione viene dall’osservazione che la linearizzazione delle seconde equazioni di (3.26), cioè di yi/(D)ii−xi= 0, è migliore della linearizzazione di
ψµ(x) per µ ≈ 0 e xi ≈ 0, uno scenario inevitabile dato che, per µ piccolo, la soluzione
ottima tenderà ad essere sparsa. Per intuire perché questo è vero osserviamo che, per µ e xi piccoli, il gradiente ∇ψµ(x) tende ad essere singolare, perciò la sua linearizzazione tende ad essere inaccurata. Invece yi/(D)ii− xi = yi(µ2+ x2i)1/2− xi non ha una
singolarità per µ ≈ 0 e xi ≈ 0: ci aspettiamo perciò che la sua linearizzazione sia più precisa.
3.2.2 Riformulazione primale-duale
Mostriamo adesso che le condizioni di ottimalità alternative (3.26) corrispondono a una riformulazione primale-duale del problema (3.25). Ciò spiega inoltre l’origine del prefisso “primale-duale” nel nome del metodo.
Capitolo 3. Metodi risolutivi
Ogni i-esimo termine |xi|µ= (µ2+ x2i)1/2− µ della funzione pseudo-Huber (3.22) approssima il valore assoluto |xi|. Il termine |xi|µ può essere ottenuto regolarizzando
la formulazione duale di |xi|, cioè
|xi| = sup |yi|≤1
xiyi dove yi∈ R,
mediante il termine µ(1 − y2i)1/2 per ottenere
|xi|µ= sup |yi|≤1
xiyi+ µ(1 − yi2)1/2− µ.
Perciò la funzione pseudo-Huber (3.22) ha la seguente formulazione duale
ψµ(x) = N X i=1 sup |yi|≤1 xiyi+ µ(1 − y2i)1/2− µ.
Il problema (3.25) è quindi equivalente alla formulazione primale-duale
min x kyksup ∞≤1 τ (xTy + µ N X i=1 (1 − y2i)1/2− N µ) + ϕ(x)
dove y ∈ RN denota le variabili duali. Le condizioni di ottimalità del prim’ordine di questa formulazione primale-duale sono
τ y + ∇ϕ(x) = 0
xi− µyi(1 − yi2)−1/2 = 0 ∀i ∈ [N ]
kyk∞≤ 1.
(3.28)
Si può dimostrare che le condizioni di ottimalità del prim’ordine (3.28) della formula- zione primale-duale sono equivalenti alle condizioni (3.26) (vedi [19]).
3.2.3 L’algoritmo
Il nostro obiettivo è quindi quello di risolvere le equazioni (3.26): per farlo, applichiamo il metodo di Newton ma con opportune modifiche.
Chiamando F (x, y) : R2N → R2N la funzione F (x, y) = " τ y + ∇ϕ(x) D−1y − x #
le due equazioni in (3.26) si riscrivono semplicemente come F (x, y) = 0. Perciò, dati i punti x(j)e y(j)calcolati all’iterazione precedente j −1, al passo j il metodo di Newton applicato a questa equazione prevede la risoluzione del sistema ∇F (x(j), y(j))d = −F (x(j), y(j)) per calcolare la direzione corrente. Svolgendo i calcoli si trova che
∇F (x, y) =
∇2ϕ(x) τ I
D diag(x) diag(y) − I D−1
3.2. L’algoritmo primale-duale Newton-gradiente coniugato
e, chiamando dx (direzione primale) e dy (direzione duale) rispettivamente i vettori delle prime N e delle ultime N componenti di d, il sistema di Newton al passo j diventa
( ∇2ϕ(x(j))d
x+ τ dy = −(τ y(j)+ ∇ϕ(x(j)))
(D diag(x(j)) diag(y(j)) − I)dx+ D−1dy = −(D−1y(j)− x(j)).
Arrivati a questo punto, se si utilizzasse il metodo di Newton-CG classico si dovrebbe risolvere questo sistema mediante gradiente coniugato per ottenere d e dy, dopodiché
si calcolerebbero i nuovi punti con x(j+1)= x(j)+ dx e y(j+1) = y(j)+ dy. In questo
particolare algoritmo tuttavia si segue una strada diversa, modificando in parte l’iterazione di Newton.
Intanto ricaviamo dy dalla seconda equazione e sostituiamolo nella prima, per trovare
(
∇2ϕ(x(j)) + τ D(I − D diag(x(j)) diag(y(j))dx= −(∇ϕ(x(j)) + τ Dx(j))
dy = −(y(j)− Dx(j)) + D(I − D diag(x(j)) diag(y(j)))dx,
e osserviamo come il termine noto della prima equazione sia proprio uguale a −∇fτµ(x(j)). Denotiamo inoltre la matrice del sistema della prima equazione con
H(x, y) = ∇2ϕ(x) + τ D(I − D diag(x) diag(y)). (3.29)
Riscriviamo perciò semplicemente la prima equazione come
H(x(j), y(j))dx= −∇fτµ(x(j)) (3.30)
e chiamiamo semplicemente d(j)∈ RN la sua soluzione. Risolviamo quindi il sistema (3.30) in modo approssimato con il metodo del gradiente coniugato con punto iniziale zero, terminando prematuramente l’iterazione quando si verifica un opportuno criterio di terminazione che discuteremo nel seguito. Una volta calcolato d(j) in questo modo, dalla seconda equazione ricaviamo
d(j)y = −(y(j)− Dx(j)) + D(I − D diag(x(j)) diag(y(j)))d(j). (3.31)
Adesso possiamo finalmente calcolare i punti successivi. • Poniamo ˜y(j+1)= y(j)+ d(j) y e calcoliamo y(j+1)= PBN ∞(˜y (j+1)) (3.32) dove PBN
∞ è la proiezione sulla palla unitaria rispetto alla norma infinito. Questa
proiezione ci permette di garantire sempre la condizione kyk∞≤ 1 di (3.26).
• Effettuiamo una ricerca lineare a partire da x(j) lungo la direzione d(j) per
Capitolo 3. Metodi risolutivi
e 0 < c3 < 1, prendiamo il più piccolo intero h∗ tale che fτµ(x) decresca
sufficientemente lungo d(j), cioè
h∗ = minnh ∈ N | fτµ(x(j)+ ch3d(j)) ≤ fτµ(x(j)) − c2ch3kd(j)k2x(j)
o
, (3.33) e poniamo α = ch3∗. Dopodiché ovviamente si pone x(j+1) = x(j)+ αd(j).
Abbiamo utilizzato la norma k·kx(j) definita come
kvkx(j) =
q
vTH(x(j), y(j))v. (3.34)
Come dimostreremo nel Lemma 3.9, la matrice H(x(j), y(j)) è definita positiva grazie
all’assunzione kyk∞≤ 1, perciò questa norma è ben definita. Possiamo riassumere la procedura descritta nello pseudocodice 2.
Algoritmo 2 Algoritmo primale-duale Newton-CG (pdNCG) Input: Punti iniziali x0 e y0 e tolleranza tol.
1: for j = 0, 1, 2, . . . do
2: Risolvo in modo approssimato il sistema (3.30) con il gradiente coniugato (con o senza precondizionamento) per ottenere d(j):
H(x(j), y(j))d = −∇fτµ(x(j)).
3: Calcolo d(j)y con la (3.31):
d(j)y = −(y(j)− Dx(j)) + D(I − D diag(x(j)) diag(y(j)))d(j).
4: Pongo ˜y(j+1)= y(j)+ d(j)y e calcolo y(j+1) con la (3.32):
y(j+1)= PBN ∞(˜y
(j+1)).
5: Eseguo la ricerca lineare (3.33): h∗= min n h ∈ N | fτµ(x(j)+ ch3d(j)) ≤ fτµ(x(j)) − c2ch3kd(j)k 2 x(j) o . 6: Calcolo x(j+1)= x(j)+ ch3∗d(j).
7: Termino quando kd(j)kx(j)≤ tol.
8: end for
I seguenti due lemmi, relativi a due proprietà del metodo del gradiente coniugato, ci permettono di osservare che, in realtà, la strategia di ricerca lineare che abbiamo utilizzato non è nient’altro che la regola di Armijo [3].
Lemma 3.6. Consideriamo il sistema lineare M z = w con M ∈ RN ×N matrice
simmetrica definita positiva. Supponiamo di risolvere questo sistema con il metodo del gradiente coniugato e indichiamo con z(h), d(h) e α(h) rispettivamente le iterate, le
3.2. L’algoritmo primale-duale Newton-gradiente coniugato
direzioni e i passi prodotti dal metodo applicato a questo sistema all’iterazione h-esima, in modo che z(h+1) = z(h)+ α(h)d(h). Allora, definendo ϕ(z) = 1
2zTM z − zTw, per ogni h vale z(h)= arg minϕ(z) | z ∈ z(0)+ Eh dove Eh = span v(0), . . . , v(h−1). Dimostrazione. Chiamando gh(α0, . . . , αh−1) = ϕ(z(0)+ α0v(0)+ · · · + αh−1v(h−1)),
la minimizzazione di ϕ(z) sul sottospazio affine z(0) + Eh può essere riformulata
equivalentemente come il seguente problema non vincolato: arg mingh(α0, . . . , αh−1) | α0, . . . , αh−1∈ R . Scriviamo esplicitamente gh(α0, . . . , αh−1) = ϕ(z(0)) + h−1 X i=0 α2i 2 (v (i))TM v(i)− α i(v(i))T(w − M z(0))
e calcoliamo le derivate parziali rispetto agli αi:
∂gh
∂αi
(α0, . . . , αh−1) = αi(v(i))TM v(i)− (v(i))T(w − M z(0)).
Osserviamo adesso che tutte queste derivate parziali si annullano se e solo se αi =
(v(i))T(w − M z(0))/(v(i))TM v(i) = α(i) e perciò z(0)+ α0v(0)+ · · · + αh−1v(h−1) = z(h)
minimizza ϕ(z) su z(0)+ Eh.
Lemma 3.7. Consideriamo il sistema lineare M z = w con M ∈ RN ×N matrice simmetrica definita positiva. Supponiamo di risolvere questo sistema con il metodo del gradiente coniugato e utilizziamo le stesse notazioni del lemma precedente. Allora, se il gradiente coniugato è inizializzato con z(0) = 0, il punto z(h) calcolato all’iterazione h-esima soddisfa
(z(h))TM z(h)= (z(h))Tw per ogni h.
Lo stesso risultato vale per il metodo del gradiente coniugato con precondizionamento. Dimostrazione. Dal Lemma 3.6 sappiamo che, per il metodo del gradiente coniugato inizializzato con z(0) = 0, vale
z(h) = arg min z∈RN 1 2z TM z − zTw | z ∈ E h , Eh= span w, M w, . . . , Mh−1w.
Poiché z(h) è il minimo di 12zTM z − zTw su Eh, la derivata direzionale lungo una
qualsiasi direzione p ∈ Eh deve necessariamente essere zero in z(h), cioè
d dt 1 2(z (h)+ tp)TM (z(h)+ tp) − (z(h)+ tp)Tw = M z(h)− wT p = 0.
Capitolo 3. Metodi risolutivi
Poiché anche z(h)∈ Eh, in particolare, per p = z(h), vale
M z(h)− wT
z(h)= 0 ⇐⇒ (z(h))TM z(h) = (z(h))Tw,
e questo completa la prima parte della dimostrazione. Nel caso in cui si utilizzi un pre- condizionamento mediante la matrice simmetrica definita positiva P = EET, applicare il gradiente coniugato precondizionato al sistema originale è equivalente ad applicare il gradiente coniugato senza precondizionamento al sistema E−1M (E−1)Tξ = E−1w e poi calcolare z(h)= (E−1)Tξ(h). Perciò, utilizzando quanto già dimostrato, troviamo che (ξ(h))TE−1M (E−1)Tξ(h) = (ξ(h))TE−1w e sostituendo ξ(h) = ETx(h) otteniamo
la seconda parte della tesi del teorema.
Osservazione 3.8. Grazie al lemma precedente possiamo dire che kd(j)k2x(j) = (d(j))TH(x(j), y(j))d(j)= −∇fτµ(x(j))Td(j)
perciò la condizione di sufficiente decrescita e il relativo metodo di calcolo di h∗ che compaiono nell’equazione (3.33) sono proprio le stesse della procedura di Armijo per il calcolo del passo in una ricerca lineare. Il fatto che d(j) sia una direzione di discesa per fτµ(x) in x(j) è garantito dall’utilizzo del metodo del gradiente coniugato
inizializzato a zero. Per verificarlo ci basta provare che h∇fτµ(x(j)), d(j)i < 0, ma
questo è ovvio per quanto osservato sopra:
∇fτµ(x(j))Td(j)= −kd(j)k2x(j) < 0.
La risoluzione del sistema lineare in (3.30) viene realizzata mediante il gradiente coniugato (CG) (o la sua variante precondizionata (PCG)) inizializzato con il vettore nullo, ma l’iterazione viene arrestata prematuramente non appena si verifica la condizione
krµτ(x(j), y(j))k ≤ ηjk∇fτµ(x(j))k, (3.35)
dove, detto di il vettore calcolato dopo i iterazioni del gradiente coniugato, la quantità
rτµ(x(j), y(j)) = H(x(j), y(j))di+ ∇f (x(j)) è il residuo del gradiente coniugato dopo i
iterazioni e 0 ≤ ηj < 1 è una costante scelta dall’utente. Se non abbiamo raggiunto l’ottimo (cioè ∇f (x(j)) 6= 0), osserviamo come, poiché ηj < 1, non potremo mai avere
come output del gradiente coniugato il vettore zero, perché, almeno per i = 0 e d0 = 0,
la condizione precedente non è verificata. Di conseguenza, il gradiente coniugato farà sempre almeno un’iterazione e la direzione restituita in output non sarà mai nulla. L’analisi teorica verrà condotta con la scelta
ηj = min 1 2, k∇f µ τ(x(j))k . (3.36) 3.2.4 Convergenza
Presentiamo adesso alcuni risultati sulla convergenza di questo metodo. Saranno enunciati per il caso in cui si utilizzi il gradiente coniugato per risolvere il sistema (3.30), ma, grazie al Lemma 3.7, possono essere facilmente estesi al caso in cui si
3.2. L’algoritmo primale-duale Newton-gradiente coniugato
Lemma 3.9. Se kyk∞≤ 1, allora
λmI ≺ H(x, y)
2τ µ + λ1
I, dove le costanti λ1 e λm sono le stesse di (3.20).
Dimostrazione. Riprendiamo la definizione (3.29) della matrice H(x, y) = ∇2ϕ(x) + τ D(I − D diag(x) diag(y))
e concentriamoci sul secondo addendo. Osserviamo che è una matrice diagonale e che D(I − D diag(x) diag(y))ii= 1
(x2i + µ2)1/2 1 − xiyi (x2i + µ2)1/2 . Grazie all’ipotesi kyk∞≤ 1 possiamo dire che
xiyi (x2i + µ2)1/2 ≤ |xi| (x2i + µ2)1/2 < 1, perciò
0 < D(I − D diag(x) diag(y))
ii<
2 µ.
Grazie a questo risultato, è immediato verificare che, se kyk∞≤ 1, l’equivalenza della norma euclidea e della norma che abbiamo introdotto in (3.34) è data dalle disuguaglianze λ 1 2 mkdk2 ≤ kdkx ≤ 2τ µ + λ1 12 kdk2. (3.37)
Indicheremo con ˜λ1= 2τ /µ + λ1 (limitazione superiore per gli autovalori di H(x, y))
e con κ = ˜λ1/λm (limitazione superiore per il numero di condizionamento di H(x, y)).
Per alleggerire la notazione, nelle pagine seguenti trascureremo gli indici τ e µ per la funzione fτµ, che sarà indicata semplicemente come f .
Proposizione 3.10. Sia x ∈ RN l’iterata corrente del metodo pdNCG e sia d ∈ RN la direzione per le variabili x calcolata mediante CG. Se x non è il minimo del problema (3.25), cioè ∇f (x) 6= 0, allora la ricerca lineare del metodo pdNCG calcolerà un valore α tale che
α ≥ c3 λm ˜ λ1 = c3 1 κ, κ = 2τ /µ + λ1 λm , . Ponendo x(α) = x + αd, per α = α vale che
f (x) − f (x(α)) > c4kdk2x,
Capitolo 3. Metodi risolutivi
Dimostrazione. Sviluppando f (x) al second’ordine si trova che f (x(α)) = f (x) + α∇f (x)Td +α 2 2 d T∇2f (x)d ≤ f (x) + α∇f (x)Td +α2 2 ˜ λ1kdk22.
Grazie al Lemma 3.7 sappiamo che
dTH(x, y)d = −dT∇f (x),
perciò la disuguaglianza precedente diventa
f (x(α)) ≤ f (x) − αkdk2x+α 2 2 ˜ λ1kdk22. Usando la (3.37) troviamo f (x(α)) ≤ f (x) − αkdk2x+α 2 2 ˜ λ1 λm kdk2x.
Il lato destro di questa disuguaglianza è minimizzato da α∗ = λm/˜λ1. Perciò,
valutando per α = α∗, si trova
f (x(α∗)) ≤ f (x) −1 2 λm ˜ λ1 kdk2x.
Osserviamo come, per questa scelta del passo α∗, la condizione di sufficiente decrescita per la ricerca lineare in (3.33) è verificata, in quanto
f (x(α∗)) = f (x + α∗d) ≤ f (x) −1 2 λm ˜ λ1 kdk2x < f (x) − c2 λm ˜ λ1 kdk2x= f (x) − c2α∗kdk2x,
perciò il passo α restituito dalla procedura di ricerca lineare dell’algoritmo pdNCG è limitato da
α > c3
λm
˜ λ1
in quanto, non appena la ricerca lineare raggiunge un α tale che α∗ < α ≤ α∗/c3,
basterà un ulteriore passo (una moltiplicazione per c3) per ottenere c3α∗ < c3α ≤ α∗.
La seconda disuguaglianza ci assicura che il passo α ottenga una decrescita sufficiente della f (e quindi la ricerca lineare termina restituendo questo valore α = c3α), mentre la prima ci fornisce la limitazione dal basso evidenziata sopra. Si ottiene quindi una decrescita della f pari a
f (x) − f (x(α)) > c2c3 λm ˜ λ1 kdk2x = c2c3 1 κkdk 2 x.
Il seguente teorema stabilisce la convergenza globale delle variabili x(j). Il teo-
rema successivo si occuperà delle variabili y(j), per cui è necessario un differente ragionamento.
3.2. L’algoritmo primale-duale Newton-gradiente coniugato
Teorema 3.11. Sia x(j) una successione di variabili primali generata dal metodo pdNCG. Allora x(j) converge al punto di minimo x∗ del problema (3.25).
Dimostrazione. Come già osservato, il gradiente coniugato restituisce la direzione nulla se e solo se ∇f (x(j)) = 0. Inoltre, dalla Proposizione 3.10, sappiamo che, se ∇f (x(j)) 6= 0, il passo α(j) è sempre lontano da zero e la funzione f decresce strettamente quando ci muoviamo con x(j+1)= x(j)+ α(j)d(j). Poiché f è limitata dal basso e decresce strettamente ad ogni passo, necessariamente la successione f (x(j)) converge ad un limite finito e quindi f (x(j)) − f (x(j+1)) → 0. La monotonia della successione f (x(j)) implica anche che, dato un qualsiasi punto iniziale x(0) tale che f (x(0)) < ∞, tutta la successione x(j)appartiene all’insieme di sottolivello Sf(x(0)) =
{x | f (x) ≤ f (x(0))}. Poiché f è fortemente convessa, e quindi coerciva, tutti i suoi
sottolivelli sono compatti; la successione x(j) ammette quindi una sottosuccessione convergente ad un certo punto x∗. Usando la Proposizione 3.10 e il fatto che f (x(j)) − f (x(j+1)) → 0, troviamo che kd(j)kx(j) → 0, perciò, grazie alla (3.37), anche
kd(j)k
2 → 0, e quindi d(j)→ 0. Grazie all’osservazione iniziale sull’annullamento del
gradiente, segue che anche ∇f (x(j)) → 0, e questo ci garantisce che x∗ è un minimo per f (x).
Applicando adesso questo stesso ragionamento ad una qualsiasi sottosuccessione di x(j) otteniamo che da ogni sottosuccessione si può estrarre una ulteriore sotto- successione convergente allo stesso limite x∗. Questo ci assicura quindi che tutta la successione x(j) converge a x∗.
Teorema 3.12. Sia y(j) una successione di variabili duali generata dal metodo pdNCG. Allora y(j) converge a Dx∗, dove x∗ è la soluzione ottima del problema (3.25) e la matrice D è definita come in (3.27) ma per x = x∗. Questo implica inoltre che le iterate primali-duali del metodo pdNCG convergono alla soluzione del sistema (3.26). Dimostrazione. Dal teorema precedente abbiamo che d(j)→ 0 e che x(j)→ x∗. Perciò,
dalla definizione (3.31) di d(j)y e da ˜y(j+1)= y(j)+ d(j)y , troviamo che ˜y(j)→ Dx∗. Di
conseguenza, per continuità della proiezione e osservando che kDx∗k∞≤ 1, troviamo
y(j)= PBN ∞(˜y (j)) → P BN ∞(Dx ∗) = Dx∗
Con un’immediata verifica si prova anche che i valori x∗ e y∗ risolvono le condizioni di ottimalità del sistema (3.26).