Ariete divina deluxe user manual

4.3 Algoritmi iterativi e convergenza
Programma non lineare (PNL):
min
s.v .
f (x)
gi (x) ≤ 0
1≤i ≤m
x ∈ S ⊆ Rn
La natura e la difficolt`
a di risoluzione dipendono dalle caratteristiche di f e dalla
struttura della regione ammissibile X = {x ∈ S : gi (x) ≤ 0, 1 ≤ i ≤ m}.
In genere si suppone che f e gi siano almeno continuamente differenziabili.
PNL vincolato se X ⊂ Rn e non vincolato se X = Rn .
In alcuni casi (ad es. programmazione lineare e ottimizzazione combinatoria) `e possibile
determinare una soluzione ottima in numero finito, anche se elevato, di iterazioni.
Efficienza dipende da come il numero di iterazioni necessarie cresce con la dimensione
dell’istanza (polinomiale versus esponenziale).
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
1 / 17
La maggior parte dei metodi di PNL sono algoritmi iterativi che
- partono da x 0 ∈ X e
- generano (in base a x k precedenti, f e alle sue derivate) una successione {x k }k≥0 che
“converge” ad un punto dell’insieme Ω delle “soluzioni desiderate”.
Se f (x k+1 ) < f (x k ) per ogni k, sono dei metodi di discesa.
Significato di “converge” e di “soluzioni desiderate” varia a seconda del tipo di
problema:
• ∃ x k tale che x k ∈ Ω, la successione {x k }k≥0 converge ad un punto di Ω,
∃ un punto di accumulazione di {x k }k≥0 che appartiene a Ω (siamo in grado di
ottenere una buona stima dopo un numero sufficiente di iterazioni).
• Ω = insieme degli ottimi globali,
Ω = insieme dei punti candidati che soddisfano le condizioni necessarie di ottimalit`
a
del 1o ordine (∇f (x) = 0 se X = Rn ).
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
2 / 17
Siamo interessati a metodi affidabili ed efficienti:
1) Affidabilit`
a associata al concetto di convergenza globale
Definizione: Un algoritmo converge globalmente se {x k }k≥0 soddisfa una delle propriet`
a
precedenti per qualsiasi punto iniziale x 0 ∈ X .
Un algoritmo converge localmente se propriet`
a valida solo per x 0 in un opportuno intorno
di un x ∗ ∈ Ω.
2) Efficienza caratterizzata da vari tipi di rapidit`
a di convergenza (comportamento
asintotico)
Ipotesi: limk→∞ x k = x ∗ con x ∗ ∈ Ω non necessariamente ottimo globale
Definizione: {x k }k≥0 converge ad x ∗ con ordine p ≥ 1 se ∃ r > 0 e k0 ∈ N tale che
kx k+1 − x ∗ k ≤ r kx k − x ∗ kp
∀k ≥ k0 .
Il pi`
u grande valore di p `e l’ordine di convergenza e il pi`
u piccolo valore di r > 0 `e il
tasso di convergenza.
Se p = 1 e r < 1 la convergenza `e lineare, se p = 1 e r ≥ 1 convergenza sublineare.
N.B.: Se p = 1 la distanza rispetto a x ∗ decresce ad ogni iterazione di un fattore
costante r .
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
3 / 17
Definizione: La convergenza `e superlineare se esiste {rk }k≥0 con limk→∞ rk = 0 tale
che
∀k ≥ k0 .
kx k+1 − x ∗ k ≤ rk kx k − x ∗ k
Esempio: 1 +
1
kk
Definizione: Se p = 2 (e r non necessariamente < 1), la convergenza `e quadratica.
Esempio: 1 +
1
k
22
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
4 / 17
4.4 Metodi basati su direzioni di ricerca
Problema di ottimizzazione non vincolata:
min f (x)
x∈Rn
con f : Rn → R di classe C 1 o C 2 e limitata inferiormente.
Gli algoritmi iterativi di PNL partono da x 0 ∈ Rn e generano (in base a x k precedenti, f
e alle sue derivate) una sequenza infinita {x k }k≥0 che “converge” ad un punto
dell’insieme Ω delle “soluzioni desiderate”.
In genere Ω = {x ∈ Rn : ∇f (x) = 0}, a volte punti che soddisfano anche le Condizioni
Necessarie di Ottimalit`
a del 2o ordine.
Spesso ma non sempre metodi di discesa: f (x k+1 ) < f (x k ) per ogni k
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
5 / 17
1) Schema generale
Scegliere x 0 e ε > 0, porre k := 0
Repeat
Scegliere direzione di ricerca d k ∈ Rn
Determinare il passo αk > 0 lungo d k tale che minα≥0 φ(α) = f (x k + αd k )
Porre x k+1 := x k + αk d k e k := k + 1
Until condizione di arresto `e soddisfatta
Condizione di arresto: k∇f (x k )k < ε o |f (x k ) − f (x k+1 )| < ε o kx k+1 − x k k < ε
Spesso αk `e determinato in modo approssimato tale che f (x k+1 ) < f (x k ) ∀k.
Molta flessibilit`
a nella scelta delle direzioni d k e dei passi αk , l’efficienza dipende da
entrambi!
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
6 / 17
2) Direzioni di ricerca
In molti algoritmi iterativi basati su direzioni di ricerca
d k = −Dk ∇f (x k )
con Dk matrice n × n definita positiva.
In tal caso d k `e una direzione di discesa poich´e
∇t f (x k )d k = −∇t f (x k )Dk ∇f (x k ) < 0
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
7 / 17
Esempio 1: Metodo del gradiente
Sia f ∈ C 1
Considerare l’approssimazione lineare di f (x k + d) intensa come funzione del vettore d
lk (d) := f (x k ) + ∇t f (x k )d
e scegliere la direzione dk ∈ Rn che minimizza lk (d) sulla sfera di raggio k∇f (x k )k:
min
s.v.
∇t f (x k )d
(1)
kdk = k∇f (x k )k
Poich´e ∇t f (x k )d = k∇t f (x k )kkdk cos(θ), ∇t f (x k )d = k∇t f (x k )k2 cos(θ)
e (1) `e minimizzata quando cos(θ) = −1, ossia θ = π.
Direzione di massima discesa:
d k = −∇f (x k )
ovvero Dk = In .
Chiaramente direzione d k `e di discesa se ∇f (x k ) 6= 0
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
8 / 17
Esempio 2: Metodo di Newton
Sia f ∈ C 2 e H(x k ) = ∇2 f (x k )
Considerare l’approssimazione quadratica di f (x k + d) intorno a x k come funzione di d:
1 t
d H(x k )d
2
e scegliere la direzione (e il passo) che portano ad un punto stazionario di qk (d).
qk (d) := f (x k ) + ∇t f (x k )d +
Poich´e ∇d qk (d) = 0 implica ∇t f (x k ) + d t H(x k ) = 0, se H −1 (x k ) esiste la
direzione di Newton `e:
d k = −H −1 (x k )∇f (x k )
ovvero Dk = H
−1
(x k ).
Se H(x k ) `e definita positiva e ∇f (x k ) 6= 0, d k `e di discesa
∇t f (x k )d k = −∇t f (x k )H −1 (x k )∇f (x k ) ≤ −σk k∇f (x k )k2 < 0
per un σk > 0, visto che y t H −1 (x k )y ≥ σk ky k2 per ogni y ∈ Rn .
Se H(x k ) non `e definita positiva la direzione di Newton pu`
o non essere definita (quando
H −1 (x k ) non esiste) o non essere una direzione di discesa!
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
9 / 17
3) Lunghezza del passo
In genere, per garantire la convergenza globale basta determinare il passo αk lungo la
direzione d k risolvendo il problema di ricerca unidimensionale
min φ(α) = f (x k + αd k )
α≥0
in modo approssimato.
∃ vari metodi (con e senza derivate) che generano una sequenza di valori di α e si
fermano quando opportune condizioni sono soddisfatte (molto semplici, soddisfatte dopo
un numero molto limitato di tentativi).
f (x k + αk d k ) < f (x k ) non basta, ci vuole una riduzione sufficiente!
Principi fondamentali:
- passo α non deve essere troppo piccolo (per evitare convergenza prematura)
- passo α non deve essere troppo grande (rischio di oscillazioni)
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
10 / 17
Condizioni di Wolfe:
Riduzione sufficiente:
φ(α) ≤ φ(0) + c1 αφ′ (0)
con c1 ∈ [0, 1]
che equivale a
f (x k + αd k ) ≤ f (x k ) + c1 α∇t f (x k )d k
(criterio di Armijo)
φ′ (0) < 0 perch´e d k `e di discesa, c1 ≤ 1/2 cos`ı `e soddisfata dal minimo di una φ(α)
quadratica convessa.
Per evitare passi troppo piccoli (fare progressi ragionevoli) si considera anche condizione:
φ′ (α) ≥ c2 φ′ (0)
con c2 ∈ (c1 , 1)
che equivale a
∇t f (x k + αd k )d k ≥ c2 ∇t f (x k )d k .
In genere c2 = 0.9 per (quasi)-Newton e c2 = 0.1 per gradienti coniugati non-lineari.
Condizioni di Wolfe deboli:
φ(α) ≤ φ(0) + c1 αφ′ (0)
′
(2)
′
φ (α) ≥ c2 φ (0)
(3)
con 0 < c1 < c2 < 1
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
11 / 17
Condizioni di Wolfe forti:
φ(α) ≤ φ(0) + c1 αφ′ (0)
′
(4)
′
|φ (α)| ≤ c2 |φ (0)|
(5)
con 0 < c1 < c2 < 1
Unica differenza: non si considerano i valori di α con derivata φ′ (α) “troppo” positiva, si
escludono quindi i valori lontani dai punti stazionari di φ.
Condizioni invarianti rispetto a moltiplicazione della funzione obiettivo con costante o
trasformazione affine delle variabili.
Proposizione:
Sia f : Rn → R di classe C 1 e d k una direzione di discesa in x k t.c. f `e limitata
inferioremente lungo il raggio {x k + αd k : α > 0}. Allora se 0 < c1 < c2 < 1 esistono
degli “intervalli di passi” che soddisfano le condizioni di Wolfe (deboli e forti).
Semplice conseguenza del teorema del valore medio.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
12 / 17
Condizioni di Goldstein:
φ(0) + (1 − c)αφ′ (0) ≤ φ(α) ≤ φ(0) + cαφ′ (0)
con 0 < c < 1/2.
Svantaggio: certi valori di c possono escludere il minimo di g .
Adatte per metodi di tipo Newton ma non per quasi-Newton.
Metodi di ricerca unidimensionale
Esistono vari metodi (con/senza derivate) per determinare una soluzione approssimata
αk di
min φ(α) = f (x k + αd k )
α≥0
che soddisfa opportune condizioni (e.g. Wolfe) che garantiscono convergenza globale.
In genere due fasi:
- si determina un itervallo [a, b] che contiene passi “accettabili” (“bracketing phase”),
- si seleziona un buon valore α in questo intervallo tramite bisezione o interpolazione.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
13 / 17
Bisezione
φ ∈ C 1 , φ′ (0) < 0 perch´e d k direzione di discesa e ∃ α tale che φ′ (α) > 0 per α ≥ α.
Si parte da [αmin , αmax ] tale che φ′ (αmin ) < 0 e φ′ (αmax ) > 0 e si riduce iterativamente
secondo il principio di bisezione.
Iterazione: Porre α
˜ = 12 (αmin + αmax )
IF φ′ (α)
˜ > 0 THEN αmax := α
˜
IF φ′ (α)
˜ < 0 THEN αmin := α
˜
Convergenza lineare con tasso 1/2
Per trovare [αmin , αmax ] iniziale:
1) αmin := 0 e s := s0 (dato passo)
2) Calcolare φ′ (s)
IF φ′ (s) < 0 THEN αmin := s, s := 2s e GOTO 2)
IF φ′ (s) > 0 THEN αmax := s e STOP
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
14 / 17
Principio si pu`
o adattare per determinare un passo αk che soddisfa le condizioni di Wolfe
Procedura:
i) Scegliere α > 0 e porre αmin = αmax = 0
ii) IF α soddisfa Wolfe (2) THEN GOTO iii)
ELSE αmax := α, α :=
αmin +αmax
2
e GOTO ii)
iii) IF α soddisfa Wolfe (3) THEN αk = α e STOP
ELSE αmin := α
α :=
(
2αmin
1
(αmin + αmax )
2
se αmax = 0
se αmax > 0
e GOTO ii)
Si pu`
o verificare:
Proposizione: Se f ∈ C 1 e f `e limitata inferiormente lungo il raggio
{x k + αd k : α ≥ 0}, la procedura termina dopo un numero finito di iterazioni e fornisce
un αk che soddisfa entrambe le condizioni di Wolfe.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
15 / 17
4) Convergenza globale dei metodi basati sulle direzioni di ricerca
o garantire
Sotto opportune ipotesi relative sia ai passi αk che alle direzioni d k , si pu`
convergenza globale.
Aspetto fondamentale: angolo θk tra d k e la direzione di massima discesa −∇f (x k )
cos(θk ) = −
∇t f (x k )d k
k∇f (x k )kkd k k
Risultato generale che indica di quanto d k pu`
o discostarsi da −∇f (x k ) garantendo
comunque la convergenza globale.
Consideriamo le condizioni di Wolfe deboli ma risultati analoghi per quelle di Wolfe forti
e di Goldstein.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
16 / 17
Teorema: (Zoutendijk)
Metodo basato su direzioni di discesa d k e con αk che soddisfano le condizioni di Wolfe.
f limitata inf. su Rn , f ∈ C 1 su N aperto che contiene L0 = {x ∈ Rn : f (x) ≤ f (x 0 )} e
∇f soddisfa le condizioni di Lipschitz su N, ovvero ∃ L > 0 t.c.
k∇f (x) − ∇f (y )k ≤ Lkx − y k
Allora
X
∀x, y ∈ N.
cos2 (θk )k∇f (x k )k2 < +∞.
(6)
k≥0
La condizione di Zoutendijk (6) implica cos2 (θk )k∇f (x k )k2 → 0 quando k → ∞,
se cos θk ≥ δ > 0 ∀k ≥ 0 allora (6) implica che limk→∞ k∇f (x k )k = 0 per qualsiasi x 0 .
Conseguenza: Il metodo del gradiente (cos θk = 1) che soddisfa Wolfe `e globalmente
convergente.
Se Dk simmetriche e d.p. ∀k ≥ 0 e ∃ costante M t.c.
kDk kkDk−1 k ≤ M
∀k ≥ 0
si pu`
o verificare che cos θk ≥ 1/M.
In tal caso i metodi Newton e quasi-Newton hanno convergenza globale.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
17 / 17

Download Report