Metodi di Ottimizzazione

Marco Sciandrone

Autore
Lorenzo Cioni

2 Luglio 2015
Indice

1 Parte prima 4
1.1 Insiemi convessi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Esistenza di soluzione al problema di ottimizzazione . . . . . . . . . . . . 8
1.2.1 Funzioni continuamente differenziabili . . . . . . . . . . . . . . . 9
1.2.2 Trucchi per il calcolo di ∇f (x) e ∇2 f (x) . . . . . . . . . . . . . . 10
1.2.3 Funzione convessa a una variabile . . . . . . . . . . . . . . . . . . 10
1.3 Problema di regressione . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Condizioni di ottimalità per ottimizzazione non vincolata . . . . . . . . . 12
1.4.1 Concetto di derivata direzionale . . . . . . . . . . . . . . . . . . . 13
1.4.2 Condizioni di discesa . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.3 Condizioni di ottimalità del I ◦ ordine . . . . . . . . . . . . . . . . 14
1.4.4 Condizioni di ottimalità del II ◦ ordine . . . . . . . . . . . . . . . 14
Determinare una direzione di discesa . . . . . . . . . . . . . . . . 15
1.4.5 Condizioni di ottimalità nel caso quadratico . . . . . . . . . . . . 16
Problema dei minimi quadrati lineari . . . . . . . . . . . . . . . . 17
1.4.6 Determinare una direzione di discesa in Rn . . . . . . . . . . . . . 17
1.5 Algoritmi di ottimizzazione non vincolata . . . . . . . . . . . . . . . . . . 18
Schema generale . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Obiettivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.1 Convergenza degli algoritmi . . . . . . . . . . . . . . . . . . . . . 19
1.5.2 Rapidità di convergenza degli algoritmi . . . . . . . . . . . . . . . 20
1.5.3 Classificazione degli algoritmi . . . . . . . . . . . . . . . . . . . . 20
1.5.4 Convergenza globale e locale degli algoritmi . . . . . . . . . . . . . 21
1.6 Metodi basati su ricerche unidimensionali . . . . . . . . . . . . . . . . . . 21
Analisi delle condizioni . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.1 Ricerca del passo αk . . . . . . . . . . . . . . . . . . . . . . . . . 24
Il metodo di Armijo . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7 Metodo del gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.1 Metodo del gradiente con passo costante . . . . . . . . . . . . . . 29
1.7.2 Metodo del gradiente nel caso di funzione quadratica strettamente
convessa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.7.3 Ruolo del metodo del gradiente nelle reti neurali . . . . . . . . . . 31
1.8 Metodo di Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.8.1 Il metodo di Newton . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.8.2 Modifiche globalmente convergenti del metodo di Newton . . . . . 36

1
2 Parte seconda 38
2.1 Metodi delle direzioni coniugate . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.1 Metodo delle direzioni coniugate . . . . . . . . . . . . . . . . . . . 39
2.1.2 Metodo del gradiente coniugato (funzione quadratica) . . . . . . . 41
Relazioni utili per determinare forme equivalenti di βk+1 . . . . . 41
Formalizzazione del metodo . . . . . . . . . . . . . . . . . . . . . 42
2.1.3 Metodo del gradiente coniugato (minimi quadrati lineari) . . . . . 43
2.1.4 Metodo del gradiente coniugato (caso generale) . . . . . . . . . . . 43
Schema generale . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.5 Condizioni di Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2 Condizioni di ottimalità per problemi di ottimizzazione vincolata . . . . . 44
2.2.1 Condizioni di ottimalità di Fritz-John . . . . . . . . . . . . . . . . 45
2.2.2 Condizioni di qualificazione dei vincoli . . . . . . . . . . . . . . . 45
2.2.3 Condizioni di Karush-Kuhn-Tucker (KKT) . . . . . . . . . . . . . 47
2.2.4 Esempi di applicazione delle condizioni di ottimalità per problemi
di ottimizzazione vincolata . . . . . . . . . . . . . . . . . . . . . . 47
Problemi con vincoli di box . . . . . . . . . . . . . . . . . . . . . 47
Problemi con vincolo di simplesso . . . . . . . . . . . . . . . . . . 49
2.3 Metodi di Trust Region . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3.1 Introduzione ai metodi Trust Region . . . . . . . . . . . . . . . . 49
2.3.2 Schema generale dei metodi Trust Region . . . . . . . . . . . . . . 50
2.3.3 Punti cruciali dello schema generale dei metodi Trust Region . . . 51
Definizione di sufficiente decremento del modello quadratico . . . 51
Calcolo della soluzione del sottoproblema in modo da ottenere suf-
ficiente decremento . . . . . . . . . . . . . . . . . . . . . 52
2.4 Metodi Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4.1 Interpretazione geometrica in una variabile . . . . . . . . . . . . . 57
2.4.2 I metodi Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . 57
2.4.3 Conclusioni su BFGS . . . . . . . . . . . . . . . . . . . . . . . . 58
2.5 Metodo del gradiente di Barzilai-Borwein . . . . . . . . . . . . . . . . . . 58
2.5.1 Caso quadratico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Interpretazione del metodo BB: metodo spettrale del gradiente . . 59
Interpretazione del metodo BB: metodo del gradiente con ritardo 60
2.5.2 Caso non quadratico . . . . . . . . . . . . . . . . . . . . . . . . . 61
Cenni sui metodi non monotoni . . . . . . . . . . . . . . . . . . . 61
2.6 Metodi per problemi di minimi quadrati . . . . . . . . . . . . . . . . . . 62
2.6.1 Problemi di minimi quadrati lineari . . . . . . . . . . . . . . . . . 62
Metodo incrementale (filtro di Kalman) . . . . . . . . . . . . . . . 63
2.6.2 Problemi di minimi quadrati non lineari . . . . . . . . . . . . . . 63
Metodo di Gauss-Newton . . . . . . . . . . . . . . . . . . . . . . 64
Metodo di Levenberg-Marquardt . . . . . . . . . . . . . . . . . . 65
2.7 Metodi per problemi a larga scala . . . . . . . . . . . . . . . . . . . . . . 65
2.8 Metodi senza derivate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.8.1 Metodi basati sulle approssimazioni alle differenze finite . . . . . . 66
2.8.2 Metodi di ricerca diretta . . . . . . . . . . . . . . . . . . . . . . . 67
Metodo di Nelder-Mead . . . . . . . . . . . . . . . . . . . . . . . 67
Metodi delle coordinate . . . . . . . . . . . . . . . . . . . . . . . 68
Metodo di Hook-Jeeves . . . . . . . . . . . . . . . . . . . . . . . . 70

2
2.9 Problemi di ottimizzazione vincolata . . . . . . . . . . . . . . . . . . . . 70
2.9.1 Insieme S definito mediante vincoli lineari . . . . . . . . . . . . . 72
2.9.2 Condizioni di ottimalità per problemi di vincoli di box . . . . . . . 73
2.9.3 Condizioni di ottimalità per problemi con vincolo di simplesso . . 74
2.10 Proiezione di punti su un insieme convesso . . . . . . . . . . . . . . . . . 75
2.10.1 Problemi con vincoli di box trattati mediante proiezioni . . . . . . 77
2.11 Metodo del gradiente proiettato . . . . . . . . . . . . . . . . . . . . . . . 77
2.11.1 Formalizzazione del metodo . . . . . . . . . . . . . . . . . . . . . 78
2.11.2 Criticità del metodo del gradiente proiettato . . . . . . . . . . . . 79
2.12 Metodo di Frank-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.12.1 Formalizzazione del metodo . . . . . . . . . . . . . . . . . . . . . 79

3
Capitolo 1

Parte prima

Sia S ⊆ Rn insieme ammissibile, f : S → R funzione obiettivo (da minimizzare o

massimizzare), considero il problema:

min f (x)
x∈S

• Se S ⊂ {0, 1}n → ottimizzazione combinatoria.

• Se S ⊂ Zn → ottimizzazione intera.

• Se le variabili possono assumere valore continuo → ottimizzazione continua.

• Se le variabili possono assumere sia valori interi che continui → ottimizzazione mista

Nel corso ci occuperemo principalmente di ottimizzione continua.

min f (x)
x∈S⊆Rn

• Se S ≡ Rn ottimizzazione non vincolata.

• Se S ⊂ Rn ottimizzazione vincolata.

• Se f, gj , hi funzioni differenziabili → ottimizzazione differenziabile

gj (x) ≤ 0 j = 1, . . . , n

hi (x) = 0 i = 1, . . . , p

• Altrimenti ottimizzazione non differenziabile

Definizione 1 (Punto di minimo globale)

x∗ ∈ S : f (x∗ ) ≤ f (x) ∀x ∈ S

Definizione 2 (Punto di minimo locale)

x∗ ∈ S se ∃ una sfera aperta B(x∗ , c) tale che f (x∗ ) ≤ f (x) ∀x ∈ B(x∗ , c) ∩ S

4
 Figura 1.1: Punti di minimo di una funzione

Osservazione: ogni punto di minimo globale è anche un punto di minimo locale.

Quando vale anche il viceversa ⇒ ipotesi di convessità.

Richiamo 1 (Norma di un vettore in Rn ) La norma di un vettore in Rn è una

funzione k k : Rn → R+ avente le seguenti proprietà:

1) kxk ≥ 0

2) kxk = 0 ⇒ x = 0

3) kxxk = kxkkxk

4) kx + yk ≤ kxk + kyk

Si definisco tre diverse norme:

v
u n
uX
• Euclidea: kxk2 = t( x2i )
i=1

n
X
• Norma 1 : kxk1 = |xi |
i=1

• Norma ∞: max |xi |

1≤i≤n

Una volta introdotta la funzione norma, si introduce il concetto di distanza. La distanza

tra due vettori x, y ∈ Rn è definita come

d(x, y) = kx − yk

Con il concetto di distanza si può indicare una sfera di centro x e raggio l l’insieme

B(x, l) = {x ∈ Rn : kx − xk < l}

5
1.1 Insiemi convessi
Definizione 3 (Insieme convesso) S è un insieme convesso se ∀x, y ∈ S il segmento
(1 − λ)x + λy ∈S ∀λ ∈ [0, 1]

Figura 1.2: Insieme convesso ed insieme non convesso

Proposizione 1 (La sfera B(x, l) insieme convesso) La sfera B(x, l) è un insieme

convesso:
∀w, z ∈ B(x, l) (1 − λ)w + λz ∈ B(x, l)
Dimostrazione
I due punti appartengono alla sfera, quindi per definizione kw − xk ≤ l kz − xk ≤ l.
Vogliamo dimostrare che il segmento che congiunge w e z è ancora contenuto nella
sfera, quindi che
k(1 − λ)w + λz − xk ≤ l ∀ λ ∈ [0, 1]
Allora:
k(1 − λ)w + λz − xk = k(1 − λ)w + λz − x + λx − λxk
= k[(1 − λ)w − (1 − λ)x] + [λz − λx]k
≤ k(1 − λ)(w − x)k + kλ(z − x)k
≤ |(1 − λ)|kw − xk + |λ|kz − xk
≤ (1 − λ)l + λl = l

Proprietà: l’intersezione di insiemi convessi è ancora un insieme convesso.

Definizione 4 (Funzione convessa su insieme convesso) Sia S insieme convesso e

f : S → R.
f è funzione convessa su S se:
f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) ∀x, y ∈ S

Figura 1.3: Funzione convessa

6
Proposizione 2 (Coincidenza tra minimi locali e globali nel caso di convessità)
Sia S ⊆ Rn un insieme convesso e f : Rn → R funzione convessa su S. Allora:

i) ogni punto di minimo locale è anche di minimo globale

ii) l’insieme dei punti di minimo è un insieme convesso

Dimostrazione

i) x∗ ∈ S è un punto di minimo locale. Dobbiamo far vedere che x∗ è anche un punto

di minimo globale.

∃ B(x∗ , l) : f (x∗ ) ≤ f (x) ∀ x ∈ B(x∗ , l) ∩ S

Devo dimostrare che ∀ x ∈ S risulta che f (x∗ ) ≤ f (x)

Per la convessità ho che z = (1 − λ)x∗ + λx λ ∈ [0, 1]

Quindi se λ = 0, z = x∗ ; λ = 1, z = x. Per λ sufficientemente piccolo ⇒ z ∈

B(x∗ , l) ∩ S. Allora:

f (x∗ ) ≤ f (z) = f ((1 − λ)x∗ + λx) ≤ (1 − λ)f (x∗ ) + λf (x)

per la convessità.

f (x∗ ) ≤ (1 − λ)f (x∗ ) + λf (x) ⇒ λf (x∗ ) ≤ λf (x) ⇒ f (x∗ ) ≤ f (x)

se λ sufficientemente piccolo.

ii) Sia X ∗ l’insieme dei punti di minimo e siano x∗ , y ∗ ∈ X ∗

f (x∗ ) = f (y ∗ ) ≤ f (x) ∀x∈S

Dobbiamo fare vedere che (1 − λ)x∗ + λy ∗ ∈ X ∗ ∀ λ ∈ [0, 1]

f ((1 − λ)x∗ + λy ∗ ) = f (x∗ ) = f (y ∗ )

f (x∗ ) ≤ f ((1 − λ)x∗ + λy ∗ ) ≤ (1 − λ)f (x∗ ) + λf (x∗ ) = f (x∗ )

per la convessità. Quindi:

f ((1 − λ)x∗ + λy ∗ ) = f (x∗ )

Osservazione: La convessità, quindi, ci indica la coincidenza tra minimi locali e

globali di una funzione.

Definizione 5 (Funzione strettamente convessa) Sia S un insieme convesso. f è

una funzione strettamente convessa se, ∀x, y ∈ S, x 6= y:

f ((1 − λ)x + λy) < f (1 − λ)f (x) + λf (y) ∀λ ∈ (0, 1)

7
1.2 Esistenza di soluzione al problema di ottimizzazio-
ne
I seguenti teoremi e le seguenti proposizioni trattano l’esistenza di soluzione a problemi
di ottimizzazione non vincolata del tipo

min f (x)
x∈S

Il problema di ottimizzazione può ammettere tre possibili conclusioni:

• Il problema non ammette soluzione (es. f (x) = e−x )

• La soluzione esiste ed è univoca (es. f (x) = x2 )

• Il problema ammette più di una soluzione

Proposizione 3 (Condizione sufficiente di unicità di soluzione) Sia S insieme

convesso e sia f : Rn → R funzione strettamente convessa su S. Allora se ∃ soluzione,
questa è unica.

Dimostrazione
Per assurdo considero l’esistenza di due soluzioni al problema. Siano x∗ , y ∗ ∈ X ∗ ⇒
f (x∗ ) = f (y ∗ ). Allora:

f (x∗ ) ≤ f (1 − λ)x∗ + λf (y ∗ ) < (1 − λ)f (x∗ ) + λf (y ∗ ) < f (x∗ )

Assurdo perché f (x∗ ) non può essere strettamente minore di sè stesso.

Teorema 4 (Weierstrass) Sia S un insieme compatto (chiuso e limitato) non vuoto.

Se f è continua su S ⇒ il problema ammette soluzione.

Dimostrazione
Poichè S è non vuoto ⇒ ∃ inf x∈S f (x) = f ∗ ≥ −∞.
Per definizione di estremo inferiore, ∃ una successione di punti {xk } ⊂ S tale che:

lim f (xk ) = f ∗ ≤ f (x) ∀x ∈ S (a)

k→∞

Poichè S compatto:
∃{xk }k : lim xk = x ∈ S
k∈K,k→∞

Dove {x }k è una sottosuccessione di {xk } e x è un punto di accumulazione. Dunque:

k

lim f (xk ) = f ∗ = f (x) (b)

k∈K,k→∞

Unendo insieme (a) e (b) si ottiene:

f (x) ≤ f (x) ∀x ∈ S ⇒ x è un punto di minimo globale

8
Richiamo 2 (Insieme di livello di funzione) Dato un numero α, definisco l’insieme
di livello della funzione f :

L(α) = {x ∈ Rn : f (x) ≤ α}

tale che l’insieme così definito sia non vuoto.

Proposizione 5 Sia f : Rn → R una funzione continua su Rn ed esista un insieme di

livello L(α) compatto. Allora:

Il problema minn f (x) ammette soluzione

x∈R

Dimostrazione
Il problema minx∈L(α) f (x) ammette soluzione per il teorema di Weiestrass. Allora:

∃ x∗ ∈ L(α) : f (x∗ ) ≤ f (x) ∀x ∈ L(α)

∀x ∈ L(α) f (x) > α ≥ f (x∗ ) ⇒ x∗ minimo globale su Rn

Proposizione 6 Sia f : Rn → R continua. Condizione sufficiente affinché tutti gli

insiemi di livello siano compatti è che f sia coerciva, cioè tale che:

∀{xk } : kxk k → ∞ ⇒ lim f (xk ) = +∞

k→∞

Da queste ultime due proposizioni si deduce che: condizione sufficiente affinché il

problema di ottimizzazione non vincolata minx∈Rn f (x) ammetta soluzione è che f sia
coerciva.

1.2.1 Funzioni continuamente differenziabili

Sia data una funzione f : Rn → R almeno continuamente differenziabile, si definisce il
vettore gradiente ∇f (x) ∈ Rn , come:
 δf (x) 
δx1
∇f (x) = 
 .. 
. 
δf (x)
δxn

Si definisce poi la matrice delle derivate seconde, o matrice Hessiana, ∇2 f (x) ∈ Rn∗n ,
come:
 2
δ 2 f (x)

δ f (x)
2 · · · δx1 xn
2
 δx. 1 . .. 
∇ f (x) =  ..
 .. .  
δ 2 f (x) δ 2 f (x)
δxn x1
··· δx2
n

9
1.2.2 Trucchi per il calcolo di ∇f (x) e ∇2 f (x)
In alcune condizioni il calcolo del vettore grandiente e della matrice Hessiana è quasi
immediato. Gli esempi che vengono riportati in seguito sono casi d’uso classici per la
semplificazione del calcolo.

• Caso di una variabile: f (x) = cT x

∇f (x) = c ∇2 f (x) = [0]n∗n

1
• Funzione quadratica: f (x) = xT Qx + cT x Q(n ∗ n) matrice simmetrica
2
∇f (x) = Qx + c ∇2 f (x) = Q

1 1
• Minimi quadrati lineari: f (x) = kAx − bk22 → (ax − b)2 f 0 = a(ax − b)
2 2
∇f (x) = AT (Ax − b) ∇2 f (x) = AT A

1.2.3 Funzione convessa a una variabile

Proposizione 7 (Condizione necessaria e sufficiente di convessità) Sia ∇f (x)
continua su Rn . f (x) convessa in Rn se e solo se:

f (y) ≥ f (x) + ∇f (x)T (y − x) ∀x, y ∈ Rn

Proposizione 8 (Condizione necessaria e sufficiente di convessità) Sia ∇2 f (x)

continua su Rn . f (x) convessa in Rn se e solo se ∇2 f (x) è semidefinita positiva ∀x ∈ Rn

Richiamo 3 (Matrici definite positive) Sia A una matrice n x n.

• A è definita positiva se xT Ax > 0 ∀x 6= 0

• A è semidefinita positiva se xT Ax ≥ 0 ∀x ∈ Rn
Se A è matrice simmetrica:
• A è definita positiva se gli autovalori sono > 0

• A è semidefinita positiva se gli autovalori sono ≥ 0

Valgono poi le seguenti disuguaglianze:
• xT Ax ≥ λ min(A)kxk2

• xT Ax ≤ λ max(A)kxk2

Richiamo 4 (Disuguaglianza di Cauchy-Schwarz) Siano a, b ∈ Rn . La disugua-

glianza
|aT b| ≤ kak2 kbk2
vale se e solo se a = λb.

10
Proposizione 9 (Condizione sufficiente di f strettamente convessa) Sia ∇2 f con-
tinua. Se ∇2 f (x) è definita positiva ∀x ∈ Rn ⇒ f strettamente convessa.

Osservazione: Sia f funzione quadratica. f è coerciva se e solo se A è definita po-

sitiva.

Dimostrazione

• f coerciva ⇒ A definita positiva

Per assurdo. Supponiamo che A non sia definita positiva. Allora ∃ y ∈ Rn :

y T Ay ≤ 0.
Senza perdita di generalità possiamo affermare che −cT y ≤ 0. Quindi:

{xk } = ky kxk → ∞ f (x∗ ) ≤ 0

Essendo minore di 0 non può tendere a +∞ ⇒ f non è coerciva. Assurdo per

ipotesi.

• A definita positiva ⇒ f coerciva

1 1
f (x) = xT Ax + cT x ≥ λ min(A)kxk2 − kck2 kxk2
2 2
1
≥ kxk[ λ min(A)kxk − kck] → ∞
2
Quindi ∀ xk , kxk k → ∞ lim f (xk ) = +∞
k→∞
Nel caso di minimi quadrati :
1
f (x) = kAx − bk2 A(nxn)
2
1 1 1
kxk2 = xT x kAx − bk2 = xT AT Ax − cT x + kbk2
2 2 2
Quindi condizione necessaria e sufficiente affinchè f sia coerciva è che A abbia
rango massimo, ovvero
Rango(A) = n
e che AT A sia definita positiva. Quindi:

– Se Rango(A) = n ⇒ f è coerciva ed esiste soluzione al problema

– Se Rango(A) < n ⇒ f non è lineare, ma il problema ammette comunque
soluzione

Quindi f è convessa poichè ∇2 f (x) = AT A.

11
1.3 Problema di regressione
u ∈ Rn → Modello matematico con un vettore di parametri x ∈ Rn → y(u, x)
Ad esempio un polinomio di 3◦ grado, con x i coefficienti
 
a0
 a1 
x =  ..
 

 . 
an
Sono quindi disponibili n osservazioni del fenomeno
(ui , xi ) i = 1, . . . , n
Definiamo dunque una funzione errore di valutazione
Ei (x) = y(ui , xi ) − y i i = 1, . . . , n
   
E1 (x) y(ui , x) − y 1
E(x) =  .. ..
=
   
. . 
n n
En (x) y(u , x) − y
Il problema di ottimizzazione diventa
min kE(x)k
x∈Rn

1.4 Condizioni di ottimalità per ottimizzazione non vin-

colata
Dato un problema di ottimizzazione del tipo:

min f (x)
x∈Rn
si introducono motivazioni teoriche e motivazioni algoritmiche per individuare condi-
zioni di ottimalità del problema stesso.
• Motivazioni teoriche
– Condizioni necessarie: individuano i candidati ad essere soluzione al problema.
– Condizioni sufficienti: costituiscono un certificato di ottimalità.
• Motivazioni algoritmiche: dallo studio delle condizioni di ottimalità spesso se
ne deducono idee algoritmiche per la risoluzione del problema (soprattutto nel caso
particolare).

Definizione 6 (Direzione di discesa per f in un punto x) Un vettore d ∈ Rn è

detto di discesa per f in un punto x se:
∃ t > 0 : f (x + td) < f (x) ∀ t ∈ (0, t]

Proposizione 10 (Condizione necessaria di ottimalità) Se x è un punto di minimo

locale allora non può esistere una direzione di discesa in x.

12
1.4.1 Concetto di derivata direzionale
Siano x, d ∈ Rn . Il limite:
f (x + td) − f (x)
lim+
t→0 t
se esiste è detto derivata direzionale. Supponiamo che ∇f (x) esista e sia continuo, allora:
f (x + td) − f (x)
lim+ = ∇f (x)T d
t→0 t

1.4.2 Condizioni di discesa

Proposizione 11 (Condizione sufficiente di discesa) Supponiamo ∇f (x) continuo.
Se ∇f (x)T d < 0 ⇒ d è di discesa.

Osservazione: in generale è non necessaria, cioè:

∃ ∇f (x)T d > 0 con d di discesa
Per essere anche necessaria ho bisogno dell’ipotesi di convessità di f .

Proposizione 12 (Condizione necessaria e sufficiente di discesa) Sia f funzione

convessa.
d ∈ Rn è di discesa ⇔ ∇f (x)T d < 0
Dimostrazione
Condizione sufficiente già dimostrata. Condizione necessaria: d è di discesa per ipotesi.
Poichè f è convessa e ∇f (x) esiste ed è continuo:

f (x) > f (x + td) ≥ f (x) + t∇f (x)T d

f (x) > f (x) + t∇f (x)T d ⇒ ∇f (x)T d < 0

Richiamo 5 (Coseno tra vettori in Rn ) Siano a, b ∈ Rn , a, b 6= 0. Il coseno θ tra i

due vettore è definito come
aT b
cos θ =
kakkbk

Interpretazione geometrica della condizione di discesa ∇f (x)T d < 0

Geometricamente ∇f (x)T d < 0 implica che, data una direzione d ∈ Rn , se d forma un
angolo ottuso con il gradiente ∇f (x) allora d è di discesa ⇒ il vettore antigradiente è
sempre una direzione di discesa.

In sintesi:
• Se ∇f (x)T d < 0 ⇒ d è di discesa.
• Se ∇f (x)T d = 0 non possiamo dire nulla.
• Se ∇f (x)T d > 0 ⇒ d è di salita.

13
1.4.3 Condizioni di ottimalità del I ◦ ordine
Proposizione 13 (Condizione necessaria di ottimalità del I ◦ ordine)

x∗ è un minimo locale ⇒ ∇f (x∗ ) = 0

Dimostrazione
Supponiamo per assurdo che ∇f (x∗ ) 6= 0. Prendo come d ∈ Rn d = −∇f (x∗ ) (direzione
antigradiente). Allora:

∇f (x∗ )d = ∇f (x∗ )(−∇f (x∗ )) = −k∇f (x∗ )k2 < 0

Ho trovato una direzione di discesa quindi x∗ non è un minimo. Assurdo per ipotesi.

Proposizione 14 (Condizione necessaria e sufficiente di ottimalità del I ◦ ordine)

Sia f convessa. Allora:

x∗ è un minimo globale ⇔ ∇f (x∗ ) = 0

Dimostrazione
Condizione necessaria già dimostrata. Dimostriamo la condizione sufficiente, ovvero che:

∇f (x∗ ) = 0 ⇒ x∗ è minimo locale

Dobbiamo far vedere che f (x∗ ) ≤ f (x) ∀x ∈ Rn . Poichè f è convessa:

∀x ∈ Rn f (x) ≥ f (x∗ ) + ∇f (x∗ )T (x − x∗ ) = f (x∗ )

Quindi x∗ è un punto di minimo globale.

1.4.4 Condizioni di ottimalità del II ◦ ordine

Richiamo 6 (Continua differenziabilità) Se ∇f esiste ed è continuo in Rn allora:

f (x + d) = f (x) + ∇f (x)T d + α(x, d)

α(x, d)
lim =0
kdk→0 kdk

Se ∇2 f esiste ed è continua su Rn allora:

1
∀ x ∈ Rn , f (x + d) = f (x) + ∇f (x)T d + ∇2 f (x)d + β(x, d)
2
β(x, d)
lim =0
kdk→0 kdk2

Definizione 7 (Direzione a curvatura negativa) Una direzione d ∈ Rn è detta a

curvatura negativa se

dT ∇2 f (x)d < 0

14
Proposizione 15 (Condizione sufficiente di discesa del II ◦ ordine) Supponiamo
che ∇2 f esista e sia continua. Se d ∈ Rn è una direzione a curvatura negativa tale che

∇f (x∗ )T d = 0 ⇒ d è direzione di discesa

Dimostrazione
Poichè f è differenziabile 2 volte
1
f (x∗ + td) = f (x∗ ) + t∇f (x∗ )T d + t2 dT ∇2 f (x∗ )d + β(x∗ , td)
2
f (x∗ + td) − f (x∗ ) 1 T 2 ∗ β(x∗ , td)
= d ∇ f (x )d + <0
t2 2 t2

f (x∗ + td) < f (x∗ ) per t sufficientemente piccolo ⇒ d è di discesa

Proposizione 16 (Condizione necessaria di ottimalità del II ◦ ordine) Sia x∗ un

punto di minimo locale. Allora:

i) ∇f (x∗ ) = 0

ii) ∇2 f (x∗ ) è semidefinita positiva.

Dimostrazione

i) Già dimostrata.

ii) Per assurdo.

Supponiamo che ∇2 f (x) non sia semidefinita positiva ⇒ ∃ d : dT ∇2 f (x∗ )d < 0.

∇f (x∗ ) = 0 ⇒ ∇f (x∗ )T d = 0

Quindi d è direzione di discesa in x∗ . Assurdo perchè x∗ è un minimo per ipotesi.

Determinare una direzione di discesa

Sia x∗ : ∇f (x∗ ) = 0 e supponiamo ∇2 f (x∗ ) non definita positiva. Supponiamo che ∃
almeno un autovalore λi < 0.
Sia ui l’autovettore corrispondente all’autovalore λi , quindi tale che

∇2 f (x∗ )ui = λi ui
per la definizione di autovettore. Allora

uTi ∇2 f (x∗ )ui = λi uTi ui = λi kui k2 < 0

Pongo d = ui direzione di discesa. Se ∇2 f (x∗ ) non è definita positiva e ∇f (x∗ ) è
uguale a 0 prendo l’autovettore corrispondente all’autovalore negativo.

15
Proposizione 17 (Condizione sufficiente di ottimalità del II ◦ ordine) Sia x∗ :
∇f (x∗ ) = 0. Supponiamo che ∇2 f (x∗ ) sia definita positiva (quindi è localmente stretta-
mente convessa) allora x∗ è un minimo locale.

Proposizione 18 (Condizione sufficiente di ottimalità del II ◦ ordine) Sia x∗ :

∇f (x∗ ) = 0. Supponiamo che ∃ B(x∗ , l) : ∇2 f (x) sia semidefinita positiva ∀x ∈ B(x∗ , l).
Allora x∗ è un minimo locale.

1.4.5 Condizioni di ottimalità nel caso quadratico

Il caso quadratico viene studiato e tenuto in particolare considerazione poichè è la funzione
non lineare più semplice.
Il problema di ottimizzazione nel caso quadratico si traduce in
1
min xT Qx − cT x
2
x∈Rn

con Q matrice simmetrica n x n. Come abbiamo già calcolato in precedenza

∇f (x) = Qx − c ∇2 f (x) = Q

Proposizione 19 (Condizioni di ottimalità caso quadratico)

i) Il problema ammette soluzione se e solo se Q è semidefinita positiva ed il sistema

Qx − c = 0 ammette soluzione.

ii) Se Q è semidefinita positiva, ogni soluzione nel sistema Qx − c = 0 è soluzione al

problema di ottimizzazione.

iii) La soluzione al problema di ottimizzazione è unica se e solo se Q è definita positiva.

Dimostrazione

i) Il problema ammette soluzione ⇒ ∃ x∗ minimo globale.

Per la condizione necessaria di secondo ordine abbiamo che

∇f (x∗ ) = 0 ∇2 f (x∗ ) semidefinita positiva

quindi Q è semidefinita positiva.

Poichè Q semidefinita positiva → f è convessa. Se il sistema Qx = c ammette
soluzione ⇒ ∃ x∗ : ∇f (x∗ ) = 0.
⇓
x∗ è un minimo globale ed è soluzione. Il problema ammette quindi soluzione.

ii) Se Q semidefinita positiva ogni soluzione del sistema Qx − c = 0 è soluzione al

problema. Poichè Q semidefinita positiva, f è convessa. Il sistema Qx − c = 0 è
uguale a ∇f (x) = 0.
⇓
x è minimo globale ⇒ ogni soluzione al sistema è soluzione.

16
 iii) Supponiamo che la soluzione al problema sia unica ⇒ Q definita positiva.
Il sistema Qx − c = 0 deve ammettere un’unica soluzione.

Q non singolare (gli autovalori sono tutti 6= 0). Quindi:

λi 6= 0, λi ≥ 0 ⇒ λi > 0 ⇒ Q definita positiva

Se Q è definita positiva, f è convessa ed il sistema Qx − c = 0 ammette soluzione.

Quindi la soluzione al problema è unica.

Problema dei minimi quadrati lineari

Sia dato il problema di ottimizzazione
1
minn kAx − bk2
x∈R 2

1
f (x) = (Ax − b)T (Ax − b)
2
1 T T
= x A Ax − (AT b)T x
2
1 T
= x Qx − cT x
2
con Q = AT A e c = (AT b). Allora:

∇f (x) = Qx − c = AT (Ax − b) ∇2 f (x) = AT A

Utilizzando il risultato ottenuto in precedenza: il problema ammette soluzione se e solo

se:

• ∇2 f (x) = AT A semidefinita positiva

• AT Ax = AT b ammette soluzione?

– Se Rango(A) = n ⇒ AT A definita positiva ⇒ il problema ammette soluzione

– Se Rango(A) < n ⇒ AT A semidefinita positiva, ma il sistema ammette
comunque soluzione

AT (Ax − bR − bN ) = 0 AT (Ax − bR ) = 0

ammette soluzione.

1.4.6 Determinare una direzione di discesa in Rn

Sia D = {d1 , . . . , dn , −d1 , . . . , −dn } una base di Rn . Allora:

Se ∇f (x) 6= 0 ⇒ ∃ d ∈ D : ∇f (x)T d < 0

Dimostrazione

17
 n
X X X
−∇f (x) = βi di = βi di + kβi k(−di )
i=1 i∈I + i∈I −

con I + = {i : βi > 0} e I − = {i : βi < 0}.

Allora abbiamo che:
X X
−∇f (x)T ∇f (x) = βi ∇f (x)T di + kβi k∇f (x)T (−di ) < 0
i∈I + i∈I −

∃ almeno un i ∈ I + , I − : ∇f (x)T di < 0 oppure ∇f (x)T (−di ) < 0

1.5 Algoritmi di ottimizzazione non vincolata

Sia considerato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

Se ∇f (x) esiste ed è continuo si parla di problemi di ottimizzazione smooth.

Consideriamo x0 ∈ Rn il punto iniziale. Assumiamo che l’insieme di livello L0 = {x ∈
Rn : f (x) ≤ f (xo )} sia compatto ⇒ la soluzione al problema esiste.
Posso così definire l’insieme dei punti stazionari, ovvero dei punti che soddisfano le
condizioni necessarie di ottimalità del primo ordine:

Λ = {x ∈ Rn : ∇f (x) = 0}

Schema generale
Dati: x0 ∈ Rn , k = 0 (k è il contatore delle iterazioni).

Algoritmo 1 Schema generale

while xk 6∈ Λ do
calcola uno spostamento sk ∈ Rn
poni xk+1 = xk + sk
k =k+1
end while

abbiamo quindi {xk } successione di punti, {f (xk )} la successione di valori della

funzione f e {∇f (xk )} è la successione del vettore gradiente.

Obiettivi
Gli obiettivi nella valutazione degli algoritmi sono:

• {xk } → esistenza di punti di accumulazione

• {f (xk )} → convergenza

• {∇f (xk )} → {k∇f (xk )k} dovrebbe tendere a 0.

18
Proposizione 20 Supponiamo L0 compatto (chiuso e limitato), f (xk+1 ) ≤ f (xk ). Allora:

i) {xk } ammette punti di accumulazione e ogni punto di accumulazione ∈ L0

ii) {f (xk )} converge

Dimostrazione

i) f (xk+1 ) ≤ f (xk ) ⇒ f (xk ) ≤ f (x0 ) ∀k = 0, . . . , ∞

Questo vuol dire che {xk } ⊂ L0 , che è compatto per ipotesi. Poichè L0 è limitato,
{xk } è una sequenza limitata, e quindi ammette punti di accumulazione.
Inoltre, poichè L0 è chiuso, ciascun punto di accumulazione appartiene ad L0 .

ii) Se f (xk+1 ) ≤ f (xk ) parliamo di una successione di valori monotonicamente decre-

scenti. Quindi:

k −∞
{f (x )} → f
> −∞

Ma poichè L0 è compatto, allora è limitato inferiormente, quindi {f (xk )} converge.

1.5.1 Convergenza degli algoritmi

• Convergenza finita
Si parla di convergenza finita se l’algoritmo termina (trova quindi un punto stazio-
nario) in un numero finito di iterazioni (ad esempio il caso quadratico). Quindi:

∃ k : ∇f (xk ) = 0

• Convergenza asintotica forte

Si parla di convergenza asintotica forte se la successione di punti {xk } ammette
punti di accumulazione ed ogni punto di accumulazione è un punto stazionario.
Quindi:
lim k∇f (xk )k = 0
k→∞

• Convergenza asintotica debole

Si parla di convergenza asintotica debole se la successione di punti {xk } ammette
punti di accumulazione ed esiste almeno un punto di accumulazione stazionario.
Quindi:
lim inf{k∇f (xk )k} = 0
k→∞

19
1.5.2 Rapidità di convergenza degli algoritmi
Supponiamo che {xk } → x∗ , con x∗ punto stazionario (∇f (x∗ ) = 0).

• Rapidità di convergenza lineare

Si parla di rapidità di convergenza lineare se:

∃ σ ∈ (0, 1) : kxk+1 − x∗ k ≤ σkxk − x∗ k

• Rapidità di convergenza superlineare

Si parla di rapidità di convergenza superlineare se:

kxk+1 − x∗ k
lim =0
k→∞ kxk − x∗ k

La rapidità superlineare implica la rapidità lineare.

• Rapidità di convergenza quadratica

Si parla di rapidità di convergenza quadratica se:

∃ c > 0 : kxk+1 − x∗ k ≤ ckxk − x∗ k2

La rapidità quadratica implica la rapidità superlineare.

1.5.3 Classificazione degli algoritmi

• Algoritmi che utilizzano f e ∇f

– Metodo del gradiente

– Metodo del gradiente coniugato
– Metodo quasi-Newton

• Algoritmi che utilizzano f , ∇f e ∇2 f

– Metodo tipo Newton

• Algoritmi che utilizzano solo f

– Metodi senza derivate

Per la classe specifica di problemi di minimi quadrati non lineari, quindi del tipo
m
X
minn Zi2 (x)
x∈R
i=1

con Zi funzioni non lineari, si utilizzano:

• Metodo di Gauss-Newton

• Metodo di Lelemberg-Mardvart

20
1.5.4 Convergenza globale e locale degli algoritmi
• Algoritmi localmente convergenti
Si parla di algoritmi localmente convergenti se:

Dato x∗ : ∇f (x∗ ) = 0 ∃ B(x∗ , l) se x0 ∈ B(x∗ , l) ⇒ {xk } → x∗

• Algoritmi globalmente convergenti

Si parla di algoritmi globalmente convergenti se:

∀ x0 ⇒ {xk } → x∗ : ∇f (x∗ )

Per progettare algoritmi globalmente convergenti posso usare diverse tecniche:

– Strategia basata su ricerche unidimensionali (Line Search)

– Strategia basata su regione di confidenza (Trust Region)
– Metodi di ricerca diretta (basati sulla valutazione di f )

1.6 Metodi basati su ricerche unidimensionali

Lo schema generale dei metodi basati su ricerche unidimensionali (Line Search) ha come
dati in ingresso x0 ∈ Rn punto iniziale e k = 0 il contatore di iterazioni.

Algoritmo 2 Metodi basati su ricerche unidimensionali

while xk 6∈ Λ do
calcola una direzione di ricerca dk ∈ Rn
calcola un passo αk ∈ Rn
xk+1 = xk + αk dk
k =k+1
end while

Il requisito minimo è che dk sia una direzione di discesa, quindi che ∇f (xk )T dk < 0.

Definizione 8 (Funzione di forzamento) Sia σ : R+ → R+ e presa una successione

{tk } ⊂ R+ , σ è una funzione di forzamento se

lim σ(tk ) = 0 ⇒ lim tk = 0

k→∞ k→∞

Un esempio di funzione di forzamento

σ(t) = ct c>0

Proposizione 21 (Condizioni di convergenza globale del metodo) Sia ∇f (x) con-

tinuo e L0 compatto ( ipotesi sul problema).
Siano verificate le seguenti condizioni ( condizioni sull’algoritmo):

• f (xk+1 ) ≤ f (xk )

21
 |∇f (xk )T dk |
• ∃ σ funzione forzamento tale che ≥ σ(k∇f (xk )k) valga cioè la condi-
kdk k
zione d’angolo su dk
∇f (xk )T dk
• lim =0
k→∞ kdk k
Allora:

i) {xk } ammette punti di accumulazione ed ogni punto di accumulazione appartiene

ad L0 .

ii) {f (xk )} converge.

iii) lim k∇f (xk )k = 0

k→∞

iv) Ogni punto di accumulazione di {xk } è un punto stazionario.

Dimostrazione

i) Già dimostrata

ii) Già dimostrata

iii)
|∇f (xk )T dk |
≥ σ(k∇f (xk )k) ≥ 0 (1.1)
kdk k
|∇f (xk )T dk |
lim =0 (1.2)
k→∞ kdk k
Per (1.1) e (1.2) si ha che
lim σ(k∇f (xk )k) = 0
k→∞

⇓
lim k∇f (xk )k = 0
k→∞

per la definizione di funzione di forzamento.

iv) Sia x un punto di accumulazione. Allora:

∃ K ⊆ {0, 1, . . . , ∞} : lim xk = x
k∈K,k→∞

per la definizione di punto di accumulazione. Quindi:

lim k∇f (xk )k = 0 = k∇f (x)k

k∈K,k→∞

per la continuità del gradiente.

22
Analisi delle condizioni
a) f (xk+1 ) ≤ f (xk ) la soddisfo con dk e αk .
|∇f (xk )T dk |
b) ≥ σ(k∇f (xk )k) la soddisfo con dk .
kdk k
∇f (xk )T dk
c) lim = 0 la soddisfo mediante la ricerca unidimensionale di αk ,
k→∞ kdk k
supponendo dk direzione di discesa.

Soddisfare la condizione (b) Prendo σ(t) = ct , c > 0 e una direzione dk di discesa,

quindi tale che ∇f (xK )T dk < 0. Allora:

∇f (xk )T dk ≤ −ck∇f (xk )kkdk k

condizione d’angolo, ovvero, considerato θ l’angolo tra il gradiente e la direzione dk , ho

che:
∇f (xk )T dk
cos θ = ≤ −c
k∇f (xk )T kkdk k
In pratica la direzione dell’ antigradiente, dk = −∇f (xk ), soddisfa la condizione d’an-
golo con c = 1.

Richiamo 7 (Teorema della media) Sia ∇f continuo.

f (x + d) = f (x) + ∇f (ξ)T d con ξ = x + θd, θ ∈ [0, 1)

Ponendo y = x + d:
f (y) = f (x) + ∇f (ξ)T (y − x)
con ξ = x + θ(y − x) e θ ∈ (0, 1).

Richiamo 8 (Teorema di Taylor) Se ∇2 f continuo

1
f (x + d) = f (x) + ∇f (x)T d + dT ∇2 f (ξ)d
2
con ξ = x + θ(y − x) e θ ∈ (0, 1). Ponendo y = x + d:
1
f (y) = f (x) + ∇f (x)T (y − x) + (y − x)T ∇2 f (ξ)(y − x)
2

Soddisfare la condizione (c) La direzione dk è ora assegnata. Il requisito minimo è

che ∇f (xk )T dk < 0, cioè che dk sia di discesa.
Definisco Φ(α) = f (xk + αdk ), una funzione a una variabile (α), poichè xk è fissato (è
il punto corrente dell’iterazione dell’algoritmo).

Φ̇(α) = ∇f (xk + αdk )T dk Φ̇(0) = ∇f (xk )dk < 0

La funzione Φ è quindi, a partire dal punto α = 0, almeno inizialmente descrescente,
poichè ∇f (xk )dk < 0.

23
1.6.1 Ricerca del passo αk
• Ricerca di linea esatta
Il metodo di ricerca di linea esatta determina un passo αk tale che Φ̇(αk ) = 0.
Se Φ(α) è convessa ⇒ αk : Φ̇(αk ) = 0 è un punto di minimo globale di Φ(α),
quindi il metodo è fattibile se la funzione f (x) è quadratica, ovvero del tipo f (x) =
1 T
2
x Qx − cT x e Q è una matrice n x n simmetrica e definita positiva.
Nel caso in cui f sia strettamente convessa anche Φ(α) = f (xk +αdk ) è strettamente
convessa. Quindi:
1 T
Φ(α) = f (xk ) + α∇f (xk )T dk + α2 dk Qdk
2
applicando il teorema di Taylor.
T
Φ̇(α) = ∇f (xk )T dk + αdk Qdk = 0

−∇f (xk )T dk
αk =
dk T Qdk
che rappresenta la formula analitica per il calcolo di αk .

• Ricerca di linea inesatta

Data una qualsiasi f continuamente differenziabile, con l’ipotesi che dk sia di discesa
(∇f (xk )T dk < 0). Si applica il Metodo di Armijo.

Il metodo di Armijo
La ricerca di linea esatta, ossia la determinazione di un αk che risolva il problema di
ottimizzazione è notevolmente dispendiosa, soprattutto per problemi in cui f è non
convessa.
D’altra parte, non esistono particolari vantaggi, dal punto di vista del funzionamento
complessivo dei metodi di minimizzazione, nel determinare il punto di minimo lungo dk .
Si preferisce quindi adottare criteri approssimati che siano più facilmente utilizzabili dal
punto di vista computazionale e garantiscano al tempo stesso opportune proprietà di
convergenza.
Viene tracciata una retta a partire dal punto Φ(xk ) con pendenza verso il basso.

f (xk ) + γα∇f (xk )T dk γ ∈ (0, 1)

Considero poi un passo di prova iniziale, ∆k . Se Φ(∆k ) ≥ f (xk ) + γ∆k ∇f (xk )T dk
(il valore della funzione calcolato in ∆k si trova al di sopra della retta tracciata) allora
riduco il passo di δ ∈ (0, 1) finchè Φ(δ∆k ) non si trova sotto la retta.

Condizione di Armijo La condizione di Armijo ci indica quale sia il sufficiente de-

cremento, ovvero quanto la funzione debba essere minore abbastanza rispetto alla f (xk ):

f (xk + αk dk ) ≤ f (xk ) + γαk ∇f (xk )T dk < f (xk )

24
Formalizzazione Sia xk il punto corrente e dk la direzione corrente di discesa, quindi
tale che ∇f (xk )T dk < 0.
Siano ∆k > 0 il passo iniziale, δ ∈ (0, 1) il fattore di contrazione e γ ∈ (0, 1) l’inclinazione
della retta.
Pongo α = ∆k , j = 0 (j contatore di iterazioni).

Algoritmo 3 Metodo di Armijo

while f (xk + αdk ) > f (xk ) + γα∇f (xk )T dk do
α = δα
j =j+1
end while

Alla fine del ciclo ho αk = α.

Dobbiamo ora dimostrare che il metodo:

• Sia ben definito (termini cioè in un numero finito di operazioni).
• Consenta di soddisfare la terza condizione di convergenza globale, cioè:
∇f (xk )T dk
lim =0
k→∞ kdk k

Proposizione 22 (Correttezza del metodo di Armijo)

i) Il metodo di Armijo termina in un numero finito di operazioni con un passo
αk tale che
f (xk + αk dk ) ≤ f (xk ) + γαk ∇f (xk )T dk
ii) Il passo αk è tale che una delle due seguenti condizioni è verificata:
a) αk = ∆k
b) αk ≤ δ∆k
k k k
cioè tale che f (xk + αδ dk ) > f (xk )+γ αδ ∇f (xk )T dk con αδ che rappresenta
il tentativo precedente dove non è soddisfatta la condizione di Armijo.
Quindi αk ≤ δ∆k significa cioè che ho fatto almeno un tentativo.
Dimostrazione
dk è una direzione di discesa per ipotesi. Supponiamo per assurdo che il metodo di
Armijo non termini, cioè che j → ∞. Allora:

f (xk + δ j ∆k dk ) > f (xk ) + γδ j ∆k ∇f (xk )T dk ∀ j = 0, 1, . . . , ∞

f (xk + δ j δ k dk ) − f (xk )
> γ∇f (xk )T dk
δ j ∆k
La prima parte della disequazione al limite tende a ∇f (xk )T dk . Quindi:

∇f (xk )T dk > γ∇f (xk )T dk ⇒ (1 − γ)∇f (xk )T dk > 0

assurdo perchè γ ∈ (0, 1) e ∇f (xk )T dk < 0 per ipotesi (dk è di discesa).

25
Condizione di Armijo e funzione quadratica Consideriamo ora il caso di
funzione quadratica. Quindi, per il risultato calcolato il precedenza, il passo ottimo
αk è calcolato con

−∇f (xk )T dk
αk =
dk T Qdk

Il passo ottimo soddisfa la condizione di Armijo se e solo se γ ∈ (0, 21 ].

Dimostrazione
1 T
f (xk + αk dk ) = f (xk ) + αk ∇f (xk )T dk + (αk )2 dk Qdk
2
1 T
= f (xk ) + αk [∇f (xk )T dk + αk dk Qdk ]
2
1
= f (xk ) + αk ∇f (xk )T dk
2
valido se e solo se γ ≤ 21 .

Proposizione 23 (Convergenza del metodo di Armijo) Sia ∇f continuo e

sia L0 compatto. Supponiamo che:

– ∇f (xk )T dk < 0 → dk direzione di discesa

k )T dk |
– ∆k ≥ 1
kdk k
σ( |∇f (x
kdk k
)

Allora:

a) f (xk+1 ) < f (xk )

∇f (xk )T dk
b) lim =0
k→∞ kdk k
Dimostrazione

a) Dalla condizione di Armijo segue che

f (xk+1 ) ≤ f (xk ) + γαk ∇f (xk )T dk < f (xk )

b) Da (a) segue che {xk } ⊂ L0 , con L0 compatto per ipotesi. Da Armijo segue
che
∇f (xk )T dk
f (xk ) − f (xk+1 ) ≥ −γαk ∇f (xk )T dk = −γαk kdk k ≥0
kdk k

{f (xk )} è monotona decrescente (poichè f (xk+1 ) < f (xk )) limitata inferior-

mente (per la compattezza di L0 ). Ne viene che

lim f (xk ) = f > −∞

k→∞

26
quindi

k k+1 k ∇f (xk )T dk
k
lim [f (x ) − f (x )] = 0 ⇒ lim γα kd k =0
k→∞ k→∞ kdk k

∇f (xk )T dk
lim αk kdk k =0 (1.3)
k→∞ kdk k
Supponiamo ora per assurdo che

∇f (xk )T dk
lim 6= 0
k→∞ kdk k
Allora:
– {xk } limitata perchè L0 compatto
k
– { kddk k } limitata perchè la norma vale 1
– k∇f (xk )k limitata
∇f (xk )T dk
Quindi { } è una sequenza limitata e dunque ammette punti di
kdk k
accumulazione, quindi:

∇f (xk )T dk
∃ K ⊆ {0, 1, . . .} : lim = −µ < 0 con µ > 0 (1.4)
k∈K,k→∞ kdk k
Mettendo insieme 1.3 e 1.4 si ottiene

lim αk kdk k = 0 (1.5)

k→∞

k dk
Ma {x } è limitata e { k } è limitata e ciò implica che
kd k
(
limk∈K1 ,k→∞ xk = x
∃ K1 ⊆ K : k
limk∈K1 ,k→∞ kddk k = d

Quindi, per la continuità di ∇f , ho che

∇f (xk )T dk
lim = ∇f (x)d = −µ < 0
k∈K1 ,k→∞ kdk k

- Caso αk = δk .
Supponiamo che ∃ K2 ⊆ K1 : αk = ∆k , ∀ k ∈ K2 . Dalle ipotesi ho che

1 |∇f (xk )T dk |
∆k ≥ σ( )
kdk k kdk k
da cui segue
k |∇f (xk )T dk |
k
∆ kd k ≥ σ( )
kdk k
|∇f (xk )T dk |
∀ k ∈ K2 αk kdk k ≥ σ( )≥0
kdk k

27
 Dalla espressione precedente e dalla 1.5 si ottiene che
|∇f (xk )T dk |
lim =0
k∈K1,k→∞ kdk k
Assurdo, perchè quel limite vale −µ < 0.
- Caso αk ≤ δk .

Per k ∈ K1 e k sufficientemente grande abbiamo che

αk k αk
αk ≤ δ∆k ≤ f (xk + d ) > f (xk ) + γ ∇f (xk )T dk
δ δ
su questa applichiamo il teorema della media
αk k αk
f (xk + d ) = f (xk ) + ∇f (ξ k )T dk
δ δ
k
con ξ = xk + σ αδ dk e σ k ∈ (0, 1). Otteniamo dunque che
αk αk
f (xk ) + ∇f (ξ k )T dk > f (xk ) + γ ∇f (xk )T dk
δ δ
k T k k k
∇f (ξ ) d ∇f (x )d
k
>γ (1.6)
kd k kdk k
xk → x per k ∈ K1 , k → ∞ (1.7)
ξ k → x per k ∈ K1 , k → ∞ perchè αk kdk k → 0 (1.8)
Unendo i risultati ottenuti in 1.6, 1.7, 1.8 e la continuità di ∇f otteniamo che,
mandando k → ∞, k ∈ K1 :
∇f (x)T d ≥ γ∇f (x)T d
(1 − γ)∇f (x)T d ≥ 0
Assurdo poichè (1 − γ) > 0 e ∇f (x)T d = µ < 0.

1.7 Metodo del gradiente

Il metodo del gradiente è il metodo di ricerca più rapido, chiamato anche steppest descent
method.
In ingresso abbiamo x0 ∈ Rn , k = 0, con x0 punto iniziale e k il contatore delle
iterazioni.
Algoritmo 4 Metodo del gradiente
while ∇f (xk ) 6= 0 do
poni dk = −∇f (xk )
calcola αk con il metodo di Armijo
poni xk+1 = xk + αk dk
k =k+1
end while

Vogliamo vedere se il metodo converge globalmente. Le condizioni sufficienti di con-

vergenza globale sono:

28
 1) f (xk+1 ) ≤ f (xk )
|∇f (xk )T dk |
2) ≥ σ(k∇f (xk )k)
kdk k
∇f (xk )T dk
3) lim =0
k→∞ kdk k
La numero (2) è verificata se prendo σ(t) = t, poichè:
dk = −∇f (xK ) k∇f (xk )k ≥ k∇f (xk )k
La (1) e la (3) sono soddisfatte da Armijo, quindi il metodo converge globalmente (è
il primo algoritmo a farlo).

1.7.1 Metodo del gradiente con passo costante

Il metodo del gradiente con passo costante introduce una costante µ > 0 che rappresenta
il passo dell’algoritmo, anzichè calcolarlo con il metodo di Armijo.

Algoritmo 5 Metodo del gradiente con passo costante

while ∇f (xk ) 6= 0 do
poni dk = −∇f (xk )
poni xk+1 = xk + µdk
k =k+1
end while

Si introduce poi una nuova ipotesi sul gradiente, ovvero che questo sia Lipschitz
continuo su Rn .

Richiamo 9 (Lipschitz continuità del gradiente) Il gradiente è Lipschitz continuo

su Rn se
∃ L > 0 : ∀ x, y ∈ Rn k∇f (y) − ∇f (x)k ≤ Lky − xk

Con queste ipotesi abbiamo che:

Proposizione 24
1
∀ d ∈ Rn f (x + d) ≤ f (x) + ∇f (x)T d + Lkdk2
2
con L costante di Lipschitz.

Proposizione 25 (Convergenza del metodo del gradiente con passo costante)

Sia ∇f Lipschitz continuo con costante di Lipschitz L e sia L0 compatto.

xk+1 = xk − µk ∇f (xk )
Il passo µk è tale che
2−ε
ε ≤ µk ≤
L
29
 ⇓
{xk } ammette punti di accumulazione ed ogni punto di accumulazione è un punto stazio-
nario.
→ in pratica però non è utilizzato perchè non si conosce L.

Dimostrazione
Dalla proposizione precedente, ponendo d = −µk ∇f (xk ) abbiamo che
1
f (xk − µk ∇f (xk )) ≤ f (xk ) − µk k∇f (xk )k2 + (µk )2 Lk∇f (xk )k2
2
k
Lµ
≤ f (xk ) − µk (1 − )k∇f (xk )k2
2
⇓
Lµk
f (xk ) − f (xk+1 ) ≥ µk (1 − )k∇f (xk )k2 ≥ 0
2
Lµk
se µk > 0 e 1 − > 0 (*). Quindi:
2
f (xk+1 ) ≤ f (xk ) poiché lim f (xk ) = f > −∞
k→∞

⇓
{xk } ⊂ L0 compatto ⇒ {xk } ammette punti di accumulazione.

2−ε
Se µk ≥ ε e µk ≤ L
le condizioni (*) sono verificate. (i)

Lµk
lim f (xk ) − f (xk+1 ) = 0 ⇒ lim µk (1 − )k∇f (xk )k2 = 0 (ii)
k→∞ k→∞ 2
Per (i) e (ii) abbiamo che

lim k∇f (xk )k = 0

k→∞

cioè il gradiente converge.

1.7.2 Metodo del gradiente nel caso di funzione quadratica stret-

tamente convessa
Sia data una funzione quadratica
1
f (x) = xT Qx − cT x
2
con Q matrice nxn simmetrica e definita positiva. Poichè definita positiva gli autova-
lori sono tutti strettamente positivi: λ1 , λ2 , . . . , λn > 0.
1
xk+1 = xk − ∇f (xk ) k = 1, . . . , n
λk
Al più in n iterazioni il metodo converge al punto di minimo globale, quindi il metodo
converge finitamente.

30
 Dimostrazione
1
xk+1 = xk − k
∇f (xk )
λ
Moltiplico per Q:
1
Qxk+1 = Qxk − Q∇f (xk )
λk
Sottraggo ora c:
1
Qxk+1 − c = Qxk − c − Q∇f (xk )
λk
1
∇f (xk+1 ) = ∇f (xk ) − Q∇f (xk )
λk
Q
)∇f (xk )
= (I −
λk
Ripetendo all’indietro il ragionamento ottengo:
k
k+1
Y Q
∇f (x )= (I − i )∇f (x1 )
i=1
λ
Siano u1 , . . . , un gli autovettori associati agli autovalori λ1 , . . . , λn .
n
X
1
∇f (x ) = βj uj
j=1
n k
k+1
X Y Q
∇f (x )= βj [ (I − )]uj
j=1 i=1
λi
n n
n+1
X Y λj uj
∇f (x )= βj [ (uj − )] = 0
j=1 i=1
λi

1.7.3 Ruolo del metodo del gradiente nelle reti neurali

Modello di neurone artificiale
Sia x ∈ Rn un vettore in ingresso, ω ∈ Rn un vettore di pesi sinaptici e θ ∈ R il valore
di soglia.

x0 w0

x1 w1 θ

x2 w2 y(x, ω, θ)
P

.. ..
. .
xn wn

Ingressi Pesi

31
 L’uscita y ha valore binario:

0 se ω T x − θ ≥ 0
y(x, ω, θ) =
1 se ω T x − θ < 0
Se y = 1 il neurone è ON, se è 0 il neurone è OFF. Il neurone è quindi un separatore
lineare.
Sia dato dunque un training set:

T S = {(xp , dp ) : xp ∈ Rn , dp ∈ R, p = 1, . . . , P }
Algoritmo Perceptron: se i due insiemi sono linearmente separabili determina un
iperpiano di separazione in un numero finito di iterazioni.
Dato il training set si parla di:

• Classificazione se dp ∈ {0, 1}

• Approssimazione se dp ∈ R

L’incognita del problema è il vettore dei pesi sinaptici. Definisco così una funzione
errore:
P
X
E(ω) = Ep (ω) con Ep (ω) = (dp − y(xp , ω))2
p=1

Si introduce così il problema dell’addestramento della rete neurale

min E(ω)
ω

Al posto delle funzione gradino dei neuroni metto una sua approssimazione iperbolica
(funzione logistica). Il problema di ottimizzazione è non vincolato con funzione obiettivo
continuamente differenziabile.

Metodo della Back Propagation

ω k+1 = ω k − µ∇E(ω k )
con µ learning rate. Il metodo è il metodo del gradiente con passo costante.

1.8 Metodo di Newton

Dato un sistema di equazioni non lineari

F (x) = 0
con F : Rn → Rn , F continuamente differenziabile. Poichè F è differenziabile esiste
la matrice Jacobiana di F ed è continua:
 
∇F1T (x)
J(x) = 
 .. 
. 
T
∇Fn (x)

32
 F (xk + s) = F (xk ) + J(xk )s + γ(xk , s)
γ(xk , s)
lim =0
ksk→0 ksk
Se xk è il punto corrente:

F (xk + s) ' F (xk ) + J(xk )s = 0

Se J(xk ) è invertibile ⇒ sk = −[J(xk )]−1 F (xk ). Quindi:

xk+1 = xk + sk = xk − [J(xk )]−1 F (xk )

- Caso n = 1
F (x) = 0 F :R→R
Vogliamo trovare uno zero della F :

F (xk )
F (xk ) + Ḟ (xk )s = 0 s=−
Ḟ (xk )

In una variabile è detto anche metodo della tangente.

- Caso generale, n equazioni, n incognite

Richiamo 10 (Funzioni vettoriali) Sia F : Rn → Rn .

Se F è continuamente differenziabile allora
Z 1
F (y) = F (x) + J(x + λ(y − x))(y − x)dλ
0

Proposizione 26 (Convergenza del metodo di Newton) Ipotesi:

• F continuamente differenziabile su Rn

• ∃ x∗ : F (x∗ ) = 0

• J(x∗ ) sia non singolare (invertibile)

Se valgono le ipotesi allora

∃ B(x∗ , ε) : se x0 ∈ B(x∗ , ε) allora {xk } ⊂ B(x∗ , ε) e xk → x∗

con rapidità di convergenza superlineare, cioè tale che

kxk+1 − x∗ k
lim =0
k→∞ kxk − x∗ k

Se J(x) è Lipschitz continua su Rn

kJ(y) − J(x)k ≤ Lky − xk

33
allora la rapidità di convergenza è quadratica, cioè tale che

∃ c > 0 : kxk+1 − x∗ k ≤ ckxk − x∗ k

Dimostrazione
J(x∗ ) non singolare e continua per ipotesi allora

∃ B(x∗ , ε1 ) in cui J −1 (x∗ ) esiste ed è continuo ∀ x ∈ B(x∗ , ε1 )

∃ µ > 0 : kJ −1 (x)k ≤ µ ∀ x ∈ B(x∗ , ε1 )

Dalla continuità di J(x) segue che, preso un σ ∈ (0, 1)
σ
∃ ε ≤ ε1 : ∀ x, y ∈ B(x∗ , ε) kJ(y) − J(x)k ≤ (1.9)
µ

Se xk ∈ B(x∗ , ε) ⇒ xk+1 ∈ B(x∗ , ε). Riprendiamo adesso l’iterazione di Newton:

xk+1 = xk − [J(xk )]−1 F (xk )

E’ ben definita? Si, perchè xk ∈ B(x∗ , ε). Ricrodando che, per il richiamo precedente
Z 1
∗
k
F (x ) − F (x ) = J(x∗ + λ(xk − x∗ ))(xk − x∗ )dλ
0

posso procedere con

xk+1 − x∗ = xk − x∗ − [J(xk )]−1 F (xk )

= [J(xk )]−1 [J(xk )](xk − x∗ ) − [J(xk )]−1 F (xk )
= −[J(xk )]−1 [F (xk ) − J(xk )(xk − x∗ )]
= −[J(xk )]−1 [F (xk ) − F (x∗ ) − J(xk )(xk − x∗ )]
Z 1
k −1
= −[J(x )] [( J(x∗ + λ(xk − x∗ )) − J(xk ))(xk − x∗ )dλ]
0

Z 1
∗ −
kx k+1
− x k ≤ kJ 1(x )kk k
J(x∗ + λ(xk − x∗ )) − J(xk ))(xk − x∗ )dλk
0
Z 1
≤ µ kJ(x∗ + λ(xk − x∗ )) − J(xk )kkxk − x∗ kdλ
0
σ
≤ µ kxk − x∗ k
µ
per 1.9. Quindi:
kxk+1 − x∗ k ≤ σkxk − x∗ k (1.10)
con σ ∈ (0, 1) e xk+1 ∈ B(x∗ , ε).
Per induzione, se x0 ∈ B(x∗ , ε) ⇒ {xk } ⊂ B(x∗ , ε). Applicando ripetutamente 1.10:

kxk − x∗ k ≤ σkx0 − x∗ k

con σ ∈ (0, 1). Mandando k → ∞ abbiamo che xk → x∗ , quindi il metodo converge.

34
 Devo ora dimostrare che la convergenza abbia rapidità superlineare.
Z 1
∗
kx k+1
−x k≤µ kJ(x∗ + λ(xk − x∗ )) − J(xk )kkxk − x∗ kdλ
0

Se xk 6= x∗ :
1
kxk+1 − x∗ k
Z
≤µ kJ(x∗ + λ(xk − x∗ )) − J(xk )kkxk − x∗ kdλ
kxk − x∗ k 0

⇓
kxk+1 − x∗ k
lim =0
k→∞ kxk − x∗ k

quindi la rapidità di convergenza è superlineare.

Supponiamo ora J Lipschitz continua

kJ(x∗ + λ(xk − x∗ )) − J(xk )k ≤ Lkx∗ + λ(xk − x∗ ) − xk k = L(1 − λ)kxk − x∗ k

Z 1
k+1 ∗ k ∗ 2
kx − x k ≤ µLkx − x k (1 − λ)dλ
0
µL k
≤ kx − x∗ k2
2
cioè ha rapidità di convergenza quadratica

1.8.1 Il metodo di Newton

Dato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

con f : Rn → R e sia
Λ = {x ∈ Rn : ∇f (x) = 0}
l’insieme dei punti stazionari, il metodo di Newton per la minimizzazione di una funzione
f in n variabili diventa
xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk )

Proposizione 27 (Convergenza locale del metodo) Se ∃ x∗ : ∇f (x∗ ) = 0 e sia

∇2 f (x∗ ) non singolare, allora:

∃ B(x∗ , ε) : se x0 ∈ B(x∗ , ε) ⇒ {xk } ⊂ B(x∗ , ε)

quindi:
xk → x∗ con rapidità superlineare
Se ∇2 è Lipschitz continua allora la rapidità di convergenza è quadratica.

35
1.8.2 Modifiche globalmente convergenti del metodo di Newton
Dato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

utilizzando il metodo di Newton otteniamo un risultato localmente convergente.

Possiamo riscrivere l’iterazione come xk+1 = xk + dk con

dk = −[∇2 f (xk )]−1 ∇f (xk ) direzione di Newton

Ci troviamo di fronte a tre possibili casi:

1) La direzione di Newton potrebbe non esistere perché ∇2 f (xk ) è singolare.

2) Supponiamo che la direzione esista, non è detto che ∇f (xk )T d < 0 (la direzione
potrebbe quindi non essere di discesa).

3) Supponiamo che la direzione esista e che sia di discesa, non è detto che dk soddisfi
la condizione d’angolo.

Apportando alcune modifiche al metodo di Newton si riesce però ad ottenere un

risultato globalmente convergente. Le modifiche che vengono esposte in seguito sono dei
metodi basati su ricerche unidimensionali:

• Metodi ibridi

• Metodi basati sulle modifiche della matrice Hessiana

Metodo ibrido Provo a calcolare la direzione di Newton con il sistema

[∇2 f (xk )]d = −∇f (xk )

Se 6 ∃ soluzione oppure la soluzione trovata non è di discesa, prendo dk = −∇f (xk ).

xk+1 = xk + αk dk

Supponiamo di aver trovato quindi una direzione di Newton dk , calcolo αk con il metodo
di Armijo, ponendo ∆k = 1 il passo iniziale. Il passo ∆k deve soddisfare la condizione

1 |∇f (xk )T dk |
∆k > σ( )
kdk k kdk k

Quindi
|∇f (xk )T dk |
kdk k ≥ σ( )
kdk k
Condizioni su dk
|∇f (xk )T dk |
1) ≥ σ(k∇f (xk )k) condizione d’angolo
kdk k
k T dk |
2) kdk k ≥ σ( |∇f (x )
kdk k
)

36
Vengono soddisfatte se

∇f (xk )T dk ≤ −c1 k∇f (xk )k2 con c1 > 0
kdk k ≤ c2 k∇f (xk )k con c2 > 0

Potrebbero però essere condizioni troppo restrittive se ∇2 f (xk ) è definita positiva e

∇f (xk ) = 0. In questo caso si modificano con

∇f (xk )T dk ≤ −c1 k∇f (xk )k2 Ψ(xk ) con c1 > 0
Ψ(xk )kdk k ≤ c2 k∇f (xk )k con c2 > 0

con Ψ(xk ) un fattore che rende le equazioni meno restrittive quando xk → x∗ .

In caso di punti stazionari del secondo ordine (∇f (xk ) = 0 e ∇2 f (x∗ ) semidefinita
positiva):
xk+1 = xk + (αk )2 sk + αk dk
con sk una direzione che serve a garantire la convergenza globale e dk la direzione che
consente di uscire di non convessità di f , cioè dai punti in cui ∇2 f (xk ) è indefinito
(questo valore è legato all’autovalore più piccolo, è l’autovettore corrispondente con il
segno opportuno).

37
Capitolo 2

Parte seconda

2.1 Metodi delle direzioni coniugate

I metodi delle direzioni coniugate sono metodi che utilizzano f e ∇f . Per lo studio dei
metodi è utile inizialmente partire dal caso quadratico per poi estendere i metodi al caso
non quadratico.
Sia dato quindi un problema di ottimizzazione di funzione quadratica
1
min xT Qx − cT x
2
con Q una matrice nxn simmetrica e definita positiva.
Si utilizza inoltre una notazione semplificata del vettore gradiente, indicandolo con
g:
gn = g(xn ) = ∇f (xn )

Definizione 9 (Direzioni mutuamente coniugate rispetto a Q) I vettori d1 , . . . , dm ∈

Rn sono mutuamente coniugati se

dTi Qdj = 0 ∀ i, j = 1, . . . , m i 6= j

Proposizione 28 (Indipendenza lineare di vettori mutuamente coniugati) Se

d0 , . . . , dm−1 ∈ Rn sono mutuamente coniugati allora sono linearmente indipendenti.

Dimostrazione
Dobbiamo far vedere che
m−1
X
α j dj = 0 ⇒ αj = 0 j = 0, . . . , m − 1
j=0

Sia i ∈ {0, 1, . . . , m − 1}.

m−1
X
αj dTi Qdj = 0
j=0

Per la mutua coniugatezza dTj Qdj = 0 per ogni i 6= j, quindi possiamo semplificare la
sommatoria in
αi dTi Qdi = 0 ⇒ αi = 0

38
poichè dTi Qdi > 0 perchè Q è definita positiva. Quindi la mutua coniugatezza implica
l’indipendenza lineare.

2.1.1 Metodo delle direzioni coniugate

Poichè Q è simmetrica e definita positiva

∃! x∗ soluzione al problema

⇓
∗
Qx = c ⇒ x∗ = Q−1 c
Sia d0 , . . . , dn−1 ∈ Rn una base di Rn (siano quindi linearmente indipendenti), allora
n−1
X
∗
x = α i di
i=0

dove però i coefficienti αi li conosco se e solo se conosco la soluzione x∗ .

Siano ora d0 , . . . , dn−1 mutuamente coniugati. Sappiamo dunque che, per la pro-
posizione precedente, sono linearmente indipendenti
n−1
X
x∗ = α i di
i=0

Moltiplico ora per Q

n−1
X
Qx∗ = αi Qdi
i=0

e ora per dTj

n−1
X
dTj Qx∗ = αi dTj Qdi = αj dTj Qdj
i=0

poichè mutuamente coniugati rimane solo il termine con indice j.

Ma Qx∗ = c, quindi:
dTj c
αj = T
dj Qdj
Ho quindi ricavato i coefficienti α in funzione dei dati del problema e non della soluzione.
n−1
X dTi c
x∗ = T
di
i=0
di Qd i

Noti dunque Q e c posso calcolare la soluzione x∗ come semplice combinazione lineare.

Dati n vettori d0 , . . . , dn−1 ∈ Rn mutuamente coniugati posso immaginare di determi-
nare x∗ attraverso un processo iterativo a partire dal punto iniziale x0 .

x∗ = x0 + α0 d0 + α1 d1 + . . . + αn−1 dn−1
Definisco ora il processo fino all’iterazione k:

xk = x0 + α0 d0 + α1 d1 + . . . + αk−1 dk−1

39
 dTk Q(xk − x0 ) = 0
Quindi:
dTk Q(x∗ − x0 ) = αk dTk Qdk
⇓
dTk Q(x∗ − x0 ) dTk Q(x∗ − xk + xk − x0 ) dTk Q(x∗ − xk )
αk = = =
dTk Qdk dTk Qdk dTk Qdk
dT [Qx∗ − Qxk ] dT (c − Qxk ) −dT gk
= k T = k T = Tk
dk Qdk dk Qdk dk Qdk
poichè c − Qxk è l’antigradiente calcolato in xk . Dunque:
−gk dk
αk = (2.1)
dTk Qdk
è il passo ottimo lungo dk .

Proposizione 29 (Convergenza finita del metodo delle direzioni coniugate)

Siano d0 , . . . , dn−1 ∈ Rn mutuamente coniugati e sia
xk+1 = xk + αk dk
con αk passo ottimo
−gk dk
αk =
dTk Qdk
Allora:
i) gkT di = 0 i = 0, . . . , k − 1
ii) ∃ m ≤ n − 1 : gm+1 = 0
ovvero il metodo trova una soluzione in al più n iterazioni.
Dimostrazione
i) xk = xi + k−1
P
j=i αj dj i ∈ {0, . . . , k − 1}
k+1
X
Qxk = Qxi + αj Qdj
j=i

k+1
X
Qxk − c = Qxi − c + αj Qdj
j=i
k+1
X
gk = gi + αj Qdj
j=i

dTi gk = dTi gi + αi dTi Qdi

g T di T
= dTi gi − Ti d Qdi
di Qdi i
= 0
sostituendo αi con con il passo ottimo.

40
 ii) Supponiamo di aver effettuato n iterazioni. Per la (i) abbiamo che

gnT di = 0 i = 0, . . . , n − 1

Ma d0 , . . . , dn−1 costituiscono una base di Rn :

 
dT0
Dgn = 0 D =  ... 
 
dTn−1

con D non singolare poichè linearmente indipendenti. Quindi gn = 0, ovvero il

metodo converge al più in n iterazioni.

2.1.2 Metodo del gradiente coniugato (funzione quadratica)

Pongo d0 = −g0 . In generale
xk+1 = xk + αk dk
con αk passo ottimo, ovvero
−gkT dk
αk =
dTk Qdk
dk+1 = −gk+1 + βk+1 dk
Voglio però che dk+1 e dk siano coniugati, quindi utilizzo βk+1

dTk+1 Qdk = −gk+1

T
Qdk + βk+1 dTk Qdk = 0

poichè per essere mutuamente coniugati deve essere nullo. Quindi:

T
−gk+1 Qdk
βk+1 = T
dk Qdk

Relazioni utili per determinare forme equivalenti di βk+1

xk+1 = xk + αk dk
Qxk+1 − c = Qxk − c + αk Qdk
⇓
gk+1 = gk + αk Qdk
1
Qdk = (gk+1 − gk ) (2.2)
αk
Utilizzando la 2.2:
T
gk+1 (gk+1 − gk )
βk+1 = T
dk (gk+1 − gk )
T
gk+1 dk = gkT dk + αk dTk Qdk = 0
sostituendo αk nell’ultimo passaggio.
T
gk+1 dk = 0 (2.3)

41
Utilizzando la 2.3:
T
gk+1 (gk+1 − gk )
βk+1 =
−dTk gk
dk = −gk + βk dk−1
Utilizzando la 2.3:
dTk gk = −kgk k2 + βk gkT dk−1
dTk gk = −kgk k2 (2.4)
Utilizzando la 2.4:
T
gk+1 (gk+1 − gk )
βk+1 =
kgk k2
Si può infine dimostrare che
T
gk+1 gk = 0 (2.5)
Utilizzando quindi la 2.5:
kgk+1 k2
βk+1 =
kgk k2

Formalizzazione del metodo

Dati x0 ∈ Rn , k = 0, d0 = −g0 .

Algoritmo 6 Metodo del gradiente coniugato (forma quadratica)

while gk 6= 0 do
kgk k2
calcola αk = T
dk Qdk
poni xk+1 = xk + αk dk
calcola gk+1 = gk + αk Qdk
kgk+1 k2
calcola βk+1 =
kgk k2
poni dk+1 = −gk+1 + βk+1 dk
k =k+1
end while

Il metodo del gradiente coniugato per la forma quadratica è un algoritmo che termina
in al massimo n iterazioni, è quindi a convergenza finita.
E’ un algoritmo iterativo per la risoluzione del sistema lineare Qx = c, con Q matrice
nxn simmetrica e definita positiva. Gli algoritmi di calcolo diretto della soluzione hanno
un costo computazionale elevato, o(n2 ). Il metodo del gradiente coniugato ha, nel caso
peggiore, costo o(n). Quindi la scelta del metodo migliore da implementare dipende dalla
dimensione del problema considerato.
Se Q è semidefinita positiva, il problema non è detto che ammetta soluzione. Se
ammette soluzione allora ammette infinite soluzioni. Nel caso in cui ammetta infinite so-
luzioni allora il metodo del gradiente coniugato determina una delle soluzioni al problema
in un numero finito di iterazioni.

42
2.1.3 Metodo del gradiente coniugato (minimi quadrati lineari)
Il problema di ottimizzazione
1
min kAx − bk2
2
è un problema quadratico convesso (in generale non strettamente convesso) che ammette
soluzione.
1
min xT AT Ax − (AT b)T x
2
Il problema ammette soluzione, quindi posso applicare il metodo del gradiente coniuga-
to. Prendendo come punto iniziale x0 = 0 il metodo determina la soluzione a minima
norma.

2.1.4 Metodo del gradiente coniugato (caso generale)

Dato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

con f continuamente differenziabile, f ∈ C 1 .

Schema generale
Dati x0 ∈ Rn , k = 0, d0 = −g0 .

Algoritmo 7 Metodo del gradiente coniugato

while gk 6= 0 do
calcola αk con una ricerca unidimensionale
poni xk+1 = xk + αk dk
poni dk+1 = −gk+1 + βk+1 dk
k =k+1
end while

Nel caso quadratico la scelta delle formule per il calcolo di βk+1 era indifferente, poichè
le formule erano del tutto equivalenti.
Nel caso non quadratico le formule di βk+1 non sono equivalenti e la diversa scelta di
una di queste nell’esecuzione dell’algoritmo dà origine a metodi con diverse denominazio-
ni.
T
gk+1 (gk+1 − gk )
• Metodo di Poliak-Ribiele: βk+1 =
kgk k2
kgk+1 k2
• Metodo di Fletcher-Reeved : βk+1 =
kgk k2

Per quanto riguarda invece il calcolo di αk si necessita ora di un tipo di ricerca

unidimensionale più complessa del metodo di Armijo.
Il requisito minimo è sempre, come nel metodo di Armijo, che dk+1 sia una direzione
di discesa:
T
gk+1 dk < 0

43
 T
gk+1 dk+1 = −kgk+1 k2 + βk+1 gk+1
T
dk < 0
Poichè −kgk+1 k2 è sicuramente negativo, per far verificare la disequazione ho bisogno di
T
controllare βk+1 gk+1 dk . Il termine βk+1 nelle varie formule dipende da xk , αk e dk :
gk+1 = g(xk + αk dk )
T
gk+1 dk = g(xk + αk dk )T dk = Φ̇(αk )
con Φ(α) = f (xk + αdk ) e Φ̇(α) = ∇f (xk + αdk )T dk . La condizione di Armijo afferma
che
f (xk + αk dk ) ≤ f (xk ) + γαk ∇f (xk )T dk
ovvero di sufficiente decremento della funzione.
Si rende più forte la condizione su αk utilizzando metodi di ricerca unidimensionale
basati sulle condizioni di Wolfe.

2.1.5 Condizioni di Wolfe

1
Sia 0 < γ ≤ 2
< σ < 1.
• Wolfe debole
f (xk + αk dk ) ≤ f (xk ) + γαk ∇f (xk )T dk
∇f (xk + αk dk )T dk ≥ σ∇f (xk )T dk

• Wolfe forte
f (xk + αk dk ) ≤ f (xk ) + γαk ∇f (xk )T dk
|∇f (xk + αk dk )T dk | ≤ σ|∇f (xk )T dk |

2.2 Condizioni di ottimalità per problemi di ottimizza-

zione vincolata
Sia f : Rn → R, g : Rn → Rm , h : Rn → Rp , e sia dato il problema di ottimizzazione
vincolata

min f (x)
gi (x) ≤ 0 i = 1, . . . , m
hj (x) = 0 j = 1, . . . , p
con gi (x) ≤ 0 e hj (x) = 0 detti vincoli di disuguaglianza e vincoli di uguaglianza.
Associamo ora ai vincoli i moltiplicatori di Lagrange:
λ0 → f (x) λi → gi (x) µj → hj (x)
possiamo così definire la funzione lagrangiana.

Definizione 10 (Funzione Lagrangiana)

m p
X X
L(x, λ0 , λ, µ) = λ0 f (x) + λi gi (x) + µj hj (x)
i=1 j=1

44
2.2.1 Condizioni di ottimalità di Fritz-John
Le condizioni di ottimalità di Fritz-John per problemi di ottimizzazione vincolata sono
condizioni necessarie di ottimalità.
Sia x∗ minimo locale. Allora ∃ λ∗0 , λ∗ ≥ 0; µ∗ :

1) (λ∗0 , λ∗ , µ∗ ) 6= (0, 0, 0)
m p
X X
2) λ∗0 ∇f (x∗ ) + λ∗i ∇gi (x∗ ) + µ∗i ∇hj (x∗ ) = 0
i=1 j=1

3) λ∗i gi (x∗ ) = 0 i = 1, . . . , m condizioni di complementarietà

4) g(x∗ ) ≤ 0 h(x∗ ) = 0 condizioni di ammissibilità

Le condizioni di complementarietà ci indicano che uno dei due fattori (λ∗i o gi (x∗ ) deve
essere nullo, mentre quelle di ammissibilità che la soluzione sia ammissibile per il problema
di ottimizzazione.
Posso riscrivere le condizioni in forma vettoriale tramite l’utilizzo della funzione la-
grangiana.
L(x, λ0 , λ, µ) = λ0 f (x) + λT g(x) + µT h(x)
Indico con  
∇g = ∇g1 · · · ∇gm
 
∇h = ∇h1 · · · ∇hm
Allora, derivando la lagrangiana rispetto alla variabile x:

∇x L(x, λ0 , λ, µ) = λ0 ∇f (x) + ∇g(x)λ + ∇h(x)µ (2.6)

Unendo la condizione numero 2 di Fritz-John e 2.6 ottengo che

∇x L(x∗ , λ∗0 , λ∗ , µ∗ ) = 0

cioè ottengo che il gradiente della funzione lagrangiana si annulla rispetto a x. Le

condizioni di Fritz-John definiscono così condizioni di complementarietà e ammissibilità.

Condizioni di complementarietà Le condizioni di complementarietà espresse da

Fritz-John possono essere espresse come

λ∗ T g(x∗ ) = 0

perchè λi gi (x) sono tutti non positivi. Possiamo quindi esprimere queste condizioni sotto
forma di prodotto scalare.

2.2.2 Condizioni di qualificazione dei vincoli

Se λ∗0 = 0 nelle condizioni di Fritz-John non compare la funzione obiettivo. Questo
potrebbe renderle poco significative perdendo il legame tra funzione e vincoli del problema.
Siamo quindi interessati ai casi in cui λ∗0 > 0. Abbiamo bisogno di nuove condizioni sui
vincoli del problema, dette di qualificazione dei vincoli.

45
Definizione 11 (Vincoli attivi) Un vincolo di un problema di ottimizzazione non vin-
colata si dice attivo se
gi (x∗ ) = 0
Definiamo ora l’ insieme dei vincoli attivi come

I(x∗ ) = {i ∈ {1, . . . , m} : gi (x∗ ) = 0}

Si può assicurare che, sotto opportune ipotesi su g ed h, λ∗0 > 0.

1) Linearità: la condizione vale se g, h sono funzioni lineari.

2) Indipendenza lineare dei gradienti: la condizione vale se c’è indipendenza li-

neare dei gradienti dei vincoli di uguaglianza e dei gradienti dei vincoli attivi. Cioè
se
∇h1 (x∗ ) · · · ∇hp (x∗ )∇gi (x∗ ) i ∈ I(x∗ )
 

linearmente indipendenti.

Dimostrazione
Dalle condizioni di Fritz-John
m p
X X
λ∗0 ∇f (x∗ ) + λ∗i ∇gi (x∗ ) + µ∗j ∇hj (x∗ ) = 0
i=1 j=1

p
X X
λ∗0 ∇f (x∗ ) + λ∗i ∇gi (x∗ ) + µ∗j ∇hj (x∗ ) = 0
i∈I(x∗ ) j=1

per le condizioni di complementarietà, se i 6∈ I(x∗ ) ⇒ gi (x∗ ) < 0 ⇒ λ∗ = 0. Quindi,

supponiamo per assurdo che λ∗0 = 0. Sappiamo che (λ∗0 , λ∗ , µ∗ ) 6= (0, 0, 0), allora:

(λ∗ , µ∗ ) 6= (0, 0)
p
X X
λ∗i ∇gi (x∗ ) + µ∗j ∇hj (x∗ ) = 0
i∈I(x∗ ) j=1

ma, poichè linearmente indipendenti è assurdo.

3) Condizioni di Mangasarian-Fromowitz: la combinazione conica (combinazione

lineare a coefficienti non negativi) del gradiente dei vincoli di disuguaglianza attivi
in x∗ e del gradiente dei vincoli di uguaglianza non esiste.

4) Condizioni di Slater: se il problema è convesso, esiste un punto x in cui sono

soddisfatti i vincoli di uguaglianza e i vincoli di disuguaglianza attivi in x∗ sono
strettamente minori di zero.

46
2.2.3 Condizioni di Karush-Kuhn-Tucker (KKT)
Dalle condizioni di Fritz-John, unite alle condizioni di qualificazione dei vincoli (basta
che una di esse sia verificata) si arriva alla definizione delle condizioni di ottimalità di
Karush-Kuhn-Tucker o KKT.
Poichè almeno una condizione di qualificazione è verificata abbiamo che

λ∗0 > 0

Proposizione 30 (Condizioni di KKT) Sia x∗ minimo locale e valga una tra le

condizioni di qualificazione dei vincoli. Allora ∃ λ∗ ≥ 0, µ∗ :
m p
X X
∗
1) ∇f (x ) + λ∗i ∇gi (x∗ ) + µ∗j ∇hj (x∗ ) = 0
i=1 j=1

2) λ∗i gi (x∗ ) = 0 i = 1, . . . , m

3) g(x∗ ) ≤ 0 h(x∗ ) = 0

Osservazione: Se f è convessa e g, h lineari allora le condizioni di KKT sono neces-

sarie e sufficienti di minimo globale.

Esprimendole in forma vettoriale tramite la funzione lagrangiana

L(x, λ, µ) = f (x) + λT g(x) + µT h(x)

abbiamo quindi che

1) ∇x L(x∗ , λ∗ , µ∗ ) = 0

2) λ∗ T g(x∗ ) = 0

3) λ∗ ≥ 0

4) h(x∗ ) ≤ 0 h(x∗ ) = 0

2.2.4 Esempi di applicazione delle condizioni di ottimalità per

problemi di ottimizzazione vincolata
Problemi con vincoli di box
Sia dato il problema di ottimizzazione vincolata

min f (x)
l≤x≤u

con li ≤ xi ≤ ui i = 1, . . . , n. Poichè i vincoli di disuguaglianza sono lineari valgono le

condizioni di KKT. Possiamo riscrivere il problema come

min f (x)

47
 xi − ui ≤ 0 i = 1, . . . , n
li − xi ≤ 0 i = 1, . . . , n
−
Associamo i moltiplicatori λ+
i e λi alle due disuguaglianze

n
X n
X
+ −
L(x, λ , λ ) = f (x) + λ+
i (xi − ui ) + λ−
j (lj − xj )
i=1 j=1

−
Per le condizioni di KKT, λ+
i , λi ≥ 0 i = 1, . . . , n.

δL δf (x) −
= + λ+
i − λi = 0 i = 1, . . . , n
δxi δxi
Per la complementarietà abbiamo che
−
λ+
i (xi − ui ) = 0 λi (li − xi ) = 0 i = 1, . . . , n

Per l’ammissibilità abbiamo che

li ≤ xi ≤ ui i = 1, . . . , n

Sia ora x∗ minimo locale.

a) Supponiamo che x∗i = li ⇒ x∗i < ui . Unendo questo risultato alle condizioni di
complementarietà otteniamo che

δf (x∗ )
λ+
i = 0 ⇒ = λ−
i ≥ 0
δxi

b) Supponiamo che x∗i = ui ⇒ x∗i > li . Unendo questo risultato alle condizioni di
complementarietà otteniamo che

δf (x∗ )
λ−
i = 0 ⇒ = −λ+
i ≤ 0
δxi

c) Supponiamo li ≤ xi ≤ ui :
x∗i < ui ⇒ λ+
i = 0

li < x∗i ⇒ λ−
i = 0

δf (x∗i
Quindi = 0.
δxi

Proposizione 31 (Condizione necessaria di ottimalità per problemi di ottimiz-

zazione con vincoli di box) Sia x∗ minimo locale. Allora:

1) l ≤ x∗ ≤ u

∗  ≥ 0 se x∗i = li
δf (x )
2) =0 se li < xi < ui
δxi 
≤0 se x∗i = ui

48
Problemi con vincolo di simplesso
Dato un problema di ottimizzazione vincolata

Pnmin f (x)
i=1 xi =1

con x ≥ 0, è detto con vincolo di simplesso.

Sia x∗ minimo locale. x∗ è ammissibile se
δf (x∗ ) δf (x∗ )
∀ j ∈ {1, . . . , n} : x∗j > 0 ⇒ ≤ i = 1, . . . , n
δxj δxi

2.3 Metodi di Trust Region

Dato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

introduciamo i metodi di Trust Region, o Regione di confidenza. Riprendendo il metodo

di Newton:
1
f (xk + s) ' f (xk ) + ∇f (xk )T s + sT ∇2 f (xk )s
2
Introduco il concetto di modello quadratico, definito come
1
m(s) = f (xk ) + ∇f (xk )T s + sT ∇2 f (xk )s
2
In base alla matrice Hessiana si possono distinguere due casi:
• Se ∇2 f (xk ) è definita positiva allora

min m(s)
s

skN = −[∇2 f (xk )]−1 ∇f (xk )

• Se ∇2 f (xk ) è indefinita allora il problema

min m(s)
s

non ammette soluzione.

2.3.1 Introduzione ai metodi Trust Region

Ad ogni iterazione k si costruisce un modello quadratico di f . Indichiamo con mk (s) il
modello al passo k definito come
1
mk (s) = f (xk ) + ∇f (xk )T s + sT Bk s
2
con Bk matrice nxn simmetrica.
Bk potrebbe quindi essere la matrice Hessiana o una sua approssimazione. Non
facciamo nessuna ipotesi che sia definita o meno.

49
 Consideriamo ora il sottoproblema

min mk (s) ksk ≤ ∆k

s

con ∆k raggio della regione di confidenza. Così definito il sottoproblema è un problema

di ottimizzazione vincolato: ammette dunque sicuramente soluzione per il teorema di
Weierstrass e ∆k definisce la sfera (regione spaziale) in cui il modello quadratico è una
buona approssimazione di quello lineare.
Supponiamo di determinare una soluzione sk , eventualmente approssimata, del sot-
toproblema definito. La soluzione potrebbe essere approssimata poiché f potrebbe non
essere convessa. Dobbiamo decidere quindi se accettare o meno il punto xk + sk , ovvero
il prossimo punto dell’iterazione.
Consideriamo la variazione della funzione obiettivo

f (xk ) − f (xk+1 ) Q 0

e la variazione del modello quadratico

mk (0) − mk (sk ) > 0

Non abbiamo garanzie che, ottenuta una variazione nel modello quadratico, otterrem-
mo necessariamente anche una variazione nella funzione obiettivo.
Chiamiamo ora
f (xk ) − f (xk + sk )
ρk =
mk (0) − mk (xk )
ovvero il rapporto tra le variazioni della funzione obiettivo ed il modello quadratico.
Allora:
• Se ρk sufficientemente positivo (quindi sia il modello che la funzione sono diminuiti)
allora xk+1 = xk + sk .
Se molto positivo allora ∆k+1 ≥ ∆k , allargo cioè la regione di confidenza. Altrimenti
∆k+1 ≤ ∆k , la riduco.

• Se ρk < 0, oppure non sufficientemente positivo (la funzione è dunque aumentata),

xk+1 = xk e ∆k+1 < ∆k .

2.3.2 Schema generale dei metodi Trust Region

Dati x0 ∈ Rn , ∆0 > 0, k = 0, definiamo i parametri per la valutazione di ρk ed i parametri
per l’aggiornamento della regione di confidenza, rispettivamente:

0 < µ1 < µ2 < 1 0 < γ1 < γ2 < 1

• Passo 1: Costruzione del modello quadratico mk (s). In questo passo definisco

anche Bk .

• Passo 2: Calcolo della soluzione sk , eventualmente approssimata, del problema

min mk (s) ksk ≤ ∆k

s

che fornisca un sufficiente decremento del modello quadratico.

50
 • Passo 3: Accettazione del nuovo punto. Calcolo

f (xk ) − f (xk+1 + sk )
ρk =
mk (0) − mk (xk )

Studio ora ρk :

– Se ρk ≥ µ1 ⇒ xk+1 = xk + sk
– Altrimenti ⇒ xk+1 = xk

• Passo 4: Aggiornamento del raggio di confidenza


 [∆k , ∞) se ρk ≥ µ2
∆k+1 ∈ [γ2 ∆k , ∆k ] se µ1 ≤ ρk ≤ µ2
[γ1 ∆k , γ2 ∆k ] se ρk < µ1


2.3.3 Punti cruciali dello schema generale dei metodi Trust Re-
gion
Definizione di sufficiente decremento del modello quadratico
1
min f (xk ) + ∇f (xk )T s + sT Bk s ksk ≤ ∆k
s 2
Per s = 0 ⇒ mk (0) = f (xk ). Per ottenere un sufficiente decremento calcolo il gradiente

∇mk (0) = ∇f (xk )

sk = 0 − τ ∇mk (0) = −τ ∇f (xk )

Arriviamo dunque ad un sottoproblema vincolato nella variabile τ .
1 ∆k
min f (xk ) = τ k∇f (xk )k2 + τ 2 ∇f (xk )T Bk ∇f (xk ) 0≤τ ≤
τ 2 k∇f (xk )k

Ottengo così due possibili casi:

• Se ∇f (xk )T Bk ∇f (xk ) ≤ 0 ⇒ è una funzione monotona decrescente

∆k
τ∗ =
k∇f (xk )k

• Se ∇f (xk )T Bk ∇f (xk ) > 0

∆k k∇2 f (xk )k2

τ ∗ = min{ , }
k∇f (xk )k ∇f (xk )T Bk ∇f (xk )

Definiamo dunque
sk = −τ ∗ ∇f (xk )
chiamato passo di Cauchy, che fornisce un sufficiente decremento del modello quadra-
tico. Il passo di Cauchy prende il ruolo che l’antigradiente aveva nel caso dei metodi di
ricerca lineare.

51
Calcolo della soluzione del sottoproblema in modo da ottenere sufficiente
decremento
Sia (*) il sottoproblema
1
min fk + gkT s + sT Bk s ksk ≤ ∆k
s 2
Il calcolo della soluzione può essere:
• Approssimata: ad esempio tramite il passo di Cauchy

• Esatta: anche se il sottoproblema è non convesso.

E’ dunque l’unico caso di problema non convesso in cui esistono condizioni necessarie e
sufficienti di minimo locale.

Proposizione 32 (Condizione necessaria di minimo locale) Sia s∗ minimo locale

per (*). Allora:
i) Bk s∗ + gk + λ∗ s = 0

ii) ks∗ k ≤ ∆k

iii) λ∗ (ks∗ k − ∆k ) = 0

iv) λ∗ ≥ 0
Dimostrazione
La funzione obiettivo è lineare. Trasformo i vincoli
1
min fk + gkT s + sT Bk s ksk2 − ∆2k ≤ 0
s 2
In questo modo anche i vincoli sono lineari, quindi ∈ C 1 .
Per applicare le condizioni di KKT dobbiamo verificare che sia soddisfatta almeno
una condizione di qualificazione dei vincoli. Verifichiamo se vale l’indipendenza lineare
dei gradienti dei vincoli attivi.
Supponiamo che in s∗ sia attivo il vincolo:

ksk2 − ∆2k = 0

2s∗ 6= 0 ⇒ il gradiente è linearmente indipendente

possiamo dunque procedere applicando le condizioni di KKT.
1
L(s, λ) = fk + gkT s + sT Bk s + λ(ksk2 − ∆2k )
2
i) ∇s L(s∗ , λ∗ ) = gk + Bk s∗ + 2λ∗ s∗ = 0

ii) ks∗ k ≤ ∆k

iii) λ∗ (ks∗ k2 − ∆2k ) = 0

iv) λ∗ ≥ 0

52
Proposizione 33 (Condizione necessaria e sufficiente di minimo globale) Un
punto s∗ è un punto di minimo globale se e solo se ∃ λ∗ :
i) Bk s∗ + gk + λ∗ s∗ = 0

ii) ks∗ k ≤ ∆k

iii) λ∗ (ks∗ k − ∆k ) = 0

iv) λ∗ ≥ 0

v) Bk + λ∗ I è semidefinita positiva
Dimostrazione

- Condizione necessaria

s∗ punto di minimo globale ⇒ s∗ minimo locale, quindi vale la proposizione precedente,

(i) - (iv) già dimostrate. Dobbiamo ora dimostrare la (v).
• Caso I : Supponiamo s∗ = 0 ⇒ gk = 0 dalla (i). Dalla (iii) abbiamo che λ∗ = 0.
Quindi il problema si riduce a:
1
min sT Bk s ks∗ k < ∆k
s 2

Dunque s∗ minimo non vincolato ⇒ la matrice Hessiana è semidefinita positiva ⇒

Bk è semidefinita positiva e vale la (v).

• Caso II : Supponiamo ora s∗ 6= 0.

Supponiamo per assurdo che Bk + λ∗ I sia indefinita. Allora:

∃ ẑ : ẑ T (Bk + λ∗ I) < 0

Possiamo individuare un vettore z:

z T (Bk + λ∗ I) < 0 (2.7)

z T s∗ 6= 0 (2.8)
se ẑ : ẑ T s 6= 0 ⇒ z = ẑ altrimenti z = ẑ + αs∗ . Quindi

z T s∗ = ẑ T s∗ + αks∗ k = αks∗ k2 6= 0

Se prendo α 6= 0 e sufficientemente piccolo

kz − ẑk = |α|ks∗ k

poichè devo soddisfare la 2.7. Dunque:

z T (Bk + λ∗ I)z < 0

Definisco ora un punto s = s∗ + µz. Faccio vedere che, scegliendo opportunamente

µ
ksk ≤ ∆k e mk (s) < mk (s∗ )

53
che sarebbe assurdo poichè avrei trovato un punto ammissibile strettamente minore.

ksk2 = sT s
= ksk2 + 2µs∗ T z + kzk2 µ2
= µ(2s∗ T z + µkzk2 + ksk2 )

−2s∗ T z
Prendo ora µ = . Quindi
kzk2

ksk2 ≤ ks∗ k2 ≤ ∆2k

ovvero ho soddisfatta la condizione di ammissibilità. Poichè mk (s) è una funzione

quadratica, tramite lo sviluppo di Taylor :
1
mk (s) = mk (s∗ ) + ∇mk (s∗ )T (s − s∗ ) + µ2 z T Bk z
2
con s − s∗ = µz.
∇mk (s∗ ) = Bk s∗ + gk = −λ∗ s∗
per la (i).
1
mk (s) = mk (s∗ ) + µ2 z T Bk z
2
1 1 1
= mk (s∗ ) + µ2 z T Bk z + µ2 λ∗ kzk2 − µ2 λ∗ kzk2
2 2 2
1 1
= mk (s∗ ) + µ2 z T (Bk + λ∗ I)z − µ2 λ∗ kzk2 − λ∗ µz T s
2 2
dove gli ultimi due termini sono nulli per come ho scelto µ.
1
mk (s) = mk (s∗ ) + µ2 z T (Bk − λ∗ I)z
2
< mk (s∗ )

poichè z T (Bk + λ∗ I)z < 0 ed è assurdo poichè s∗ è un punto di minimo globale.

- Condizione sufficiente

Valgono (i) - (v) ⇒ s∗ è punto di minimo globale del problema non vincolato
1
min sT (Bk + λ∗ I)s) + gkT s
s 2

Quindi
1 1
∀ s ∈ Rn ⇒ sT Bk s + gkT s ≥ s∗ T Bk s∗ + gkT s∗ + λ∗ [ks∗ k2 − ksk] (2.9)
2 2

54
 – Supponiamo che s∗ < ∆k . Allora:

λ∗ per la complementarietà ⇒ λ∗ = 0

Quindi
1 T 1
∀ s ∈ Rn s Bk s + gkT ≥ s∗ T Bk s∗ + gkT s∗
2 2
∗
da cui ricaviamo che s è minimo globale di mk (s) su tutto Rn , quindi anche
all’interno della regione di confidenza.
– Supponiamo che s∗ = ∆k . Allora:

∀ s : ksk ≤ ∆k ⇒ ksk ≤ ks∗ k (2.10)

Quindi, unendo la 2.9 e la 2.10 otteniamo che

1 1
∀ s : ksk ≤ ∆k ⇒ sT Bk s + gkT s ≥ s∗ T Bk s∗ + gkT s∗
2 2
e s∗ è minimo globale nella regione di confidenza.

2.4 Metodi Quasi-Newton

Richiamo 11 (Metodo di Newton)

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk )

Definiamo lo schema dei metodi Quasi-Newton come:

xk+1 = xk − αk Bk−1 ∇f (xk )

con Bk che approssima ∇2 f (xk ).

Caso quadratico f (x) = 21 xT Qx − cT x

∇f (x) = Qx − c ∇2 f (x) = Q

Q−1 (∇f (y) − ∇f (x)) = y − x

Q(y − x) = ∇f (y) − ∇f (x)

Caso generale
xk+1 = xk − αk Bk−1 ∇f (xk )
sk = xk+1 − xk
yk = ∇f (xk+1 ) − ∇f (xk )
Voglio determinare Bk in modo tale che:

1) Bk+1 sk = yk

55
 2) Bk+1 = Bk + ∆Bk con ∆Bk detta matrice delle correzioni.

Ragionando ora in termini di inversa, consideriamo

Hk+1 approssimazione di [∇2 f (xk )]−1
abbiamo che:
3) Hk+1 yk = sk
4) Hk+1 = Hk + ∆Hk con ∆Hk matrice delle correzioni.
Abbiamo che Bk+1 e Hk+1 sono matrici simmetriche.
I vari metodi Quasi-Newton differiscono tra loro nella scelta delle matrici di correzione
∆Bk e ∆Hk . Considerando che
• (1) e (3) sono formule di aggiornamento dirette
• (2) e (4) sono formule di aggiornamento inverse
Se lavoriamo con quelle dirette si ottiene che
−1
xk+2 = xk+1 − αk+1 Bk+1 ∇f (xk )
Se invece lavoriamo con quelle inverse
xk+2 = xk+1 − αk+1 Hk+1 ∇f (xk )
I metodi Quasi-Newton sono anche detti a matrice variabile (quello del gradiente era
detto a discesa più ripida). Sia Bk una matrice simmetrica e definita positiva. Considero
dunque la norma indotta di Bk
1
kxkBk = (xT Bk x) 2
Vogliamo ora
min ∇f (xk )T d kdkBk = 1
d
Per Weierstrass il problema ammette soluzione. Il problema è vincolato, vedo dunque se
posso applicare le condizioni di KKT. Se rinomino il vincolo come (elevando alla seconda):
dT Bk d − 1 = 0
con Bk d gradiente vincolato 6= 0.
⇓
Esiste dunque indipendenza lineare dei gradienti dei vincoli di uguaglianza come condi-
zione di qualificazione dei vincoli. Posso quindi applicare le condizioni di KKT. Valgono
però solo le condizioni necessarie poichè i vincoli non sono lineari.
L(α, µ)g T d + µ(dT Bk d − 1)
1) g + µBk d = 0 ⇒ d = − µ1 Bk−1

2) dT Bk d = 1 ⇒ µ1 g T Bk−1 g = ±1
q
µ= g T Bk−1
Si hanno quindi 2 soluzioni, quella che ci interessa è la positiva. La soluzione è dunque
Bk−1 gk
d=−
gkT Bk gk

56
2.4.1 Interpretazione geometrica in una variabile
Data una funzione in una variabile g : R → R un metodo Quasi-Newton è detto metodo
della secante. Ricaviamo l’equazione della retta secante
gk − gk+1
y = gk+1 + (x − xk+1 )
xk − xk+1
gk − gk+1
o = gk+1 + (xk+2 − xk+1 )
xk − xk+1
xk − xk+1
xk+2 = xk+1 − gk+1 = xk+1 − hk+1 gk+1
gk − gk+2
chiamando
xk − xk+1
hk+1 =
gk − gk+2
ho dunque
hk+1 (gk − gk+1 ) = xk − xk+1
e cioè della forma
Hk+1 (∇f (xk ) − ∇f (xk+1 )) = xk − xk+1
quindi si può dire che con n = 1 il metodo Quasi-Newton è detto metodo della secante.

2.4.2 I metodi Quasi-Newton

I metodi Quasi-Newton si dividono principalmente in base al rango delle formule di
aggiornamento.

Metodi basati su formule di aggiornamento di rango 1

Bk+1 = Bk + ϕk µk vkT

Il metodo più importante è quello di Brayden.

Metodi basati su formule di aggiornamento di rango 2

Hk+1 = Hk + ak uk uTk + bk vk vkT

Il metodo più usato è BFGS :

xk+1 = xk − αk Hk gk

dkN = −Hk gk di discesa ⇒ gkT dkN < 0

con Hk definita positiva.
Determino αk con una ricerca unidimensionale (tramite Armijo o le condizioni di
Wolfe). Poiché la direzione tiene memoria delle iterazioni precedenti non posso però
usare Armijo, sono obbligato ad usare le condizioni di Wolfe.

Hk definita positiva ⇒ Hk+1 definita positiva

Hk+1 yk = sk

57
per l’equazione di QN.
ykT Hk+1 yk = ykT sk > 0
(gk+1 − gk )T > 0
con αk che scompare poiché > 0.

g(xk + αk dk )dk > g(xk )dk

Sia Φ(α) = f (xk + αdk ), la sua derivata è Φ̇(α) = g(xk + αdk )T dk . Si ha dunque che

Φ̇(α) > Φ̇(0)

per cui αk deve soddisfare una condizione sulla pendenza.

2.4.3 Conclusioni su BFGS

• Converge globalmente sotto ipotesi di continuità di f .
• Ha rapidità di convergenza superlineare (come Newton).

2.5 Metodo del gradiente di Barzilai-Borwein

Il metodo del gradiente di Barzilai-Borwein (BB) è una più versione (datata 1988) del
metodo del gradiente che si è rivelata particolarmente efficiente nella soluzione di problemi
difficili e a grande dimensione. Studiamo inizialmente il metodo nel caso quadratico e
successivamente lo estendiamo al caso non quadratico.

2.5.1 Caso quadratico

Sia dato un problema di ottimizzazione non vincolata con funzione obiettivo quadratica
1
minn xT Qx − cT x
x∈R 2

con Q matrice simmetrica e definita positiva. Ricordiamo il metodo della discesa più
ripida
xk+1 = xk − αk ∇f (xk )
con αk passo ottimo lungo la direzione −∇f (xk )
k∇f (xk )k
αk =
∇f (xk )T Q∇f (xk )
Questo metodo converge globalmente all’unica soluzione del problema, ma è poco efficien-
te.
Consideriamo ora
1
xk+1 = xk − ∇f (xk )
µk
= xk − Bk−1 ∇f (xk )
= xk − Hk ∇f (xk )
1
con Bk = µk I e Hk = µk
I.

58
 • Bk la posso considerare un’approssimazione della matrice Hessiana, Q.
• Hk la posso considerare un’approssimazione dell’inversa della matrice Hessiana,
Q−1 .
Dobbiamo ora formalizzare cosa intendiamo per approssimazione. Indichhiamo con
s = xk − xk−1
y = ∇f (xk ) − ∇f (xk−1 )
Qs = y Q−1 y = s
soddisfano cioè le equazioni Quasi-Newton.
Scelgo ora µk in modo tale da minimizzare l’errore nell’equazione Quasi-Newton
min kµIs − yk2 = min µ2 sT s − 2µsT y
µ µ

La soluzione costituisce la I a formula di Barzilai-Borwein:

(a) sT y
µk = (2.11)
sT s
Analogamente per l’inversa
1 2
min ks − yk
µ µ
1
β= min ks − βyk2 = min β 2 y T y − 2βsT y
µ β β

sT y
β=
yT y
La soluzione costituisce la II a formula di Barzilai-Borwein:
(b) yT y
µk = (2.12)
sT y
Il metodo di BB converge globalmente per qualsiasi dimensione del problema in caso
di funzione obiettivo quadratica e strettamente convessa (risultato del 1992).

Interpretazione del metodo BB: metodo spettrale del gradiente

Il metodo è anche detto metodo spettrale del gradiente, legato cioè agli autovalori della
matrice Q.
Definiamo il quoziente di Raileigh della matrice Q come

xT Qx
λmin (Q) ≤≤ λmax (Q)
kxk2
Possiamo far vedere che le due formule, 2.11 e 2.12, sono due quozienti di Raileigh.
• La 2.11 è un quoziente di Raileigh
(a) sT y
µk = y = ∇f (xk ) − ∇f (xk−1 ) = Qs
sT s
(a) sT Qs sT Qs
µk = = ⇒ è un quoziente di Raileigh
sT s ksk2

59
 • La 2.12 è un quoziente di Raileigh

(b) yT y (b) yT y
µk = s = Q−1 y µk =
sT y y T Q−1 y

1 y T Q−1 y 1
≤ T
≤
λmax (Q) y y λmin (Q)
(b)
λmax (Q) ≤ µk ≤ λmin (Q)

Dunque entrambi i valori di µ appartengono allo spettro di Q.

Interpretazione del metodo BB: metodo del gradiente con ritardo

Riprendiamo ora il metodo del gradiente
1
xk+1 = xk − ∇f (xk )
µk
1
xk = xk−1 − ∇f (xk−1 )
µk−1
(a)
Consideriamo ora la prima formula di BB µk = µk :

sTk−1 yk−1
µk =
sTk−1 sk−1

Ricordando che sk−1 = xk − xk−1 e yk−1 = ∇f (xk ) − ∇f (xk−1 ). Moltiplico ora l’equazione
del gradiente per Q e sottraggo c da ambo le parti, ottenendo:
1
yk−1 = ∇f (xk ) − ∇f (xk−1 ) = − Q∇f (xk−1 )
µk−1
1
sTk−1 yk−1 = −( )2 ∇f (xk−1 )T Q∇f (xk−1 )
µk−1
1
sTk−1 sk−1 = ( )2 k∇f (xk−1 )k2
µk−1

1
xk+1 = xk − ∇f (xk )
µk
k∇f (xk−1 )k2
= xk − ∇f (xk )
∇f (xk−1 )T Q∇f (xk−1 )

con µ1k che rappresenta il passo ottimo relativo all’iterazione precedente. Questo dà luogo
ad un metodo del gradiente con ritardo.

60
2.5.2 Caso non quadratico
L’estensione del metodo del gradiente di Barzilai-Borwein al caso non quadratico risale
all’anno 1997.
Sia dato un problema di ottimizzazione non vincolata

min f (x)
x∈Rn

utilizziamo le due formule di BB ottenute nel caso quadratico

(a) sT y (b) yT y
µk = µk =
sT s sT y
1
xk+1 = xk − αk ∇f (xk )
µk
Osservazioni

• Nel caso quadratico µk era sicuramente positivo (essendo compreso nello spettro
della matrice Q, definita positiva). Nel caso non quadratico non ho limitazioni di
segno per µk , quindi è necessario effettuare un controllo
1
0 < ε ≤ µk ≤ ε ' 10−10
ε

• αk determinato con una ricerca unidimensionale, Armijo non monotono

Cenni sui metodi non monotoni

Riprendiamo il metodo di Newton

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk )

Se x0 ∈ B(x∗ , ε) ⇒ il metodo converge localmente con rapidità superlineare. Non è però

assicurato che f (xk+1 ) < f (xk ), cioè il metodo è generalmente non monotono. Nel caso
del metodo di Newton non posso quindi utilizzare Arminjo (è un metodo monotono) senza
stravolgimenti del metodo stesso. Esiste però una versione di Armijo non monotona:

• Armijo monotono

f (xk+1 ) ≤ f (xk ) + γαk ∇f (xk )T dk

• Armijo non monotono

f (xk+1 ) ≤ W k + γαk ∇f (xk )T dk W k = max {f (xk−j )}

0≤j≤M

con M intero finito. Può quindi accadere che si verifichi la condizione f (xk+1 ) >
f (xk ).

61
2.6 Metodi per problemi di minimi quadrati
Sia dato un problema di ottimizzazione non vincolata
m
X
minn ri2 (x)
x∈R
i=1

con r funzione dei residui.


ri (x) = aTi x − bi i = 1, . . . , m ⇒ minimi quadrati lineari
Se
altrimenti ⇒ minimi quadrati non lineari

2.6.1 Problemi di minimi quadrati lineari

1
minn kAx − bk2
x∈R 2
   
aT1 b1
A =  ...  b= .. 
  
. 
aTm bm
Vogliamo dimostrare che il problema ammette soluzione qualunque sia la matrice A. Devo
far vedere che il sistema
AT Ax = AT b
ammette soluzione, questo perchè
∇f (x) = AT Ax − AT b ∇2 f (x) = AT A
cioè ∃ x∗ : ∇f (x∗ ) = 0 ⇒ x∗ è soluzione poichè f è convessa. Vediamo ora un risultato
di geometria
b = bR + bN bR ∈ Range(A) bN ∈ Ker(AT )

AT Ax = AT (bR + bN )
= A T bR
Per dimostrare il risultato di geometria consideriamo il problema
min kb − yk2 AT y = 0
y

Il problema ammette soluzione perchè la funzione obiettivo è coerciva e l’insieme ammis-

sibile è chiuso e non vuoto. Poichè i vincoli sono lineari posso applicare le condizioni
KKT :
L(y, λ) = kb − yk2 + λT (AT y)
∇y L(y, λ) = −(b − y ∗ ) + Aλ∗ = 0
⇓
b = y + Aλ∗
∗

In questo caso le condizioni KKT sono condizioni necessarie e sufficienti poichè f convessa
ed i vincoli sono lineari.
bR = Aλ∗ ∈ Range(A)
bN = y ∗ ∈ Ker(A)
Per il calcolo della soluzione si può ricorrere a metodi diretti (ad esempio quello della
pseudoinversa) o metodi iterativi (gradiente coniugato).

62
Metodo incrementale (filtro di Kalman)

Data Ã(k, n) e b̃ ∈ Rn , abbiamo cioè k osservazioni precedenti

1
min kÃx − b̃k2
2
Indichiamo con x(k) la soluzione al problema precedente. A questo punto abbiamo la
nuova (k + 1)-esima osservazione e vogliamo esprimere x(k + 1) in funzione di x(k).
Indichiamo con    
à b̃
A= b=
aTk+1 bk+1
Viene soddisfatta AT Ax(k + 1) = AT b poichè x(k + 1) annulla il gradiente della funzione
obiettivo.
ÃT Ãx(k) = ÃT b̃ (2.13)
all’iterazione precedente.
 
T T Ã
A A = (Ã ak+1 ) = ÃT Ã + ak+1 aTk+1
aTk+1
 
T T b̃
A b = (Ã ak+1 ) = ÃT b̃ + ak+1 bk+1
bk+1
Utilizzando la 2.13:

[ÃT Ã + ak+1 aTk+1 ]x(k + 1) = ÃT b̃ + ak+1 bk+1 = ÃT Ãx(k) + ak+1 bk+1

[ÃT Ã + ak+1 aTk+1 ]x(k + 1) = [ÃT Ã + ak+1 aTk+1 ]x(k) − ak+1 aTk+1 x(k) + bk+1 ak+1
Chiamo ora
Hk = [ÃT Ã + ak+1 aTk+1 ] Hk = ÃT Ã
Se Hk è invertibile ⇒ Hk+1 è invertibile, poichè definita positiva

−1
x(k + 1) = x(k) + Hk+1 ak+1 (bk+1 − aTk+1 x(k))
E’ una funzione di aggiornamenti che mi fornisce la nuova soluzione a partire dalla
soluzione precedente con
Hk+1 = Hk + ak+1 aTk+1
−1
Esistono formule che forniscono Hk+1 nota Hk−1 . E’ un metodo incrementale. Viene
utilizzato quando il numero dei dati dati e delle caratteristiche è molto elevato.

2.6.2 Problemi di minimi quadrati non lineari

Nel caso di problemi di minimi quadrati non lineari devo innanzitutto garantire l’esistenza
della soluzione (ad esempio con ipotesi di coercività). Per il calcolo della soluzione si può
poi ricorrere al metodo di Gauss-Newton oppure al metodo di Levembert-Marquardt.
Dato un problema di ottimizzazione non vincolata di minimi quadrati non lineari
m
1X 2 1
minn ri (x) = kri (x)k2
x∈R 2 i=1 2

63
con n ≥ m, r(x) : Rn → Rm .
 
∇riT (x)
J(x) = 
 .. 
. 
T
∇rm (x)
m
X
∇f (x) = ri (x)∇riT (x) = J T (x)r(x)
i=1
m
X m
X m
X
∇2 f (x) = ∇ri (x)∇riT (x) + ri (x)∇2 ri (x) = J T (x)J(x) + ri (x)∇2 ri (x)
i=1 i=1 i=1

Metodo di Gauss-Newton
Consideriamo il metodo di Newton

∇2 f (xk )d = −∇f (xk )

Se ri (x) hanno valori piccoli posso approssimare la matrice Hessiana con

∇2 f (xk ) ' J T (xk )J(xk )

trascurando cioè il termine composto unicamente dai residui. Con questa approssimazione
introduco il metodo di Gauss-Newton:

• Risolvi il sistema J T (xk )J(xk )d = −J T (xk )r(xk )

• Poni xk+1 = xk + dk

Il sistema ammette sempre soluzione poichè è un sistema di minimi quadrati lineari,

equivale cioè a risolvere
min kJ(xk )d + r(xk )k2
d
∗
La soluzione che otteniamo, d , è sempre una direzione di discesa. Il metodo di Gauss-
Newton ha convergenza locale con rapidità superlineare o quadratica, otteniamo cioè gli
stessi risultati di convergenza del metodo di Newton senza però l’utilizzo delle derivate
seconde. Il vincolo nell’applicazione del metodo è dato unicamente dalla trascurazione
dei residui e quindi dall’approssimazione della matrice Hessiana.
Una variante del metodo di Gauss-Newton, detta damped, introduce una ricerca
unidimensionale
xk+1 = xk + αk dk
Utilizziamo Armijo non monotono per determinare αk .

Proposizione 34 (Convergenza globale del metodo di Gauss-Newton) Se J T (xk )J(xk )

è uniformemente definita positiva, ovvero l’autovalore minimo al variare di k è maggiore
di un valore minimo, la convergenza del metodo di Gauss-Newton è globale.

64
Metodo di Levenberg-Marquardt
Sia
J T (xk )J(xk ) + Dk
con Dk definita positiva, detta matrice di perturbazione. Considero Dk = µk I

(J T (xk )J(xk ) + µk I)d = −J T (xk )r(xk )

Le varie versioni del metodo differiscono nella scelta di µk .

Una buona scelta potrebbe essere

µk = min{a, k∇f (xk )k}

ovvero perturbo sempre meno il metodo avvicinandomi ad un punto stazionario.

2.7 Metodi per problemi a larga scala

Sia dato un problema di ottimizzazione non vincolata il cui numero di variabili è elevato

min f (x)
x∈Rn

Possiamo utilizzare:

• Metodo di Barzalai-Borwein o gradiente coniugato (non richiedono la memorizza-

zione di matrici)

• Metodo di Newton troncato

∇2 f (xk )d = −∇f (xk )

Se ∇2 f (xk ) definita positiva

1
min dT ∇2 f (xk )d + ∇f (xk )T d
d 2

posso quindi risolvere il problema con il metodo del gradiente coniugato per funzioni
quadratiche
∇f (xk + εv) − ∇f (xk )
∇2 f (xk )v '
ε
Si chiama troncato poichè il metodo del gradiente coniugato è iterativo e potrebbe
essere sufficiente interrompere il processo per ottenere una buona approssimazione.

• Metodi Quasi-Newton a memoria limitata (L-BFGS)

Bk d = −∇f (xk )

65
2.8 Metodi senza derivate
Dato un problema di ottimizzazione non vincolata del tipo

min f (x)
x∈Rn

con f ∈ C 1 , funzione obiettivo di cui non conosciamo le derivate.

Si può procedere alla risoluzione del problema seguendo due approcci:

• Metodi basati sulle approssimazioni alle differenze finite

• Metodi di ricerca diretta

2.8.1 Metodi basati sulle approssimazioni alle differenze finite

Si procede fornendo un approssimazione delle derivate parziali alle differenze finite
δf (x) f (x + εli ) − f (x)
'
δxi ε

con ε > 0 sufficientemente piccolo, ε ' 10−7 . Indichiamo con ˆ (x) l’approssimazione
∇f
del gradiente della funzione obiettivo, ∇f (x).
 
0
 ..
 f (x+εl )−f (x) 
1
 .

ε 
ˆ (x) = 
∇f .. l =  1
  
 .  i
 .

f (x+εln )−f (x)  ..


ε
0

con li vettore con solo la (i)-esima componente unitaria. A questo punto applico un
ˆ (x) al posto
metodo di tipo gradiente (gradiente coniugato, Quasi-Newton) utilizzando ∇f
di ∇f (x).
Questi metodi possono però essere molto inefficaci in problemi in cui è presente un
rumore

66
 δf (x) fˆ(x + εli ) − fˆ(x) |ρ(x + εli ) − ρ(x)|
| − | ≤ c1 ε +
δxi ε ε
Dalla formula precedente si nota che ε si trova sia a numeratore che a denominatore,
dovendo così trovare un compromesso nella scelta del valore finale.

2.8.2 Metodi di ricerca diretta

I metodi di ricerca diretta più rilevanti sono

• Metodo di Nelder-Mead

• Metodo delle coordinate

• Metodo di Hook-Jeeves

Ci sono poi varie estensioni dei metodi precedenti.

Metodo di Nelder-Mead
Il metodo di Nelder-Mead è anche detto metodo del simplesso, poichè si basa su (n + 1)
punti e viene utilizzato l’involucro convesso (detto simplesso) di questi punti. L’involucro
convesso è l’area delimitata dai punti dati.
Alla generica iterazione abbiamo S = {x1 , x2 , . . . , xn+1 }, li ordiniamo in modo tale
che
f (x1 ) ≤ f (x2 ) ≤ · · · ≤ f (xn+1 )
L’idea di questo metodo è di sostiuire il punto xn+1 (il peggiore nell’insieme dato di punti)
con un nuovo punto in modo da ottenere un miglioramento della funzione obiettivo.
Chiamo x̄ il baricentro degli n punti. Nel caso n = 2:
n
1X
x̄ = xi
n i=1

A partire dal punto peggiore (x3 ) traccio la linea che passa per il baricentro fino a xr ,
definito come
xr = x̄ + (x̄ − xn+1 )

67
Se xr è un buon punto (cioè tale che f (xr ) ≤ f (x1 )) provo a migliorare ancora nella stessa
direzione (ipotizzata essere di discesa) fino a calcolare xe = x̄ + 2(x̄ − xn+1 ). Nel caso in
cui f (xe ) > f (xr ) interrompo la ricerca ed inserisco xr al posto di xn+1 e riordino S.

• Se f (x1 ) ≤ f (x2 ) < f (xr ) ⇒ sostituisco xn+1 con xr .

• Se f (xr ) ≥ f (xn ) allora

– Se f (xr ) > f (xn+1 ) genero xci = x̄ − 12 (x̄ − xn−1 ), contrazione interna.

– Se f (xc i) > f (xn+1 ) procedo con un operazione di shrinking, contrazione del
simplesso, generando i punti xi = x1 + 21 (x̄ − x1 ).
– Se f (xr ) ≤ f (xn+1 ) genero xce = x̄+ 21 (x̄−xn+1 ), contrazione esterna e procedo
come nel caso precedente.

Caratteristiche

• Molto efficiente in pratica.

• Proprietà di convergenza globale (solo nel caso n = 1).

• Esistono contro esempi di non convergenza già nel caso n = 2.

• Esistono varie modifiche del metodo globalmente convergenti.

Metodi delle coordinate

In assenza di informazioni sulle derivate non sappiamo se una data direzione è di discesa.
Anzichè una singola direzione possiamo quindi pensare di operare con un insieme di
direzioni. La proprietà richiesta all’insieme di direzioni è che almeno una di esse sia di
discesa in xk punto corrente, anche non sapendo quale.
Considero quindi

D = {e1 , e2 , . . . , en , −e1 , −e2 , . . . , −en }

un insieme di 2n direzioni che gode della proprietà precedente, vedi sezione 1.4.6.
L’idea del metodo delle coordinate consiste nel ricercare un punto migliore procedendo
nelle direzioni di D di un passo αk .

Se ∃ i ∈ {1, . . . , n} : f (xk + αk ei ) < f (xk ) ⇒ xk+1 = xk + αk ei

Se ∃ i ∈ {1, . . . , n} : f (xk − αk ei ) < f (xk ) ⇒ xk+1 = xk − αk ei
Se la condizione precedente non è valida diminuisco αk .

αk = θαk θ ∈ (0, 1)

xk+1 = xk

68
Formalizzazione Dati x0 ∈ Rn , D = {e1 , e2 , . . . , en , −e1 , −e2 , . . . , −en }, θ ∈ (0, 1)

Algoritmo 8 Metodo delle coordinate

for k = 0, 1, . . . do
if ∃ i ∈ {1, . . . , n} : f (xk ± αk ei ) < f (xk ) then
xk+1 = xk ± αk ei
αk+1 = αk
else
xk+1 = xk
αk+1 = θαk
end if
end for

Assumiamo ora che L0 = {x ∈ Rn : f (x) ≤ f (x0 )} sia compatto.

Proposizione 35 Sia L0 compatto. Allora:

lim αk = 0
k→∞

Proposizione 36 (Convergenza del metodo delle coordinate) Sia f ∈ C 1 , L0

compatto. Allora:

• {xk } ammette punti di accumulazione

• ∃ almeno un punto di accumulazione stazionario.

Risultato debole di convergenza: possono esistere punti di accumulazione non stazionari.

Dimostrazione

• f (xk+1 ) ≤ f (xk ) ⇒ {xk } ⊂ L0 , compatto. Quindi {xk } ammette punti di accumu-

lazione.

•
lim αk = 0 ⇒ ∃ K1 ⊆ {0, 1, . . .} : αk+1 = θαk
k→∞

K1 è quindi l’insieme delle iterazioni in cui ho diminuito il passo αk . Considero ora

la sottosequenza di {xk }. Quindi:

∃ K2 ⊆ K1 : lim xk = x̄
k∈K2 ,k→∞

∀; k ∈ K2 : f (xk + αk ei ) ≥ f (xk ) f (xk − αk ei ) ≥ f (xk ) ∀ i = 1, . . . , n

Applico ora il teorema della media:

f (xk + αk ei ) = f (xk ) + αk ∇f (uik )T ei con uik = xk + tk αk ei tk ∈ (0, 1)

f (xk − αk ei ) = f (xk ) − αk ∇f (vki )T ei con vki = xk − zk αk ei zk ∈ (0, 1)

69
 Quindi:
αk ∇f (uik )T ei ≥ 0 αk ∇f (vki )T ei ≤ 0
Ma per lim αk = 0 e lim xk = x̄ ho che
k→∞ k∈K2 ,k→∞

lim uik = x̄ lim vki = x̄

k∈K2 ,k→∞ k∈K2 ,k→∞

Mandiamo ora al limite per k ∈ K2 , k → ∞ (tenendo conto della continuità del

gradiente).
∇f (x̄)T ei ≥ 0 ∇f (x̄)T ei ≤ 0
δf (x̄) δf (x̄)
≥0 ≤0
δxi δxi
⇓
δf (x̄)
=0 i = 1, . . . , n
δxi
Quindi x̄ è un punto stazionario.

Metodo di Hook-Jeeves
Il metodo di Hook-Jeeves è una variante del metodo delle coordinate.

2.9 Problemi di ottimizzazione vincolata

Dato un problema di ottimizzazione vincolata
min f (x) S ⊂ Rn
x∈S

con S insieme ammissibile.

Definizione 12 (Direzione ammissibile in un punto) Un vettore d ∈ Rn , d 6= 0 è

detto direzione ammissibile nel punto x̄ se
x̄ + td ∈ S ∀ t ∈ [0, t̄]

Proposizione 37 (Condizione necessaria di minimo locale) Sia x̄ ∈ S un punto di

minimo locale. Allora non può esistere una direzione ammissibile di discesa

Dimostrazione

Ovvia, segue dalla definizioni di minimo locale e direzione di discesa.

Supponiamo f continuamente differenziabile.

Proposizione 38 (Condizione necessaria di minimo locale) Sia x̄ ∈ S un punto di

minimo locale. Allora non esiste una direzione ammissibile d ∈ Rn tale che
∇f (x̄)T d < 0

70
 Dimostrazione

Supponiamo per assurdo che esista d ∈ Rn tale che

∇f (x̄)T < 0

Allora d è una direzione ammissibile e di discesa, ma x̄ non sarebbe un minimo locale.

Assurdo.

Supponiamo ora f due volte continuamente differenziabile.

Proposizione 39 (Condizione necessaria di minimo locale) Sia x̄ ∈ S un punto di

minimo locale. Allora non può esistere direzione ammissibile tale che

dT ∇2 f (x̄)d = 0 dT ∇2 f (x̄)d < 0

Dimostrazione

Come la dimostrazione della proposizione precedente.

Proposizione 40 (Direzione ammissibile in caso di convessità) Sia x̄ ∈ S. Co-

munque si prenda x ∈ S, con x 6= x̄ allora

d = x − x̄ è una direzione ammissibile in x̄

Dimostrazione

S convesso ⇒ (1 − λ)x̄ + λx ∈ S ∀ λ ∈ [0, 1].

x̄ + λ(x − x̄) ∈ S ∀ λ ∈ [0, 1]

x̄ + λd ∈ S ⇒ dè ammissibile

Proposizione 41 (Condizione necessaria minimo locale) Sia x̄ ∈ S minimo locale.

Allora:
1) Se f ∈ C 1 ⇒ ∇f (x̄)T (x − x̄) ≥ 0 ∀ x ∈ S

2) Se f ∈ C 2 ⇒ ∀ x ∈ S : ∇f (x̄)T (x − x̄) = 0 ⇒ (x − x̄)T ∇2 f (x̄)(x − x̄) ≥ 0

Dimostrazione

Sia x ∈ S con x 6= x̄. Per la proposizione precedente ho che

d = (x − x̄) è ammissibile

1) Poiché x̄ minimo locale, d non può essere di discesa quindi

∇f (x̄)T d = ∇f (x̄)T (x − x̄) ≥ 0

71
 2) Dimostrazione analoga

Proposizione 42 (Condizione necessaria e sufficiente di minimo globale) Sia

f ∈ C 1 , convessa. x̄ è un punto di minimo globale se e solo se

∇f (x̄)T (x − x̄) ≥ 0 ∀x∈S

Dimostrazione

• Condizione necessaria già dimostrata.

• Condizione sufficiente

Per la convessità di f , ∀ x ∈ S:

f (x) ≥ f (x̄) + ∇f (x̄)T (x − x̄) ≥ f (x̄)

quindi x̄ è un punto di minimo globale.

Definizione 13 (Insieme dei punti critici) Dato un problema di ottimizzazione vin-

colata su insieme convesso S si definisce l’insieme dei punti critici (o stazionari), ovvero
quei punti che soddisfano le condizioni necessarie di ottimalità del primo ordine

Λ = {x̄ ∈ S : ∇f (x̄)T (x − x̄) ≥ 0 ∀ x ∈ S}

2.9.1 Insieme S definito mediante vincoli lineari

Dato un problema di ottimizzazione vincolata su insieme S sia

S = {x ∈ Rn : Ax ≤ b}

con A matrice (mxm) e b di dimensione m. L’area delimitata risulta essere quindi un

poliedro.
Sia x̄ ∈ S. Sia poi I(x̄) l’insieme degli indici dei vincoli attivi

I(x̄) = {i ∈ {1, . . . , m} : aTi x̄ = bi }

Dalla definizione, maggiore è la cardinalità di I, minore sarà la libertà di scelta delle

direzioni ammissibili in x̄.

Proposizione 43 (Direzione ammissibile in un punto) Sia x̄ ∈ S. Una direzione

d ∈ Rn , d 6= 0 è ammissibile in x̄ se e solo se

aTi d ≤ 0 ∀ i ∈ I(x̄)

Sia ora S = {x ∈ Rn : Ax ≤ b, ux = c}. Abbiamo quindi inserito nell’insieme S anche

i vincoli di uguaglianza. Quindi

I(x̄) = {i ∈ {1, . . . , m} : aTi x = bi }

72
d è direzione ammissibile in x̄ se e solo se aTi d ≤ 0 ∀ i ∈ I(x̄), ma devo tenere di conto
anche dei vincoli di uguaglianza. Esplicito i vincoli di uguaglianza in disuguaglianza

ux = c ⇒ uTi x ≤ ci − uTi x ≤ −ci

quindi aggiungo la condizione uTi d = 0 ∀ i ∈ I(x̄).

2.9.2 Condizioni di ottimalità per problemi di vincoli di box

Dato un problema di ottimizzazione con vincoli di box del tipo

min f (x)
li ≤xi ≤ui

per i = 1, . . . , n. Per studiarlo ho due approcci

• Approccio algebrico (usando le condizioni di KKT)

• Approccio geometrico

Utilizzando le condizioni di KKT avevamo ricavato che, dato x̄ minimo locale:


≥ 0 se x̄i = li
δf (x̄) 
= = 0 se li ≤ x̄i ≤ ui
δxi
≤ 0 se x̄i = ui


Questo tipo di approccio è di tipo algebrico.

A queste stesse conclusioni possiamo giungere utilizzando i risultati sulle direzioni
ammissibili e di discesa, approccio geometrico.
Sia x ∈ S minimo locale.

• Caso I: supponiamo x̄i = li .

La direzione d = ei (vettore con solo la i-esima componente unitaria) è ammissibile.

δf (x̄)
∇f (x̄)T d = ∇f (x̄)T ei = ≥0
δxi

• Caso II: supponiamo li ≤ x̄i ≤ ui .

Sia ei che −ei sono direzioni ammissibili in x̄. Dunque
(
 δf (x̄)
∇f (x̄)T ei ≥ 0 δxi
≥0 δf (x̄)
T ⇒ δf (x̄) ⇒ =0
−∇f (x̄) ei ≥ 0 δxi
≤0 δxi

• Caso III: supponiamo x̄i = ui .

In questo caso solo −ei è direzione ammissibile in x̄.

δf (x̄)
−∇f (x̄)T ei ≥ 0 ⇒ ≤0
δxi

73
2.9.3 Condizioni di ottimalità per problemi con vincolo di sim-
plesso
Dato il problema di ottimizzazione vincolata

Pnmin f (x) x≥0

i=1 xi =1

possiamo anche in questo caso procedere per via alegebrica (usando le condizioni di KKT)
oppure in via geometrica.
Voglio dimostrare che, dato x̄ minimo locale

δf (x̄) δf (x̄)
x̄i > 0 ⇒ ≤ j = 1, . . . , n
δxi δxj

• Metodo algebrico

Utilizzo le condizioni di KKT, poichè i vincoli sono lineari.

Xn
L(x, λ, µ) = f (x) + µ( xi − 1) − λT x
i=1

Applico KKT
δL(x, λ, µ) δf (x̄)
= + µ̄ − λ̄i = 0
δxi δxi
λ̄i x̄i = 0 i = 1, . . . , n
λ̄ ≥ 0
Sia x̄i > 0 ⇒ λ̄i = 0 per la complementarietà

δf (x̄)
= −µ̄ (2.14)
δxi
con µ̄ che non dipende da i. In generale possiamo dire che

δf (x̄)
= λ̄i − µ̄ ≥ −µ̄ (2.15)
δxi

poichè λ̄i ≥ 0.
Da 2.14 e 2.15 segue che

δf (x̄) δf (x̄)
x̄i > 0 ⇒ ≤ j = 1, . . . , n
δxi δxj

• Metodo geometrico Riscrivo i vincoli

1T x = 1 aT x = b

x≥0 −x≤0
Sia quindi x̄ minimo locale, quindi ammissibile. La direzione d è ammissibile in x̄
se e solo se

74
 a. 1T d = 0
b. di ≥ 0 ∀ i : x̄i = 0

considerando I(x̄) = {i : x̄i = 0}.

Consideriamo direzioni ammissibili con 2 componenti diverse da zero.

 
0
 .. 
 . 
 +1 
 
 . 
d=  .. 
 1T d = 0
 −1 
 
 . 
 .. 
0

il vincolo (a) è quindi soddisfatto.

Supponiamo ora che x̄i > 0, associo il −1 a quella componente. La componente uni-
taria la posso associare a qualsiasi altra componente. In questo modo anche la condizione
(b) è soddisfatta e d è ammissibile. Quindi:

∇f (x̄)T d ≥ 0

δf (x̄) δf (x̄)
− ≥0
δxj δxi
δf (x̄) δf (x̄)
≥ ∀ j = 1, . . . , n
δxj δxi

2.10 Proiezione di punti su un insieme convesso

Sia S ⊆ Rn insieme convesso, chiuso e non vuoto, x ∈ Rn . Vogliamo trovare

min kx − yk
y∈S

Definizione 14 (Proiezione) Sia S ⊂ Rn convesso, chiuso e non vuoto. Sia x ∈ Rn e

k · k norma euclidea. La proiezione p(x) di x su S è la soluzione del problema

min kx − yk
y∈S

ovvero p(x) ∈ S tale che

kx − p(x)k ≤ kx − yk ∀y∈S

Proposizione 44 Sia S ⊂ Rn convesso, chiuso e non vuoto. Sia x ∈ Rn e k · k norma

euclidea. Allora:

a. Il punto y ∗ ∈ S è la proiezione di x su S, ovvero y ∗ = p(x) se e solo se (x−y ∗ )T (y −

y∗) ≤ 0 ∀ y ∈ S

75
 b. L’operazione di proiezione è continua e non espansiva, vale cioè kp(z) − p(x)k ≤
kz − xk ∀ x, y ∈ Rn
Dimostrazione
a. La proiezione p(x) è l’unica soluzione del problema
1
min kx − yk2
y∈S 2

dunque y ∗ = p(x) se e solo se

∇f (y ∗ )∗ (y − y ∗ ) ≥ 0 ∀y∈S
ossia
−(x − y ∗ )T (y − y ∗ ) ≥ 0 ∀y∈S
(x − y ∗ )T (y − y ∗ ) ≤ 0 ∀y∈S

b. Siano x, z ∈ Rn e si considerino le loro proiezioni p(x), p(z) ∈ S.

(x − p(x))T (y − p(x)) ≤ 0 ∀y∈S
(z − p(z))T (y − p(z)) ≤ 0 ∀y∈S
Sostituisco a y le due proiezioni (essendo contenute in S):
(x − p(x))T (p(z) − p(x)) ≤ 0 (z − p(z))T (p(x) − p(z)) ≤ 0
(x − p(x))T (p(z) − p(x)) + (z − p(z))T (p(x) − p(z)) ≤ 0
(x − p(x))T (p(z) − p(x)) − (z − p(z))T (p(z) − p(x)) ≤ 0
(x − p(x) − z + p(z))T (p(z) − p(x)) ≤ 0
kp(z) − p(x)k2 − (p(z) − p(x))T (z − x) ≤ 0
kp(z) − p(x)k2 ≤ (p(z) − p(x))T (z − x) ≤ kp(z) − p(x)kkz − xk
kp(z) − p(x)k ≤ kz − xk

Proposizione 45 (Punto critico) Si consideri il problema di ottimizzazione del tipo

min f (x), S ⊆ Rn convesso e sia x∗ ∈ S. Supponiamo che f ∈ C 1 in un intorno di x∗ .
x∈S
Allora:
x∗ è un punto critico per f su S ⇔ x∗ = p[x∗ − s∇f (x∗ )] s > 0

Dimostrazione

x∗ è la proiezione di x∗ − s∇f (x∗ ) su S se e solo se

(x∗ − s∇f (x∗ ) − x∗ )T (x − x∗ ) ≤ 0 ∀x∈S
ovvero
−s∇f (x∗ )T (x − x∗ ) ≤ 0
∇f (x∗ )T (x − x∗ ) ≥ 0 ∀x ∈ S
quindi x∗ è un punto critico.

76
2.10.1 Problemi con vincoli di box trattati mediante proiezioni
Si consideri un problema di ottimizzazione con vincoli di box del tipo

min f (x)
x∈S

con S = {x ∈ Rn : l ≤ x ≤ u l, u ∈ Rn }.

Sia x ∈ Rn , la proiezione y ∗ ∈ S di x su S è data da:


 li se xi < li
∗
yi = xi se li ≤ xi ≤ ui
ui se xi > ui


Quindi (x − y ∗ )T (x − y ∗ ) ≤ 0 ∀ y ∈ S.

 0 se li ≤ xi ≤ ui
xi − yi∗ = xi − li < 0 se xi < li
xi − u i > 0 se xi > ui


Dunque abbiamo che

X X
(x − y ∗ )T (x − y ∗ ) = (xi − li )T (xi − li ) + (xi − ui )T (xi − ui ) ≤ 0
i=xi <li i=ui <xi

2.11 Metodo del gradiente proiettato

Una diversa estensione del metodo del gradiente a problemi vincolati è il metodo del
gradiente proiettato, che è definito dall’iterazione

xk+1 = xk + αk (p[xk − sk ∇f (xk )] − xk )

con αk > 0 trovato con uno dei vari metodi di ricerca unidimensionale, sk > 0 e con
p[xk − sk ∇f (xk )] la proiezione del punto xk − sk ∇f (xk ).
Il metodo del gradiente proiettato può essere realizzato sia fissando sk a un valore
costante ed effettuando una ricerca unidimensionale tipo-Armijo per il calcolo di αk , sia
fissando αk a un valore costante ∈ (0, 1] ed effettuando una ricerca su sk (nel secondo
caso, al variare di sk si definisce un percorso curvilineo su S).
Verifichiamo ora che la direzione di ricerca sia una direzione di discesa, ovvero che

dk = p[xk − sk ∇f (xk )] − xk ∇f (xk )T dk < 0

Proposizione 46 Sia f ∈ C 1 su un insieme aperto contentent S e sia dk = p[xk −

sk ∇f (xk )] − xk con sk > 0 e con p[xk − sk ∇f (xk )] la proiezione del punto xk − sk ∇f (xk ).
Allora:
Se dk 6= 0 ⇒ ∇f (xk )T dk < 0
Dimostrazione

Sia x̂ = p[xk − sk ∇f (xk )]. Allora, per le proprietà di proiezione

(xk − sk ∇f (xk ) − x̂)T (x − x̂) ≤ 0 ∀x∈S

77
Ponendo x = x̂ (entrambi appartengono ad S)

−sk ∇f (xk )T (xk − x̂) + kxk − x̂k2 ≤ 0

sk ∇f (xk )T dk ≤ −kxk − x̂k2

1
∇f (xk )T dk ≤ − kxk − x̂k2 < 0
sk

2.11.1 Formalizzazione del metodo

Siano x0 ∈ S, s > 0.

Algoritmo 9 Metodo del gradiente proiettato

for k = 0, 1, . . . do
xˆk = p[xk − sk ∇f (xk )]
if xˆk = xk then
xk è un punto critico, STOP
else
dk = xˆk − xk
calcola αk con Armijo
xk+1 = xk + αk dk
end if
end for

Proposizione 47 (Convergenza globale del metodo del gradiente proiettato)

{xk } ammette punti di accumulazione ed ogni punto di accumulazione è un punto critico

Dimostrazione

{xk } ⊂ S compatto ⇒ {xk } ammette punti di accumulazione. Per Armijo abbiamo

che
lim ∇f (xk )T dk = 0 (2.16)
k→∞

Sia x un punto di accumulazione, cioè tale che ∃ K ⊂ {0, 1, . . .}:

lim xk = x (2.17)
k∈K,k→∞

Dalle proprietà precedenti ricaviamo che

1
∇f (xk )T dk ≤ − kxk − x̂k2 < 0 (2.18)
sk
L’operazione di proiezione è continua e non espansiva

kp(x) − p(z)k ≤ kx − zk (2.19)

Dai risultati di 2.16 e 2.17 otteniamo che

lim kxˆk − xk k = 0 (2.20)

k∈K,k→∞

78
Dai risultati di 2.18 e 2.19 otteniamo che

lim xˆk = x (2.21)

k∈K,k→∞

Ricordando che xˆk = p[xk − sk ∇f (xk )], per la continuità di f , abbiamo che x = p[x −
sk ∇f (x)] cioè che x è un punto critico.

2.11.2 Criticità del metodo del gradiente proiettato

Una delle difficoltà principali nell’applicazione del metodo del gradiente proiettato è quella
di poter effettuare in modo efficiente l’operazione di proiezione. Anche se i vincoli sono
lineari l’operazione di proiezione può essere laboriosa, in quanto si richiede di risolvere
un problema di programmazione quadratica. Quando la proiezione può essere effettuata
efficientemente, il metodo del gradiente proiettato ha rapidità di convergenza migliore del
metodo di Frank Wolfe.
Nel caso di vincoli semplici, alcune recenti versioni non monotone, in cui sk viene
scelto con le formule di Barzilai-Borwein e αk è calcolato con un metodo tipo-Armijo non
monotono appaiono particolarmente promettenti.

2.12 Metodo di Frank-Wolfe

Sia xk ∈ S. Procediamo con un linearizzazione della funzione obiettivo f come segue

f (x) ' f (xk ) + ∇f (xk )T (x − xk )

Questo equivale alla risoluzione di un problema di ottimizzazione del tipo

min ∇f (xk )T (x − xk )
x∈S

Poichè la funzione obiettivo è lineare ed S è compatto il problema per Weiestrass ammette

soluzione. Possiamo affermare che ∇f (xK )T (xˆk − xk ) ≤ 0.

2.12.1 Formalizzazione del metodo

Siano x0 ∈ S.

Algoritmo 10 Metodo di Frank-Wolfe

for k = 0, 1, . . . do
Calcola xˆk ∈ arg minx∈S ∇f (xk )T (x − xk )
if ∇f (xk )T (xˆk − xk ) = 0 then
xk è un punto critico, STOP
else
dk = xˆk − xk
calcola αk con Armijo
xk+1 = xk + αk dk
end if
end for

79
Proposizione 48 (Convergenza globale del metodo di Frank-Wolfe) {xk } am-
mette punti di accumulazione ed ogni punto di accumulazione è un punto critico

Dimostrazione

{xk } ⊂ S compatto ⇒ {xk } ammette punti di accumulazione. Sia x un punto di

accumulazione, cioè tale che ∃ K ⊂ {0, 1, . . .}:

lim xk = x
k∈K,k→∞

∀ iterazione k abbiamo che, per la definizione di xˆk

∇f (xk )T dk = ∇f (xk )T (xˆk − xk ) ≤ ∇f (xk )T (x − xk )

Preso ora un qualsiasi x ∈ S e mandando al limite per k ∈ K, k → ∞ otteniamo che

∇f (x)T (x − x) ≥ 0 ∀x∈S

Dunque x è un punto critico.

80