Ottimizzazione Continua

UNIVERSITÀ di ROMA “LA SAPIENZA”
Corso di Laurea Magistrale in Ingegneria

Gestionale
Anno Accademico 2017 –2018
Appunti dalle lezioni di
OTTIMIZZAZIONE CONTINUA
Stefano Lucidi
Dipartimento di Ingegneria Informatica Automatica e Gestionale “Antonio

Ruberti”
Università di Roma “La Sapienza”
versione preliminare
2
3
Indice
1 Problemi di Ottimizzazione Nonlineare 4

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Condizioni di esistenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Condizioni di ottimalità locale . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Condizioni di ottimalità per problemi nonvincolati . . . . . . . . 9
1.3.2 Condizioni di ottimalità per problemi vincolati . . . . . . . . . . 9
1.4 Problemi particolari di Ottimizzazione . . . . . . . . . . . . . . . . . . . 11
1.4.1 Problemi di programmazione convessa . . . . . . . . . . . . . . . 11
1.4.2 Problemi di programmazione concava . . . . . . . . . . . . . . . 14
1.5 Condizioni di ottimalità globale . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Condizione di ottimalità necessaria e sufficiente . . . . . . . . . . 15
1.5.2 Involucro convesso di una funzione . . . . . . . . . . . . . . . . . 17
1.5.3 Caratterizzazione dei minimi globali unici . . . . . . . . . . . . . 21
1.6 Proprietà generali dei metodi di ottimizzazione globale . . . . . . . . . . 23
1.6.1 Definizione e funzione di perturbazione . . . . . . . . . . . . . . . 24
1.6.2 Proprietà di convergenza degli algoritmi di ottimizzazione globale
deterministici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.6.3 Proprietà di convergenza degli algoritmi di ottimizzazione globale
probabilistici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Metodi di ottimizzazione locale 29

2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Convergenza globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Rapidità di convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Metodi di ottimizzazione non vincolata . . . . . . . . . . . . . . . . . . . 33
2.4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.2 Algoritmi di ricerca unidimensionale . . . . . . . . . . . . . . . . 37
2.4.3 Metodo del gradiente . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4.4 Metodo di Newton . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.5 Metodi Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4.6 Metodo del gradiente coniugato . . . . . . . . . . . . . . . . . . . 59
2.4.7 Metodi di Newton troncato . . . . . . . . . . . . . . . . . . . . . 63
2.4.8 Metodi che non usano le derivate . . . . . . . . . . . . . . . . . . 64
2.5 Metodi di ottimizzazione vincolata . . . . . . . . . . . . . . . . . . . . . 68
1
2.5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.5.2 Metodi di programmazione quadratica ricorsiva . . . . . . . . . . 69
2.5.3 Funzioni di penalità . . . . . . . . . . . . . . . . . . . . . . . . . 72
3 Metodi di ottimizzazione globale 83

3.1 Metodi Probabilistici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.1.1 Algoritmi che utilizzano punti scelti a caso su D. . . . . . . . . . 84
3.1.2 Metodi di tipo “simulated annealing” . . . . . . . . . . . . . . . 88
3.1.3 Metodi che usano “popolazioni” di punti . . . . . . . . . . . . . . 93
3.2 Metodi che utilizzano partizioni dell’insieme ammissibile . . . . . . . . . 97
3.2.1 Schema generale di un metodo che usa partizioni dell’insieme
ammissibile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.2.2 Scelta dei sottoinsiemi da partizionare: sottoinsiemi di dimensio-
ni più grandi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2.3 Scelta dei sottoinsiemi da partizionare: sottoinsiemi più promet-
tenti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.2.4 Algoritmo di Partizione con minimizzazioni locali. . . . . . . . . 112
3.2.5 Metodi che non utilizzano stime della costante di Lipschitz della
funzione obiettivo . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.3 Funzioni di tipo “Filled” . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.3.1 Funzioni filled di tipo 1 . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.2 Funzioni filled di tipo 2. . . . . . . . . . . . . . . . . . . . . . . . 127
2
Notazioni
Rn spazio dei vettori x a n componenti reali;
x ∈ Rn è inteso come vettore colonna;
ei ∈ Rn è il versore unitario i-esimo,

cioè il vettore che ha tutte componenti nulle escluso l’i-esima
che è uguale uno;
R+ insieme dei reali non negativi;
xT vettore riga ottenuto come trasposto di x;
(x)i oppure xi indicano la i-ma componente di x (quindi xi ∈ R);
xk indica il k-mo vettore di una successione (quindi xk ∈ Rn );
{xk } successione formata dai vettori xk ;
{xk }K sottosuccessione definita dall’ insieme (infinito) di indici K;
kxk norma di x; in assenza di altre indicazioni, kxk è la norma euclidea,

n
!1/2
x2i
X
ossia kxk = , dove xi ∈ R sono le componenti di x;
i=1
B(x⋆ ; ρ) sfera aperta di raggio ρ > 0 con centro x⋆ ∈ Rn , ossia:
B(x⋆ ; ρ) = {x ∈ Rn : kx − x⋆ k < ρ};
∇f (x) gradiente di una funzione f : Rn → R calcolato in x; ∇f (x) è inteso

∂f (x)
come vettore colonna con componenti , j = 1, . . . , n;
∂xj
∇2 f (x) matrice Hessiana (n × n) di una funzione f : Rn → R calcolata in x,
∂ 2 f (x)
con componenti , per i, j = 1, . . . , n.
∂xi ∂xj
Int(A) interno dell’insieme A ⊆ Rn .
∂(A) frontiera dell’insieme A ⊆ Rn .
A\B l’insieme definito da {x ∈ A : x ∈

/ B}.
3
Capitolo 1
Problemi di Ottimizzazione
Nonlineare
Molti problemi che nascono nell’ambito dell’Ingegneria, dell’Economia e delle Scienze

esatte e naturali possono essere rappresentati come problemi di ottimizzazione nonlinea-
re. Questo motiva il sempre maggiore interesse dal punto di vista tecnico e scientifico
verso lo studio e lo sviluppo di metodi che siano in grado di affrontare e risolvere questa
classe di difficili problemi matematici.
1.1 Introduzione
Un problema di ottimizzazione consiste nel cercare di determinare dei punti apparte-
nenti ad un insieme F in cui una funzione f assume valori più bassi possibile. Tale
problema viene rappresentato nella forma:
min f (x) (1.1)

x ∈ F,
dove
- la funzione f : F → R è detta funzione obiettivo;
- l’insieme F ⊆ Rn è detto insieme ammissibile.
Per caratterizzare i possibili punti di soluzione del precedente problema di minimizza-

zione si possono introdurre le seguenti definizioni.
Definizione 1.1.1 Un punto x⋆ ∈ F si dice punto di minimo globale di f su F se
f (x⋆ ) ≤ f (x), per ogni x ∈ F.
Definizione 1.1.2 Un punto x⋆ ∈ F si dice punto di minimo globale stretto di f su

F se
f (x⋆ ) < f (x), per ogni x ∈ F, x 6= x⋆ .
4
Definizione 1.1.3 Un punto x⋆ ∈ F si dice punto di minimo locale di f su F se esiste
un intorno B(x⋆ ; ρ), con ρ > 0 tale che
f (x⋆ ) ≤ f (x), per ogni x ∈ F ∩ B(x⋆ ; ρ).
Definizione 1.1.4 Un punto x⋆ ∈ F si dice punto di minimo locale stretto di f su F

se esiste un intorno B(x⋆ ; ρ), con ρ > 0 tale che
f (x⋆ ) < f (x), per ogni x ∈ F ∩ B(x⋆ ; ρ), x 6= x⋆ .
Si può notare che, se si ha un problema di massimizzazione cioè se si deve trovare un

punto in cui la funzione f assume valore più alto possibile, ci si può sempre ricondurre
a un problema di minimo, cambiando di segno la funzione obiettivo. Infatti un punto
di massimo del problema
max f (x)
x∈F
è un punto x⋆ ∈ F che, per definizione, soddisfa la seguente proprietà:
f (x⋆ ) ≥ f (x), per ogni x ∈ F,
che è equivalente a:
−f (x⋆ ) ≤ −f (x), per ogni x ∈ F,
da cui segue che x⋆ è anche un punto di minimo del problema
min −f (x)
x∈F
e risulta:
max f (x) = − min(−f (x)).
x∈F x∈F
Perciò non si ha nessuna perdita di generalità a studiare ed affrontare solamente

problemi di minimizzazione o, viceversa, solamente problemi di massimizzazione.
La natura del Problema (1.1) e, quindi, la sua difficoltà di risoluzione dipendono, ov-
viamente, dalle caratteristiche della funzione obiettivo e dalla struttura dell’insieme
ammissibile. Usualmente un problema di ottimizzazione viene caratterizzato dal fatto
che si abbia completa libertà o meno nella scelta del vettore x, infatti:
- è detto problema di minimizzazione non vincolata se F = Rn , cioè sel’insieme

ammissibile F coincide con tutto lo spazio Rn , cioè:
min f (x) (1.2)

x∈ Rn .
- viene detto, invece, problema di minimizzazione vincolata un problema in cui

F ⊂ Rn .
5
Tuttavia, può essere considerato come un problema di minimizzazione non vincolato
anche un qualsiasi problema in cui l’insieme ammissibile F è un insieme aperto. In-
fatti, come nel caso in cui F = Rn , i punti di minimo del problema possono essere
caratterizzati esclusivamente dall’andamento della funzione obiettivo in un intorno del
punto e non dal fatto che ci siano dei vincoli sulle variabili del problema. Perciò, per i
problemi in cui l’insieme ammissibile è un insieme aperto, si adattano facilmente tutti
i risultati e metodi proposti per il caso in cui F = Rn .
Tra i problemi vincolati in cui F è un insieme chiuso, la classe più comunemente
considerata è quella in cui F è descritto attraverso un insieme finito di vincoli di
eguaglianza e diseguaglianza:
F = {x ∈ Rn : g(x) ≤ 0, h(x) = 0},
in cui g : Rn → Rm e h : Rn → Rp sono vettori di funzioni assegnate. Il problema di

ottimo si può indicare, in tal caso, ponendo:
min f (x) (1.3)

g(x) ≤ 0
h(x) = 0.
Nei paragrafi successivi, dopo aver richiamato le condizioni di esistenza delle solu-
zioni del Problema 1.1, vengono descritte alcune condizioni che cercano di dare delle
caratterizzazioni di tali soluzioni.
1.2 Condizioni di esistenza

Nel cercare di risolvere il Problema (1.1) la prima difficoltà da affrontare è quella
di capire se è ben posto, nel senso che potrebbe non esistere un punto in F in cui
la funzione f (x) assume valore più piccolo. Infatti, si potrebbe presentare una delle
seguenti situazioni:
- l’insieme ammissibile F potrebbe essere vuoto;
- l’insieme ammissibile F potrebbe essere non vuoto ma la funzione obiettivo

potrebbe essere illimitata inferiormente su F ossia inf x∈F f (x) = −∞;
- l’insieme ammissibile F potrebbe essere non vuoto e la funzione obiettivo potreb-

be essere limitata inferiormente su F ma, anche in questo caso, potrebbero non
esistere punti di minimo globale di f su F;
Una condizione sufficiente (ma non necessaria) per l’esistenza di un punto di minimo
globale di un problema di ottimizzazione è quella espressa dalla proposizione seguente,
che segue dal ben noto Teorema di Weierstrass.
Proposizione 1.2.1 Sia F ⊂ Rn un insieme non vuoto e compatto. Sia f una

funzione continua su F. Allora esiste un punto di minimo globale di f in F.
6
La precedente proposizione si applica solamente alla classe dei problemi vincolati in cui
l’insieme ammissibile è compatto. Per poter stabilire risultati di esistenza per problemi
con insiemi ammissibili non compatti (in particolare nel caso in cui F = Rn ) è necessario
cercare di caratterizzare un qualche sottoinsieme di F contenente le soluzioni ottime
del problema.
A questo fine si introduce la definizione seguente.
Definizione 1.2.2 Sia F ⊆ Rn e sia f : F → R; si definisce insieme di livello di f su

F ogni insieme non vuoto del tipo:
L(α) := {x ∈ F : f (x) ≤ α} ,
in cui α ∈ R.
In particolare, se x0 ∈ F, indichiamo con L0 l’insieme di livello L (f (x0 )), ossia:
L0 := {x ∈ F : f (x) ≤ f (x0 )} . (1.4)
A questo punto, si può enunciare il risultato seguente che stabilisce una condizione
sufficiente per l’esistenza di soluzioni globali di un problema di ottimizzazione facendo
riferimento alla struttura degli insiemi di livello della funzione.
Proposizione 1.2.3 Sia F ⊆ Rn e sia f una funzione continua su F. Supponiamo

che esista un insieme di livello di f su F che sia non vuoto e compatto. Allora esiste
un punto di minimo globale di f in F.
Nel caso generale, stabilire l’esistenza di un insieme di livello compatto può essere diffi-
cile. Tuttavia, in molti casi, si possono ottenere delle semplici condizioni per assicurare
che tutti gli insiemi di livello siano compatti. In particolare la proposizione successi-
va fornisce una condizione necessaria e sufficiente (nota come condizione di coercività)
perchè gli insiemi di livello di f su F siano compatti.
Proposizione 1.2.4 . Sia F ⊆ Rn e sia f una funzione continua definita su F. Allora

tutti gli insiemi di livello L(α) = {x ∈ F : f (x) ≤ α} di f su F sono compatti se e solo
se le due seguenti condizioni sono soddisfatte:
(i) se {xk } è una sequenza di punti xk ∈ F tale che limk→∞ kxk k = ∞ allora segue
che
lim f (xk ) = ∞;
k→∞
(ii) se {xk } è una sequenza di punti xk ∈ F tale che limk→∞ xk = x̂ ∈

/ F, allora segue
che
lim f (xk ) = ∞.
k→∞
7
Le Proposizioni 1.2.3 and 1.2.4 forniscono delle condizioni sufficienti per l’esistenza delle
soluzioni di un problema di minimizzazione in cui l’insieme ammissibile F è un insieme
aperto. In particolare si possono considerare due casi particolari che corrispondono alle
situazioni di maggiore interesse.
Il primo dei due casi è quello in cui F = Rn .
Proposizione 1.2.5 Sia f una funzione continua su Rn e si assuma che f sia coerciva
su Rn , ossia che
lim f (xk ) = ∞,
k→∞
per ogni successione {xk }, con xk ∈ Rn , tale che limk→∞ kxk k = ∞. Allora si ha:
(i) tutti gli insiemi di livello L(α) = {x ∈ Rn : f (x) ≤ α} sono compatti;
(ii) esiste un minimo globale di f su Rn .
Il secondo caso è quello in cui F è un insieme limitato e aperto tale che f tende
all’infinito al tendere verso la frontiera di F. Per questo caso è possibile stabilire la
seguente condizione la cui prova è simile a quella della precedente proposizione.
Proposizione 1.2.6 Sia F un sottoinsieme limitato e aperto di Rn e sia f : F → R

una funzione continua. Si supponga che
lim f (xk ) = ∞,
k→∞
per ogni successione {xk }, con xk ∈ F, tale che limk→∞ xk = x̂ ∈ ∂F. Allora si ha:
(i) tutti gli insiemi di livello L(α) = {x ∈ F : f (x) ≤ α} sono compatti;
(ii) esiste un minimo globale x∗ ∈ F di f su F.
1.3 Condizioni di ottimalità locale

Purtroppo tutte le condizione di ottimalità globali proposte in letteratura hanno un
limitato interesse applicativo. Infatti, come sarà visto in seguito, esse sono legate al
comportamento globale della funzione obiettivo sull’insieme ammissibile e, perciò, sono
descritte necessariamente da condizioni complesse dal punto di vista computazionale.
Più utili dal punto di vista applicativo sono quelle che vengono dette condizioni di
ottimalità locale. Queste non sono altro che delle condizioni necessarie (ma, in generale,
non sufficienti) perchè un punto assegnato sia un punto di minimo locale (globale) di
un problema di minimizzazione. Quindi, dal punto di vista teorico, non danno una
caratterizzazione soddisfacente dei minimi locali (globali) del Problema 1.1 ma giocano
un importante ruolo nella definizione di algoritmi di minimizzazione.
8
1.3.1 Condizioni di ottimalità per problemi nonvincolati
Si consideri per primo il caso di un problema di ottimizzazione non vicolata. Le due

proposizioni successive descrivono le ben note condizioni necessarie di ottimalità per
problemi di ottimizzazione non vincolati.
Proposizione 1.3.1 (Condizione necessaria del primo ordine) Sia f continua-

mente differenziabile e sia x̄ ∈ Rn un punto di minimo locale (globale) del Problema
(1.2). Allora
∇f (x̄) = 0. (1.5)
Proposizione 1.3.2 (Condizioni necessarie del secondo ordine) Sia f due volte
continuamente differenziabile e sia x̄ ∈ Rn un punto di minimo locale (globale) del
Problema (1.2). Allora
∇f (x̄) = 0, (1.6)
T 2 n
d ∇ f (x̄)d ≥ 0, per ogni d∈R . (1.7)
In modo da caratterizzare i punti che soddisfano le precedenti condizioni necessarie del

primo ordine si introduce la seguente definizione.
Definizione 1.3.3 Sia f continuamente differenziabile su Rn , un punto x̄ ∈ Rn si dice
punto di punto stazionario del Problema (1.2) se
∇f (x̄) = 0
Perciò, da quanto detto, si ha che un punto di minimo locale (globale) del Problema
(1.2) è necessariamente un punto stazionario del Problema (1.2).
1.3.2 Condizioni di ottimalità per problemi vincolati
Passando ai problemi di ottimizzazione vincolata vale la pena ricordare che, se l’insie-

me ammissibile F è un insieme aperto, continuano a valere le precenti condizioni di
ottimalità e la precedente definizione di punto stazionario (basta cambiare Rn con F).
Mentre la situazione è abbastanza più complessa nel caso in cui l’insieme ammissibile
F non è un insieme aperto. Infatti in questo caso la presenza di un minimimo loca-
le (globale) può nascere dall’azione combinata della funzione obiettivo e dei vincoli e
questo naturalmente si riflette nelle condizioni di ottimalità.
Associato al Problema 1.3 si può introdurre la seguente definizione.
Definizione 1.3.4 Si definisce funzione Lagrangiana associata al Problema (1.3) la
funzione L : Rn × Rm × Rq → R data da:
L(x, λ, µ) := f (x) + λT g(x) + µT h(x),
con λ ∈ Rm e µ ∈ Rq .
9
Le prossime proposizioni descrivono le due condizioni necessarie di ottimalità maggior-
maente usate nell’ambito di problemi di ottimizzazione vincolati non lineari. Entrambe
queste condizioni di ottimalità possono essere stabilite solamente nel caso che l’insieme
ammissibile sia “sufficientemente regolare”. Un modo per assicurare questa regolarità
è quello di richiedere la seguente assunzione.
Assunzione 1.3.1 In ogni punto x ∈ F i gradienti ∇gi (x), i ∈ {i′ : gi′ (x) = 0}, e
∇hj (x), j = 1, . . . , q, sono linearmente indipendenti.
Utilizzando la precedente assunzione si possono enuciare le seguenti proposizioni.
Proposizione 1.3.5 (Condizioni di Kuhn-Tucker) Siano le funzioni f , gi , i =
1, . . . , m, hj , j = 1, . . . , q continuamente differenziabile e si supponga che Assunzione
1.3.1 sia verificata. Se x̄ ∈ Rn è un punto di minimo locale (globale) del Problema (1.3)
allora esistono dei vettori λ̄ ∈ Rm e µ̄ ∈ Rq tali che:
∇x L(x̄, λ̄, µ̄) = 0,
g(x̄) ≤ 0, h(x̄) = 0, (1.8)
λ̄i ≥ 0, gi (x̄)λ̄i = 0, i = 1, . . . , m.
Proposizione 1.3.6 (Condizioni di Kuhn-Tucker del secondo ordine) Siano le

funzioni f , gi , i = 1, . . . , m, hj , j = 1, . . . , q due volte continuamente differenziabile e
si supponga che Assunzione 1.3.1 sia verificata. Se x̄ ∈ Rn è un punto di minimo locale
(globale) del Problema (1.3) allora esistono dei vettori λ̄ ∈ Rm e µ̄ ∈ Rq tali che:
∇x L(x̄, λ̄, µ̄) = 0,
g(x̄) ≤ 0, h(x̄) = 0, (1.9)
λ̄i ≥ 0, gi (x̄)λ̄i = 0, i = 1, . . . , m.
z T ∇2 L(x̄, λ̄, µ̄)z ≥ 0, ∀z ∈ Rn , z 6= 0 : (1.10)

T ′
∇gi (x̄) z = 0, ∀i ∈ {i : gi′ (x̄) = 0},
T
∇hj (x̄) z = 0, ∀j = 1, . . . , q.
Analogamente al caso non vincolato si caratterizzano i punti che soddisfano le prece-

denti condizioni necessarie del primo ordine attraverso la seguente definizione.
Definizione 1.3.7 Siano le funzioni f , gi , i = 1, . . . , m, hj , j = 1, . . . , q continua-
mente differenziabile, il punto x̄ ∈ Rn è detto punto di Kuhn-Tucker del Problema di
(1.3) se esistono dei vettori λ̄ ∈ Rm e µ̄ ∈ Rq , detti moltiplicatori di Kuhn-Tucker,tali
che:
∇x L(x̄, λ̄, µ̄) = 0,
g(x̄) ≤ 0, h(x̄) = 0,
λ̄i ≥ 0, gi (x̄)λ̄i = 0, i = 1, . . . , m.
Perciò, se l’Assunzione 1.3.1 è verificata, ogni punto di minimo locale (globale) del
Problema (1.3) è necessariamente un punto di Kuhn-Tucker del Problema (1.3).
10
1.4 Problemi particolari di Ottimizzazione
In questa sezione vengono descritti alcuni esempi di classi di problemi di ottimizzazio-

ne le cui strutture particolari permettono di caratterizzare meglio, dal punto di vista
matematico, i loro punti di minimo globale.
1.4.1 Problemi di programmazione convessa

Una classe importante dal punto di vista applicativo è quella dei problemi di pro-
gammazione convessa. Prima di descrivere questa particolare classe di problemi di
minimizzazione, è necessario richiamare le seguenti defizioni.
Definizione 1.4.1 Dato un insieme C ⊆ Rn , si dice che C è un insieme convesso se

comunque scelti due punti x, y ∈ C e comunque scelto un scalare α ∈ [0, 1] si ha che
αx + (1 − α)y ∈ C.
Definizione 1.4.2 Sia C ⊆ Rn un insieme convesso e sia f : C → R. Si dice che f

è convessa su C se comunque scelti due punti x, y ∈ C e comunque scelto un scalare
α ∈ [0, 1] si ha che
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y);
si dice che f è stettamente convessa su C se comunque scelti due punti x, y ∈ C, con

x 6= y, e comunque scelto un scalare α ∈ (0, 1) si ha che
f (αx + (1 − α)y) < αf (x) + (1 − α)f (y).
Definizione 1.4.3 Sia C ⊆ Rn un insieme convesso e sia f : C → R. Si dice che f

è concava su C se comunque scelti due punti x, y ∈ C e comunque scelto un scalare
α ∈ [0, 1] si ha che
f (αx + (1 − α)y) ≥ αf (x) + (1 − α)f (y);
si dice che f è stettamente concava su C se comunque scelti due punti x, y ∈ C, con

x 6= y, e comunque scelto un scalare α ∈ (0, 1) si ha che
f (αx + (1 − α)y) > αf (x) + (1 − α)f (y).
La seguente proposizione richiama alcune delle proprietà delle funzioni convesse.
Proposizione 1.4.4 Sia C ⊆ Rn un insieme convesso aperto. Se f è continuamente

differenziabile su C allora:
(i) f è convessa su C se e solamente se per ogni x, y ∈ C si ha:
f (y) − f (x) ≥ ∇f (x)T (y − x);
11
(ii) f è strettamente convessa su C se e solamente se per ogni x, y ∈ C, con x 6= y,
si ha:
f (y) − f (x) > ∇f (x)T (y − x).
Se f è due volte continuamente differenziabile su C allora:
(iii) f è convessa su C se e solamente se per ogni x ∈ C si ha:
dT ∇2 f (x)d ≥ 0 per ogni d ∈ Rn ;
(iv) f è strettamente convessa su C se per ogni x ∈ C si ha:
dT ∇2 f (x)d > 0 per ogni d ∈ Rn , d 6= 0.
Le Proprietà (i) e (ii) sono particolarmente significative, come si vedrà in seguito, per
lo studio dei punti di minimo di questa classe particolare di funzioni. Le Proprietà (iii)
e (iv) sono delle utili condizioni per identificare la convessità di una funzione.
Analogamente al caso di funzioni convesse si può stabilire la seguente proposizione che
fornisce un aiuto a riconoscere le funzioni concave.
Proposizione 1.4.5 Sia C ⊆ Rn un insieme convesso aperto. Se f continuamente

differenziabile su C allora:
(i) f è concava su C se e solamente se per ogni x, y ∈ C si ha:
f (y) − f (x) ≤ ∇f (x)T (y − x);
(ii) f è strettamente concava su C se e solamente se per ogni x, y ∈ C, con x 6= y, si

ha:
f (y) − f (x) < ∇f (x)T (y − x).
Se f è due volte continuamente differenziabile su C allora:
(iii) f è concava su C se e solamente se per ogni x ∈ C si ha:
dT ∇2 f (x)d ≤ 0 per ogni d ∈ Rn ;
(iv) f è strettamente concava su C se per ogni x ∈ C si ha:
dT ∇2 f (x)d < 0 per ogni d ∈ Rn , d 6= 0.
A questo punto si può introdurre la classe dei problema di programmazion convessa.
12
Definizione 1.4.6 Si definisce problema di programmazione convessa un problema di
minimizzazione del tipo:
min f (x)
x∈F
in cui F è un insieme convesso e f è una funzione convessa su F o, equivalentemente,

un problema di massimizzazione del tipo:
max f (x)
x∈F
in cui F è un insieme convesso e f è una funzione concava su F.
Un esempio di classe si problemi convessi è l’insieme dei problemi di programmazione

lineare.
I problemi di programmazione convessa godono di importanti proprietà descritte nei
teoremi seguenti. Il primo dei quali mostra che nei problemi convessi non ci possono
essere dei minimi locali che non sono minimi globali.
Proposizione 1.4.7 (Coincidenza tra minimi locali e minimi globali) Sia F ⊆

Rn un insieme convesso e f una funzione convessa (strettamente convessa) su F. Allora
ogni punto (un punto) di minimo locale di f su F è anche (l’unico) punto di minimo
globale.
Il secondo risultato riguarda la minimizzazione di una funzione convessa su tutto Rn e

stabilisce la coincidenza tra punti stazionari e minimi globali.
Proposizione 1.4.8 (Coincidenza tra punti stazionari e minimi globali) Sia f

una funzione (strettamente) convessa e continuamente differenziabile su Rn . Allora un
punto stazionario di f su Rn è un minimo globale (l’unico minimo globale) di f su Rn .
L’ultimo risultato considera la coincidenza tra punti di Kuhn-Tucker e minimi globali.
Proposizione 1.4.9 (Coincidenza tra punti di Kuhn-Tucker e minimi globali)

Sia dato il seguente problema vincolato
min f (x)
gi (x) ≤ 0, i = 1, . . . , m (1.11)
aTj x − bj = 0 j = 1, . . . , q.
e sia f una funzione (strettamente) convessa e continuamente differenziabile su Rn ,

siano gi , i = 1, . . . , m, delle funzioni convesse e continuamente differenziabili su Rn .
Allora un punto di Kuhn-Tucker del Problema 1.11 è un minimo globale (l’unico minimo
globale) del Problema 1.11.
13
1.4.2 Problemi di programmazione concava
Un’altra classe di problemi di minimizzazione particolarmente importante è quella dei
problemi di programmazione concava. Infatti questi particolari problemi di ottimizza-
zione sono in grado di modellizzare numerosi problemi che nascono nel campo dell’e-
conomia. Inoltre è possibile dimostrare che, sotto opportune ipotesi, molti problemi
di ottimizzazione combinatoria possono essere trasformati in problemi (continui) di
programmazione concava.
Si definisce problema di programmazione concava un problema di minimizzazione del
tipo:
min f (x)
x∈F
in cui F è un insieme convesso e f è una funzione concava su F o, equivalentemente,
un problema di massimizzazione del tipo:
max f (x)
x∈F
in cui F è un insieme convesso e f è una funzione convessa su F.

È da notare che i problemi di programmazione lineare sono anche problemi di program-
mazione convessa.
I problemi di programmazione concava sono molto più “difficili” di quelli convessi. La
difficoltà principale risiede nel fatto che i problemi concavi presentano normalmente
molti punti di minimo locale che non sono punti di minimo globale.
Tuttavia, la particolare struttura della funzione obiettivo di questi problemi fornisce
comunque informazioni importanti circa i suoi punti di minimo globale. Infatti la
seguente proposizione dimostra che le soluzioni ottime dei problemi di programmazione
concava, ove esistano, appartengono alla frontiera dell’insieme ammissibile.
Teorema 1.4.10 (Assenza di soluzioni ottime interne) Sia F ⊆ Rn un insieme

convesso e sia f una funzione concava e non costante su F. Allora, se esiste un punto
di minimo globale di f su F, questo appartiene alla frontiera di F.
Nel caso di minimizzazione di funzioni concave con vincoli lineari, vale un risulta-
to simile al Teorema Fondamentale della Programmazione Lineare. Infatti ripetendo
argomenti simili a quelli utilizzati nel Teorema Fondamentale della Programmazione
Lineare si ha il seguente teorema.
Teorema 1.4.11 (Soluzione ottima su un vertice) Sia F ⊆ Rn un poliedro che

ha almeno un vertice e sia f una funzione concava su F che ammetta minimi globali
su F. Allora, esiste un punto di minimo globale di f su F che coincide con un vertice
del poliedro F.
14
Questo risultato mostra che, come nel caso dei problemi programmazione lineare, la
ricerca di un minimo globale di una funzione concava su un simplesso si può ridurre al
problema di minimizzare la funzione sull’insieme dei vertici del poliedro F. Tuttavia,
la nonlinearità della funzione obiettivo non permette di definire un algoritmo, analogo
al Metodo del Simplesso per la Programmazione Lineare, che sia in grado di identificare
efficientemente i vertici più promettenti trascurando gia altri.
1.5 Condizioni di ottimalità globale

Nel seguito riportiamo alcuni esempi di tali caratterizzazioni matematiche dei minimi
globali. Tuttavia, ogni trattazione teorica riguante i problemi di ottimizzazione glo-
bale, può essere effettuata se l’insieme ammissibile F è sufficientemente regolare. Per
assicurare questa regolarità viene spesso richiesta la seguente assunzione.
Assunzione 1.5.1 L’insieme ammissibile F ⊂ Rn è un insieme non vuoto e compatto

ed è tale che:
F = Cl(Int(F)), (1.12)
dove Cl() indica la chiusura di un insieme e Int() l’interno di un insieme.
Spesso, in letteratura, insiemi che soddisfano all’Assunzione 1.5.1 vengono detti insiemi
robusti.
Si può notare che la relazione (1.12) implica che un insieme robusto F gode della
seguente proprietà:
comunque scelti x̄ ∈ F e ε̄ > 0 esiste un punto x̃ tale che x̃ ∈ B(x̄, ε̄) ∩ Int(F).
Cioè in ogni intorno di un punto appartenente ad un insieme robusto esiste un punto
interno all’insieme stesso. Questo, per esempio, esclude che l’insieme contenga punti
isolati.
Nella figura (1.1) è riportato un esempio di un insieme che non soddisfa la relazione
(1.12).
1.5.1 Condizione di ottimalità necessaria e sufficiente

Le condizioni di ottimalità globale devono essere in grado di identificare i minimi globali
distinguendoli dai minimi locali e dagli altri punti stazionari. Perciò devono tener conto
del comportamento globale della funzione obiettivo.
Una delle prime e delle più note condizioni di ottimalità globale è la seguente.
Teorema 1.5.1 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1 e sia f una
funzione continua su F. Un punto x⋆ ∈ F è un minimo globale di f su F se e solamente
se l’insieme di livello L∗ := {x ∈ F : f (x) < f (x⋆ )} ha misura (di Lebesgue) nulla, cioè
meas(L∗ ) = 0.
15
F =
Int (F ) = F ≠ Cl ( Int ( F ))
Cl ( Int ( F )) =
Figura 1.1: Esempio di un insieme che non è robusto.
Prova. Si assuma, per assundo, che meas(L∗ ) = 0 e che x⋆ non sia un minimo globale
di f su F. Se x⋆ non fosse un minimo globale esisterebbe un punto x̄ ∈ F tale che
f (x̄) < f (x⋆ ).
Per la continuità della funzione obiettivo seguirebbe che
f (x) < f (x⋆ ),
per tutti i punti x appartenenti ad un intorno sufficientemente piccolo di x̄. Utilizzan-

do l’Assunzione 1.5.1, in questo intorno di x̄ ci sarebbe un punto interno all’insieme
ammissibile, quindi esisterebbe un punto x̃ ∈ Int(F) tale che:
f (x̃) < f (x⋆ ).
Perciò esisterebbe un ε̃ > 0 tale che l’intorno B(x̃, ε̃) di x̃ sarebbe strettamente conte-
nuto nell’insieme ammissibile F e che, per ogni x′ ∈ B(x̃, ε̃), si avrebbe:
f (x′ ) < f (x⋆ ).
Quindi, ricordando la definizione di L∗ , si otterrebbe
B(x̃, ε̃) ⊂ L∗ ,
16
da cui si avrebbe l’assurdo
0 = meas(L∗ ) > meas(B(x̃, ε̃)) > 0.
Se, invece, x⋆ fosse un minimo globale di f su F e si avesse che
meas(L∗ ) > 0
allora l’insieme L∗ non sarebbe vuoto. Quindi, esisterebbe un x̃ ∈ L∗ , cioè un punto

x̃ ∈ F tale che:
f (x̃) < f (x⋆ )
e, quindi, x⋆ non sarebbe un minimo globale di f su F.
Nella figura (1.2) sono riportati due esempi di insiemi L∗ : il primo esempio si riferisce
al caso in cui il punto x∗ non è un minimo globale, il secondo invece descrive il caso in
cui il punto x∗ è il minimo globale della funzione.
Il precedende risultato è significativo dal punto di vista teorico. Infatti, descrivendo una
condizione necessaria e sufficiente perchè un punto sia un minimo globale, caraterizza
perfettamente le soluzioni del Problema 1.1. Tuttavia esso ha un utilizzo limitato dal
punto di vista applicativo. Infatti la determinazione della misura di un insieme n
dimensionale ha un costo computazionale proibitivo e, quindi, il precedente teorema
fornisce uno scarso aiuto dal punto vista metodologico.
1.5.2 Involucro convesso di una funzione
Una recente condizione di ottimalità si poggia sulla definizione di involucro convesso di

una funzione.
Definizione 1.5.2 (Involucro convesso di una funzione) Sia F ⊆ Rn un insieme

convesso e sia f una funzione continua su F, si definisce involucro convesso di f (x) su
F una funzione co(f (x)) tale che:
i) co(f (x)) è convessa su F;
ii) co(f (x)) ≤ f (x) per ogni x ∈ F;
iii) se f˜(x) è una funzione convessa su F tale che f˜(x) ≤ f (x) per ogni x ∈ F, allora
si ha che f˜(x) ≤ co(f (x)) per ogni x ∈ F.
Dalla precedente definizione segue che la funzione co(f (x)) è la migliore sottostima
convessa della funzione f (x).
La funzione co(f (x)) presenta interessanti proprietà alcune di queste descritte nella
seguente proposizione.
17
f ( x)
f (x )
*
x*
{ x ∈ F : f (x ) < }
f ( x* ) ≠ φ
f ( x)
f (x ) *
x*
{ x ∈ F : f (x ) < }
f ( x* ) = φ
Figura 1.2: Insiemi L∗ nel caso in cui x∗ non è minimo globale e nel caso che x∗ è minimo
globale.
18
Proposizione 1.5.3 Sia F ⊂ Rn un insieme convesso non vuoto e compatto, sia f una
funzione continua su F. Allora ogni minimo globale di f (x) su F è anche un minimo
globale di co(f (x)) su F ed il valore ottimo di f (x) coincide con quello di co(f (x)).
Prova (la prova non fa parte del programma di esame). Sia x⋆ ∈ F un minimo
globale di f (x) su F. Per la proprietà ii) della Definizione 1.5.2 si ha:
co(f (x⋆ )) ≤ f (x⋆ ).
Se fosse co(f (x⋆ )) < f (x⋆ ) allora la seguente funzione
f˜(x) = max{f (x⋆ ), co(f (x))},
sarebbe una funzione convessa (in quanto il massimo di due funzioni convesse) tale che
f˜(x) 6= co(f (x)) e
co(f (x)) ≤ f˜(x) ≤ f (x), per ogni x ∈ F.
Questo, però, contraddirebbe la proprietà iii) della Definizione 1.5.2. Perciò si deve
avere necessariamente che:
co(f (x⋆ )) = f (x⋆ ) (1.13)
Utilizzando la (1.13), la definizione della funzione f˜(x) e la proprietà iii) della Defini-
zione 1.5.2, si ottiene che:
co(f (x⋆ )) = f (x⋆ ) ≤ f˜(x) ≤ co(f (x)), per ogni x ∈ F,
che implica che il punto x⋆ è anche un minimo globale della funzione co(f (x)) su F.
Infine la (1.13) assicura anche che i valori ottimi della funzione f (x) e della funzione
co(f (x) su F coincidono.
Un esempio di involucro convesso di una funzione è riportatato nella figura (1.3).
La funzione co(f (x)) può essere utilizzata per dare una ulteriore caratterizzazione dei
minimi globali non vincolati di una funzione continuamente differenziabile.
Teorema 1.5.4 Sia f una funzione continuamente differenziabile su Rn . Un punto

x⋆ ∈ Rn è un minimo globale di f su Rn se e solamente se le seguenti condizioni sono
verificate:
i) ∇f (x⋆ ) = 0;
ii) co(f (x⋆ )) = f (x⋆ ).
Dai precedenti risultati emerge che la funzione co(f (x)) potrebbe avere un ruolo si-
gnificativo nella definizione di metodi di ottimizzazione globale. Purtroppo la sua
utilizzazione è limitata per il fatto che, per problemi generali, non si ha una sua rap-
presentazione semplice. Infatti nel caso in cui la funzione f (x) sia continua su Rn
19
f ( x)
co ( f ( x ))
x*
Figura 1.3: Esempio di involucro convesso di una funzione.
e soddisfi ipotesi ragionevoli (al più il fatto che la funzione f (x) sia coercitiva, cioè
limkxk→∞ f (x) = ∞) si possono dare le seguenti espressioni equivalenti della funzione
co(f (x)):

co(f (x)) = sup aT x − b : a ∈ Rn , b ∈ R, aT x̃ − b ≤ f (x̃) ∀x̃ ∈ Rn , (1.14)
n+1 n+1 n+1
n
X X X
co(f (x)) = inf αi f (xi ) : xi ∈ R , αi ∈ R+ , αi = 1, αi xi = x (1.15)
,
i=1 i=1 i=1

co(f (x)) = sup pT x − sup pT x̃ − f (x̃) . (1.16)
p x̃
La (1.14) mostra che in ogni punto la funzione co(f (x)) è costituita dall’estremo
superiore delle funzioni lineari che sottostimano la funzione f (x).
La (1.15) mostra, invece, che il valore della funzione co(f (x)) nel punto x è dato dall’e-
stremo inferiore di particolari combinazioni dei valori della funzione obiettivo calcolati
nei punti di vertice di simplessi contenenti il punto x. I coefficenti di tali combinazione
sono dati dai pesi che permettono di rappresentare il punto x in funzione dei vertici del
simplesso considerato.
Infine la (1.16) mostra che la funzione co(f (x)) coincide con la funzione coniugata della
funzione coniugata della f (x). Infatti la funzione coniugata di f (x) è definita da:

∗ T
f (p) = sup p x − f (x) ,
x
20
mentre la funzione coniugata di f ∗ (p) è data da:

∗∗ T ∗
f (x) = sup p x − f (p) .
p
Dalla (1.16) segue che

co(f (x)) = f ∗∗ (x).
1.5.3 Caratterizzazione dei minimi globali unici

Nel caso in cui una funzione f abbia un solo minimo globale sull’insieme ammissibile
F, si può caratterizzare ulteriormente tale minimo globale come descritto dal seguente
teorema.
Teorema 1.5.5 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1 e sia f

continua su F. Se la funzione f ha un unico minimo globale x⋆ su F allora per
i = 1, . . . , n Z
xi e−kf (x) dx
lim ZF = x⋆i (1.17)
k→∞ −kf (x)
e dx
F
Prova. Per dimostrare il teorema basta provare che, per ogni i = 1, . . . , n, le sequenze
{φik } con Z
|xi − x⋆i |e−kf (x) dx
φik = F Z , (1.18)
e−kf (x) dx
F
sono tali che
lim φik = 0.
k→∞
Cioè si deve dimostrare che comunque scelto un ε > 0 esiste un indice kε tale che per
tutti gli indici k ≥ kε si ha:
φik ≤ ε. (1.19)
Per qualsiasi fissato ε > 0, sia Bε il seguente intorno aperto
ε
Bε = {x ∈ F : kx − x⋆ k < }.
2
Utilizzando questo intorno, si può riscrivere la (1.18) nella seguente maniera:
Z Z
|xi − x⋆i |e−kf (x) dx |xi − x⋆i |e−kf (x) dx
Bε F \Bε
φik = Z + Z . (1.20)
e−kf (x) dx e−kf (x) dx
F F
21
Per quanto riguarda il primo termine della sommatoria si ha, ricordando la definizione
di Bε : Z Z
|xi − x⋆i |e−kf (x) dx e−kf (x) dx
Bε ε Bε ε
Z ≤ Z ≤ . (1.21)
e−kf (x) dx 2 e−kf (x) dx 2
F F
Per quanto riguarda,invece, il secondo termine della somma in (1.20) può essere riscritto
nella seguente forma:
Z Z
⋆ ))
|xi − x⋆i |e−kf (x) dx |xi − x⋆i |e−k(f (x)−f (x dx
F \Bε F \Bε
Z = Z
⋆ ))
. (1.22)
e−kf (x) dx e−k(f (x)−f (x dx
F F
Poichè, dall’Assunzione 1.5.1, l’insieme F è un insieme compatto e poichè x⋆ è l’unico

minimo globale di f su F, esistono due costanti M > 0 e δ > 0 tali che, per tutti
x ∈ F \ Bε , si ha:
kx − x⋆ k ≤ M,
f (x) − f (x⋆ ) ≥ δ,
per cui dalla (1.22) si ha:

Z Z
|xi − x⋆i |e−kf (x) dx e−kδ dx
F \Bε F \Bε meas(F \ Bε )e−kδ
Z ≤MZ ⋆
≤ M Z
⋆
. (1.23)
e−kf (x) dx e−k(f (x)−f (x )) dx e−k(f (x)−f (x )) dx
F F F
Utilizzando la continuità della funzione f e sfruttando di nuovo il fatto che l’insieme F

soddisfa l’Assunzione 1.5.1 si ha che esiste un sottoinsieme Wε tale che:
Wε ⊂ F, meas(Wε ) > 0,
δ
f (x) − f (x⋆ ) ≤ per tutti x ∈ Wε .
2
Utizzando questo sottoinsieme e la (1.23) si ottiene:
Z
F \Bε meas(F \ Bε )e−kδ meas(F \ Bε )e−k(δ/2)
Z ≤M Z ≤M , (1.24)
e−kf (x) dx e−k(δ/2) dx meas(Wε )
F Wε
da cui segue che esiste un indice kε tale che, per tutti gli indici k ≥ kε , si ha:
Z
F \Bε meas(F \ Bε )e−k(δ/2) ε
Z ≤M ≤ . (1.25)
e−kf (x) dx meas(Wε ) 2
F
Concludendo la (1.20), (1.21) e la (1.25) provano la (1.19) e, quindi, dimostrano la tesi

del teorema.
22
1.6 Proprietà generali dei metodi di ottimizzazione glo-
bale
Come hanno mostrato le condizioni di ottimalità globale riportate nella sezione prece-
dente, i punti di minimo globale di un generico problema di ottimizzazione non sono
caratterizzabili matematicamente in modo semplice. Questo fatto rende difficile, da
punto di vista teorico, la definizione di algoritmi di ottimizzazione in grado di determi-
nare un punto di minimo globale. Infatti, la complessità delle condizioni di ottimalità
globale porta sia all’impossibilità di sfruttare dal punto di vista algoritmico il fatto che
un punto prodotto dall’algoritmo non è un minimo globale e sia alla difficoltà di definire
dei criteri di arresto efficienti, cioè relativamente semplici ed affidabili.
Per cercare di superare le precedenti difficoltà gli algoritmi proposti in letteratura
utilizzano due approcci differenti:
- algoritmi che utilizzano informazioni globali sul problema di ottimizzazione;
- algoritmi che utilizzano informazioni locali sul problema di ottimizzazione.
Gli algoritmi che utilizzano informazioni globali sono in grado di produrre sequenze di
punti che hanno interessanti proprietà di convergenza. Tuttavia essi richiedono o ipo-
tizzano la conoscenza di informazioni “a priori” sul problema da risolvere, per esempio:
la struttura particolare del problema come la convessità o la concavità, la costante di
Lipschitz della funzione obiettivo e dei vincoli, i limiti superiori sulle derivate prime o
seconde delle funzioni che descrivono il problema, valore ottimo della funzione obietti-
vo, il numero di minimi globali. Purtroppo tali informazioni globali sono difficilmente
disponibili nei problemi reali e questo, in qualche maniera, può limitare l’applicabilità
di questa classe di metodi.
Gli algoritmi che utilizzano informazioni locali fanno riferimento, invece, a grandezze
e quantità del problema di ottimizzazione facilmente ottenibili durante le iterazioni
dell’algoritmo, come, per esempio: i valori della funzione obiettivo e dei vincoli nei
vari punti prodotti dall’algoritmo stesso, i valori delle derivate delle funzioni che de-
scrivono il problema (se disponibili). Anche tutte le informazioni ottenibili da formule
ed espressioni che utilizzano e combinano le precedenti quantità sono di tipo locale.
Esempi di questo genere sono l’uso di formule di interpolazione o di estrapolazione, del
punto prodotto dall’algoritmo in cui si è ottenenuto il più basso valore della funzione
obiettivo, della massima pendenza della funzione obiettivo incontrata tra due punti.
Non richiedendo informazioni “a priori” sul problema, questa classe di metodi ha una
ampia applicabilità. Tuttavia, per cercare di avere una qualche proprietà di convergenza
verso minimi globali, questi metodi devono estrarre durante le loro iterazioni delle in-
formazioni sul comportamento globale della funzione obiettivo sull’insieme ammissibile
F. Questo viene fatto cercando di“campionare” (cioè valutare) la funzione obiettivo
in un numero sufficientemente grande di punti appartenenti all’insieme ammissibile F.
A seconda di come viene effettuato questo campionamento, i metodi appartenenti a
questa classe si dividono in:
23
- metodi deterministici, dove i punti in cui viene valutata la funzione obiettivo so-
no determinati utilizzano le informazioni sulla funzione già ottenute durante le
iterazione dell’algoritmo;
- metodi probabilistici, dove i punti in cui la funzione viene campionata sono dei vet-
tori aleatori distribuiti uniformemente o secondo leggi che tengono conto delle
informazione estratte dall’algoritmo.
In entrambe queste classi di metodi, l’ideale sarebbe quello di eseguire un campiona-

mento della funzione obiettivo che privileggiasse le zone in cui è localizzato un minimo
globale e che fosse in grado di assicurare la convergenza dell’algoritmo verso minimi
globali.
Nel seguito si descriveranno alcuni risultati che chiariscono il legame tra il modo di
campionare la funzione obiettivo e le proprietà di convergenza dell’algoritmo verso i
minimi globali.
1.6.1 Definizione e funzione di perturbazione
Per introdurre questi risultati è necessario definire formalmente quali sono le carat-
teristiche di un algoritmo che utilizza informazioni locali. Questo può essere fatto
introducendo la seguente definizione.
Definizione 1.6.1 Si definisce algoritmo che utilizza informazioni locali un algoritmo

che, ad ogni iterazione k, presenta le seguenti caratteristiche:
i) il nuovo punto prodotto xk+1 dipende solamente dalla funzione f : F → R, a cui

è applicato l’algoritmo, e da un certo numero di punti x̃0k , x̃1k , . . . , x̃pkk , in cui si
sono estratte le informazioni sul problema da risolvere, cioè esiste un operatore
D tale che
xk+1 = D(f, x̃0k , x̃1k , . . . , x̃pkk );
ii) se esiste un insieme N ⊆ F e due funzioni f : F → R e f˜ : F → R tali che:
f (x) = f˜(x), per ogni x∈N
e se i punti x̃0k , x̃1k , . . . , x̃pkk utilizzati dall’algoritmo sono tali che:
x̃ik ∈ N , per ogni i = 0, . . . , pk ,
allora l’algoritmo produce lo stesso punto xk+1 sia se è applicato alla funzione f
e sia se è applicato alla funzione f˜, cioè si ha
D(f, x̃0k , x̃1k , . . . , x̃pkk ) = D(f˜, x̃0k , x̃1k , . . . , x̃pkk ).
Per analizzare in generale le proprietà di convergenza di algoritmi di ottimizzazione

globale è necessario richiamare la seguente proposizione.
24
Proposizione 1.6.2 Comunque scelti due scalari ε1 > 0 e ε2 > 0 con ε1 > ε2 , si può
definire una funzione s( · ; ε1 , ε2 ) : Rn → R infinitamente differenziabile tale che:
s(x; ε1 , ε2 ) = 1, se kxk ≤ ε2 ,
0 < s(x; ε1 , ε2 ) < 1, se ε2 < kxk < ε1 ,
s(x; ε1 , ε2 ) = 0, se kxk ≥ ε1 .
Prova. Un modo per definire una funzione che soddisfa le proprietà descritte dalla
proposizione è il seguente.
Per ogni ε1 > 0 e ε2 > 0, con ε1 > ε2 , si possono introdurre le seguenti funzioni
infinitamente differenziabili:
1


 − 2 2
 e ε1 − kxk

se kxk < ε1


s1 (x; ε1 ) =

se kxk ≥ ε1

0



1


 − 2 2
 e kxk − ε2

se kxk > ε2


s2 (x; ε2 ) =

se kxk ≤ ε2 .

0



Utilizzando le presecedenti funzioni, si può definire la seguente funzione:
s1 (x; ε1 )
s(x, ε1 ; ε2 ) = . (1.26)
s1 (x; ε1 ) + s2 (x; ε2 )
È facile verificare che la funzione s(x, ε1 ; ε2 ), oltre ad essere infinitamente differenziabile,

soddisfa anche le altre richieste della proposizione, infatti:
- se kxk ≥ ε1 allora s1 (x; ε1 ) = 0 e s2 (x; ε2 ) > 0 da cui segue che s(x; ε1 , ε2 ) = 0;
- se ε2 < kxk < ε1 allora s1 (x; ε1 ) > 0 e s2 (x; ε2 ) > 0 da cui segue che 0 <
s(x; ε1 , ε2 ) < 1;
- se kxk ≤ ε2 allora s1 (x; ε1 ) > 0 e s2 (x; ε2 ) = 0 da cui segue che s(x; ε1 , ε2 ) = 1.
La precedente proposizione mostra che una qualsiasi funzione può essere perturbata
arbitrariamente in un punto x̃ lasciandola immutata in tutti i punti in cui è definita
con l’esclusione di un prefissato intorno di un punto x̃. Per esempio, data una funzione
f : Rn → R, un punto x̃ ∈ Rn ed un scalare α ∈ R, la funzione
f˜(x) = f (x) + (α − f (x̃))s(x − x̃; ε, ε/2)
25
coincide con la funzione f (x) per ogni x ∈ Rn \ B(x̃; ε) ed è tale che f˜(x̃) = α. Inoltre
la nuova funzione f˜ ha le stesse proprietà di regolarità della f , cioè se, per esempio, f
è due volte continuamente differenziabile continua ad esserlo anche la f˜.
Da quanto osservato segue facilmente la seguente proposizione.
Proposizione 1.6.3 Comunque scelti una funzione f : F → R, un punto x̃ ∈ F ed

uno scalare ε > 0, si può definire una nuova funzione f˜ : F → R tale che:
- ha le stesse proprietà di continuità di f ;
- f˜(x) = f (x) per ogni x ∈ F \ B(x̃; ε);
- il punto x̃ ∈ F è l’unico minimo globale della funzione f˜ su F.
Prova. La dimostrazione segue osservando che un esempio di una funzione f˜ che gode
delle proprietà descritte dalla proposizione è il seguente:
2
f˜(x) = f (x) + (−αe−kx−x̃k − f (x))s(x − x̃; ε, ε/2),
dove α è tale che

α > min f (x) .

x∈F
A questo punto è possibile analizzare le proprietà di convergenza degli algoritmi di

ottimizzazione globale che utilizzano informazioni locali.
1.6.2 Proprietà di convergenza degli algoritmi di ottimizzazione glo-

bale deterministici
Il primo teorema considera una prima possibile proprietà di convergenza dei punti
prodotti dall’algoritmo, cioè il caso in cui un minimo globale del problema possa coin-
cidere con un punto prodotto dall’algoritmo oppure è un punto di accumulazione della
sequenza prodotta.
Teorema 1.6.4 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1, sia C l’insie-
me delle funzioni continue su F. Per ogni funzione f ∈ C, sia x∗ un suo minimo globale
su F e sia {xk } la sequenza di punti generata da un algoritmo di ottimizzazione globale
che usa informazioni locali (Definizione 1.6.1) quando applicato alla minimizzazione di
f su F. Allora, per ogni funzione f ∈ C, esiste un indice k̄ tale che xk̄ = x⋆ oppure x⋆
è un punto di accumulazione della sequenza {xk } se e solamente se, per ogni funzione
f ∈ C, i punti prodotti dall’algoritmo, al tendere di k all’infinito, formano un insieme
denso su F (cioè comunque scelti x ∈ F e ε > 0 esistono un k̄ ed un xk tali che k ≤ k̄
e xk ∈ B(x; ε)).
26
Prova. La sufficienza segue direttamente dalla definizione di insieme denso su F.
Infatti dalla densità segue che comunque scelto un ε > 0 esistono un indice k̄ ed un
punto xk tali che k ≤ k̄ e xk ∈ B(x∗ ; ε). Sia {εi } una sequenza tale che
εi > εi+1 > 0 per ogni i,

lim εi = 0.
i→∞
Se si indica con ki il più piccolo indice k ∈ {0, 1, 2, . . .} tale che
xki ∈ B(x∗ ; εi ),
segue che:
lim xki = x∗ .
i→∞
Per dimostrare la necessità si supponga che esista una funzione f ∈ C per cui l’insieme
dei punti prodotti dall’algoritmo non formi un insieme denso su F. Allora esisterebbe
un punto x̃ ∈ F e un ε̃ > 0 tali che
xk ∈
/ B(x̃; ε̃), per tutti k. (1.27)
Sfruttando la Proposizione 1.6.2 si potrebbe costruire una funzione f˜ ∈ C che coinci-

derebbe con la funzione f al di fuori della sfera B(x̃; ε̃) e che avrebbe il suo minimo
globale x̂ all’interno della sfera B(x̃; ε̃).
Ricordando la Definizione 1.6.1, un algoritmo che usa informazioni locali produrebbe
una stessa sequenza di punti sia se applicato alla funzione f e sia se applicato alla
funzione f˜. Perciò, tenendo conto della (1.27), non ci potrebbe essere un indice k̃
tale che xk̃ = x̃ nè x̃ potrebbe essere un punto di accumulazione della sequenza {xk }
prodotta dall’algoritmo.
La proprietà di convergenza considerata nel precedente teorema può non essere comple-
tamente soddisfacente. Infatti la mancanza di condizioni di ottimalità utilizzabili porta
al fatto di non saper riconoscere un minimo globale nel caso coincidesse con un punto
prodotto dall’algoritmo e di non saper individuare la sottosequenza che sta convergendo
al minimo globale. Più interessante sarebbe stabilire che tutti i punti di accumulazione
della sequenza prodotta sono dei minimi globali del problema. Purtroppo dal prece-
dente teorema deriva un risultato negativo circa la possibilità di garantire questo tipo
di convergenza, come descritto dalla seguente proposizione.
Proposizione 1.6.5 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1, sia C

l’insieme delle funzioni continue su F. Per ogni funzione f ∈ C che non sia una
costante, la sequenza di punti {xk } generati da un algoritmo di ottimizzazione globale
che usa informazioni locali (Definizione 1.6.1) non gode della proprietà che ogni suo
punto di accumulazione è un minimo globale di f su F.
Prova. Se ogni suo punto di accumulazione della sequenza di punti {xk } generati dal-
l’algoritmo fosse un minimo globale di f su F allora il Teorema 1.6.4 implicherebbe che
27
i punti generati dall’algoritmo formerebbero un denso su F. Dalla definizione di insie-
me denso si avrebbe che ogni punto dell’insieme F sarebbe un punto di accumulazione
della sequenza di punti {xk } (basta ripetere la prima parte della prova del precedente
Teorema facendo riferimento ad un qualsiasi punto x ∈ F). Si avrebbe, quindi, l’assur-
do che ogni punto dell’insieme ammissibile F sarebbe un minimo globale del problema.
1.6.3 Proprietà di convergenza degli algoritmi di ottimizzazione glo-

bale probabilistici
Risultati analoghi a quelli ottenuti per algoritmi deterministici, si possono stabilire per
gli algoritmi di ottimizzazione globale probabilistici che utilizzano informazioni locali.
Infatti si può stabilire il seguente teorema he è l’analogo del Teorema 1.6.4.
Teorema 1.6.6 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1, sia C l’insie-
me delle funzioni continue su F. Per ogni funzione f ∈ C, sia x∗ un suo minimo globale
su F e sia {xk } la sequenza di punti aleatori generati da un algoritmo di ottimizzazione
globale probabilistico che usa informazioni locali (Definizione 1.6.1) quando applicato
alla minimizzazione di f su F. Sia p ∈ (0, 1). Allora, comunque scelta una funzione
f ∈ C, la probabilità che esiste un indice k̄ tale che xk̄ = x⋆ oppure che x⋆ è un punto di
accumulazione della sequenza {xk } è maggiore di p se e solamente se, comunque scelta
una funzione f ∈ C, la probabilità che un qualsiasi punto di F appartenga alla chiusura
dei punti generati dall’algoritmo, al tendere di k all’infinito, è maggiore di p.
L’analogo del Teorema 1.6.5 diventa, nel caso di algoritmi probabilistici, il seguente
risultato.
Teorema 1.6.7 Sia F ⊂ Rn un insieme che soddisfa l’Assunzione 1.5.1, sia C l’in-
sieme delle funzioni continue su F. Allora comunque scelto un valore p ∈ (0, 1), per
ogni funzione f ∈ C che non sia una costante, la probabilità che la sequenza di pun-
ti {xk } generati da un algoritmo di ottimizzazione globale che usa informazioni locali
(Definizione 1.6.1) non goda della proprietà che ogni suo punto di accumulazione è un
minimo globale di f su F è maggiore di p.
Come notato per i Teoremi 1.6.4 e 1.6.5, anche i Teoremi 1.6.6 e 1.6.7 continuano a
valere nel caso di funzioni continuamente deifferenziabili oppure nel caso di funzioni
due volte continuamente differenziabili.
28
Capitolo 2
Metodi di ottimizzazione locale
In questo capitolo vengono introdotti e brevemente descritti quelli che vengono detti
metodi di ottimizzazione locale. Per una trattazione completa, approfondita e rigorosa
si rimanda il lettore intessato al libro:
L. Grippo, M. Scriandrone: ”Metodi di Ottimizzazione Non Vincolata”. Springer-

Verlag Italia 2011.
In questo capitolo si seguirà l’approccio proposto nel precedente libro riportando bre-
vemente alcuni dei risultati principali.
Nel seguito si considererà una particolare classe di problemi, detti problemi di ottimiz-
zazione continuamente differenziabili, che presentano le seguenti caratteristiche:
- la funzione obiettivo f è almeno continuamente differenziabile;
- nel caso di problemi vincolati, le funzioni gi , i = 1, . . . , m, e hj , j = 1, . . . , p, che

descrivono l’insieme ammissibile, sono almeno continuamente differenziabili
2.1 Introduzione
Gli algoritmi proposti per risolvere problemi di ottimizzazione consentono di determi-
nare dei punti x∗ ∈ Ω, dove Ω è un certo insieme di punti desiderati. Gli algoritmi di
ottimizzazione sono classificati, oltre per la classe di problemi a cui si applicano, anche
per il particolare insieme Ω a cui si riferiscono. In particolare se Ω è costituito da tutti
i minimi globali del Problema 1.1, i corrispondenti algoritmi vengono detti algoritmi di
ottimizzazione globale. Purtroppo la definizione di algoritmi generali di ottimizzazione
globale è uno degli argomenti più difficili nel campo dell’ottimizzazione ed è tuttora un
argomento di ricerca aperto.
La maggior parte dei metodi ed algoritmi proposti in letteratura appartengono alla
classe chiamata metodi di ottimizzazione locale oppure, più semplicemente, metodi lo-
cali. Questa classe di metodi, partendo da un punto iniziale x0 ∈ Rn , cercano di
29
produrre una sequenza di punti {xk } che abbia una ”qualche proprietà di convergenza”
verso punti di minimo locale del problema. Questi metodi cercano di sfruttare tutte
la informazioni locali che possono essere estratte dal problema (per esempio: calcolo
delle derivate prime della funzione obiettivo e dei vincoli, calcolo delle derivate secon-
de, valutazione della funzione obiettivo e dei vincoli in punti vicini al punto corrente)
e di utilizzare il fatto che una qualsiasi funzione può essere approssimata localmente
abbastanza bene da una funzione lineare o da una funzione quadratica. In realtà, in as-
senza di particolari proprietà della funzione obiettivo e dei vincoli, le sequenze di punti
prodotte da questi metodi non presentano “proprietà di convergenza” verso dei minimi
locali del problema, ma piuttosto verso punti che soddisfano delle condizioni necessarie
di ottimo locale (viste nella sSezione 1.4.2). Questi punti, pur essendo solamente dei
candidati ad essere dei minimi locali, vengono accettati in questa classe di algoritmi
come soluzioni locali del Problema (1.1).
L’insieme Ω dei metodi di ottimizazione locale per problemi non vincolati

Normalmente, nei metodi locali per problemi non vincolati, Ω è costituito da punti che
soddisfano le condizioni necessarie di ottimalità del primo ordine (cioè quelli che sono
stati definiti punti stazionari) per il Problema (1.2) ed in cui il valore della funzione
obiettivo non è peggiorato.
Ω := {x ∈ Rn : f (x) ≤ f (x0 ), ∇f (x) = 0}.
In pratica, se il punto iniziale x0 non è un punto stazionari i metodi locali sono in grado
di garantire che f (x) < f (x0 ).
Recentemente sono stati proposti in letteratura dei metodi che permettono di determi-
nare dei punti che soddisfano le condizioni necessarie di ottimalità del secondo ordine
(cioè punti che sono dei “migliori” candidati ad essere dei minimi locali del problema
di partenza). In questo caso l’insieme Ω è dato da:
Ω := {x ∈ Rn : f (x) ≤ f (x0 ), ∇f (x) = 0, dT ∇2 f (x)d ≥ 0, ∀d ∈ Rn }.
L’insieme Ω dei metodi di ottimizazione locale per problemi vincolati

Analogamente al caso non vincolato, la maggior parte dei metodi locali per problemi
vincolati fanno riferimento ad un insieme Ω che è costituito da punti che soddisfano le
condizioni necessarie di ottimalità del primo ordine (cioè quelli che sono stati definiti
punti di Kuhn-Tucker) per il Problema (1.3). Inoltre se il punto di partenza appartiene
all’insieme ammissibile tali metodi permettono di determinare un punto di Kuhn-Tuker
in cui valore della funzione obiettivo non è peggiore di quello di partenza. Formalmente
si ha:
Ω := {x ∈ Rn : x è un punto di Kuhm-Tuker e f (x) ≤ f (x0 ) se x0 ∈ F}.
Anche nel campo dei metodi locali per problemi vincolati sono stati proposti recente-
mente degli algoritmi che cercano di produrre punti dei punti che soddisfano le condi-
zioni necessarie di ottimalità del secondo ordine per il Problema (1.3), in questi casi si
30
ha:
Ω := {x ∈ Rn : x soddisfa le condizioni necessarie di ottimalità
del secondo ordine e f (x) ≤ f (x0 ) se x0 ∈ F}.
2.2 Convergenza globale

Un algoritmo o metodo di ottimizzazione produce, a partire da una stima iniziale x0 ,
una sequenza di punti {xk } che può essere considerata una sequenza di stime successive
di un punto appartenente all’insieme desiderato Ω. Dal punto di vista applicativo si
è interessati a considerare metodi di ottimizzazione che sono affidabili ed efficienti.
L’affidabilità di un algoritmo viene comunemente associata al concetto di convergenza
globale dell’algoritmo. Mentre la sua efficienza viene associata al concetto di rapidità
(o velocità) di convergenza della sequenza dei punti prodotta dall’algoritmo.
Definizione 2.2.1 Un algoritmo o un metodo di ottimizzazione si dice globalmente

convergente se, qualunque sia il punto di partenza x0 , la sequenza di punti {xk } che
produce soddisfa una delle seguenti proprietà:
(i) esiste un punto xν tale che xν ∈ Ω;
(ii) la successione {xk } converge ad un punto di Ω;
(iii) esiste un punto di accumulazione di {xk } ed ogni punto di accumulazione di {xk }
appartiene ad Ω;
(iv) esiste un punto di accumulazione di {xk } che appartiene ad Ω.
Nel caso (i) l’algoritmo termina dopo un numero finito di passi determinando un punto
di Ω. In questo caso si dice che l’algoritmo ha convergenza finita. Purtroppo solamente
per classi molto particolari di problemi si possono definire algoritmi che presentano
questa proprietà (per esempio quelli per minimizzare funzioni quadratiche convesse).
Generalmente i metodi proposti hanno, al più, proprietà di tipo asintotico del tipo (ii),
(iii) o (iv). Ovviamente, la proprietà (iv) è quella a cui corrisponde la nozione più
debole di convergenza tra quelle considerate; la proprietà (iv) tuttavia può essere già
sufficiente, dal punto di vista pratico, ad assicurare un comportamento soddisfacente
dell’algoritmo. Infatti essa assicura che, dopo aver effettuato un numero sufficiente-
mente grande di iterazioni, si è in grado di ottenere una buona stima di un punto di
Ω.
È da sottolineare che nella Definizione 1.1 il termine globale deriva dal fatto che una
delle le proprietà di convergenza (i)-(iv) deve valere comunque si fissi il punto iniziale
x0 .
Definizione 2.2.2 Se un algoritmo di ottimizzazione produce una sequenza di punti
{xk } che soddisfa una delle proprietà di convergenza (i)-(iv) solamente se il punto
iniziale x0 appartiene ad un intorno opportuno di un punto di Ω, l’algoritmo si dice
localmente convergente.
31
Generalmente, nel caso di algoritmi localmente convergenti, l’intorno a partire dal quale
convergono non è conosciuto a priori ma se ne conosce solamente l’esistenza.
2.3 Rapidità di convergenza

Per quanto riguarda lo studio della caratterizzazione della rapidità di convergenza di
un algoritmo di ottimizzazione, esso viene effettuato, per semplicità, supponendo che la
sequenza {xk } sia convergente ad un punto x∗ ∈ Ω.
Una seconda semplificazione, che comunemente viene fatta, deriva dal fatto che nor-
malmente si può escludere il caso in cui si ha convergenza finita, cioè che esiste un
valore finito di k per cui xk = x∗ . Infatti algoritmi che convergono in un numero fi-
nito di iterazioni si riferiscono a problemi di ottimizzazione molto particolari e la loro
efficienza può essere naturalmente misurata dal numero di iterazioni necessarie ad ot-
tenere il punto x∗ . Diversa è la situazione nel caso generale di algoritmi che producono
sequenze infinite di punti {xk }. Una valutazione della efficienza di questi algoritmi
implica necessariamente lo studio e la caratterizzazione del comportamento asintotico
della sequenze {xk } prodotta al tendere di k all’infinito.
In letteratura, la rapidità di convergenza di un algoritmo è stata valutata utilizzando
diversi tipi di misure. Il criterio più diffuso è quello di considerare l’andamento della
norma della differenza tra il punto xk , ottenuto all’iterazione k-esima, ed il punto x∗ ,
cioè l’errore commesso ek dato da:
ek = kxk − x∗ k.
La rapidità di convergenza di un algoritmo può quindi essere definita caratterizzando

la velocità con cui ek tende a zero e questo, generalmente, è stato fatto confrontando
le norme dei ek+1 e ek .
Definizione 2.3.1 Sia xk → x∗ . Se esistono k̄ ≥ 0, p > 0 e α ≥ 0 tali che per k ≥ k̄

si ha:
kxk+1 − x∗ k ≤ αkxk − x∗ kp
allora si dice che la {xk } ha rapidità di convergenza di ordine p.
In pratica i casi più interessanti sono p = 1 e p = 2, in quanto la maggior parte degli

algoritmi proposti in letteratura presentano rapidità di convergenza che ricadono in
questi due casi.
- Se p = 2 nella Definizione 2.3.1, allora si dice che la sequenza {xk } ha rapidità di

convergenza quadratica.
- Se p = 1 nella Definizione 2.3.1, allora si dice che la sequenza {xk } ha rapidità di

convergenza
- lineare se α ∈ [0, 1),
32
- sublineare se α ∈ [1, ∞).
Tra la rapidità di convergenza quadratica e quella lineare si può introdurre un livello

intermedio utilizzando la sequente definizione
Definizione 2.3.2 Sia xk → x∗ . Se esistono un k̄ ≥ 0 ed una sequenza di scalari
positivi {αk }, con αk → 0, tali che per k ≥ k̄ si ha:
kxk+1 − x∗ k ≤ αk kxk − x∗ k
allora si dice che la sequenza {xk } ha rapidità di convergenza superlineare.
2.4 Metodi di ottimizzazione non vincolata

In questa sezione si descriveranno molto brevemente alcune delle classi più importanti
di algoritmi di minimizzazione non vincolata.
2.4.1 Introduzione
Gran parte degli algoritmi di ottimizzazione non vincolata presenta la seguente strut-
tura:
Schema generale di un algoritmo

Passo 1: Si sceglie un punto iniziale x0 ∈ Rn e si pone k = 0.
Passo 2: Se xk è un punto stazionario stop.
Passo 3: Si determina un vettore dk ∈ Rn , detto direzione di ricerca.
Passo 4: Si determina uno scalare αk ∈ R, detto passo (o spostamento) lungo dk .
Passo 5: Si produce un nuovo punto
xk+1 = xk + αk dk ,
si pone k = k + 1 e si ritorna al Passo 2.
Una possibile spiegazione di una tale struttura risiede nel fatto che l’idea di fondo di
un metodo di ottimizzazione non vincolata è quella di cercare di trovare un’approssi-
mazione del minimo della funzione obiettivo attraverso una sequenza di minimizzazioni
“più semplici”. Infatti al Passo 3 la direzione dk viene usualmente calcolata facendo
riferimento alla minimizzazione di una funzione η(d) che rappresenta una approssi-
mazione della funzione f (xk + d) pensata come funzione della sola variabile d ∈ Rn .
Ovviamente η(d) viene scelta in maniera tale da poter determinare il suo minimo in
maniera semplice. Una volta determinata la direzione dk , nel Passo 4 si calcola lo spo-
stamento αk in maniera tale che sia una approssimazione di un minimo della funzione
φ(α) := f (xk + αdk ) che dipende dalla sola variabile scalare α ∈ R.
33
Il primo problema da affrontare, quando si vuole dimostrare la convergenza globale
di un algoritmo, è quello di assicurare che la sequenza di punti {xk } prodotta abbia
almeno un punto di accumulazione. A questo fine, normalmente, si assume di conoscere
un punto x0 ∈ Rn tale che l’insieme di livello
L0 := {x ∈ Rn : f (x) ≤ f (x0 )}
sia compatto.
Poiché la minima richiesta rivolta ad un algoritmo di minimizzazione è quella di mi-
gliorare la stima iniziale x0 , si ha che tutti punti prodotti xk devono necessariamente
soddisfare la condizione f (xk ) ≤ f (x0 ). Quindi segue che tutti i punti della succesione
rimangono nell’insieme compatto L0 e questo implica l’esistenza di almeno un punto di
accumulazione.
Una volta considerato il problema dell’esistenza di punti di accumulazione, il passo
successivo per stabilire la convergenza globale dell’algoritmo è quello di stabilire se la
sequenza di punti {xk } prodotta soddisfa una delle proprietà (i)-(iv) della Definizione
2.2.1
Molti risultati generali sono stati proposti in letteratura per caratterizzare la conver-
genza dei metodi di ottimizzazione non vincolata. Qui se ne riporta uno che, nella sua
semplicità, mette comunque in evidenza che la convergenza globale di un algoritmo può
essere assicurata richiedendo ipotesi riconducibili a condizioni da imporre sulla scelta
della direzione di ricerca dk e del passo αk .
Proposizione 2.4.1 Sia {xk } la successione prodotta dall’algoritmo, si supponga che

L0 sia compatto. Supponiamo inoltre che valgano le condizioni:
i) f (xk+1 ) ≤ f (xk ) per ogni k;
ii) se ∇f (xk ) 6= 0 per ogni k, si ha:
∇f (xk )T dk
lim = 0; (2.1)
k→∞ kdk k
iii) esistono due costanti c > 0 e q ≥ 0 tali che, per dk 6= 0 si ha:
∇f (xk )T dk
≤ −ck∇f (xk )kq . (2.2)
kdk k
Allora, o esiste un indice ν ≥ 0 tale che xν ∈ L0 e ∇f (xν ) = 0, oppure oppure viene

prodotta una successione infinita tale che:
(a) {xk } rimane in L0 ed ammette punti di accumulazione;
(b) la successione {f (xk )} converge;
34
(c) limk→∞ k∇f (xk )k = 0, cioè ogni punto di accumulazione x̄ di {xk } è tale che
∇f (x̄) = 0.
Come detto in precedenza le ipotesi (i)-(iii) della Proposizione 2.4.1 possono essere
riconducibili a condizioni sulla direzione dk e sul passo αk .
- L’ipotesi i) può essere soddisfatta scegliendo valori per αk sufficientemente piccoli

ed una direzione dk tale che soddisfa la seguente condizione:
∇f (xk )T dk < 0
che garantisce che, per valori abbastanza piccoli di α, si abbia f (xk + αk dk ) <
f (xk ).
- L’ipotesi ii) può essere soddissfatta utilizzando delle semplici tecniche di ricerca
unidimensionale per il calcolo di αk .
- L’ipotesi iii) pone delle condizioni sulla scelta della direzione dk . Infatti, ricordan-
do che il coseno dell’angolo θk tra il gradiente ∇f (xk ) e la direzione dk è definito
da:
∇f (xk )T dk
cos θk = .
kdk k k∇f (xk )k
l’ipotesi iii) implica che cos θk < 0 che, geometricamente, equivale a richiedere che
la direzione dk formi sempre un angolo acuto con la direzione dell’antigradiente
−∇f (xk ).
La Proposizione 2.4.1 può essere utilizzata per assicurare la convergenza globale di

molte classi di metodi di ottimizzazione non vincolata. Infatti le richieste sulla scelta
del passo αk possono essere soddisfatte molto facilmente (come si vedrà nella prossima
sezione) ed inoltre non è difficile trovare delle direzioni che soddisfano l’ipotesi iii).
L’esempio più immediato è quello di considerare delle direzioni del tipo
dk = −Hk ∇f (xk )
dove Hk è una matrice definita positiva, con massimo autovalore λM (Hk ) e minimo
autovalore λm (Hk ) tali che, per ogni k, verificano M ≥ λM (Hk ) ≥ λm (Hk ) ≥ m > 0,
con M ≥ m > 0.
In tal caso si ha che la iii) della Proposizione 2.4.1 è verificata con q = 1 e c = m/M .
Infatti usando la seguente relazione
kdk k = kHk ∇f (xk )k ≤ λM (Hk )k∇f (xk )k ≤ M k∇f (xk )k
si ha:
m
∇f (xk )T dk = −∇f (xk )T Hk ∇f (xk ) ≤ −λm (Hk )k∇f (xk )k2 ≤ − k∇f (xk )kkdk k
M
35
Un altro modo (molto diffuso nei metodi tipo-Newton) per assicurare la condizione (iii)
della Proposizione 2.4.1 è quella di mostrare che, per ogni k, esistono numeri c1 > 0,
c2 > 0, q1 > 0 e q2 > 0 tali che la direzione dk verifica le seguenti condizioni:
∇f (xk )T dk ≤ −c1 k∇f (xk )kq1 , kdk kq2 ≤ c2 k∇f (xk )k. (2.3)
Tuttavia, benché le sue condizioni sembrano essere alquanto generali, la Proposizione

2.4.1 si è rilevata inadeguata a stabilire la convergenza globale di classi importanti di
algoritmi di minimizzazione non vincolata come, ad esempio metodi del tipo del gra-
diente coniugato o i metodi Quasi Newton. Questo è dovuto al fatto che, in questi casi,
risulta difficile stabilire la validità della condizione iii) di Proposizione 2.4.1. Infatti in
tutti gli algoritmi in cui la direzione dk viene scelta in base ad informazioni relative alle
iterazioni precedenti, non sembra possibile cercare di soddisfare una condizione, come
la iii) di Proposizione 2.4.1, che si basa su grandezze e variabili relative esclusivamente
alla iterazione corrente.
È nata quindi l’esigenza di dare dei criteri di convergenza globale che richiedano con-
dizioni più deboli sulla direzione di ricerca dk . Questo può essere fatto a prezzo, però,
di richiedere condizioni più forti sulla scelta del passo αk come mostra la seguente
proposizione.
Proposizione 2.4.2 Sia {xk } la successione prodotta dall’algoritmo e si supponga che

L0 sia compatto e che dk 6= 0 per ∇f (xk ) 6= 0. Supponiamo che valgano le condizioni:
i) f (xk+1 ) ≤ f (xk ) per ogni k;
∞
∇f (xk )T dk 2
X
< ∞; (2.4)
k=0
kdk k
iii) se ∇f (xk ) 6= 0 per ogni k allora si ha:
∞ 2
X ∇f (xk )T dk
= ∞. (2.5)
k=0
kdk k k∇f (xk )k
Allora, o esiste un indice ν ≥ 0 tale che xν ∈ L0 e ∇f (xν ) = 0, oppure viene prodotta

una successione infinita tale che:
(c) lim inf k→∞ k∇f (xk )k = 0, cioè esiste un punto di accumulazione x̄ di {xk } tale
che ∇f (x̄) = 0.
36
È da notare, innanzitutto, che il risultato di convergenza ottenuto è più debole rispetto
al precedente: infatti, mentre nella Proposizione 2.4.1 si riusciva a stabilire che tutti i
punti di accumulazione della sequenza {xk } sono dei punti stazionari, nella Proposizione
2.4.2 si riesce a dimostrare solamente che un punto di accumulazione di {xk } è un punto
stazionario.
Come detto precedentemente la condizione iii) di Proposizione 2.4.1 è più stringente
della iii) di Proposizione 2.4.2. Inversamente, la ii) di Proposizione 2.4.2 implica la ii)
di Proposizione 2.4.1.
2.4.2 Algoritmi di ricerca unidimensionale

Gli algoritmi di ricerca unidimensionale sono delle tecniche che permettono di calco-
lare il passo αk da effettuare lungo una assegnata direzione. Come visto nella prece-
dente sezione, si può dire che l’obiettivo di queste tecniche è quello di effettuare una
minimizzazione della funzione
φ(α) := f (xk + αdk ),
Tuttavia, benché φ è funzione della sola variabile α, una sua minimizzazione è, in
generale, molto dispendiosa specialmente in problemi in cui f non è convessa. D’altra
parte, l’esperienza computazionale mostra che non esistono particolari vantaggi nel
cercare di determinare αk come una buona stima del minimo di φ(α).
Tenendo conto delle precedenti osservazioni, un metodo di ricerca unidimensionale deve
cercare di determinare in maniera semplice un αk che, pur essendo una stima molto
approssimata di un minimo di φ, garantisca comunque all’algoritmo di minimizzazione
opportune proprietà di convergenza. In pratica, un algoritmo di ricerca unidimensionale
può essere definito utilizzando determinati criteri di accettabilità. Tali criteri, essendo
molto semplici, possono essere soddisfatti, in generale, dopo un numero molto limitato
di tentativi. Tuttavia i valore che vengono accettati per αk sono tali da garantire che
sono soddisfatte le ipotesi che servono a stabilire la convergenza globale dell’algoritmo
di ottimizzazione (per esempio le ipotesi i) e ii) della Proposizione 2.4.1 oppure le ipotesi
i) e ii) della Proposizione 2.4.2).
Criterio di Armijo, condizioni di Goldstein

Uno dei modi più semplici per assicurare il soddisfacimento delle le ipotesi i) e ii) della
Proposizione 2.4.1 è quello di impoporre che il valore αk soddisfi il seguente criterio di
Armijo.
Criterio di Armijo
• Dati a > 0, δ ∈ (0, 1), γ ∈ (0, 1/2).
• Si sceglie αk = δh a dove h è il più piccolo intero non negativo tale che:
f (xk + δh adk ) ≤ f (xk ) + γδh a∇f (xk )T dk . (2.6)
37
Dal punto di vista geometrico, la precedente condizione impone di scegliere αk come il
più grande valore di α nell’insieme:
A = {α : α = δj a, j = 0, 1, . . .}
per cui il valore della funzione φ(αk ) sia al di sotto del valore della retta passante per
(0, φ(0)) e avente pendenza γ φ̇(0) = γ∇f (xk )T dk .
Le proprietà del metodo di Armijo sono descritte nella proposizione seguente.
Proposizione 2.4.3 Supponiamo che l’insieme di livello L0 sia compatto e supponia-

mo che valgano le condizioni:
i) ∇f (xk )T dk < 0 per ogni k,
ii) esistono delle costanti c > 0 e q > 0) per cui si ha per ogni k:
q
|∇f (xk )′ dk |

kdk k ≥ c .
kdk k
Allora esiste un valore αk > 0 che soddisfa il criterio di Armijo e la successione definita
da xk+1 = xk + αk dk soddisfa le condizioni:
(a) f (xk+1 ) < f (xk );
∇f (xk )′ dk
(b) lim = 0.
k→∞ kdk k
Prova. Dalla condizione (2.6) su αk e dal fatto che ∇f (xk )T dk < 0 si ha che:
f (xk+1 ) ≤ f (xk ) − αk γ|∇f (xk )T dk |, (2.7)
da cui segue che il punto (a).

Dalla 2.7) si ha anche che
xk ∈ L 0 , per ogni k, (2.8)
da cui, ricordando l’ipotesi di compattezza dell’insieme L0 , si ha che la sequenza {xk }

è limitata e che ammette almeno un punto di accumulazione.
La (2.7) e la compatezza dell’insieme L0 implicano anche che la sequenza di scalari
{f (xk )} è non crescente e limitata inferiormente. Perciò la sequenza {f (xk )} ammette
un limite f¯, cioè:
lim f (xk ) = f¯. (2.9)

k→∞
Dal precedente limite e dalla (2.7) si ottiene:

lim αk γ|∇f (xk )T dk | ≤ lim f (xk ) − f (xk+1 = 0,
k→∞ k→∞
38
da cui segue che:
lim αk |∇f (xk )T dk | = 0. (2.10)

k→∞
Se, per assurdo, il punto b) della proposizione non fosse vero e ricondando l’assunzione
ii), il limite (2.10) implicherebbe l’esistenza di un insieme infinito di indici K e di
sottosequenze {xk }K e {αk }K tali che:
k∇f (xk )k ≥ ε > 0, per ogni k ∈ K,
kdk k ≥ cεq > 0, per ogni k ∈ K,
limk→∞,k∈K αk = 0.
Poichè xk ∈ L0 , per ogni k ∈ K, e che L0 è un insieme compatto esisterebbero un

sottoinsieme infinito di indici K ′ ⊆ K e tre sottosequenze {xk }K ′ , { kddkk k }K ′ e {αk }K ′
tali che:
lim xk = x̄, (2.11)

k→∞,k∈K ′
dk ¯
lim = d, (2.12)
k→∞,k∈K ′ kdk k
lim αk = 0, (2.13)
k→∞,k∈K ′
∇f (xk )T dk
lim = ∇f (x̄)T d¯ = −η < 0. (2.14)
k→∞,k∈K ′ kdk k
Dalla (2.13) si avrebbe che, per valori k ∈ K ′ sufficientemente grandi, αk < a. Per
questi valori di k, le condizioni su αk del criterio di Armijo implicherebbero:
αk αk
f (xk + dk ) > f (xk ) + γ∇f (xk )T dk , (2.15)
δ δ
Ricondando il Teorema della media si avrebbe che:
αk αk αk
f (xk + dk ) = f (xk ) + ∇f (xk + θk dk )T dk ,
δ δ δ
con θk ∈ (0, 1).
Applicando questo teorema alla (2.15) si avrebbe per valori k ∈ K ′ sufficientemente
grandi:
αk
∇f (xk + θk dk )T dk > γ∇f (xk )T dk ,
δ
da cui seguirebbe:
αk dk ∇f (xk )T dk
∇f (xk + θk dk )T >γ . (2.16)
δ kdk k kdk k
39
Facendo il limiti per k → ∞ e k ∈ K ′ , la (2.16) porterebbe a:
∇f (x̄)T d¯ ≥ γ∇f (x̄)T d,

¯ (2.17)
che contraddirebbe la (2.14) ed l’ipotesi che δ ∈ (0, 1).
Osserviamo innanzitutto che l’ipotesi ii) della precedente proposizione non è particolar-
mente restrittiva. Infatti, come si è visto precedentemente, per soddisfare la condizione
iii) di Proposizione 2.4.1, si sceglie una direzione che verifica
∇f (xk )T dk ≤ −c1 k∇f (xk )kq1
La precedente relazione implica la ii) di Proposizione 2.4.3. Infatti, dalla diseguaglianza

Schwarz, si ha:
q1
|∇f (xk )T dk | 1 M

≤ k∇f (xk )kq1 ≤ |f (xk )T dk | ≤ kdk k,
kdk k c1 c1
dove M è il massimo di k∇f (xk )k su L0 .
Da quanto visto un algoritmo di ricerca unidimensionale che utilizza il criterio di Ar-

mijo inizia la ricerca di αk a partire da un valore costante a prefissato e calcola la
funzione in tutti i punti aδj con j = 0, 1, . . . , fino a trovare un valore che soddisfi la
(2.6). Un tale algoritmo è sicuramente molto adatto per i metodi tipo-Netwon in cui
iniziare la ricerca unidimensionale a partire dal valore costante a = 1 è un requisito
essenziale per assicurarne la rapidità di convergenza superlineare. Per altri metodi (per
esempio metodi del gradiente, metodi delle direzioni coniugate) partire da un valore di
prova iniziale α = a costante per ogni iterazione può richiedere un numero elevato di
valutazioni della funzione durante la ricerca unidimensionale in quanto il valore a, non
avendo nessuna motivazione teorica, può produrre spostamenti troppo grandi (cioè a
può essere molto distante da un minimo di φ(α)); da qui la necessità di dover ridurre
molte volte il valore di α secondo il fattore costante δ.
Per questi metodi è preferibile far partire la ricerca unidimensionale da una stima di un
minimo di φ(α) ottenuta utilizzando della approssimazioni quadratiche o cubiche della
funzione φ(α) e quindi variabile con k. Da cui, per questi casi, è necessario definire
criteri di accettabilità che risultino applicabili anche a partire da stime iniziali non
costanti.
Un esempio di un criterio di questo tipo è costituito dalla seguente variazione del criterio
Armijo.
Criterio di Armijo generalizzato

• Dato γ ∈ (0, 1/2).
• Si sceglie αk > 0 tale che:
f (xk + αk dk ) ≤ f (xk ) + αk γ∇f (xk )T dk

f (xk + 2αk dk ) > f (xk ) + 2αk γ∇f (xk )T dk
40
Il precedente criterio permette di utilizzare stime iniziali del passo che posso variare
ogni iterazione, però richiede almeno due calcoli di funzione.
Nel caso in cui si è in grado di produrre dei valori iniziali del parametro α efficienti,
è preferibile utilizzare le seguenti condizioni di Goldstein che, nel caso più favorevole
usano un solo calcolo di funzione obiettivo.
Condizioni di Goldstein
• Dati a > 0, 0 < γ1 < γ2 < 1/2.
• Si sceglie αk tale da soddisfare:
f (xk + αk dk ) ≤ f (xk ) + γ1 αk ∇f (xk )T dk

f (xk + αk dk ) ≥ f (xk ) + γ2 αk ∇f (xk )T dk .
Da un punto di vista geometrico, questa condizione impone di scegliere come valore di

αk un punto tale che il corrispondente valore di φ sia compreso tra le due rette con
pendenza, rispettivamente γ1 ∇f (xk )T dk e γ2 ∇f (xk )T dk passanti per il punto (0, φ(0)).
Anche, per il criterio di Armijo generalizzato e per le condizioni di Goldstein si possono

dimostrare le proprietà a) e b) della Proposizione 2.4.3. Inoltre, per entrambe, non è
necessario richiedere l’assunzione ii).
Condizioni di Wolfe
In certi casi è necessario scegliere il passo αk in maniera più precisa rispetto al criterio di
Armijo o alle condizioni di Goldstein. A questo fine si possono considerare le condizioni
di Wolfe che sono dei criteri di accettabilità che impongono condizioni sulla derivata
della funzione φ(α) nel punto αk .
Condizioni deboli di Wolfe
• Dati γ1 ∈ (0, 1/2) e γ2 ∈ (γ1 , 1).
f (xk + αk dk ) ≤ f (xk ) + γ1 αk ∇f (xk )T dk (2.18)

∇f (xk + αk dk )T dk ≥ γ2 ∇f (xk )T dk . (2.19)
Condizioni forti di Wolfe

• Dati γ1 ∈ (0, 1/2) e γ2 ∈ (γ1 , 1).
f (xk + αk dk ) ≤ f (xk ) + γ1 αk ∇f (xk )T dk (2.20)
|∇f (xk + αk dk )T dk | ≤ γ2 |∇f (xk )T dk |. (2.21)
41
Analogamente al criterio di Armijo o alle condizioni di Goldstein, le precedenti con-
dizioni di Wolfe richiedono una sufficiente riduzione della funzione φ(α) (attraverso le
(2.18) e (2.20)). La (2.19) richiede inoltre che la tangente alla curva φ(α) in αk ab-
bia pendenza positiva (φ(α) crescente) oppure abbia pendenza negativa ma minore, in
valore assoluto, di γ2 |∇f (xk )T dk |. Il criterio forte con la (2.21) richiede invece che la
pendenza sia in valore assoluto minore di γ2 |∇f (xk )T dk |. In altre parole questo equivale
a richiedere che αk sia scelto in una zona in cui φ(α) è sufficientemente piatta.
Per entrambi i criteri di Wolfe si possono stabilire le stesse proprietà.
Proposizione 2.4.4 Supponiamo che l’insieme di livello L0 sia compatto e che ∇f (xk )′ dk <
0 per ogni k. Allora, esiste un intervallo [αl , αu ], con 0 ≤ αl < αu tale che ogni
αk ∈ [αl , αu ] soddisfa il criterio debole (forte) di Wolfe e la successione definita da
xk+1 = xk + αk dk soddisfa le condizioni:
(a) f (xk+1 ) < f (xk );

∇f (xk )′ dk
(b) lim = 0;
k→∞ kdk k
(c) se esiste una costante di Lipschitz L > 0 tale che, per ogni x, y ∈ L0 risulti
k∇f (y) − ∇f (x)k ≤ Lky − xk,
allora si ha anche: ∞
∇f (xk )T dk 2
X
< ∞.
k=0
kdk k
Il punto (c) della precedente proposizione mostra che i criteri di Wolfe, a differenza
delle altre tecniche, sono in grado di soddisfare l’ipotesi ii) della Proposizione 2.4.2.
2.4.3 Metodo del gradiente

Come si è detto precedentemente, normalmente la direzione di ricerca dk viene deter-
minata considerando una approssimazione della funzione obiettivo. Nel metodo del
gradiente si fa riferimento una approssimazione lineare di f (xk + d) pensata come
funzione del solo vettore d.
Avendo supposto che f è continuamente differenziabile, si può scrivere:
f (xk + d) = f (xk ) + ∇f (xk )T d + β1 (xk , d),
con
β1 (xk , d)
lim = 0.
kdk→0 kdk
42
L’idea del metodo del gradiente è quella di approssimare la funzione f (xk + d) con la
funzione ψk (d) data da:
ψk (d) := f (xk ) + ∇f (xk )T d,
e di scegliere come direzione di ricerca dk quella direzione che minimizza la ψk (d) nella
sfera di raggio unitario. In altre parole, dk è la soluzione del seguente problema:
min ψk (d),
kdk = 1,
che è equivalente a
min ∇f (xk )T d,
kdk = 1.
Ricordando la diseguaglianza di Schwarz, la soluzione al precedente problema è data

da d∗k = −∇f (xk )/k∇f (xk )k e quindi il metodo del gradiente può essere descritto da:
∇f (xk )
xk+1 = xk − α̃k ,
k∇f (xk )k
che, ridefinendo il passo lungo la direzione (α := α̃/k∇f (xk )k), può essere riscritto
come
xk+1 = xk − αk ∇f (xk ).
Convergenza globale
Poiché nel metodo del gradiente si ha dk = −∇f (xk ), si può notare subito che è
soddisfatta la condizione iii) di Proposizione 2.2.1 Quindi la convergenza globale di
questo metodo può essere caratterizzata dal seguente risultato.
Proposizione 2.4.5 Sia {xk } la successione prodotta dal metodo delgradiente e si

assuma che L0 sia compatto. Si supponga inoltre che la ricerca unidimensionale per
calcolare αk sia tale da soddisfare le condizioni:
i) f (xk+1 ) < f (xk ) se ∇f (xk ) 6= 0;
∇f (xk )T dk
lim = 0.
k→∞ kdk k
Allora, o esiste un indice ν ≥ 0 tale che xν ∈ L0 e ∇f (xν ) = 0, oppure viene prodotta

una successione infinita tale che:
a) {xk } rimane in L0 ed ammette punti di accumulazione;
b) ogni punto di accumulazione x̄ di {xk } soddisfa ∇f (x̄) = 0;
43
c) ogni punto di accumulazione è un punto stazionario che non è un massimo locale
di f .
In base alla proposizione precedente, per ottenere un algoritmo globalmente convergente
basta associare al metodo del gradiente una qualsiasi delle ricerche unidimensionali
descritte nella precedente sezione, in quanto tutte soddisfano le proprietà (i) e (ii) di
Proposizione 2.4.5.
Rapidità di convergenza
Purtroppo il difetto del metodo del gradiente è la sua rapidità di convergenza. Infatti
si può dimostrare che anche le caso ideale in cui la funzione da minimizzare sia una
funzione quadratica convessa ed il passo αk sia calcolato minimizzando esattamente la
funzione scalare φ(α) = f (xk + αdk ) esistono punti iniziali a partire dai quali il metodo
del gradiente produce una sequenza di punti {xk } per cui la rapidità di convergenza è
lineare.
In particolare si ha il seguente risultato risultato.
Proposizione 2.4.6 Sia data funzione
1
f (xk ) = xT Qx,
2
dove Q è una matrice simmetrica definita positiva.
Il metodo del gradiente definito con αk ottenuto minimizzando esattamente la funzione
f (xk + αdk ), cioè:
∇f (xk )T dk k∇f (xk )k2
αk = − = )
dTk Qdk ∇f (xk )T Q∇f (xk )
converge al minimo x∗ = 0 di f (x) e si ha:
1/2
λM λM − λm

kxk+1 − x∗ k ≤ kxk − x∗ k,
λm λM + λm
in cui λM e λm sono, rispettivamente, il massimo ed il minimo autovalore di Q.
Il precedente risutato mostra che il metodo del gradiente nel caso di funzioni quadratiche
e convesse ha una rapidità di convergenza che è almeno lineare e che dipende dal
rapporto λM /λm tra il massimo ed il minimo autovalore della matrice Hessiana di
f (x). Quindi ci si può aspettare che la rapidità di convergenza del metodo del gradiente
peggiori, in genere, al crescere della differenza tra λM e λm , ossia all’aumentare del mal
condizionamento della matrice Q.
Questa analisi, svolta in un semplice caso quadratico convesso, dà delle indicazione
negative sul comportamento locale del metodo gradiente nel caso di funzioni non qua-
dratiche. L’esperienza di calcolo ha, infatti, confermato queste conclusioni in quan-
to il metodo del gradiente è apparso complessivamente un metodo molto semplice di
minimizzazione non vincolata ma poco efficiente.
44
Recenti sviluppi
Per ottenere informazioni sulla rapidità di convergenza ed ottenere, nella preceden-

te proposizione, si è scelto il passo αk nella maniera che sembrava essere la migliore
possibile, cioè minimizzando esattamente lungo l’antigradiente. Tutte le conclusioni ot-
tenute e le successive implementazioni del metodo del gradiente sono state influenzate
da questa scelta.
La seguente proposizione descrive un caso in cui si fa una diversa scelta per il passo αk .
Proposizione 2.4.7 Sia data funzione

1
f (xk ) = xT Qx,
2
dove Q è una matrice simmetrica definita positiva.
Il metodo del gradiente in cui si abbia
1
αk =
λk+1
dove λi , i = 1, . . . , n sono gli autovalori della matrice Q, converge al minimo x∗ di f (x)
al più in n passi.
Quindi, a differenza della Proposizione 2.4.6, in questo caso si ottiene la convergenza

finita dell’algoritmo qualunque sia il punto di partenza. Questa differenza fra i risultati
ottenuti utilizzando due scelte diverse per il passo αk ci porta alle seguenti osservazioni:
- Determinare il passo αk cercando di minimizzare la funzione f (xk − α∇f (xk ))
può non essere la scelta migliore;
- scelte differenti possono far migliorare l’efficienza del metodo del gradiente nel
caso di funzioni non quadratiche;
- in particolare bisognerebbe determinare αk cercando di “estrarre” informazioni

del secondo ordine della funzione obiettivo.
Recentemente, ispirandosi ai metodi Quasi-Newton, si sono proposte delle nuove regole

per la scelta di α non più legate alla minimizzazione lungo la direzione di ricerca. Una
di queste consiste nel determinare αk in maniera da minimizzare la funzione:
k (xk − xk−1 ) − α (∇f (xk ) − ∇f (xk−1 )) k2
cioè
(xk − xk−1 )T (∇f (xk ) − ∇f (xk−1 ))
αk = .
(∇f (xk ) − ∇f (xk−1 ))T (∇f (xk ) − ∇f (xk−1 ))
Queste nuove versioni del metodo del gradiente, anche se non impongono più una di-
minuzione monotona della funzione obiettivo, fanno migliorare in maniera significativa
l’efficienza computazionale del metodo del gradiente.
45
2.4.4 Metodo di Newton
Se la funzione f è due volte continuamente differenziabile e se xk è un punto dato, si
può scrivere:
1
f (xk + d) = f (xk ) + ∇f (xk )T d + dT ∇2 f (xk )d + β2 (xk , d), (2.22)
2
con
β2 (xk , d)
lim = 0.
kdk→0 kdk2
L’approccio del metodo di Newton è quello di cercare di determinare il minimo di una
funzione due volte continuamente differenziabile costruendo una successione di punti
ottenuti minimizzando ad ogni passo l’approssimazione quadratica della funzione f data
da:
1
φk (d) := f (xk ) + ∇f (xk )T d + dT ∇2 f (xk )d. (2.23)
2
Tale funzione quadratica φk , in base alla (2.22), può essere considerata una buona
approssimazione di f (xk + d).
Quindi, a partire da x0 , il metodo di Newton è definito dall’iterazione:
xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ). (2.24)
dove il vettore dk = −[∇2 f (xk )]−1 ∇f (xk ), detto direzione di Newton, è un punto
stazionario della funzione quadratica φk (d). Inoltre, se la matrice Hessiana ∇2 f (xk )
è definita positiva, allora la direzione di Newton è il punto di minimo della funzione
quadratica φk (d).
2.4.4.1 Convergenza locale e rapidità di convergenza
Il fatto di utilizzare le informazione derivanti dalle derivate del primo e del secondo
ordine permette al metodo di Newton di avere localmente ottime proprietà di con-
vergenza. Infatti, utilizzando queste informazioni è possibile costruire ed utilizzare la
funzione quadratica φk (d) che, in un intorno sufficientemente piccolo di un minimo della
funzione obiettivo, approssima ottimamente il comportamento della funzione obiettivo.
La seguente proposizione mostra le ottime proprietà locali di convergenza del metodo
di Newton.
Proposizione 2.4.8 Sia f una funzione due volte continuamente differenziabile su
Rn . Supponiamo inoltre che valgano le condizioni seguenti:
i) esiste un x⋆ ∈ Rn tale che ∇f (x⋆ ) = 0;
ii) la matrice Hessiana ∇2 f (x⋆ ) è non singolare;
iii) esiste una costante L > 0 tale che, per ogni x, y ∈ Rn , si abbia

2
∇ f (x) − ∇2 f (y) ≤ Lkx − yk.

46
Allora esiste una sfera aperta B(x⋆ ; ε) := {x ∈ Rn : kx − x⋆ k < ε}, tale che, se
x0 ∈ B(x⋆ ; ε), la successione {xk } generata dal metodo di Newton a partire da x0
rimane in B(x⋆ ; ε) e converge a x⋆ con rapidità di convergenza quadratica.
Dim. Poiché ∇2 f (x⋆ ) è non singolare e ∇2 f (x) è continua su Rn , è possibile trovare

un ε1 > 0 e un µ > 0 tali che B(x⋆ ; ε1 ) e che, per ogni x ∈ B(x⋆ ; ε1 ) risulti:

2
∇ f (x)−1 ≤ µ.

Sia ora
ε < min [ε1 , 1/µL]
e supponiamo che sia xk ∈ B(x⋆ ; ε).
Essendo per ipotesi ∇f (x⋆ ) = 0, possiamo riscrivere la (2.24) nella forma:
xk+1 − x⋆ = −∇2 f (xk )−1 [ − ∇2 f (xk )(xk − x⋆ ) + ∇f (xk ) − ∇f (x⋆ )],
da cui segue:
kxk+1 − x⋆ k ≤ ∇2 f (xk )−1 −∇2 f (xk )(xk − x⋆ ) + ∇f (xk ) − ∇f (x⋆ )

(2.25)
≤ µ −∇2 f (xk )(xk − x⋆ ) + ∇f (xk ) − ∇f (x⋆ ) .

Poiché ∇f è differenziabile, si ha:

Z 1
⋆
∇f (xk ) − ∇f (x ) = ∇2 f (x⋆ + λ(xk − x⋆ ))(xk − x⋆ )dλ,
0
e quindi, per la (2.25) si può scrivere:

Z 1
kxk+1 − x⋆ k ≤ µ [∇2 f (x⋆ + λ(xk − x⋆ )) − ∇2 f (xk )](xk − x⋆ )dλ

.
0
Dalla diseguaglianza precedente si ottiene:

Z 1
⋆ 2
kxk+1 − x k ≤ µ ∇ f (x⋆ + λ(xk − x⋆ )) − ∇2 f (xk ) dλ kxk − x⋆ k

0
e quindi, tenendo conto dell’ipotesi (iii) si ha:
kxk+1 − x⋆ k ≤ µLkxk − x⋆ k2 . (2.26)
Poiché si è assunto xk ∈ B(x⋆ , ε) e si è scelto ε < 1/µL, dalla (2.26) segue
kxk+1 − x⋆ k ≤ µLkxk − x⋆ k2 ≤ µLεkxk − x⋆ k < kxk − x⋆ k. (2.27)
Ciò implica xk+1 ∈ B(x⋆ , ε) e di conseguenza, per induzione, si ha xk ∈ B(x⋆ , ε) per

ogni k.
Applicando ripetutamente la (2.27) si ha anche:
kxk − x⋆ k ≤ (µLε)k kx0 − x⋆ k,
47
da cui segue, essendo µLε < 1, che xk → x⋆ . La (2.26) implica allora che la rapidità di
convergenza è quadratica.
Osservazione. Il metodo di Newton presenta anche una interessante proprietà di

invarianza rispetto alla scalatura delle variabili.
Supponiamo di di effettuare un cambio di variabili del tipo
y = Tx
dove T è una matrice invertibile.

Nel nuovo spazio di variabili la funzione da minimizzare, il suo gradiente ed Hessiano
diventano:
f˜(y) = f (T −1 y), ∇f˜(y) = T −1 ∇f (T −1 y), ∇2 f˜(y) = T −1 ∇2 f (T −1 y)T −1 .
Una iterazione del metodo di Newton rispetto al nuovo vettore di variabili y assume la
seguente forma:
yk+1 = yk − ∇2 f˜(yk )−1 ∇f˜(yk ) = yk − T ∇2 f (T −1 yk )−1 T T −1 ∇f (T −1 yk ).
Se dal punto yk+1 si ritorna allo spazio delle variabili x si ha:
xk+1 = T −1 yk+1 = T −1 yk − ∇2 f (T −1 yk )−1 ∇f (T −1 yk ) = xk − ∇2 f (xk )−1 ∇f (xk ),
che coincide con il punto fornito dalla iterazione del metodo di Newton fatta diretta-
mente nello spazio delle xk .
2.4.4.2 Modifiche globalmente convergenti del metodo di Newton
La precedente Proposizione 2.4.8 mette in evidenza sia i pregi e sia i difetti del metodo
di Newton. Infatti da una parte ci indica che questo metodo ha in pratica la migliore
rapidità di convergenza, dall’altra però, mostra che nella sua forma pura, non può essere
utilizzato come algoritmo di minimizzazione globalmente convergente. Infatti ci sono i
seguenti problemi da affrontare:
- ∇2 f (xk ) può essere singolare e, quindi, la direzione di Newton può non essere
definita in xk ;
- il punto iniziale x0 può non appartenere all’insieme B(x⋆ ; ε) e, di conseguenza, la

successione prodotta dal metodo di Newton può non convergere;
- la Proposizione 2.4.8 mostra che il metodo di Newton converge a partire da un

intorno di un qualsiasi punto stazionario in cui ∇2 f (xk ) non è singolare, quindi
si può avere convergenza verso massimi locali.
48
Un argomento importante nel campo dell’ottimizzazione non vincolata è quello di defi-
nire degli algoritmi di minimizzazione che superino le precedenti difficoltà, e che quindi
siano globalmente convergenti pur preservando contemporaneamente le buone caratte-
ristiche di rapidità di convergenza del metodo di Newton. In particolare è utile dare la
seguente definizione:
Definizione 2.4.9 Sia f due volte continuamente differenziabile e supponiamo che

l’insieme di livello L0 = {x ∈ Rn : f (x) ≤ f (x0 )} sia compatto. Diremo che l’algoritmo
definito dall’iterazione:
xk+1 = xk + sk , k = 0, 1 . . .
(con sk = 0 se e solo se ∇f (xk ) = 0), è una modifica globalmente convergente del
metodo di Newton se valgono le seguenti proprietà:
(i) se {xk } è infinita ogni punto di accumulazione di {xk } è un punto stazionario di

f appartenente a L0 ;
(ii) nessun punto di accumulazione di {xk } è un punto di massimo locale di f ;
(iii) se {xk } converge ad un punto di minimo locale x⋆ di f e ∇2 f (x) soddisfa le

ipotesi della proposizione 2.4.1, esiste un k⋆ tale che, per ogni k ≥ k ⋆ si ha:
sk = −[∇2 f (xk )]−1 ∇f (xk ).
La maggior delle modifiche globalmente convergenti del metodo di Newton proposte in

letteratura ricadono nelle seguenti due classi di metodi:
- metodi che utilizzano ricerche unidimensionali;
- metodi della regione di confidenza (trust region).
- Metodi che utilizzano ricerche unidimensionali
Uno dei modi più immediati per realizzare una modifica globalmente convergente del
metodo di Newton è quello di far riferimento ai criteri di convergenza globale descritti
precedentemente.
Seguendo questa impostazione, il primo passo da fare è quello di introdurre di nuovo

il parametro scalare αk che definisce il passo lungo la direzione (ciò equivale a porre
sk := αk dk nella Definizione 2.22). Il secondo è quello di perturbare la direzione di
Newton se non soddisfa le condizioni di convergenza. In particolare si può stabilire il
seguente risultato.
49
Proposizione 2.4.10 Sia f due volte continuamente differenziabile e supponiamo che
l’insieme di livello L0 = {x ∈ Rn : f (x) ≤ f (x0 )} sia compatto. L’algoritmo definito
dall’iterazione:
xk+1 = xk + αk dk , k = 0, 1 . . . ,
è una modifica globalmente convergente del metodo di Newton se valgono le seguenti
proprietà:
(i) il passo αk viene calcolato utilizzando il metodo di Armijo assumendo come valore
di prova iniziale a = 1;
(ii) la direzione dk soddisfa le condizioni (iii) di Proposizione 2.4.1 e (i)-(ii) di

Proposizione 2.4.3;
(iii) se {xk } converge ad un punto di minimo locale x⋆ di f (x) e ∇2 f (x) soddisfa le

ipotesi della Proposizione 2.4.8, esiste un k⋆ tale che, per ogni k ≥ k⋆ si ha:
dk = −[∇2 f (xk )]−1 ∇f (xk ).
Il risultato precedente, mentre definisce esattamente il modo di calcolare il passo αk ,

lascia abbastanza libertà nella scelta della direzione di ricerca dk . In letteratura sono
stati proposti vari criteri per calcolare dk in maniera tale da soddisfare le condizioni
(iii) di Proposizione 2.4.1 e (i)-(ii) di Proposizione 2.4.3;
Uno dei modi più semplici di determinare una direzione dk che permetta di definire
una modifica globalmente convergente del metodo di Newton, è quella di utilizzare
la direzione dell’antigradiente quando la direzione di Newton non soddisfa opportune
condizioni. In particolare è possibile definire il seguente schema che fornisce una dk che
soddisfa le condizioni (iii) di Proposizione 2.4.1 e (i)-(ii) di Proposizione 2.4.3;
Modifica della direzione di Newton
• Dati: c1 > 0, c2 > 0, c3 > 0, q1 > 0, q2 ≥ 2 e q3 ≥ 3.
• Se vale una delle seguenti relazioni:

Det(∇2 f (xk )) ≤ c1 k∇f (xk )kq1 ,

h i−1
−∇f (xk )′ ∇2 f (xk ) ∇f (xk ) > −c3 k∇f (xk )kq3 ,
h i−1 q2
2
∇ f (xk ) ∇f (xk )
> c2 k∇f (xk )k ,
si pone dk = −∇f (xk );

−1
• altrimenti si pone dk = − ∇2 f (xk )

∇f (xk ).
50
- Metodi della regione di confidenza (Trust Region)
In questa classe di metodi si determina contemporaneamente sia la direzione e sia l’am-

piezza dello spostamento lungo questa la direzione. Analogamente al metodo di Newton
puro, i metodi Trust Region determinano, ad ogni iterazione, un vettore sk minimiz-
zando il modello quadratico φk (s) della funzione obiettivo f . A differenza del metodo
di Newton questa minimizzazione non viene effettuata su tutto Rn ma solo su una
regione sferica di centro xk in cui si suppone che il modello quadratico sia una buona
approssimazione di f .
Molti algoritmi di tipo Trust Region sono stati proposti in letteratura, lo schema
generale iniziale di questa classe di metodi è il seguente.
Schema generale di un algoritmo Trust Region
• Dati a0 > 0, c ∈ (0, 1). Sia

1
φk (s) = f (xk ) + ∇f (xk )′ s + s′ ∇2 f (xk )s.
2
• Sia sk ∈ Rn il minimo di
min φk (s) (2.28)

ksk ≤ ak .
• Si controlla se φk (s) nella regione ksk ≤ ak è una buona approssimazione di f ;
• questo controllo viene effettuato confrontando la riduzione effettiva
∆fk (sk ) = f (xk ) − f (xk + sk )
e la riduzione prevista
∆φk (sk ) = f (xk ) − φk (sk );
che si hanno passando da xk a xk + sk ;
• se ∆fk (sk ) < c∆φk (sk ) allora si diminuisce ak scegliendo ak ∈ [γ1 ak , γ2 ak ],

si risolve nuovamente il problema (2.28) e si determina un nuovo sk ;
• se ∆fk (sk ) ≥ c∆φk (sk ) si pone:
xk+1 = xk + sk ;
se inoltre ∆fk (sk ) è “abbastanza” più grande di ∆qk (sk ) allora all’iterazione
successiva si può aumentare ak .
Dal punto di vista geometrico si può osservare che:
- se ak → 0 allora la direzione di sk tende alla direzione di −∇f (xk );
51
- se ∇2 f (xk ) è definita positiva allora per valori crescenti di ak la direzione di sk
tende alla direzione di −[∇2 f (xk )]−1 ∇f (xk ).
Quindi, l’algoritmo Trust Region fornisce una spostamento che può essere visto come
una combinazione tra uno spostamento lungo l’antigradiente, che tende a garantire la
convergenza globale, ed uno spostamento lungo la direzione di Newton che cerca di
assicurare una buona rapidità di convergenza.
Per quanto riguarda le proprietà di convergenza dello schema di algoritmo precedente-
mente descritto si ha il seguente risultato.
Proposizione 2.4.11 Sia f due volte continuamente differenziabile e sia l’insieme di

livello L0 = {x ∈ Rn : f (x) ≤ f (x0 )} compatto. L’algoritmo Trust Region precedente-
mente descritto è una modifica globalmente convergente del metodo di Newton.
Inoltre, se la successione di punti prodotta dall’algoritmo converge ad un punto x⋆ allora
la matrice Hessiana in x⋆ è semidefinita positiva.
Dal risultato precedente si può osservare che i metodi Trust Region presentano proprietà
più forti rispetto alle modifiche del metodo di Newton viste nel paragrafo precedente.
Infatti, come mostra la precedente proposizione, essi convergono a punti che soddisfano
le condizioni necessarie del secondo ordine.
Purtroppo il prezzo da pagare per ottenere queste buone proprietà di convergenza è
alto. Infatti ad ogni passo è necessario risolvere esattamente il problema (2.28) e questo
è estremamente oneroso specialmente nel caso in cui la matrice Hessiana ∇2 f (xk ) non
è definita positiva.
Allo scopo di superare questa difficoltà si sono proposti dei metodi Trust Region che
risolvono solo in maniera approssimata il sottoproblema (2.28).
Questi metodi sono tipicamente più efficienti dal punto di computazionale rispetto
all’algoritmo originario ma la maggior parte di loro perde la proprietà di convergere
a punti che soddisfano le condizioni necessarie del secondo ordine (cioè convergono ai
punti stazionari).
2.4.4.3 Metodo di Newton “inesatto”
Nel metodo di Newton per determinare la direzione di ricerca è necessario risolvere

esattamente ad ogni iterazione il seguente sistema lineare
∇2 f (xk )d + ∇f (xk ) = 0. (2.29)
Per problemi di dimensioni elevate la risoluzione esatta del sistema (2.29) può essere
troppo oneroso se non addirittura praticamente impossibile. Quindi un problema im-
portante da affrontare è quello di capire se è possibile, risolvendo approssimativamente
52
il sistema (2.29), ottenere una direzione che permetta di definire un algoritmo di mini-
mizzazione con una buona rapidità di convergenza. Una interessante risposta a questa
questione è data dalla seguente proposizione.
Proposizione 2.4.12 Sia f due volte continuamente differenziabile e sia {xk } la suc-
cessione generata dall’iterazione
xk+1 = xk + dk , k = 0, 1, . . . ,
dove dk è una soluzione approssimata del sistema lineare (2.29), cioè un vettore che
soddisfa la (2.29) a meno di un residuo rk dato da:
rk = ∇2 f (xk )d + ∇f (xk ).
Se la successione di punti prodotta dall’algoritmo converge ad un punto x⋆ , se sono

soddisfatte le ipotesi della Proposizione 2.4.8 e se
krk k
lim = 0,
k→∞ k∇f (xk )k
allora la successione {xk } converge superlinearmente ad x⋆ .
Il risultato precedente mostra che, se nel calcolare la direzione di Newton si commette

un errore che tende a zero “abbastanza“ velocemente all’avvicinarsi ad un punto sta-
zionario, si continua a mantenere una buona rapidità di convergenza. Infatti la rapidità
di convergenza superlineare, sebbene inferiore a quella quadratica, assicura comunque
un comportamento molto soddisfacente dal punto di vista pratico.
La Proposizione 2.4.12 è la base per definire quella classe di modifiche globalmente
convergenti del metodo di Newtopn dette metodi di Newton troncato . Tali metodi
permettono di affrontare e risolvere efficientemente problemi a grandi dimensioni e
saranno brevemente descritti in seguito nella sezione riguardante i metodi delle direzioni
coniugate.
2.4.4.4. Metodi di globalizzazione non monotoni
Recentemente un nuovo approccio per definire delle nuove modifiche globalmente con-
vergenti del metodo di Newton è stato proposto in letteratura. Questo nuovo filone è
nato dall’osservazione il metodo di Newton nella sua forma pura (2.4.2) è frequentemen-
te molto più efficiente delle varie modifiche proposte. Per esempio si può considerare
la seguente funzione
f (x) = 108 (x2 − x21 )2 + (1 − x1 )2 ,
e come punto di partenza x0 = (−1.2, 1). In questo caso il metodo di Newton puro
converge in 3 iterazioni mentre una delle più efficienti modifiche convergenti del metodo
53
di Newton (implementata nella routine E04LBF della libreria NAG) converge in 1631
iterazioni (e 2447 calcoli di funzione).
Una della cause di questa differenza di efficienza fra il metodo di Newton puro e le sue
modifiche globalmente convergenti è il fatto che quest’ultime producono una successione
di punti a cui corrispondono necessariamente valori monotonicamente descrescenti
della funzione obiettivo. Questa diminuzione del valore della funzione obiettivo ad ogni
iterazione è ottenuta
- controllando il passo αk lungo la direzione di ricerca nell’approccio che utilizza le

ricerche unidimensionali;
- controllando il raggio ak della regione di confidenza nell’approccio trust region.
In entrambi i casi si è spesso (specialmente quando si vuole minimizzare funzioni molto

non lineari) costretti ad scegliere valori “piccoli” per il passo αk o per il raggio ak
e, quindi, ad effettuare spostamenti alquanto diversi da quelli che farebbe il metodo
di Newton puro. Questo fenomeno porta sicuramente a conseguenze negative in un
intorno di un punto stazionario che soddisfa le ipotesi della Proposizione 2.4.8 Infatti
questa proposizione assicura che esiste un intorno (di cui non si sa a priori l’estensione
e che non è detto che sia piccolo) in cui il metodo di Newton puro converge ed ha una
rapidità di convergenza quadratica. Perciò, in questo intorno, l’imporre una decrescita
monotona della funzione obiettivo può essere una richiesta contrastante con l’efficienza
del metodo, perché potrebbe portare a non effettuare lo stesso spostamento del metodo
di Newton puro.
Per superare le difficoltà descritte, recentemente sono stati proposti degli algoritmi
che, pur assicurando la convergenza globale, evitano però di richiedere che i valori della
funzione obiettivo diminuiscano ad ogni iterazione. La maggior parte di questi nuovi
algoritmi ricadono nella classe delle modifiche globalmente convergenti di Newton che
utilizzano le ricerche unidimensionali.
Uno dei primi metodi proposti si basa su un criterio accettazione del passo αk che
permette che la funzione possa aumentare durante un numero di passi prefissato. In
particolare si può definire il seguente algoritmo.
Criterio di Armijo non monotono
• Dati a > 0, δ ∈ (0, 1), γ ∈ (0, 1/2) ed un intero M .
• Si sceglie αk = δh a dove h è il più piccolo intero nonnegativo tale che:
f (xk + αk dk ) ≤ max [f (xk−j )] + γαk ∇f (xk )′ dk .

0≤j≤M
Si può notare che il precedente criterio consente che f (xk+1 ) possa essere maggiore
di f (xk ) e, perciò, che possa essere accettato più facilmente il passo unitario lungo la
direzione di Newton.
54
Si può dimostrare che se si utilizza il precedente criterio di Armijo non monotono (con
a = 1) con una direzione di ricerca che soddisfa le condizioni (iii) di Proposizione
2.4.1 e (ii) di Proposizione 2.4.3 si ottiene un metodo che è una modifica globalmente
convergente del metodo di Newton.
Benché l’utilizzazione di una ricerca unidimensionale di tipo nonmonotono in una modi-
fica del metodo di Newton abbia fatto migliorare i risultati numerici rispetto ai metodi
monotoni, si è notato che ulteriori miglioramenti possono essere ottenuti “concedendo”
ancora più libertà al metodo di Newton. Per esempio ottimi risultati possono essere
ottenuti se non si effettuano controlli sul valore della funzione obiettivo per un numero
prefissato di iterazioni, quindi scegliendo sempre il passo unitario in queste iterazioni.
Questo comportamento sembra indicare che è utile cercare di utilizzare il più possibile
il metodo di Newton puro anche se non si è nella sua regione di convergenza. Una
possibile spiegazione di questo fatto è che, in generale, la direzione di ricerca contiene
più informazioni sul problema rispetto ai criteri di scelta dello spostamento. Infatti:
- la direzione di Newton utilizza ∇2 f (xk ) e ∇f (xk ) che sono equivalenti a n(n+3)/2
calcoli di funzioni;
- le tecniche che determinano gli spostamenti αk lungo la direzione di ricerca si

basano su singoli calcoli di funzione.
Però, dall’altra parte, una scelta “sbagliata” del passo αk influenza pesantemente
l’entità dello spostamento effettuato dall’algoritmo.
Quindi in base alle precedenti considerazioni, una possibilità per sviluppare dei nuovi
algoritmi di ottimizzazione più efficienti è quella di proporre dei metodi di globalizza-
zione che determinino il passo αk cercando di sfruttare più informazioni sul problema.
Utilizzando non solamente i valori della funzione obiettivo ma anche altre grandezze
che possano caratterizzare il comportamento dell’algoritmo.
2.4.5 Metodi Quasi-Newton

I metodi Quasi-Newton nascono dall’esigenza di definire dei metodi efficienti di otti-
mizzazione non vincolata senza richiedere la conoscenza delle derivate seconde della
funzione obiettivo. Tali metodi infatti presentano le seguenti caratteristiche:
- utilizzano soltanto la conoscenza delle derivate prime;
- rappresentano delle approssimazioni del metodo di Newton che conservano (sotto

appropriate ipotesi) una rapidità di convergenza superlineare.
Da quanto visto nella sezione precedente, il metodo di Newton è dato dalla seguente
iterazione:
xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ).
Un iterazione di un generico metodo Quasi-Newton è descritta da:
xk+1 = xk − αk Bk−1 ∇f (xk ), (2.30)
55
in cui Bk è una matrice aggiornata iterativamente ed αk è, al solito, lo spostamento
lungo la direzione di ricerca. Affinché un metodo descritto dall’iterazione (2.30) possa
ereditare l’ottima rapidità di convergenza del metodo di Newton è naturale richiedere
che la matrice Bk approssimi (in un qualche senso) la matrice Hessiana.
La scelta più immediata è quella di richiedere che le matrici Bk siano delle appros-
simazioni consistenti della matrice Hessiana, cioè che abbiano la proprietà che, se la
successione di punti {xk } converge ad un punto stazionario x∗ (con la matrice Hessiana
non singolare), allora:
lim kBk − ∇2 f (x∗ )k = 0.
k→∞
I metodi del tipo (2.30) che utilizzano matrici che godono della precedente proprietà
sono detti metodi tipo-Newton.
La richiesta che la successione di matrici {Bk } siano delle approssimazioni consistenti
della matrice Hessiana può essere alquanto pesante e, ai fini di mantere una rapidità
di converganza superlineare, può essere indebolita in maniera significativa. Infatti ci si
può ispirare al seguente risultato.
Proposizione 2.4.13 Sia f (x) due volte continuamente differenziabile, sia {Bk } una
successione di matrici non singolari, sia {xk } data da:
xk+1 = xk − Bk−1 ∇f (xk )
e sia {xk } convergente al punto x∗ dove ∇2 f (x∗ ) è non singolare. Allora {xk } converge
superlinearmente ad x∗ e risulta ∇f (x∗ ) = 0 se e solo se:
Bk − ∇2 f (x∗ ) (xk+1 − xk )

lim = 0.
k→∞ kxk+1 − xk k
Quindi, il risultato precedente indica che, al fine di avere una buona rapidità di con-
vergenza, una matrice B̃ può essere considerata una buona “approssimazione” di ∇2 f
se
B̃(xk+1 − xk ) ≈ ∇2 f (xk )(xk+1 − xk ),
che è una relazione vettoriale e, perciò, molto più debole della richiesta che B̃ ≈ ∇2 f (xk )
che è una relazione matriciale.
Ricordando i teoremi della media, si ha che se il punto xk+1 è sufficientemente vicino
a xk allora:
∇2 f (xk )(xk+1 − xk ) ≈ ∇f (xk+1 ) − ∇f (xk ),
Quindi una matrice B̃ può essere considerata una “approssimazione” di ∇2 f se soddisfa
la condizione:
B̃(xk+1 − xk ) ≈ ∇f (xk+1 ) − ∇f (xk ).
In linea con la precedente considerazione, i metodi Quasi-Newton producono ad ogni
iterazione una matrice Bk+1 che soddisfa la sequente equazione di Quasi-Newton:
Bk+1 (xk+1 − xk ) = ∇f (xk+1 ) − ∇f (xk ). (2.31)
56
Un modo equivalente per giustificare il fatto di richiedere le matrici prodotte soddisfino
l’equazione Quasi-Newton (2.31) è quello di far riferimento nuovamente al modello
quadratico. Infatti è facile verificare che se la funzione obiettivo fosse una funzione
quadratica, con matrice Hessiana Q, si avrebbe:
Q(xk+1 − xk ) = ∇f (xk+1 ) − ∇f (xk ).
Quindi l’imporre l’equazione Quasi-Newton, equivale a richiedere che la matrice pro-

dotta soddisfi una relazione verificata dalla matrice Hessiana nel caso in cui la funzione
obiettivo fosse quadratica.
Come accennato nei metodi Quasi-Newton viene prodotta una sequenza di matrici
{Bk }. In particolare, alla generica k-esima iterazione, la matrice Bk+1 viene determi-
nata aggiornando Bk con dei termini di correzione in modo tale che la matrice ottenuta
soddisfi l’equazione Quasi-Newton riferita ai punti xk+1 e xk , cioè:
Bk+1 = Bk + ∆Bk ,
γk = (Bk + ∆Bk ) δk . (2.32)
dove, per semplicità si pone:
δk = xk+1 − xk , γk = ∇f (xk+1 ) − ∇f (xk ).
Le formule del tipo (2.32), in cui si cerca di approssimare la matrice Hessiana, vengono
dette formule dirette.
Un approccio alternativo nell’ambito dei metodi Quasi-Newton è quello di produrre una
matrice Hk+1 che cerchi di approssimare l’inversa della matrice Hessiana. In questo
caso la formula Quasi-Newton da soddisfare è la seguente:
Hk+1 (∇f (xk+1 ) − ∇f (xk )) = xk+1 − xk .
Coerentemente, l’iterazione di un metodo Quasi-Newton che segue questa impostazione

è definita da
xk+1 = xk − αk Hk ∇f (xk ),
e la matrice Hk+1 è ottenuta utilizzando le seguenti formule, dette formule inverse:
Hk+1 = Hk + ∆Hk ,
(Hk + ∆Hk ) γk = δk .
I vari metodi Quasi-Newton finora proposti differiscono fra loro essenzialmente per le
formule usate nella definizione della matrici di aggiornamento ∆Bk o ∆Hk . La loro
carattereristica comune è che sia ∆Bk che ∆Hk vengono ottenuti con la sola valu-
tazione del gradiente nel punto xk+1 e quindi senza un eccessivo aumento del costo
computazionale rispetto ad un qualsiasi algoritmo tipo gradiente.
Un esempio di una formula di aggiornamento diretta particolarmente utilizzata è la
seguente:
γk γ T Bk δk δT Bk
Bk+1 = Bk + T k − T k ,
δk γk δk Bk δk
57
mentre, riguardo le formule di aggiornamento inverse, un esempio particolarmente
significativo è il seguente:
δk δkT Hk γk γkT Hk
Hk+1 = Hk + − .
δkT γk γkT Hk γk
Per quanto riguarda la scelta del passo αk , motivazioni di sia di tipo teorico che di
tipo pratico indicano che, nei metodi Quasi-Newton, la tecnica più adeguata è quella
di calcolare il passo in modo da soddisfare le condizioni di Wolfe (si veda la Sezione
2.4.2).
- Metodi Quasi-Newton a memoria limitata
I metodi Quasi-Newton a memoria limitata sono stati proposti per estendere l’approc-
cio dei metodi Quasi-Newton anche a problemi a grandi dimensioni. L’idea di questi
nuovi metodi è quella di costruire una direzione che approssimi la direzione di Newton
utilizzando solamente le informazioni ottenute nelle ultime iterazioni. Tali informazioni
vengono memorizzate utilizzando un numero limitato di vettori.
Un metodo a memoria limitata, che si è rivelato particolarmente efficiente, è quello che
viene chiamato metodo BFGS a memoria limitata. Questo metodo è molto simile al
metodo BFGS standard, la sola differenza è nella matrice di aggiornamento. Infatti, se
si sceglie B0 = I, al posto di
k−1
X γi γi′ Bi δi δi′ Bi
Bk = I + [ − ′ ],
i=0
δi′ γi δi Bi δi
si utilizza (per k ≥ m + 1)
k−1
X γi γi′ Bi δi δi′ Bi
B̃k = I + [ − ′ ].
i=k−m−1
δi′ γi δi Bi δi
la direzione dk = −B̃k−1 ∇f (xk ) si può calcolare eseguendo solamente pochi prodotti

scalari.
I risultati numerici ottenuti con questi metodi hanno mostrato che è sufficiente scegliere
m = 5 per ottenere risultati comparabili con il metodo BFGS completo. Un tale valore
per m permette di risolvere efficientemente anche problemi a grosse dimensioni. Inoltre
l’esperienza numerica sembra indicare che, sorprendentemente, il comportamento di
questo metodo non migliora in maniera significativa per valori più grandi della memoria
m. Tale comportamento continua a presentarsi anche al crescere delle dimensioni dei
problemi da minimizzare.
Per quanto riguarda le proprietà teoriche del metodo BFGS a memoria limitata, si
è provato che questo metodo è globalmente e linearmente convergente per funzioni
convesse.
58
2.4.6 Metodo del gradiente coniugato
Il metodo del gradiente coniugato è stato studiato e sviluppato per affrontare principal-
mente problemi di ottimizzazione non vincolata a grosse dimensioni. Per tali problemi
non è ammissibile far uso di operazioni matriciali e richiedere la conoscenza della ma-
trice Hessiana. Inoltre è necessario ridurre il più possibile il numero di vettori utilizzati
dall’algoritmo per limitare il più possibile l’occupazione di memoria del calcolatore.
Quindi il metodo maggiormente applicabile per questa classe di problemi sembrereb-
be essere il metodo del gradiente. Purtroppo, per quanto detto nella sezione 2.4.3, le
versioni tradizionali di tale metodo possono essere alquanto inefficienti e quindi non
utilizzabili in pratica per risolvere problemi di ottimizzazione non vincolata a grosse
dimensioni.
Per cercare di avere una efficienza migliore rispetto al metodo del gradiente tradizio-
nale, il metodi di tipo gradiente coniugato prendono come punto di partenza il fatto di
approssimare una generica funzione obiettivo f (xk + d) con il suo modello quadratico
φk (d) (definito dalla (2.23) in Sezione 2.4.4) e di cercare di minimizzare questa funzio-
ne quadratica senza dover fare l’inversione della matrice Hessiana, come nel caso del
metodo di Newton.
Per affrontare questo sfida uno strumento essenziale sono le direzioni coniugate rispetto
alla matrice Hessiana di f (x).
- Direzioni coniugate
Definizione 2.4.14 Assegnata una matrice Q simmetrica, due vettori non nulli di , dj ∈
Rn si dicono coniugati rispetto a Q (oppure Q-coniugati) se risulta:
dTi Qdj = 0.
Dalla precedente definizione segue immediatamente la seguente proposizione.
Proposizione 2.4.15 Siano d0 , . . . , dm ∈ Rn vettori non nulli mutuamente coniu-

gati rispetto ad una matrice Q simmetrica definita positiva. Allora d0 , . . . , dm sono
linearmente indipendenti.
Dopo aver introdotto le direzioni coniugate si può ritornare al problema di voler mini-
mizzare, senza fare inversioni di matrici, una funzione quadratica del tipo:
1
f (x) = xT Qx + cT x, (2.33)
2
in cui Q è una matrice simmetrica definita positiva.
59
Se si conoscono n direzioni d0 , . . . , dn−1 coniugate rispetto a Q, si può effettuare la
seguente trasformazione dello spazio delle variabili:
n−1
X
x= αi di .
i=0
Nel nuovo spazio la funzione obiettivo assume la forma:

n−1 n−1
X 1 2 T

f˜(α) = αi di Qdi + αi dTi ci = f˜i (αi ),
X
i=0
2 i=0
cioè diventa la somma di n funzioni quadratiche ciascuna di una sola variabile scalare
αi .
Quindi utilizzando n direzioni coniugate si può trasformare un problema di ottimiz-
zazione su Rn in n problemi separati di ottimizzazione su R. Questo fa capire che,
utilizzando le direzioni coniugate, si può determinare il minimo di una funzione qua-
dratica strettamente convessa in un numero finito di iterazioni. Più formalmante si ha
il seguente risultato.
Proposizione 2.4.16 Sia f (x) data dalla (2.33) e sia d0 , d1 , . . . , dn−1 un insieme di
vettori non nulli e mutuamente coniugati rispetto a Q. Si definisca l’algoritmo
in cui x0 ∈ Rn è un punto iniziale arbitrario ed αk è scelto in modo da minimizzare

f (x) lungo dk , ossia:
∇f (xk )T dk (Qxk + c)T dk

αk = − = − .
dTk Qdk dTk Qdk
Allora esiste m ≤ n − 1 tale che xm+1 coincide con il punto di minimo x∗ di f (x).
- Metodo del gradiente coniugato nel caso quadratico
Da quanto visto nella sezione precedente una funzione quadratica strettamente convessa
può essere minimizzata molto efficientemente se si conoscono n direzioni coniugate
rispetto alla sua matrice Hessiana. Quindi il problema si sposta a quello di trovare in
maniera “semplice” delle direzioni coniugate.
Questo problema, sempre nel caso di funzioni quadratiche, può essere risolto utilizzando
il metodo del gradiente coniugato che fornisce, attraverso un processo iterativo, delle
direzioni coniugate.
60
Sia x0 ∈ Rn un punto arbitrario allora ogni iterazione del metodo del gradiente
coniugato è data da:
 −∇f (xk ), se k = 0,

dk =
−∇f (xk ) + βk dk−1 , se k ≥ 1;

∇f (xk )T Qdk−1
βk =
dTk−1 Qdk−1
xk+1 = xk + αk dk ;
∇f (xk )T dk
αk = −
dTk Qdk
Per tale metodo si può provare il seguente risultato.
Proposizione 2.4.17 Sia data la funzione

1
f (x) = xT Qx + cT x.
2
(a) Se la matrice Q è definita positiva allora l’algoritmo del gradiente coniugato pro-
duce delle direzione d0 , . . . , dk che sono Q-coniugate e determina, in al più n
iterazioni, il punto di minimo x∗ della funzione f (x).
(b) Se la matrice Q è semidefinita positiva e se la funzione f (x) ha un punto di mi-

nimo allora l’algoritmo del gradiente coniugato produce delle direzione d0 , . . . , dk
che sono Q-coniugate e determina, in al più n − 1 iterazioni, un punto di minimo
x∗ della funzione f (x).
- Metodo del gradiente coniugato nel caso non quadratico
Il metodo del gradiente coniugato, come descritto nel paragrafo precedente, permette
di trovare il minimo di un funzione quadratica strettamente convessa senza effettuare
inversioni di matrici. Se si vuole utilizzare questo metodo per minimizzare funzioni
generali a grandi dimensioni, bisogna risolvere i seguenti problemi:
- il calcolo del passo αk : in generale non è possibile nel caso di funzioni non
quadratiche calcolare il passo αk minimizzando esattamente la funzione obiettivo.
- Il calcolo dello scalare βk : infatti nella espressione di βk compare esplicitamente

la matrice Hessiana della funzione obiettivo e quindi si richiedono operazioni
matriciali che limitano fortemente le dimensioni del problema da minimizzare.
61
Il primo dei due ostacoli viene superato determinando il passo αk utilizzando uno degli
algoritmi di ricerca unidimensionale viste nella sezione 2.4.2, in particolare quello che
si avvivicina di più ad una minimizzazione esatta lungo alla direzione di ricerca.
Per quanto riguarda il secondo ostacolo da risolvere, si può notare che, nel caso quadra-
tico, si possono ricavare diverse espressioni di βk che sono tutte fra di loro equivalenti.
In alcune di queste non compare più la matrice Hessiana della funzione obiettivo e,
quindi, possono essere utilizzate nel caso di problemi a grandi dimensioni. Tuttavia è
da notare che queste espressioni diverse di βk sono equivalenti solo nel caso quadratico
e, perciò, danno luogo ad algoritmi diversi per il calcolo della direzione nel caso non
quadratico. In definitiva un esempio di un metodo del gradiente coniugato nel caso non
quadratico può essere descritto nella seguente maniera.
- dato un qualsiasi punto iniziale x0 ∈ Rn allora per ogni iterazione k si pone:

 −∇f (xk ), se k = 0,

dk =
−∇f (xk ) + βk dk−1 , se k ≥ 1;

- dove
- lo scalare αk viene usualmente calcolato le utilizzando le condizioni forti
di Wolfe (si veda la Sezione 2.4.2) oppure altre condizioni che tendono ad
assicurare buone proprità alla successiva direzione;
- lo scalare βk è dato normalmente da una delle seguenti due formule (equi-
valenti nel caso di funzioni quadratiche):
k∇f (xk )k2 ∇f (xk )T (∇f (xk ) − ∇f (xk−1 ))
βk = , βk = .
k∇f (xk−1 )k2 k∇f (xk−1 )k2
Grazie alla utilizzazione di particolari tecniche di per il calcolo del passo αk si riesce
a garantire ai matodi del gradiente coniugato soddisfacenti proprietà di convergenza
globale.
Per quanto riguarda la rapidità di convergenza di questi metodi, la maggior parte
di questi dei risultati proposti riguardano il caso in cui le ricerche unidimensionali
sono esatte. Il risultato più significativo stabilisce che, in un intorno di un punto
stazionario che soddisfa le condizioni della Proposizione 2.4.8, la sequenza di punti
prodotta soddisfa la seguente relazione:
kxk+n − x∗ k = O(kxk − x∗ k2 ).
Cioè, al meglio, questi metodi presentano una rapidità di convergenza quadratica ogni
n passi. Questo riflette il fatto che n iterazioni di un metodo del gradiente coniugato
permettono di minimizzare una funzione quadratica strettamente convessa e, quindi,
equivalgono approssimativamente ad una iterazione del metodo di Newton.
62
2.4.7 Metodi di Newton troncato
I metodi di Newton Troncato appartengono alla classe delle modifiche globalmente

convergenti del metodo di Newton e sono particolarmente adatti per affrontare problemi
a grandi dimensioni.
Tali metodi si basano sul fatto che, se la matrice Hessiana ∇2 f (xk ) è definita po-
sitiva allora, determinare la direzione di Newton equivale a minimizzare la funzione
quadratica:
1
φk (d) = f (xk ) + ∇f (xk )′ d + dT ∇2 f (xk )d
2
cioè a trovare una direzione tale che
∇φk (d) = ∇2 f (xk )d + ∇f (xk ) = 0. (2.34)
La cosa importante è che la Proposizione 2.4.12 indica che una “buona” direzione dk può
essere ottenuta minimizzando in maniera approssimata la funzione φk (d). Infatti, per
avere un algoritmo superlinearmente convergente, è sufficiente ottenere una direzione
dk tale che:
k∇φk (dk )k ≤ ηk k∇f (xk )k (2.35)
con ηk → 0. Il soddisfare la condizione (2.35) equivale al fatto che la direzione dk
soddisfa il sistema (2.34)) a meno di un errore rk = k∇φk (dk )k per cui vale:
krk k k∇φk (dk )k

lim = lim = 0.
k→∞ k∇f (xk )k k→∞ k∇f (xk )k
Nella maggior parte dei metodi di Newton troncato il calcolo della direzione dk viene
effettuato applicando il metodo del gradiente coniugato (vedere sezione 2.4.6) per mi-
nimizzare in maniera approssimata la funzione quadratica φk (d). Tale scelta presenta
i seguenti vantaggi:
- in molti casi una direzione dk che soddisfa un criterio del tipo (2.35) può essere
ottenuta con questo metodo in poche iterazioni;
- se k∇f (xk )k è grande il gradiente coniugato fornisce una dk che tende a coincidere
con l’antigradiente della funzione obiettivo, mentre se k∇f (xk )k è piccola la dk
calcolata tende a coincidere con la direzione di Newton; quindi il metodo del
gradiente coniugato fornisce una direzione che impone la convergenza globale se
si è distanti da un punto stazionario, mentre, se si è vicini, produce una direzione
che assicura una buona rapidità di convergenza;
- se ∇2 f (xk ) non è definita positiva, la minimizzazione di φk (d) con il gradiente

coniugato usualmente si arresta fornendo una direzione di discesa a curvatura
negativa.
63
Il metodo di Newton Troncato, proposto per primo in letteratura, può essere descritto
dal seguente schema.
- dato un qualsiasi punto iniziale x0 ∈ Rn allora per ogni iterazione k si pone:
- dove
- lo scalare αk viene calcolato con Criterio di Armijo ponendo a = 1 (vedere

la Sezione 2.4.2);
- direzione dk è calcolata dal seguente algoritmo:
P0: dati ε1 > 0 ε2 > 0, si pone p0 = 0, s0 = −∇φk (p0 ) = −∇f (xk ) e i = 0.

Se sT0 ∇2 f (xk )s0 < ε1 ks0 k2 si pone dk = −∇f (xk ) e Stop;
P1: si pone
∇φk (pi )T si
pi+1 = pi + αi si ; αi = −
sTi ∇2 f (xk )si
P2: se
1
k∇φk (pi+1 )k ≤ ε2 k∇f (xk )k
k+1
si pone dk = pi+1 e Stop; altrimenti si pone i = i + 1;
P3: si pone
∇φk (pi )T ∇2 f (xk )si−1

si = −∇φk (pi ) + βi si−1 , βi =
sTi−1 ∇2 f (xk )si−1
P4: se
sTi ∇2 f (xk )si < ε1 ksi |2
si pone dk = pi e Stop; altrimenti si torna a P1;
2.4.8 Metodi che non usano le derivate
Tutti i metodi descritti precedentemente si basano sulla conoscenza del gradiente della
funzione obiettivo. Come visto, il gradiente della funzione obiettivo ha giocato un ruolo
importante sia nell’individuazione di una direzione lungo la quale la funzione diminuisce
che nella determinazione di un efficiente spostamento da effettuare lungo una direzione
di discesa.
64
Purtroppo, varie classi di importanti problemi applicativi particolarmente complessi
possono essere modellizzati come problemi di ottimizzazione in cui non sono disponibili
le informazioni del primo ordine della funzione obiettivo e dei vincoli. Per esempio, nei
problemi di programmazione matematica che nascono nell’ambito della progettazione
ottima, non sono note le espressioni analitiche della funzione obiettivo o dei vincoli del
problema. In questi casi si possono ottenere delle approssimazioni dei valori di queste
funzioni attraverso dei complessi codici di simulazione o dei processi di misurazione.
La non conoscenza delle rappresentazioni analitiche delle funzioni che caratterizzano
questi particolari problemi di ottimo implica l’impossibilità di calcolarne le derivate
prime e, quindi, i rispettivi gradienti.
I valori delle derivate prime di una funzione posso essere approssimate con buona
precisione sfruttando la seguente relazione:
∂f (x) f (x + ηei ) − f (x)
≈ (2.36)
∂xi η
dove ei è il versore i-esimo (cioè un vettore che tutte le componenti uguali a zero con
l’eccezione della i-esima che è uguale a uno) e η è uno scalare sufficientemente piccolo.
Tuttavia questa possibilità non può essere sfruttata nella precedente classe di problemi
applicativi in quanto le valutazioni di funzione ottenute possono essere affette da errori
di approssimazione o di misura. Se si indica con ω1 e ω2 gli errori associati al calcolo
di f (x + ηei ) e f (x), si ottiene la seguente relazione:
(f (x + ηei ) + ω1 ) − (f (x) + ω2 ) ∂f (x) ω1 − ω2
≈ + ,
η ∂xi η
dove l’ultimo termine può assumere valori significativi (per il fatto che η deve essere
piccolo) e, quindi, rendere imprecisa la stima della derivata parziale di f rispetto a xi .
Da quanto detto, risulta evidente l’importanza dal punto di vista applicativo di stu-
diare e proporre algoritmi di ottimizzazione che usino solamente i valore della funzione
obiettivo e dei vicoli. Per poter avere buone proprietà proprità teoriche, tali metodi
devono essere in grado di sostituire le informazioni derivanti dalla conoscenza del gra-
diente che guidano la convergenza della sequenza dei punti prodotta da un algoritmo
di ottimizzazione.
Le componenti del gradiente forniscono una importante misura della sensibilità della
funzione al variare delle corrispondenti variabili (si veda l’equazione (2.36). Grazie a
questa caratteristica il gradiente di una funzione permette di determinare efficiente-
mente delle direzioni di ricerca.
Gli algoritmi che non usano le derivate determinano delle direzioni di discesa valutan-
do la funzione obiettivo su particolari insieme di direzioni. Molto frequentemente gli
insiemi di direzioni usate da tali algoritmi soddisfano la seguente assunzione.
Assunzione 2.4.1 L’insieme di direzioni d1 , d2 , . . . , dq , con kdi k = 1 per ogni i =

1, . . . , q, è tale che per ogni d ∈ Rn esistono degli scalari β1 , β2 , . . . , βq ∈ R+ tali che
d
X
d= βi di .
i=1
65
Esempi di direzioni che soddisfano la precedente assunzione sono i seguenti.
d1 = e1 , d2 = −e1 , d3 = e2 , d4 = −e2 , ... , d2n−1 = en , , d2n = −en ;

e
d1 = e1 , d2 = e2 , d3 = e3 , ... , dn = en , dn+1 = − ,
kek
dove e ∈ Rn è un vettore le cui componenti sono uguali a uno.

L’interesse di insieme di direzioni che soddisfano la precedente assunzione è descritto
nella seguente proposizione.
Proposizione 2.4.18 Sia d1 , d2 , . . . , dq un insieme di direzioni che soddisfa l’Assun-

zione 2.4.1 allora x̄ non è un punto stazionario se e solamente se esiste almeno una
direzione dh appartenente all’insieme considerato tale che
∇f (x̄)T dh < 0.
La precedente proposizione che garantisce che, in corrispondenza di un punto non sta-

zionario, almeno una delle direzioni di un insieme che soddisfa l’Assunzione 2.4.1 è di
discesa.
Identificata una direzione di discesa si deve affrontare il problema della scelta di un
passo efficiente αk da effettuare lungo questa direzione. Le tecniche di linesearch viste
precedentemente sfruttavano la conoscenza del gradiente. Tuttavia è possibile definire
tecniche con proprietà teoriche simili che utilizzano solamente i valori della funzione
obiettivo.
Un esempio di un criterio di questo tipo è costituito dalla seguente verrsione del criterio
Armijo che non utilizza il gradiente.
Criterio di Armijo senza derivate
• Dati x ∈ Rn , d ∈ Rn con kdk = 1, γ ∈ (0, 1).
• Si sceglie α > 0 tale che:
f (x + αd) ≤ f (x) − γα2

f (x + 2αd) > f (x) − γ(2α)2
A questo punto si sono introdotti tutti gli strumenti per riportare un esempio di un
algoritmo di minimizzazione che non usa le derivate.
66
Algoritmo che non use le derivate.
Dati: x0 ∈ Rn , d1 ∈ Rn , . . . , dq ∈ Rn , con kdk = 1, α̃10 > 0, . . . , α̃q0 > 0, γ ∈ (0, 1)

e k = 0;
Passo 1: si pone i = 1 e yk1 = xk ;
Passo 2: se f (yki + α̃k di ) ≤ f (yki )− γ(α̃ik )2 allora si calcola un αik che soddisfa il Criterio
di Armijo senza derivate e si pone α̃ik = αik ;
altrimenti si pone αik = 0 e α̃ik = 0.5α̃ik ;
Passo 3: si pone yki+1 = yki + αk di ;
Passo 4: se i < q si pone i = i + 1 e si ritorna al Passo 2.
Passo 5: si determina xk+1 tale che f (xk+1 ) ≤ f (yki+1 ), si pone k = k + 1 e si ritorna
al Passo 1.
Riguardo al precedente algoritmo si possono fare due precisazioni:

- l’algoritmo produce le sequenze di scalari {α̃ik }, con i = 1, . . . , q, ad ogni iterazione
k, lo scalare α̃ik rappresenta il passo che viene effettuato lungo la direzione di nel
Passo 2 per capire se tale direzione è di discesa. Questi scalari {α̃ik } vengono
aggiornati durante le iterazioni dell’algoritmo in modo da cercare di estrarre la
variabilità delle funzione obiettivo lungo la corrispondente direzione;
- nel Passo 5 l’algoritmo accetta come xk+1 un qualsiasi punto ottenuto da tec-
niche di approssimazione varie purche produca un miglioramento della funzione
obiettivo rispetto al punto yki+1 prodotto dall’algoritmo. Se nessuna tecnica di
approssimazione è disponibile allora si può porre xk+1 = yki+1 .
Proposizione 2.4.19 Sia {xk } la successione prodotta dall’algoritmo, si supponga

che L0 sia compatto. Supponiamo che l’insieme di direzioni d1 , d2 , . . . , dq soddisfi
l’Assunzione 2.4.1.
Allora, o esiste un indice ν ≥ 0 tale che xν ∈ L0 e ∇f (xν ) = 0, oppure oppure viene
prodotta una successione infinita tale che:
(c) limk→∞ k∇f (xk )k = 0, cioè ogni punto di accumulazione x̄ di {xk } è tale che
∇f (x̄) = 0.
67
2.5 Metodi di ottimizzazione vincolata
2.5.1 Introduzione
Come già detto, se si deve risolvere un problema di ottimizzazione vincolata, la situa-
zione è molto diversa a seconda che l’insieme ammissibile F è un insieme chiuso oppure
che è aperto.
Infatti se F è un insieme chiuso può accadere che la soluzione del problema cada proprio
sulla frontiera dell’insieme ammissibile. Normalmente, in questi casi, la presenza di un
minimo è dovuto all’azione congiunta della funzione obiettivo ed dei vincoli rendendo
assolutamente inadeguati i risultati e le tecniche proposte nel campo dell’ottimizzazione
non vincolata.
Diversa è la situazione se F è un insieme aperto. In questo caso, se esiste una solu-
zione questa è localmente un minimo non vincolato della funzione obiettivo e, perciò,
continuano ad essere valide tutte le condizioni di ottimalità ottenute nel caso non vin-
colato oltre al fatto che, in un intorno della soluzione, molti degli algoritmi proposti
per risolvere problemi non vincolati possono essere applicati direttamente.
Sempre nel caso in cui F è aperto, il Problema (1.1) si semplifica drasticamente se si
conosce un punto x̃ interno all’insieme ammissibile e se è compatto l’insieme di livello
LF (x̃) := {x ∈ F : f (x) ≤ f (x̃)}.
In questo caso, una soluzione del problema può essere ottenuta, a partire dal punto
x̃, adattando facilmente uno dei metodi o algoritmi proposti per risolvere problemi di
minimizzazione non vincolata. L’unica modifica da effettuare è quella di introdurre
(per esempio nelle minimizzazioni unidimensionali) dei controlli sul fatto che i punti
prodotti non escano dall’insieme ammissibile.
Quindi, in conclusione, si può dire che un problema vincolato reale è quello in cui
l’insieme ammissibile è un insieme chiuso. Invece, un problema vincolato in cui l’in-
sieme ammissibile è un insieme aperto, si conosce un punto ammissibile ed l’insieme
di livello LF (x̃) è un insieme compatto è assolutamente equivalente ad un problema di
minimizzazione non vincolato.
Risolvere un problema di ottimizzazione vincolata presenta un ordine di difficoltà mag-
giore del risolvere un problema di ottimizzazione non vincolato. Infatti, in generale,
un problema vincolato può essere visto come la somma di due sottoproblemi alquanto
difficili:
- quello di determinare dei punti ammissibili;
- quello di minimizzare la funzione obiettivo.
Perciò un generico algoritmo di ottimizzazione vincolata deve essere in grado di risolvere

contemporaneamente i due precedenti sottoproblemi. In pratica, ad ogni iterazione,
deve riuscire a bilanciare l’esigenza di far migliorare il valore della funzione obiettivo
con quella di controllare la violazione dei vincoli. In particolare, trovare un punto che
soddisfa determinati vincoli è equivalente ad un problema di ottimizzazione globale,
68
cioè quello di minimizzare una funzione che pesa la violazione dei vincoli. Anche nei
casi fortunati in cui si conoscano dei punti ammissibili od in cui l’insieme ammissibile
abbia una struttura particolarmente semplice, la sola presenza di vincoli sulla variabili
rende più difficile il problema di minimizzare la funzione obiettivo. Una conferma di
questo fatto può aversi, per esempio, osservando le condizioni di ottimalità: quelle per
problemi vincolati sono alquanto più complesse ed articolate di quelle per problemi non
vincolati.
A causa delle difficoltà descritte, lo studio di metodi per l’ottimizzazione vincolata ha
avuto una sviluppo molto più lento e meno armonioso rispetto a quello per l’ottimiz-
zazione non vincolata. Tuttavia, recentemente, vari algoritmi per problemi vincolati
sono stati proposti in letteratura. Se si trascurano tutti quei metodi che sfruttano
una qualche particolarità presente nella struttura del problema vincolato (per esem-
pio, vincoli lineari, programmazione convessa, programmazione quadratica), nel pro-
porre la maggior parte degli algoritmi per problemi vincolati generali, si sono seguiti
tradizionalmente due approcci:
- risolvere il problema originale risolvendo una sequenza di problemi vincolati più

semplici;
- trasformare il problema originale vincolato in una sequenza di problemi non

vincolati oppure in un singolo problema non vincolato.
Nel ambito del primo approccio, i metodi i più considerati e più studiati sono metodi
di programmazione quadratica ricorsiva (metodi RQP).
Per quanto riguarda il secondo approccio i metodi più promettenti si basano sulla pos-
sibilità di risolvere un problema vincolato attraverso una minimizzazione non vincolata
di particolari funzioni continuamente differenziabile.
Nel seguito si decriverà brevemente le idee su cui si basano i metodi RQP e le funzioni
di penalità.
2.5.2 Metodi di programmazione quadratica ricorsiva

L’idea da cui hanno origine i metodi di programmazione quadratica ricorsiva (RQP) è
quella di estendere al caso vincolato il metodo di Newton. Come visto precedentemente
il metodo di Newton determina la direzione di ricerca minimizzando l’approssimazione
quadratica della funzione obiettivo. L’estensione naturale di questo approccio è quello
di determinare una direzione dk risolvendo il seguente problema:
1
min dT ∇2 f (xk )d + ∇f (xk )T d + f (xk )
d 2
1 T 2
d ∇ gi (xk )d + ∇gi (xk )T d + gi (xk ) ≤ 0 i = 1, . . . , m, (2.37)
2
1 T 2
d ∇ hj (xk )d + ∇hj (xk )T d + hj (xk ) = 0 j = 1, . . . , p.
2
Il precedente problema, che costituisce l’approssimazione quadratica del Problema
(1.3), presenta la difficoltà di avere dei vincoli quadratici e, quindi, di non poter essere
69
risolto facilmente. Da qui la necessità di approssimare il problema originale con un
problema più trattabile dal punto di vista computazionale. L’idea è stata quella di
utilizzare come approssimazione del Problema (1.3) un problema di programmazione
quadratica, cioè un problema di minimizzazione vincolata in cui la funzione obiettivo
è quadratica ed i vincoli sono lineari. In particolare si può notare che, se la tripla
(d∗ , η ∗ , ρ∗ ) è un punto stazionario della funzione Lagrangiana del Problema (2.37), è
anche un punto stazionario della funzione Lagrangiana del seguente problema:
1
min dT ∇2x L(xk , η ∗ , ρ∗ )d + ∇f (xk )T d + f (xk )
d 2
∇gi (xk )T d + gi (xk ) ≤ 0 i = 1, . . . , m, (2.38)
T
∇hj (xk ) d + hj (xk ) = 0 j = 1, . . . , q.
Questo fatto suggerisce che può essere possibile ottenere una buona approssimazione del
Problema (1.3) anche utilizzando un problema di programmazione quadratica, in cui
i vincoli sono una approssimazione lineare dei vincoli non lineari di partenza. Questo
può essere ottenuto, purché la funzione obiettivo del problema approssimante, oltre ad
essere costituita dal modello quadratico della funzione obiettivo del problema originario,
include anche delle informazioni del secondo ordine dei vincoli.
Seguendo quanto visto, l’approccio dei metodi di programmazione quadratica ricorsiva
è quello:
- di risolvere un problema vincolato risolvendo una sequenza di problemi di pro-
grammazione quadratica;
- di sfruttare il fatto che, sotto opportune ipotesi, un problema di programmazione
quadratica può essere risolto efficientemente (cioè in un numero finito di passi).
Nella sua forma originale un metodo RQP può essere descritto dal seguente schema.
Schema originale di un algoritmo RQP

• Siano x0 , λ0 e µ0 delle stime iniziali del punto soluzione del problema vincolato
e dei sui moltiplicatori associati.
• Alla k-esima iterazione, data la tripla (xk , λk , µk ), si trova il minimo dk del
seguente problema ed i suoi moltiplicatori associati (ηk , ρk ):
1
min dT ∇2x L(xk , λk , µk )d + ∇f (xk )T d + f (xk )
d 2
∇gi (xk )T d + gi (xk ) ≤ 0 i = 1, . . . , m, (2.39)
T
∇hj (xk ) d + hj (xk ) = 0 j = 1, . . . , q.
• Si pone:
xk+1 = xk + dk ,
λk+1 = ηk ,
µk+1 = ρk .
70
Il sottoproblema (2.39) deriva dal Problema (2.38) in cui si sono sostituiti nella fun-
zione obiettivo i moltiplicatori ottimi (η ∗ , ρ∗ ) del Problema (2.37) con le stime correnti
(λk , µk ). Nonostante questa ulteriore approssimazione il sottoproblema (2.39) continua
ad avere con il problema originale dei forti legami. Infatti si può dimostrare che:
- l’insieme ammissibile del sottoproblema quadratico (QPk ) è un’approssimazione

lineare di quello del problema originale;
- la funzione Lagrangiana del sottoproblema quadratico LQ (d, η, ρ) è un’approssi-
mazione quadratica della funzione Lagrangiana del Problema (1.3), infatti, se si
pone dη := η − λk e dρ := ρ − µk , si ha:
LQ (d, dη , dρ ) = L(xk , λk , µk ) + ∇L(xk , λk , µk )T (d, dη , dρ ) (2.40)
1
+ (d, dη , dρ )T ∇2 L(xk , λk , µk )(d, dη , dρ ).
2
Perciò, in base ai precedenti legami, un’iterazione del metodo RQP equivale a
- effettuare un passo del metodo di Newton per la funzione Lagrangiana;
- forzare l’ammissibilità rispetto alla linearizzazione dell’insieme ammissibile.
Infatti determinare una tripla di Kuhn-Tucker del sottoproblema (2.39) equivale, da
una parte, a trovare un punto stazionario del modello quadratico (2.40) della funzione
Lagrangiana del Problema (1.3), e, dall’altra, a determinare una direzione di ricerca
che soddisfa le approssimazioni lineari dei vincoli.
- Convergenza locale
Come visto precedentemente, i metodi di programmazione quadratica ricorsiva sono
stati proposti cercando di estendere l’approccio del metodo di Newton al caso di pro-
blemi di minimizzazione vincolata. Il frutto di questo tentativo è il fatto che questi
metodi presentano proprietà di convergenza locale simili a quelle del metodo di New-
ton per problemi non vincolati. Uno dei risultati che riguardano le proprietà locali di
questi metodi è descritto dalla seguente proposizione.
Proposizione 2.5.1 Siano f , gi , i = 1, . . . , m e hj , j = 1, . . . , q delle funzioni due

volte continuamente differenziabili. Siano le matrici Hessiane ∇2 f , ∇2 gi , i = 1, . . . , m,
e ∇2 hj , j = 1, . . . , q, Lipschitz continue. Sia (x∗ , λ∗ , µ∗ ) una tripla di Kuhn-Tucker in
cui sono verificate le seguenti ipotesi:
i) i gradienti dei vincoli attivi sono linearmente indipendenti;
ii) sono soddisfatte le condizioni sufficienti del secondo ordine;
iii) è soddisfatta la stretta complementarità.
Allora esiste un intorno aperto D di (x∗ , λ∗ , µ∗ ) tale che, se (x0 , λ0 , µ0 ) ∈ D, la succes-
sione {xk , λk , µk } prodotta dal algoritmo RQP precedentemente descritto è ben definita
(cioè i sottoproblemi (2.39) ammettono soluzione) e converge a (x∗ , λ∗ , µ∗ ) con rapidità
di convergenza quadratica.
71
- Convergenza globale
La precedente proposizione mostra che i metodi di programmazione quadratica ricor-
siva, sotto opportune ipotesi, hanno buone proprietà di convergenza in un intorno di
un minimo del problema vincolato. Per quanto riguarda l’utilizzazione pratica di que-
sti algoritmi bisogna tener conto che, quando non si conosce un punto di partenza x0
“sufficientemente” vicino ad un minimo, si devono affrontare le seguenti difficoltà:
- l’algoritmo può non essere definito, cioè il sottoproblema quadratico può non
ammettere soluzione;
- la sequenza di punti {xk } prodotta può non convergere.

Per quanto riguarda il primo dei due problemi, una possibile causa può essere il fat-
to che la funzione obiettivo del sottoproblema (2.39) è illimitata inferiormente sul-
l’insieme ammissibile linearizzato. Questa situazione può essere evitata utilizzando
un’approssimazione Bk della matrice Hessiana ∇2x L(xk , λk , µk ) che sia definita positiva.
Ben più difficile è il caso in cui invece l’insieme ammissibile linearizzato è vuoto. Per
superare questo secondo ostacolo, l’approccio seguito è quello di risolvere in questi casi,
un nuovo sottoproblema quadratico a dimensioni più grandi che però ammette sempre
una soluzione.
Per quanto riguarda il problema della non convergenza della successione {xk } prodotta
dagli algoritmi di programmazione quadratica ricorsiva, ci si ispira alle tecniche pro-
poste per assicurare la convergenza globale del metodo di Newton. L’idea è quella di
controllare lo spostamento da effettuare lungo la direzione prodotta dal sottoproblema
quadratico, cioè il nuovo punto dovrebbe essere prodotto da una iterazione del tipo:
dove il passo αk dovrebbe essere calcolato utilizzando una ricerca unidimensionale che
valuti la bontà del nuovo punto prodotto. Come accennato precedentemente, la difficoltà
dei problemi di minimizzazione vincolati risiede nel fatto che la misura della bontà
di un nuovo punto prodotto deve tener conto contemporaneamente di una possibile
diminuzione della funzione obiettivo e di un possibile miglioramento (o mantenimento)
della ammissibilità del punto prodotto.
Un modo naturale per valutare se un punto è migliore dell’altro è quello di utilizzare
una funzione di penalità che, come si vedrà nella prossima sezione, permette di pesare
contemporaneamente le due diverse esigenze presenti in un problema di ottimizzazione
vincolata.
2.5.3 Funzioni di penalità

Un modo per affrontare un problema di ottimizzazione vincolata è quello di cercare di
trasformarlo nella minimizzazione non vincolata di una particolare funzione detta nor-
malmente funzione di penalità o funzione di merito. In generale le funzioni di penalità
vengono costruite aggiungendo alla funzione obiettivo un termine che penalizza la viola-
zione dei vincoli. In letteratura sono state proposte numerose funzioni di merito che si
72
differenziano tra di loro nel modo di penalizzare la violazione dei vincoli. Tali differenze
si riflettono nelle proprietà teoriche che le varie funzioni di penalità presentano.
Nel seguito si descriveranno brevemente alcune funzioni di penalità che non richiede la
conoscenza di un punto strettamente interno all’insieme ammissibile o la possibilità di
sfruttare qualche particolarità della sua struttura.
- Funzioni di penalità sequenziali esterne

Queste funzioni sono del tipo:
1
PS (x; ε) = f (x) + φS (x),
ε
dove ε è un scalare positivo detto parametro di penalità o coefficiente di penalità e φS è
la funzione detta termine di penalità. Questa funzione φS serve a misurare la violazione
dei vincoli e soddisfa le seguenti proprietà:
i) φS (x) è una funzione continuamente differenziabile;
ii) φS (x) = 0 se x ∈ F;
iii) φS (x) > 0 se x ∈

/ F.
Un esempio di funzione che soddisfa le precedenti proprietà è la seguente:

m q
2
hj (x)2 .
X X
φS (x) = max{0, gi (x)} +
i=1 j=1
Le funzioni di penalità che appartengono a questa classe hanno il pregio di essere molto
semplici. Dal punto di vista teorico si può dimostrare che, se xε è il minimo di PS (x; ε),
allora per valori di ε che tendono a zero si ha che i punti xε tendono ad una soluzione
del problema vincolato. Un difetto di questa classe di funzioni di penalità è quello di
essere non esatte, cioè non esiste nessun valore di ε per cui è possibile dimostrare che il
problema vincolato di partenza è equivalente a minimizzare in maniera non vincolata
una di queste funzioni PS (x).
Una ulteriore limitazione di queste funzioni di merito è dovuta al fatto che non si può
stabilire nessuna relazione tra i suoi punti stazionari ed il problema vincolato di par-
tenza. Questo fatto costituisce un grosso problema dal punto di vista computazionale
in quanto gli algoritmi di minimizzazione non vincolata permettono di determinare
solamente dei punti stazionari della funzione di penalità.
Nonostante questi limiti questa classe di funzioni di penalità permettono di definire
uno dei primi metodi proposti in letteratura in questo ambito (chiamato Metodo delle
Penalità Sequenziali). Anche se non è sicuramente molto efficiente, questo metodo ha
un certo interesse per la sua semplicità e per le discrete proprietà teroriche.
73
Tale metodo consiste trasformare il problema di partenza in una sequenza di minimiz-
zazioni (approssimate) non vincolate della seguente funzione di penalità:
m p
1X 1X
P (x; ε) = f (x) + max{0, gi (x)}2 + hj (x)2 , (2.41)
ε i=1 ε i=1
L’idea di fondo del Metodo delle Penalità Sequenziali è quella di produrre una sequenza
di punti {xk } attraverso delle minimizzazioni approssimate della funzione P (x, εk ).
In particolare, al crescere del numero di iterazioni, ciascun punto xk della sequenza
approssima sempre meglio un punto stazionario della funzione P (x, εk ).
Nelle iterazioni iniziali, al parametro di penalità εk che compare nella funzione P (x, εk )
vengono assegnati valori relativamente grandi. L’idea è che, in queste iterazione, la
funzione obiettivo del problema vincolato abbia nella espressione della funzione P (x, εk )
un peso relativamente grande.
All’aumentare della iterazioni i punti xk vengono ottenuto minimizzando in maniera
sempre più precisa la funzione P (x, εk ) in cui si scengono valori del parametro di pena-
lità εk sempre più piccoli in modo da aumentare, sempre di più il peso della violazione
dei vincoli. In questa modo si cerca di garantire di ottenere, al limite, punti che sod-
disfano tutti i vincoli e che stiano in zone in cui la funzione obiettivo assume valori
relativamente piccoli.
Il Metodo delle Penalità Sequenziali può essere descritto dai seguenti passi.
74
Metodo delle Penalità Sequenziali.
Passo 0. Dati x0 ∈ Rn , θ1 , θ2 , θ3 ∈ (0, 1), ε−1 = ε0 > 0 e δ0 > 0, si pone k = 0.
Passo 1. Si pone
2
(λk )i = max{0, gi (xk )}, i = 1, . . . , m,
εk−1
2
(µk )j = hj (xk ), j = 1, . . . , p,
εk−1
se (xk , λk , µk ) soddisfa le condizioni di KKT Stop.
Passo 2. A partire da punto xk , si calcola il punto xk+1 ∈ Rn tale tale che
k∇P ((xk+1 ; εk )k ≤ δk .
Passo 3. Se
m p m
X p
2 2 2 2
X X X
max{0, gi (xk+1 )} + hj (xk+1 ) ≤ θ1 max{0, gi (xk )} + hj (xk ) ,
i=1 j=1 i=1 j=1
si pone εk+1 = εk altrimenti si pone εk+1 = θ2 εk .
Passo 4. Si pone δk+1 = θ3 δk , k = k + 1 e si ritorna al Passo 1.
Nel Passo 1 si determinano della stime dei moltiplicatori di KKT e si controlla se xk

ottenuto soddista le condizioni di KKT.
Nel passo 2 si effettua una minimizzazione non vincolata di P (x, εk ). Tale minimizza-
zione viene effettuata in maniera approssimata, infatti viene arrestata appena si ottiene
un punto xk+1 in cui la norma del gradiente di P è inferiore o uguale al parametro δk .
Un tale punto può essere determinato, in un numero finito di iterazioni, da un qual-
siasi metodo di ottimizzazione non vincolata, tra cui il Metodo del Gradiente descritto
precedentemente.
Il Passo 3 è dedicato all’aggiornamento del parametro di penalità εk . Se nel nuovo
punto determinato xk+1 la violazione dei vincoli non è migliorata in maniera significa-
tiva rispetto al punto ottenuto all’iterazione precedente, il parametro di penalità viene
diminuinuto nella iterazione successiva. Altrimenti rimane invariato.
Nell’ultimo passo viene diminuito il parametro δk che determina errore accettato nel-
l’approssimare un punto stazionario della funzione P (x, εk ) attraverso una sua mini-
mizzazione non vincolata.
Il seguente teorema descrive le proprietà asintotiche dei punti prodotti dal precedente
metodo. Le ipotesi di questo teorema necessitano della definizione dell’insieme degli
75
indici dei vincoli attivi o violati, cioè dell’insieme:
˜
I(x̄) = {i = 1, . . . , m : gi (x) ≥ 0} . (2.42)
Teorema 2.5.2 Siano f ∈ C 1 (Rn ) e gi ∈ C 1 (Rn ), per ogni i = 1, . . . , m, e hj ∈

C 1 (Rn ), per ogni j = 1, . . . , p. Sia {xk } la sequenza di punti prodotta dal Metodo delle
Penalità Sequenziali. Sia x̄ un punto di accumulazione della sequenza {xk } che soddisfa
la seguente ipotesi:
˜
- non esistono degli scalari αi ≥ 0, i ∈ I(x̄), e βj , j = 1, . . . , p, non tutti nulli per
cui si ha: p
X X
αi ∇gi (x̄) + βj ∇hj (x̄) = 0.
˜
i∈I(x̄) j=1
Allora x̄ è un punto di Karush-Kuhn-Tucker.
Prova. Sia {xk }K la sottosequenza tale che
lim xk = x̄. (2.43)

k→∞,k∈K
La tesi del teorema segue dalla dimostrazione dei seguenti tre punti:
i) il punto x̄ appartiene all’insieme ammissibile del problema, cioè x̄ ∈ F;
ii) le sequenze di vettori {λk }K e {µk }K generate dall’algorimo al Passo 1 sono

limitate;
iii) il punto x̄ soddisfa le condizioni di Karush-Kuhn-Tucker del problema.
Punto i). Se esiste un k̄ tale che, per ogni k ≥ k̄, si ha εk = ε > 0 significa che per ogni
k ≥ k̄ il test al Passo 3 è soddisfatto, quindi
m p m
X p
2 2
θ1k−k̄ 2 2
X X X
max{0, gi (xk )} + hj (xk ) ≤ max{0, gi (xk̄ )} + hj (xk̄ ) ,
i=1 j=1 i=1 j=1
Da questo, tenendo conto che θ1 ∈ (0, 1) segue che:

m p
2
hj (xk )2 = 0,
X X
lim max{0, gi (xk )} +
k→∞
i=1 i=1
da cui segue che:

m
X m
X
lim max{0, gi (xk )} = max{0, gi (x̄)} = 0,
k→∞,k∈K
i=1 i=1
Xp p
X
lim hj (xk ) = hj (x̄) = 0.
k→∞,k∈K
j=1 j=1
76
Le precedenti relazioni provano che x̄ ∈ F.
Si consideri ora il caso in cui la sequenza di scalari {εk } è tale che
lim εk = 0.
k→∞
Dal Passo 2 si ha:

m
X p
X

εk−1 ∇f (xk ) +
max{0, gi (xk )}∇gi (xk ) + ≤ εk−1 δk−1 .
hj (xk )∇hj (xk )
i=1 j=1
Facendo i limiti per k → ∞ e k ∈ K si ottiene

m
X p
X
max{0, gi (x̄)}∇gi (x̄) + hj (x̄)∇hj (x̄) = 0,
i=1 j=1
che può essere riscritta:
X p
X
max{0, gi (x̄)}∇gi (x̄) + hj (x̄)∇hj (x̄) = 0,
˜
i∈I(x̄) j=1
La precedente uguaglianza e l’ipotesi fatta di regolarità dei vincoli nel punto x̄ implicano
che:
max{0, gi (x̄)} = 0, i = 1, . . . , m, hj (x̄) = 0, j = 1, . . . , p,
che assicurano nuovamente che x̄ ∈ F.

Punto ii). Sia
v
p
um
uX X
Vk = t 2
(λk )i + (µk )2j . (2.44)
i=1 j=1
Se, per assurdo, le sequenze di vettori {λk }K e {µk }K fossero illimitate, esisterebbero
delle sottosequenze {λk }K̃ e {µk }K̃ , con K̃ ⊆ K tali che:
lim Vk = ∞. (2.45)
k→∞,k∈K̃
Dalla definizione di Vk si avrebbe che le sottosequenze {λk /Vk }K̃ e {µk /Vk }K̃ sarebbero
limitate quindi esisterebbe un sottoinsieme di indici K̂ ⊆ K̃ tale che:
(λk )i
lim = λ̃i ≥ 0, i = 1, . . . , m, (2.46)
k→∞,k∈K̂ Vk
(µk )j
lim = µ̃j , j = 1, . . . , p. (2.47)
k→∞,k∈K̂ Vk
77
Inoltre dalla definizione di λk e dalla (2.44) si avrebbe anche:
(λk )i ˜
lim = λ̃i = 0, i∈
/ I(x̄), (2.48)
k→∞,k∈K̂ Vk
v
p
um 2 X
uX
t λ̃i + µ̃2j = 1. (2.49)
i=1 j=1
Il Passo 2 implicherebbe:
m p
∇P (xk ; εk−1 ) = ∇f (xk ) +
1 (λk )i (µk )j δk−1

X X
V V ∇gi (xk ) + ∇hj (xk ) ≤ .
k k i=1
Vk j=1
Vk Vk
Facendo i limiti per k → ∞ e k ∈ K̂ e ricordando la (2.48) si avrebbe:
X p
X
λ̃i ∇gi (x̄) + µ̃j ∇hj (x̂) = 0. (2.50)
˜
i∈I(x̄) j=1
La (2.46), la (2.49), la (2.47) e la (2.50) negherebbero l’ipotesi di regolarità dei vincoli

nel punto x̄.
Punto iii). Dal Passo 2 e dalla definizione del vettore λk si ha:
m
X p
X

∇f (xk ) + (λ )
k i ∇g (x
i k ) + (µ )
k j ∇hj k ≤ δk−1 ,
(x ) (2.51)

i=1 j=1
λTk g(xk ) ≥ 0, (2.52)

λk ≥ 0. (2.53)
Poichè le sottosequenze {λk }K e {µk }K sono limitate esiste un sottoinsieme di indici

K̄ ⊆ K tale che:
lim xk = x̄ ∈ F, (2.54)
k→∞,k∈K̄
lim λk = λ̃ ≥ 0, (2.55)
k→∞,k∈K̄
lim µk = µ̄, (2.56)
k→∞,k∈K̄
lim δk−1 = 0. (2.57)
k→∞,k∈K̄
Dalle (2.51)-(2.57) si ottiene:
∇f (x̄) + ∇g(x̄)λ̄ + ∇h(x̄)µ̄ = 0, (2.58)

T
λ̄ g(x̄) ≥ 0, (2.59)
λ̄ ≥ 0, (2.60)
g(x̄) ≤ 0, (2.61)
h(x̄) = 0. (2.62)
78
La (2.60) e la (2.61) implicano che λ̄T g(x̄) ≤ 0 che, insieme alla (2.59), da
λ̄T g(x̄) = 0. (2.63)
In conclusione si ottiene che le (2.58),(2.60), (2.61), (2.62), (2.63) mostrano che il punto
x̄ è un punto di Karush-Kuhn-Tucker del problema. ✷
- Funzioni di penalità esatte non differenziabili

Queste funzioni di merito hanno una struttura del tipo:
1
PN (x; ε) = f (x) + φN (x),
ε
dove, in questo caso, la funzione φN ha le seguenti caratteristiche:
i) φN (x) non è una funzione continuamente differenziabile;
ii) φN (x) = 0 se x ∈ F;
iii) φN (x) > 0 se x ∈
/ F.
In letteratura sono state proposte numerose funzioni φN (x) che soddisfano i precedenti
punti (i)-(iii), una delle più note è la seguente:
m
X q
X
φN (x) = max{0, gi (x)} + |hj (x)|.
i=1 j=1
Il fatto che in questa classe di funzioni di merito si rilassi la richiesta che il termine
di penalità φN (x) sia continuamente differenziabile permette di superare le limitazioni
delle funzioni di penalità sequenziali. Infatti le funzioni di penalità non differenziabili
sono esatte, in quanto, sotto opportune ipotesi, è possibile dimostrare che, per valori
sufficientemente piccoli del parametro di penalità ε, ogni minimo globale (locale) del
problema vincolato è un minimo globale (locale) non vincolato di PN (x; ε) e viceversa.
Inoltre, una relazione analoga vale anche tra i punti di Kuhn-Tucker del problema
originale ed i punti critici della funzione non differenziabile PN (x; ε).
Naturamente la limitazione principale nell’utilizzazione di questa classe di funzioni
di penalità risiede nella loro non differerenziabilità che le rende alquanto difficili da
minimizzare.
- Funzioni Lagrangiane aumentate

A differenza delle funzioni di merito viste precedentemente, in questa classe di funzioni
l’idea è quella di trasformare un problema di minimizzazione vincolato su Rn in uno
di minimizzazione non vincolata su Rn+m+q . In particolare la funzione di merito da
minimizzare assume la struttura:
1
LA (x, λ, µ; ε) = f (x) + φE (x, λ, µ; ε),
ε
dove il termine di penalità φE , oltre ad essere funzione della tripla (x, λ, µ), dipende
anche dal parametro di penalità ε. Nella funzione Lagrangiana aumentata classica la
funzione φE soddisfa le seguenti proprietà:
79
i) φE (x, λ, µ; ε) è una funzione continuamente differenziabile nella tripla (x, λ, µ);
ii) per ogni λ e µ si ha

lim φE (x, λ, µ; ε) = φS (x),
ε→0
dove φS è il termine di penalità usato nelle funzioni di penalità sequenziali esterne;
iii) se x ∈ F allora φE (x, λ, µ; ε) = 0 se e solamente se λi ≥ 0 e λi gi (x) = 0 per ogni

i = 1, . . . , m;
iv) se (x∗ , λ∗ , µ∗ ) è una tripla di Kuhn-Tucker allora per ogni ε si ha:

1
∇φE (x∗ , λ∗ , µ∗ ; ε) = −∇f (x∗ ).
ε
In particolare la funzione Lagrangiana aumentata tradizionale proposta la seguente

funzione:
m
−ελi −ελi 2
X
φE (x, λ, µ; ε) = ελi max{gi (x), } + max{gi (x), }
i=1
2 2
q
εµj hj (x) + hj (x)2 .
X
+
j=1
La proprietà (i) assicura ovviamente che la funzione di penalità risultante sia conti-
nuamente differenziabile. La (ii) implica che, quando il coefficiente di penalità tende
a zero, la funzione φE tende al termine di penalità utilizzato nelle funzioni di penalità
sequenziali che pesa la violazione dei vincoli. La proprietà (iii) mostra che il termi-
ne φE è in grado di forzare la positività del moltiplicatore λ e la complementarità
(cioè gi (x)λi = 0). L’ultima proprietà assicura che ogni una tripla di Kuhn-Tucker
(x∗ , λ∗ , µ∗ ) è un punto stazionario della funzione Lagrangiana aumentata.
Sotto opportune ipotesi e per valori sufficientemente piccoli del parametro di penalità ε,
si ha anche che ogni minimo globale (locale) del problema vincolato è un minimo globale
(locale) non vincolato della funzione LA (x, λ∗ , µ∗ ; ε). Purtroppo quest’ultimo risultato
non può essere applicato direttamente per trasformare il problema vincolato originale
in uno vincolato perché richiederebbe la conoscenza dei moltiplicatori di Kuhn-Tucker
λ∗ e µ∗ . Tuttavia la precedente proprietà delle funzioni Lagrangiane aumentate hanno
ispirato la definizione di una classe di algoritmi, detti metodi dei moltiplicatori, che si
basano su una sequenza di minimizzazioni, rispetto alla variabile x, di funzioni del tipo
LA (x, λk , µk ; εk ), dove le stime dei moltiplicatori (λk , µk ) e il parametro dipenalità εk
vengono aggiornati iterativamente secondo opportune regole.
- Funzioni di penalità esatte continuamente differenziabili

L’idea base su cui si fondano funzioni di penalità esatte continuamente differenziabili
è quella di approssimare in una funzione Lagrangiana aumentata i moltiplicatori di
80
Kuhn-Tucker (λ∗ , µ∗ ) attraverso delle funzioni della sola variabile x. Più precisamente
la struttura base di una funzione di penalità di questo tipo è la seguente:
1
PE (x; ε) = f (x) + φE (x, λ(x), µ(x); ε),
ε
dove il termine di penalità è lo stesso di quello utilizzato nella funzione Lagrangiana
aumentata vista precedentemente, mentre λ(x) e µ(x) sono delle particolari funzioni
tali che:
i) λ(·) : Rn → Rm e µ(·) : Rn → Rq ;
ii) se (x∗ , λ∗ , µ∗ ) è una tripla di Kuhn-Tucker allora λ(x∗ ) = λ∗ e µ(x∗ ) = µ∗ ;
iii) λ(·) e µ(·) sono funzioni continuamente differenziabili.
In letteratura tutte le funzioni che godono delle precedenti proprietà vengono dette
funzioni moltiplicatrici.
Grazie alla proprietà del termine di penalità φE e delle funzioni λ(x) e µ(x), le funzioni
di penalità di questa classe presentano delle buone proprietà di esattezza. Infatti, sotto
opportune ipotesi e per valori sufficientemente piccoli di ε, è possibile stabilire una
corrispondenza biunivoca tra i minimi globali (locali) e punti di Kuhn-Tucker del pro-
blema vincolato originario e i minimi globali (locali) e i punti stazionari della funzione
continuamente differenziabile PE (x; ε).
- Funzioni Lagrangiane aumentate esatte

Le funzioni di penalità esatte continuamente diffenziabili si basano fortemente sull’uti-
lizzazione delle funzione moltiplicatrici λ(x) e µ(x). Purtroppo il calcolo di tali funzioni
può essere troppo oneroso se il numero di vincoli del problema è grande. Le funzioni
Lagrangiane aumentate esatte permettono di trasformare un problema vincolato in uno
non vincolato evitando l’utilizzazione di funzioni moltiplicatrici. Il prezzo da pagare è
che il problema non vincolato da risolvere è un problema sullo spazio esteso Rn+m+q .
Analogamente alle funzioni di penalità esatte continuamente differenziabili, le funzioni
Lagrangiane aumentate esatte traggono ispirazione dalle funzioni Lagrangiane aumen-
tate descritte. Infatti la forma originale di una funzioni di merito di questa classe è la
seguente:
1
LE (x, λ, µ; ε) = f (x) + φE (x, λ, µ; ε) + φL (x, λ, µ),
ε
dove, nuovamente, il termine di penalità φE è quello presente nelle fuzioni di Lagran-
giane aumentate mentre il temine nuovo φL ha le seguenti caratteristiche:
i) φL (x, λ, µ) è una funzione continuamente differenziabile nella tripla (x, λ, µ);
ii) se (x∗ , λ∗ , µ∗ ) è una tripla di Kuhn-Tucker del Problema (1.3)) allora
φL (x∗ , λ, µ) = 0
se e solamente se λ = λ∗ e µ = µ∗ .
81
Quindi a differenza delle funzioni Lagrangiane aumentate, quelle esatte hanno un ter-
mine φL la cui minimizzazione forza le variabili λ e µ a coincidere con i moltiplicatori
di Kuhn-Tucker del problema vincolato.
Le funzioni Lagrangiane esatte si possono stabilire le stesse proprietà di esattezza delle
funzioni di penalità esatte continuamente differenziabili.
82
Capitolo 3
Metodi di ottimizzazione globale
La maggior parte dei metodi proposti in letteratura considerano dei problemi di otti-
mizzazione globale che hanno la seguente struttura.
min f (x) (3.1)

x ∈ D,
dove la funzione f : D → R è almeno continua e l’insieme D ⊆ Rn è dato da:
D = {x ∈ Rn : l ≤ x ≤ u}, (3.2)
dove l ∈ Rn e u ∈ Rn sono due vettori dati.

L’insieme dei punti di minimo globale del precedente problema è rappresentato da:
X ∗ = {x∗ ∈ D : f (x∗ ) ≤ f (x), per tutti x ∈ D}, (3.3)
mentre il valore ottimo della funzione obiettivo è rappresentato da:
f ∗ = f (x∗ ), con x∗ ∈ X ∗ . (3.4)
Molto spesso si ipotizza anche che i due vettori siano stati scelti in maniera tale che i
minimi globali della funzione f su D siano interni all’insieme D.
In altre parole i problemi globali maggiormante affrontati sono quelli non vincolati
oppure quelli che hanno vincoli molto semplici che impongono solamente dei limiti
superiori ed inferiori sulle componenti del vettore delle variabili.
Molto più limitatata è stata l’attività di ricerca verso problemi di ottimizzazione globale
con vincoli più complessi. Questo è dovuto alla complessità di questi problemi vincolati
che rende inapplicabile gran parte dei risultati e metodi proposti per i problemi del
tipo (3.1). Comunque, da punto di vista pratico e teorico, l’uso di funzioni di penalità
esatte o lagrangiani aumentati esatti può costituire uno strumento efficace per affrontare
problemi di ottimizzazione globale vincolata.
83
Una descrizione completa ed approfondita dei molti metodi proposti per risolvere pro-
blemi di ottimizzazione del tipo (3.1) richiederebbe una trattazione molto complessa
e molto lunga. Quindi, nei capitoli successivi, allo scopo di fornire un’introduzione
all’argomento, ci si limiterà a considerare solamente alcune classi particolari di metodi
di ottimizzazione globale. La scelta si è rivolta principalmente verso metodi che, da
una parte, fossero relativamente semplici da descrivere e particolarmente facili da rea-
lizzare e che, dall’altra parte, avessero le potenzialità per affrontare anche problemi di
ottimizzazione globale derivanti da applicazioni ingegneristiche “difficili”, cioè quelle in
cui la funzione obiettivo è rappresentata da una “black box” ed il numero di variabili
non è particolarmente piccolo.
3.1 Metodi Probabilistici

Questo capitolo è dedicato ad introdurre l’approccio probabilistico per la soluzione
di problemi di ottimizzazione globale del tipo (3.1). Dopo aver richiamato quale è
l’idea da cui parte tale approccio, vengono brevemente descritti alcuni algoritmi di
tipo probabilistico: tra cui i metodi di tipo multistart, i metodi detti di “simulated
annealing” e metodi che usano popolazioni di punti.
3.1.1 Algoritmi che utilizzano punti scelti a caso su D.

Uno dei punti di partenza dei metodi di tipo probabilistico è il seguente risultato.
Proposizione 3.1.1 Sia {xk } una sequenza di punti aleatori scelti a caso su D (cioè
vettori generati con distribuzione uniforme su D). Allora per ogni sottoinsieme A di D
tale che
meas(D) > meas(A) > 0, (3.5)
(con meas(·) misura di Lebesgue di un insieme) si ha:

lim P rob Xk ∩ A 6= ∅ = 1, (3.6)
k→∞
con Xk = {x0 , . . . , xk }.
Prova. Sia lo scalare p dato da:

meas(A)
p= ,
meas(D)
dalla (3.5) si ha:
1 > p > 0.
Come è naturale lo scalare p da la probabilità che un punto, scelto a caso su D, cada nel-
l’insieme A. Di conseguenza la probabilità che, generati k vettori con una distribuzione
uniforme su D, almeno uno cada in A è data da:

P rob Xk ∩ A 6= ∅ = 1 − (1 − p)k
84
da cui segue:
lim P rob Xk ∩ A 6= ∅ = 1.
k→∞
- Campionamento uniforme della funzione obiettivo

Il precedente risultato indica che, se A è un qualsiasi intorno di un minimo globale x∗
di f (x) su D e se si generano molti punti a caso, allora uno di questi punti generati
cade, molto probabilmante, vicino al minimo globale x∗ . Questo suggerisce un primo
semplice algoritmo di ottimizzazione globale.
Algoritmo di Campionamento Uniforme.
Passo 0: si genera a caso un punto x0 su D, si pone x∗0 = x0 e k = 1;
Passo 1: si genera a caso un punto xk su D;
Passo 2: se f (xk ) < f (x∗k−1 ) allora si pone x∗k = xk
altrimenti si pone x∗k = x∗k−1 ;
Passo 3: si pone k = k + 1 e si ritorna al Passo 1.
Utilizzando la precedente Proposizione 3.1.1, si può stabilire la seguente proprietà di

convergenza dei punti prodotti dal precedente algoritmo.
Proposizione 3.1.2 Sia {x∗k } la sequenza di punti aleatori prodotti dall’Algoritmo di
Campionamento Uniforme. Allora, comunque scelto un ε > 0, si ha:

lim P rob x∗k ∗
∈ {x ∈ D : f (x) ≤ f + ε} = 1, (3.7)
k→∞
dove f ∗ è definito dalla (3.4) ed indica il valore ottimo della f su D.

Prova. Se si definisce l’insieme A nella seguente maniera:
A = {x ∈ D : f (x) ≤ f ∗ + ε},
si può notare che

P rob x∗k ∗
∈ {x ∈ D : f (x) ≤ f + ε} = P rob Xk ∩ A 6= ∅ ,
dove Xk = {x0 , . . . , xk } è l’insieme di punti generati a caso su D dall’algoritmo.

La dimostrazione della Proposizione segue utilizzando la Proposizione 3.1.1 e ricordar-
dando che, dal Teorema 1.5.1, si ha che meas(A) > 0.
A partire dalla precedente proposizione si può anche dimostare che la sequenza dei
valori della funzione obiettivo {f (x∗k )} prodotta dal precedente algoritmo converge con
probabilità uno al valore attimo f (x∗ ) con x∗ ∈ X ∗ .
85
- Metodi di tipo multistart
Questi metodi si basano sull’idea di utilizzare la generazione di punti a caso su D
per determinare un punto in un intorno di un minimo globale e di utilizzare qualche
algoritmo di minimizzazione locale per determinare efficientemente un minimo globale.
Quindi questa classe di metodi possono essere visti o come un tentativo di globalizzare
i metodi di ottimizzazione locale oppure come un tentativo di migliorare l’efficienza del
Algoritmo di Campionamento Uniforme sfruttanto il fatto che molti algoritmi locali
possono essere attratti da un minimo globale, cioè soddisfano la seguente assunzione
Assunzione 3.1.1 Se {xk } è la sequenza di punti generata dall’algoritmo e se x∗ è

un minimo globale di f su Rn , esiste un ε > 0 tale che se, per un indice k̄, si ha
xk̄ ∈ B(x⋆ ; ε) allora:
(i) xk ∈ B(x⋆ ; ε) per tutti i k ≥ k̄;
(ii) limk→∞ xk = x⋆ .
L’algoritmo di tipo multistart di partenza è il seguente.
Algoritmo Multistart 1.
Passo 2: partendo da xk si applica un algoritmo di ottimizzazione locale ottenendo yk ;
Passo 3: se f (yk ) < f (x∗k−1 ) allora si pone x∗k = yk
Naturamente l’uso di un algoritmo determistico locale può far miglorare la proprietà

di convergenza dei punti prodotti
Proposizione 3.1.3 Se esiste un minimo globale x∗ non vincolato della funzione f su

D per cui l’algoritmo di minimizzazione locale (utilizzato al Passo 2) soddisfa l’Assun-
zione 3.1.1 allora la sequenza {x∗k } di punti aleatori prodotti dall’Algoritmo di Multistart
1 è tale che:
∗ ∗
lim P rob xk ∈ X = 1, (3.8)
k→∞
dove X∗ è l’insieme dei minimi globali del Problema (3.1).
86
Prova. Segue, nuovamente, dalla Proposizione 3.1.1. Infatti

P rob x∗k ∈ X ∗ ≥ P rob x∗k = x∗ ,
dove x∗ è il minimo globale considerato nell’enunciato della proposizione.

Quindi, si può scegliere
A = B(x∗ , ε),
dove B(x∗ , ε) è l’intorno descritto nella Assunzione 3.1.1. Poichè, per ipotesi, l’algorit-
mo di minimizzazione locale soddisfa la Assunzione 3.1.1, nel momento in cui si genera
un punto xk tale che xk ∈ B(x∗ , ε) si ha yk = x∗ . Perciò si ha che:

P rob x∗k =x ∗
= P rob Xk ∩ A 6= ∅ ,
dove Xk = {x0 , . . . , xk } è l’insieme di punti generati a caso su D dall’algoritmo e, perciò

la tesi della proposizione segue dalla Proposizione 3.1.1.
L’Algoritmo Multistart 1 è stato il primo ad essere proposto in letteratura ed è tuttora

abbastanza usato; tuttavia presenta il difetto che può richiedere un numero molto
grande di minimizzazioni locali. Per superare questo difetto sono state proposte delle
variazioni dell’Algoritmo Multistart 1 che cercano di ridurre il numero di minimizzazioni
locali senza variarne le proprietà.
Passo 2: se f (x∗k−1 ) < f (xk ) allora si pone x∗k = x∗k−1 e si va al Passo 4;
Passo 3: partendo da xk si applica un algoritmo di ottimizzazione locale ottenendo x∗k ;
Nel precedente algoritmo le minimizzazioni locali non vengono applicate se il valore della
funzione obiettivo nel punto generato a caso è peggiore del miglior valore della funzione
obiettivo ottenuto dall’algoritmo. Poichè le minimizzazioni locali producono dei punti in
cui il valore delle funzione obiettivo è non peggiore rispetto al valore che si ha nel punto
iniziale, ne deriva che ogni applicazione di tali minimizzazioni produce un punto che può
essere considerato come nuova stima x∗k . Purtroppo la strategia adottata dal precedente
algoritmo può portare ad effettuare poche minimizzazioni locali. L’algoritmo seguente
cerca di seguire una strategia intermedia tra i due precedenti algoritmi multistart.
87
Passo 1: si generano a caso Nk1 punti su D;
Passo 2: si scelgono Nk2 < Nk1 punti “più promettenti” e da ciascuno di questi si effettua
una minimizzazione locale;
N2
Passo 3: fra i punti yk1 , yk2 , . . . , yk k ottenuti da queste minimizzazioni locali si sceglie
quello yk a cui corrisponde il valore della funzione obiettivo più piccolo, cioè
f (yk ) = min 2 f (yki );

1≤i≤Nk
L’idea del precedente algoritmo è quella di ridurre il più possibile il numero delle mi-
nimizzazioni locali utilizzando le informazioni che si possono ottenere sulla funzione
andando a valutarne il valore su un certo numero di punti scelti a caso. Nel Passo 2
si cerca di raggruppare (usualmente utilizzando le tecniche della “cluster analysis”) i
punti generati al Passo 1 in maniera tale che ogni gruppo sia costituito da punti che
appartengono alla regione di attrazione dello stesso minimo locale. Dopodiché per ogni
gruppo si effettua una sola minimizzazione locale.
3.1.2 Metodi di tipo “simulated annealing”

Una evoluzione ulteriore dei metodi descritti nella precedente sezione è quella di cercare
di definire dei nuovi algoritmi di ottimizzazione globale basati sull’uso di punti generati
in maniera da cercare di sfruttare le informazioni sul problema ottenute durante le
iterazioni dell’algoritmo.
- Distribuzioni non uniformi di punti

Una osservazione importante nell’ambito dei metodi di ottimizzazione globale proba-
bilistici riguarda il fatto che le proprietà di convergenza stabilite dalla Proposizione
3.1.2 e dalla Proposizione 3.1.3 non dipendono in maniera esclusiva dal fatto che i pun-
ti x0 , . . . , xk sono generati con distribuzione uniforme su D, cioè sono realizzazioni di
variabili aleatorie destribuite con funzioni densità di probabilità costanti su D. Infatti
sia la Proposizione 3.1.2 e che la Proposizione 3.1.3 seguono dalla Proposizione 3.1.1
ma quest’ultima può essere generalizzata nella seguente proposizione.
88
Proposizione 3.1.4 Sia {mk (·)} una sequenza di misure di probabilità tali che, per
ogni sottoinsieme A di D con meas(A) > 0, soddisfano:

Π∞
k=0 1 − mk (A) = 0. (3.9)
Sia {xk } una sequenza di punti aleatori generati secondo le distribuzioni associate alle
misure di probabilità mk (·). Allora per ogni sottoinsieme A di D con meas(A) > 0 si
ha:
lim P rob Xk ∩ A 6= ∅ = 1, (3.10)
k→∞
con Xk = {x0 , . . . , xk }.
Prova. Per definizione di misura di probabilità e dalle ipotesi della proposizione,

mk (A) è la probabilità che un punto generato xk cada nell’insieme A. Di conseguenza
la probabilità che, tra i vettori generati x0 , . . . , xk , almeno uno cada in A è data da:

P rob Xk ∩ A 6= ∅ = 1 − Πki=0 1 − mi (A)
da cui, usando la (3.9), segue:

lim P rob Xk ∩ A 6= ∅ = 1.
k→∞
- Algoritmi di tipo “simulated annealing”

La Proposizione 3.1.4 mette in evidenza la possibilità di definire dei nuovi algoritmi
probabilistici che usino punti generati secondo funzioni densità di probabilità non co-
stanti su D. Questo fatto può essere sfruttato per cercare di utilizzare funzioni densità
di probabilità che siano maggiormente concentrate intorno ai minimi globali, cioè che
rendano più probabile la generazione di punti più vicini ai minimi globali.
Un esempio di una funzione densità di probabilità con queste caratteristiche può essere
ottenuto traendo ispirazione dai risultati della meccanica statistica.
Si consideri un sistema fisico composto da un numero molto grande di particelle della
stessa natura, si indichi con s lo stato del sistema e con E(s) l’energia associata a questo
stato. Se il sistema fisico è in una situazione di equilibrio termico allora la funzione
densità di probabilità, relativa al fatto che il sistema sia nello stato s, è proporzionale
a E(s)
e− KT
ove K è la costante di Boltzman e T la temperatura.
Parlando in maniera approssimata, è noto che, se si abbassa la temperatura, diventano
sempre più probabili gli stati a bassa energia, fino alla situazione limite per cui T → 0
e gli unici stati possibili sono quelli ad energia nulla. Quindi, in linea teorica, si può
immaginare un sistema fittizio che associa ad ogni suo stato x, l’energia:
E(x) = f (x) − f ∗ ≥ 0
89
dove f ∗ è, come al solito, il minimo globale della f (x). Ora, se si simulasse il compor-
tamento di questo sistema e se si facesse tendere a zero la temperatura, diventerebbero
sempre più probabili gli stati x∗ del sistema che corrispondono a basse energia fino ad
arrivare alla situazione limite che:
E(x∗ ) = f (x∗ ) − f ∗ = 0.
Per avvalorare ulteriormante questa idea si può far riferimento al Teorema 1.5.5. Infatti,
nel caso in cui il minimo globale x⋆ su D sia unico, questo teorema implica (ponendo
K = 1 e k = 1/T ):
Z Z
−f (x)/T ∗ )/T
xi e dx xi e−(f (x)−f dx
x⋆i = lim ZD = lim ZD ∗ )/T
, per i = 1, . . . , n.
T →0 T →0
e−f (x)/T dx e−(f (x)−f dx
D D
(3.11)
Le precedenti uguaglianze possono essere riscritte come:
Z
xi ∗ = lim xi pT (x)dx = lim x̄i (T ) (3.12)
T →0 D T →0
dove ∗ )/T
e−f (x)/T e−(f (x)−f
pT (x) = Z =Z ∗ )/T
(3.13)
e−f (x)/T dx e−(f (x)−f dx,
D D
è una densità di probabilità e dove x̄i (T ) sono i valori medi di variabili aleatorie che
sono distribuite secondo la densità di probabilità pT (x).
Quindi, l’idea su cui si basano i metodi di ottimizzazione globale di tipo “simulated
annealing” è quella di simulare dei vettori aleatori distribuiti secondo la densità di
probabilità pT (x) data dalla (3.13). La relazione (3.12) indica che, al diminuire di T , i
vettori x generati su D secondo la funzione densità di probabilità pT (x) si avvicinano,
in media, al punto di minimo globale della f (x) su D.
Un elemento essenziale allo sviluppo dei metodi “simulated annealing” è il fatto che
punti distribuiti secondo la funzione densità di probabilità pT (x) posso essere generati
abbastanza facilmente utilizzando il metodo di Von Neumann. Tale metodo si può
applicare a tutte le funzioni densità di probabilità p(x) che hanno la seguente struttura:
p(x) = Cs(x), (3.14)
dove C è una costante positiva e s : D → R+ è tale che 0 < s(x) ≤ 1, per tutti x ∈ D.
Utilizzando la definizione (3.13), si può scrivere:
∗ )/T
e−(f (x)−f
pT (x) = Z ∗ )/T
= C̃ s̃(x),
e−(f (x)−f dx
D
dove Z
∗ )/T ∗ )/T
C̃ = 1/( e−(f (x)−f dx) e s̃(x) = e−(f (x)−f .
D
90
Quindi la funzione pT (x) ha la struttura (3.14) e, perciò, si può utilizzare il metodo di
Von Neumann.
Sia T uno scalare positivo, sia α uno scalare scelto a caso su [0, 1] e sia x un vettore
scelto a caso su D, se
∗
α ≤ e−(f (x)−f )/T , (3.15)
allora il punto x è una realizzazione della variabile aleatoria distribuita secondo la
funzione densità di probabiltà
∗ )/T
e−(f (x)−f
pT (x) = Z ∗ )/T
. (3.16)
e−(f (x)−f dx
D
Purtroppo, per avere la struttura (3.14), la funzione densità di probabilità pT (x) deve
far comparire nella sua espressione il valore ottimo f ∗ della funzione obiettivo. Per la
maggior parte dei problemi di ottimo globale questa quantità non è nota “a priori”,
quindi viene normalmente sostituita con una sua sovrastima fˆ. Quindi la tecnica di
generazione di un nuovo punto viene adattata di conseguenza ottendendo un punto che
è la realizzazione di una nuova variabile aleatoria.
Sia T uno scalare positivo, sia fˆ tale fˆ ≥ f ∗ , sia α uno scalare scelto a caso su [0, 1] e
sia x un vettore scelto a caso su D, se
ˆ
α ≤ e−[f (x)−f ]+ /T , (3.17)
dove [f (x)− fˆ]+ = max{0, f (x)− fˆ}, allora il punto x è una realizzazione della variabile
aleatoria distribuita secondo la funzione densità di probabiltà p̂T (x) data
ˆ
e−[f (x)−f ]+ /T
p̂T (x) = Z . (3.18)
ˆ
e−[f (x)−f ]+ /T dx
D
La nuova funzione densità di probabilità p̂T (x) può svolgere un ruolo simile a quello della
funzione densità di probabilità originaria pT (x). Infatti, al diminuire della temperaura
T , invece di concentrarsi solamente intorno ai minimi globali si concentra intorno a
tutti i punti x ∈ D tali che f (x) ≤ fˆ. Se fˆ è il miglior valore della funzione obiettivo
ottenuto, la funzione densità di probabilità p̂T (x) assegna maggiore probabilità alle
regioni in cui si ha, comunque, un miglioramento della funzione obiettivo.
Una possibile utilizzazione di punti generati con la distribuzione con funzione densità
di probabilità p̂T (x) è descritta nel seguenta algoritmo.
91
Algoritmo Simulated Annealing.
Passo 0: si sceglie una temperatura iniziale T0 , si genera a caso un punto x0 su D, si

pone x∗0 = x0 e k = 1;
Passo 1: si generano a caso un punto xk su D ed uno scalare αk su [0, 1];

∗
Passo 2: se αk > e−[f (xk )−f (xk−1 )]+ /Tk−1 allora si pone x∗k = x∗k−1 e si va al Passo 6;
Passo 3: partendo da xk si applica un algoritmo di ottimizzazione locale ottenendo yk ;
Passo 5: si calcola la Tk ∈ (0, Tk−1 ];
Il precedente algoritmo può essere considerato una via di mezzo tra l’Algoritmo Multi-
start 1, dove le minimizzazione locali vengono applicate a partire da ogni punto generato
a caso su D, e l’Algoritmo Multistart 2, dove le minimizzazione locali vengono applicate
solamente a partire dai punti generati a caso su D in cui si ha un miglioramento della
funzione obiettivo. Grazie al test al Passo 2, nell’Algoritmo Simulated Annealing, le
minimizzazioni vengono applicate a partire sia dai punti generati a caso su D in cui si
ha un miglioramento della funzione obiettivo e sia da punti generati a caso su D in cui
si ha un peggioramento della funzione obiettivo ma che possono essere considerati delle
realizzazioni di variabili aleatorie distribuite secondo la funzione densità di probabilità
p̂T (x).
Per quanto riguarda le proprietà di convergenza delle sequenze dei punti generati
dall’Algoritmo Simulated Annealing si può stabilire il seguente risultato.
Proposizione 3.1.5 Se la sequenza di temperature {Tk }, utilizzate nell’Algoritmo Si-
mulated Annealing, è tale che le funzioni densità p̂Tk (x) definiscono una sequenza di
misure di probabilità {mk (·)} che soddisfano le ipotesi di Proposizione 3.1.4 e se esiste
un minimo globale x∗ non vincolato della funzione f su D per cui l’algoritmo di mini-
mizzazione locale (utilizzato al Passo 2) soddisfa la Assunzione 3.1.1, allora la sequenza
{x∗k } di punti aleatori prodotti dall’Algoritmo Simulated Annealing è tale che:

lim P rob x∗k ∈ X ∗ = 1, (3.19)
k→∞
dove X ∗ è l’insieme dei minimi globali del Problema (3.1).

Prova. La dimostrazione della proposizione segue utilizzando gli stessi ragionamenti
fatti per dimostrare la Proposizione 3.1.3, relativa alle proprietà di convergenza dell’Al-
goritmo Multistart 1, con la sola differenza di usare la Proposizione 3.1.4 invece della
Proposizione 3.1.1
92
Una condizione sufficiente a garantire che la sequenza delle temperature Tk prodotte
dall’algoritmo siano tali da soddisfare l’ipotesi della precedente proposizione è che esista
un ε > 0 tale che
Tk ≥ ε, per ogni k.
Condizioni più deboli possono essere determinate notando che, per dimostrare il li-
mite (3.19), è sufficiente che le misure di probabilità derivanti dalle funzioni densità
di probabilità p̂T (x) soddisfino la (3.9) in corrispodenza solamente ad insiemi A con
meas(A) > 0 e contenuti nell’intorno B(x∗ ; ε) descritto nella Assunzione 3.1.1.
La scelta della sequenza di temperature {Tk }, oltre ad essere legata alla convergen-
za dell’algoritmo, influenza anche l’efficienza computazione dell’algoritmo. Infatti per
temperature più basse si tenderà a produrre punti che hanno maggiore probabilità di
essere una buona approssimazione di un minimo globale. Tuttavia questi punti saranno
più difficili da generare (si veda il test al Passo 2). Viceversa, a temperature più alte,
si genereranno più facilmente i punti ma che, però, avranno meno probabilità di essere
buone approssimazioni di un minimo globale.
3.1.3 Metodi che usano “popolazioni” di punti

A partire dall’approccio probabilistico si sono sviluppati vari metodi di ottimizzazione
globale di tipo euristico. Cioè metodi per cui non si può stabilire nessuna proprietà
teorica di convergenza. Questi metodi nascono dall’esigenza di affrontare problemi
di ottimizazione reali. Infatti, per quanto visto nel capitolo precendente (si veda il
Teorema 1.6.4 ed il Teorema 1.6.6) e per quanto descritto nei paragrafi precedenti di
questo capitolo, le proprietà di convergenza di un metodo sono legate al fatto che, al
crescere delle iterazione dell’algoritmo, la funzione obiettivo è valutata “praticamente”
su tutto l’insieme ammissibile. Tuttavia seguire, anche in maniera approssimata, questo
approccio può essere assolutamente impraticabile nella maggior parte dei casi reali. Per
questo motivo sono stati proposti dei metodi che si basano sui seguenti passi:
- ottenere delle informazioni sul comportamento globale della funzione obiettivo

sull’insieme ammissibile effettuando inizialmente un campionamento finito della
funzione obiettivo su un insieme, detto popolazione, iniziale di punti.
- migliorare iterativamente i punti che costituiscono la popolazione attraverso la

sostituzione dei punti in cui il valore della funzione obiettivo è più alta con dei
nuovi punti ottenuti attraverso delle minimizzazioni locali “approssimate”;
- ripetere il precedente procedimento di miglioramento fino a quando la popolazione

non si è “concentrata” intorno ai minimi globali della funzione obiettivo.
Tra le classi di metodi che si basano sull’uso di popolazioni di punti quelle più note e
più utilizzate sono:
- gli algoritmi genetici;
- gli algoritmi evolutivi;
93
- metodi di tipo “swarm”.
Per brevità, nel seguito ci si limiterà a richiamare gli approcci dei citati metodi. Questa
scelta è dovuta dalla difficoltà di dare delle trattazioni generali degli algoritmi genetici,
degli algoritmi evolutivi e dei metodi di tipo “swarm” in grado di rappresentare le varie
scelte algoritmiche particolari.
- Algoritmi genetici
Nel determinare i nuovi punti della famiglia, gli algoritmi genetici cercano di trarre
ispirazione dai processi evolutivi biologici. Infatti negli algoritmi genetici inizialmente
proposti le variabili del problema venivano codificate attarverso stringhe di binari, i
nuovi punti venivano generati attraverso la ripetizione delle seguenti due operazioni
”genetiche”::
- l’operazione di “crossover” che consiste nel selezionare a caso due punti della
popolazione (punti genitori) e tagliando le stringhe che li rappresentano in corri-
spondenza di uno stesso indice scelto a caso; i punti figli derivavano dallo scambio
delle parti delle stringhe dei genitori (figura 3.1);
- l’operazione di “mutation” in cui un vettore della popolazione viene “mutato”

cambiandogli una componente della striga scelta a caso (figura 3.2).
Gli algoritmi genetici più recenti non utilizzano la codifica binaria ma cercano di adat-
tare le due precedenti operazioni alla codifica orginaria delle variabili del problema di
ottizzazione da risolvere. Esempi di addattamento delle operazioni di “crossover” e di
“mutation” al caso in cui i vettori hanno la loro codifica originaria sono le seguenti:
- l’operazione di “crossover” se x ∈ D e y ∈ D sono dei vettori genitori scelti

dalla popolazione, le loro componenti vengono mischiate per dare vita a dei nuovi
vettori figli, nel seguente modo:
(x̃)i = αi (x)i + (1 − αi )(y)i , i = 1, . . . , n,

i i
(ỹ)i = α (y)i + (1 − α )(x)i , i = 1, . . . , n,
dove gli scalari αi sono scelti a caso su [−0.5, 1.5];
- l’operazione di “mutation” un vettore della popolazione x ∈ D viene “mutato”

perturbargli una sola componente, cioè viene generato il nuovo punto x̂ tale che:
(x̂)i = (x)i + α̂(u − l)i ,

(x̂)j = (x)j , j = 1, . . . , n, j 6= i,
dove l’indice i è scelto a caso e α̂ = 0.1 oppure è scelto a caso tra [−0.1, 0.1].
94
1 0 0 1
0 1 1 0
1 1 1 1
1 0 1 0
0 1 0 1
0 0 0 0
1 0 1 0
x y ~
x ~
y
Figura 3.1: Esempio dell’operazione di “crossover”.
1 1
0 0
1 1
1 1
0 1
0 0
1 1
x x̂
Figura 3.2: Esempio dell’operazione di “mutation”.
95
- Algoritmi evolutivi
La caratteristica che distingue gli algoritmi evolutivi dagli algoritmi gentici è il fatto che,
ad ogni ierazione, questi algoritmi cercano di aggiornare tutti i punti della popolazione.
Più in particolare, essi cercano di sostituire ogni punto x ∈ D della popolazione con
un nuovo punto y ∈ D ottenuto dalla combinazione di operazioni di “crossover” e di
“mutation”. Se nel nuovo punto y si ha un miglioramento della funzione obiettivo allora
il punto di partenza x viene sostituito dal nuovo punto y, altrimenti nella popolazione
viene mantenuto il punto x.
Le tecniche con cui vengono questi nuovi punti variano in maniera signicativa da
algoritmo ad algoritmo. Un esempio di una tale tecnica è il seguente:
scelto un punto x ∈ D della popolazione il nuovo punto y ∈ D si determina a

partire da x e da un punto x̂ ∈ D ottenuto dalla seguente operazione:
x̂ = xa + α̂(xb − xc ),
dove α̂ ∈ (0, 1] e xa , xb , xc sono scelti a caso nella popolazione di punti;
il nuovo punto y è dato, quindi, dalle seguenti relazioni:
(y)i = (x̂)i se αi ≤ 0.5 oppure i = ı̂,

i
(y)i = (x)i se α > 0.5 e i 6= ı̂,
dove l’indice ı̂ è scelto a caso tra {1, . . . , n} e gli scalari αi , i = 1, . . . , n, sono

scelti a caso tra [0, 1].
Negli algoritmi evolutivi più recenti si cerca di migliorare ogni punto della popolazione
sfruttando anche il più possibile tutte le informazioni sulla funzione obiettivo contenute
nei punti presenti nella popolazione.
- Metodi di tipo “swarm”

I metodi di tipo “swarm” hanno in comune con gli algoritmi evolutivi l’idea di cerca-
re aggiornare, ad ogni iterazione, tutti i punti della popolazione. Ma, a differenza di
quest’ultimi, non traggono ispirazione dai processi evolutivi ma piuttosto dal compor-
tamento degli sciami (swarm). Infatti essi interpretano i vettori che formano la famiglia
all’iterazione k-esima come punti che identificano la posizione dei membri di uno sciame
all’istante k-esimo. Quindi al variare delle iterazione, l’evoluzione della popolazione è
associata al movimento complessivo dello sciame.
Lo stato dello sciame al generico istante k-esimo è identificato dalle “posizioni” degli
elementi dello sciame
Sk = {x1k , . . . , xm
k },
e dalle corrispondenti velocità
Vk = {vk1 , . . . , vkm }.
96
Nel definire le posizioni degli elementi all’istante successivo k + 1 (cioè nel definire il
nuovo insieme Sk+1 ), questi metodi cercano di simulare il comportamento in natura dei
membri di uno sciame. Infatti il movimento di ciascun elemento tiene conto della espe-
rienza individuale (che può essere rappresentata dal miglior punto incontrato durante
il movimento del i-esimo membro dello sciame) e dalla esperienza globale dello sciame
(che può essere rappresentata dal miglior punto incontrato durante il movimento di
tutti i membri dello sciame).
In particolare, un esempio di formule utilizzate dai metodi di tipo “swarm” per descri-
vere il movimento della famiglia di punti è il seguente:
i
vk+1 = vki + crk1 (x̄ik − xik ) + crk2 (x∗k − xik ), i = 1, . . . , m,
xik+1 = xik + i
vk+1 , i = 1, . . . , m.
dove
f (x̄ik ) = min f (xih ),
h=1,...,k
f (x∗k ) = min f (x̄ik ),

i=1,...,m
dove c è una costante positiva, chiamata costante di accellerazione, rk1 e rk2 sono dei
scalari scelti a caso su [0, 1].
Nei metodi di tipo “swarm” più recenti, per controllare meglio l’evoluzione delle ve-
locità ed evitare che siano usati vettori vki troppo grandi, vengono introdotti ulteriori
coefficienti nella formula che fornisce le nuove velocità:
i
vk+1 = χ(wvki + c1 rk1 (x̄ik − xik ) + c2 rk2 (x∗k − xik ), i = 1, . . . , m.
dove w è una costante chiamata inerzia, c1 e c2 sono costanti positive chiamate coeffi-
ciente cognitivo e coefficiente sociale, χ è una costante chiamata fattore di costrizione.
3.2 Metodi che utilizzano partizioni dell’insieme ammis-

sibile
In questo capitolo viene brevemente considerata una classe di metodi deterministici
di l’ottimizzazione globale che si basano sull’idea di cercare di produrre sequenze di
partizioni dell’insieme ammissibile che tendano ad essere più addensate nelle regioni in
cui ci sono i minimi globali della funzione obiettivo.
Per descrivere in maniera formale questa nuova classe di metodi è necessario introdurre
la definizione di partizione di un insieme.
Definizione 3.2.1 (Partizione di un insieme) Dato un insieme F ⊆ Rn , una

collezione di insiemi {F i : i ∈ I} è una partizione dell’insieme F se si ha:
F i,
[
F=
i∈I
i
F j = ∂F i ∂F j ,
\ \
F ∀ i, j ∈ I, i 6= j;
97
dove ∂F j indica la frontiera dell’insieme F i .
3.2.1 Schema generale di un metodo che usa partizioni dell’insieme

ammissibile
Nel caso particolare in cui l’insieme ammissibile è costituito dall’insieme D = {x ∈ Rn :
l ≤ x ≤ u} un modo naturale di partizionarlo è quello di suddividerlo in sottoinsiemi
che hanno la stessa struttura. Seguendo questa linea, in questo capitolo, si considerano
metodi che hanno come punto caratterizzante il fatto che, ad ogni iterazione, viene
prodotta una partizione {D i : i ∈ Ik } dell’insieme ammissibile D con
D i = {x ∈ Rn : li ≤ x ≤ ui }, i ∈ Ik .
Un modello generale di un algoritmo che genera una sequenza di partizioni dell’insieme

ammissibile può essere descritto descritto dal seguente schema.
Algoritmo di Partizione
Passo 0: Si pone D 0 = D, l0 = l, u0 = u, I0 = {0} e k = 0;
Passo 1: data la partizione {D i : i ∈ Ik } di D con
D i = {x ∈ Rn : li ≤ x ≤ ui }, per ogni i ∈ Ik ,
si identifica un sottoinsieme di indici Ik∗ ⊆ Ik ;

si pone I¯0 = Ik , Iˆ0 = I ∗ e p = 0
k
Passo 2: si sceglie un indice h ∈ Iˆp e si partiziona D h in m ≥ 2 sottointervalli
D h1 , D h2 , . . . , D hm .
Passo 3: si pone:
I¯p+1 = I¯p
[
{hj } \ {h},
j=1,...,m
Iˆp+1 = Iˆp \ {h},
se Iˆp+1 6= ∅ si pone p = p + 1 e si torna al Passo 2;
Passo 4: si definisce la nuova partizione {D i : i ∈ Ik+1 } con
Ik+1 = I¯p+1 ,
si pone k = k + 1 e si torna al Passo 1.
98
Al Passo 1, data una partizione dell’insieme ammissibile, l’algoritmo seleziona (secondo
un criterio non ancora specificato) un certo numero di sottoinsiemi (identificati dall’in-
sieme di indici Ik∗ ) appartenenti alla partizione. Nel passo 2 e nel passo 3 ognuno dei
sottointervalli selezionati viene partizionato (utilizzando una tecnica anche essa non
specificata) in un numero m ≥ 2 di sottoinsiemi.
Per effettuare un analisi di alcune proprietà generali del precedente algoritmo è neces-
sario caratterizzare le techiche di partizione utilizzabili attraverso il fatto che siano in
grado di soddisfare la seguente ipotesi.
Assunzione 3.2.1 Esistono dei scalari ε1 , ε2 e ε3 , con 0 < ε1 < ε2 < 1 e ε3 ≥ 0 , tali
che ogni insieme D h , h ∈ Ik∗ , selezionato dall’algoritmo in una qualsiasi iterazione k,
è partizionato in m sottoinsiemi D hj , j = 1, . . . , m che soddisfano:
ε1 Πni=1 (uh − lh )i ≤ Πni=1 (uhj − lhj )i ≤ ε2 Πni=1 (uh − lh )i , j = 1, . . . , m.(3.20)
Poichè la produttoria può essere scomoda da trattare numericamente, usualmente si

preferisce far riferimento alla seguente assunzione equivalente alla precedente.
Assunzione 3.2.2 Esistono dei scalari ε1 , ε2 e ε3 , con 0 < ε1 < ε2 < 1 e ε3 ≥ 0 , tali
che ogni insieme D h , h ∈ Ik∗ , selezionato dall’algoritmo in una qualsiasi iterazione k,
è partizionato in m sottoinsiemi D hj , j = 1, . . . , m che soddisfano:
ε1 kuh − lh k ≤ kuhj − lhj k ≤ ε2 kuh − lh k, j = 1, . . . , m; (3.21)

(uhj − lhj )imin (uh − lh )imin
≥ ε3 . (3.22)
(uhj − lhj )imax (uh − lh )imax
dove, per un qualsiasi vettore v ∈ Rn , imin e imax sono dati da (v)imin = mini=1,...,n (v)i
e (v)imax = maxi=1,...,n (v)i
A differenza degli algoritmi di minimizzazione locale, che sono caratterizzati dalla se-
quenza di punti che generano, l’evoluzione dell’Algoritmo di Partizione è rappresentata
dallo sviluppo dei sottoinsiemi generati. Perciò le sue proprietà teoriche possono es-
sere analizzate caratterizzando le sequenze di insiemi che vengono prodotte al tendere
all’infinito delle iterazione dell’algoritmo.
Queste sequenze di insiemi possono essere individuate facendo corrispondere ad ogni
sottoinsieme D ik , con ik ∈ Ik , della partizione dell’insieme D della generica iterazio-
ne k-esima, un particolare sottoinsieme D ik−1 , con ik−1 ∈ Ik−1 della partizione della
iterazione precedente. In particolare, l’insieme D ik−1 è definito nelle seguente maniera:
- se il sottoinsieme D ik nasce da un un processo di divisione allora D ik−1 è il sottoin-
sieme che lo ha generato;
- se, invece, il sottoinsieme D ik non deriva da un un processo di partizione allora si

pone D ik−1 = D ik .
99
Ripertendo lo stesso procedimento, si può associate all’insieme D ik−1 un insieme D ik−2 ,
con ik−2 ∈ Ik−2 , della partizione della iterazione k-2, a quest’ultimo si può associate
uno della partizione della iterazione k-3 e cosi via fino ad arrivare all’insieme D i0 = D.
Quindi, ad ogni sottoinsieme D ik , con ik ∈ Ik , della partizione della iterazione k-esima
si può far corrispondere la sequente collezione di insiemi
D i0 , D i1 , . . . , D ik−1 , D ik ,
Al crescere delle iterazioni dell’algoritmo, la precedente collezione di insiemi produce

una sequenza annidata {D ik } di insiemi cioè una sequenza tale che, per ogni k, si ha:
D ik+1 ⊆ D ik .
Inoltre, ad ogni iterazione, le istruzioni del Passo 2 implicano che un determinato inter-
vallo viene suddiviso in un numero prefissato di sottointervalli e, quindi, il numero di
sottoinsiemi dell’insieme ammissibile aumenta di una quantità fissa. Tra le sequenze an-
nidate prodotte dall’algoritmo alcune sono particolarmante significative, in particolare
si ha la sequenza definizione.
Definizione 3.2.2 Una sequenza {D ik } prodotta dall’Algoritmo di Partizione è detta

strettamente annidata se
D ik+1 ⊂ D ik , per un numero infinito di volte. (3.23)
Perciò, per le sequenze non strettamente annidate, esiste un indice k0 dopo il quale il
sottoinsieme D ik0 non viene più suddiviso, cioè:
D ik = D ik 0 , per tutti k ≥ k0 . (3.24)
Mentre per quelle strettamente annidate il processo di divisione continua un numero

infinto di volte.
Le tre seguenti proposizioni descrivono delle caratterizzazioni matematiche delle se-
quenze di insiemi strettamente annidate prodotte dall’Algoritmo di Partizione.
Proposizione 3.2.3 Se l’Assunzione 3.2.2 è soddisfatta, una sequenza {D ik } prodotta

dall’Algoritmo di Partizione è strettamente annidata se e solamente se
lim kuik − lik k = 0. (3.25)

k→∞
Prova. Sia {D ik } una sequenza prodotta dall’Algoritmo di Partizione. Dalla defi-

nizione della sequenza {D ik } e dalle istruzioni dell’algoritmo, ogni volta che accade
che
D ik ⊂ D ik−1 ,
significa che, nell’iterazione k-1, il sottoinsieme D ik è stato generato dalla partizione
dell’insieme D ik−1 . Dall’Assunzione 3.2.2 si ha
ε1 kuik−1 − lik−1 k ≤ kuik − lik k ≤ ε2 kuik−1 − lik−1 k, (3.26)
100
Ricordando nuovamente la definizione della sequenza di insiemi {D ik } si ha che, per
j = 1, . . . , k,
D ij ⊂ D ij−1 oppure D ij = D ij−1 .
Applicando ripetutamente la (3.26) si ha
(ε1 )pk ku0 − l0 k ≤ kuik − lik k ≤ (ε2 )pk ku0 − l0 k, (3.27)
dove pk indica quante volte il processo di divisione del Passo 2 è intervenuto per generare
l’insieme D ik oppure, equivalentemente, quante volte si ha la stretta inclusione tra due
insiemi successivi nella sequenza D i0 , D i1 , . . . , D ik−1 , D ik .
Ora, se la sequenza {D ik } prodotta dall’algoritmo è strettamente annidata segue, per
definizione, che
lim pk = ∞,
k→∞
da cui, utilizzando la (3.27) e il fatto che ε2 ∈ (0, 1), si ottiene che
lim kuik − lik k ≤ lim (ε2 )pk ku0 − l0 k = 0.

k→∞ k→∞
Viceversa, se la sequenza {D ik } prodotta dall’algoritmo soddisfa il limite (3.25), dalla

(3.27) segue che
lim (ε1 )pk ku0 − l0 k ≤ lim kuik − lik k = 0.
k→∞ k→∞
La precedente relazione e il fatto che ε1 ∈ (0, 1) implicano che
lim pk = ∞,
k→∞
da cui segue che la sequenza {D ik } prodotta dall’algoritmo è strettamente annidata.

dall’Algoritmo di Partizione è strettamente annidata se e solamente se
lim uik = x̄ (3.28)

k→∞
lim lik = x̄; (3.29)
k→∞
oppure, equivalentemente
∞
D ik = {x̄}.
\
k=0

dall’Algoritmo di Partizione è strettamente annidata e ∞ ik
k=0 D = {x̄} se e solamente
T
se, per ogni ε > 0, esiste un indice k̄ tale che per ogni k ≥ k̄ si ha:
D ik ⊂ B(x̄; ε). (3.30)
101
Dopo aver descritto alcune proprietà delle sequenze di insiemi strettamente annida-
te prodotte dall’Algoritmo di Partizione, nella seguente proposizione si affronta il
problema di garantire che tale algoritmo produca almeno una di queste sequenze.
Proposizione 3.2.6 Se l’Assunzione 3.2.2 è soddisfatta, l’Algoritmo di Partizione

genera almeno una sequenza strettamente annidata di insiemi {D ik }.
Prova. La dimostrazione segue ricordando i seguenti due punti caratterizzanti l’Algo-
ritmo di Partizione:
- alla generica iterazione k-esima, l’algoritmo ha prodotto una partizione {D i , i ∈
Ik } dell’insieme ammissibile D tale che:
Di , Int(D i ) Int(D j ) = ∅,
[ \
D= ∀ i, j ∈ Ik , i 6= j; (3.31)
i∈Ik
- ripetendo gli argomenti utilizzati nella dimostrazione della Proposizione 3.2.3

segue che l’applicazione ripetuta dell’Assunzione 3.2.2 implica, per ogni i ∈ Ik ,
(ε1 )pi ku0 − l0 k ≤ kui − li k ≤ (ε2 )pi ku0 − l0 k; (3.32)
(ui − li )imin 0 0
pi (u − l )imin
≥ (ε3 ) . (3.33)
(ui − li )imax (u0 − l0 )imax
dove pi indica il numero di volte in cui processo di divisione è intervenuto per
generare l’insieme D i a partire dall’insieme iniziale D.
Ora, si supponga per assurdo che l’algoritmo non generi nessuna sequenza strettamente
annidata. Questo implicherebbe l’esistenza di un valore p̄ tale che, per qualsiasi k,
limiterebbe superiormente i numeri di processi di divisione che avrebbero generato i
sottoinsiemi D i , con i ∈ Ik , della partizione di D nella iterazione k-esima. Cioè, per
ogni k e per ogni i ∈ Ik , si avrebbe che:
pi ≤ p̄. (3.34)
Le (3.32),(3.33) e (3.34) implicherebbero che, per ogni k e per ogni i ∈ Ik ,:
(ε1 )p̄ ku0 − l0 k ≤ kui − li k
(ui − li )imin 0 0
p̄ (u − l )imin
≥ (ε3 )
(ui − li )imax (u0 − l0 )imax
da cui se ne ricaverebbe l’esistenza di una costante δ̄ tale che, per ogni k e per ogni
i ∈ Ik , risulterebbe:
meas(D i ) ≥ δ. (3.35)
Dalle istruzioni dell’algoritmo si ha che, ad ogni iterazione, viene generata una nuova
partizione con un numero di sottoinsiemi che è aumentato di m ≥ 2 elementi rispet-
to alla partizione precedente. Quindi, per k tendente all’infinito, il numero di sot-
toinsiemi che costituiscono le partizioni tende all’infinito. Questo può essere espresso
equivalentemente con
lim |Ik | = ∞, (3.36)
k→∞
102
dove |Ik | indica la cardinalità dell’insieme Ik , cioè il numero di indici che lo compongono.
Le (3.31), (3.35) e (3.36) produrrebbero un assunrdo con la compatezza dell’insieme
ammissibile D. Infatti le (3.31), (3.35) e (3.36) implicherebbero che un insieme compat-
to può essere partizionato in un numero arbitrariamente grande di insiemi che hanno
misura uniformemente diversa da zero.
I risultati descritti in questa sottosezione derivano scegliendo la tecnica di partizione uti-

lizzata nello schema generale dell’Algoritmo di Partizione in maniera che l’Assunzione
3.2.2 sia soddisfatta.
Le prossime due sottosezioni sono dedicate all’analisi del comportamento asintotico
dell’algoritmo nel caso di due differenti approcci per la scelta dei sottoinsiemi da
partizionare.
3.2.2 Scelta dei sottoinsiemi da partizionare: sottoinsiemi di dimen-

sioni più grandi.
Una possibile caratteristica su cui possono basarsi i metodi che utilizzano partizioni
è quella di cercare di localizzare i minimi globali tentando di analizzare il comporta-
mento della funzione obiettivo su insiemi sempre più piccoli. Infatti al diminuire delle
dimensioni dell’insieme, le infomazioni locali della funzioni diventano sempre più atten-
dibili. Seguendo questa impostazione, la scelta dei sottoinsiemi da partizionare deve
garantire che, al crescere delle iterazioni, le dimensioni di tutti gli insiemi che costi-
tuiscono la partizione tendano a diminuire. In questa sottosezione viene mostrato che
questa caratteristica può essere garantita richiedendo che almeno uno dei sottoinsiemi
di dimensione massima è partizionato, ad ogni iterazione.
Per formalizzare questa modalità di scelta dei sottoinsiemi da partizionare ed effettuar-
ne l’analisi teorica è necessario introdurre alcune nuove notazioni. Data una partizione
{D i : i ∈ Ik } si identifica l’ampiezza massima dei sottointervalli con:
dmax
k = max kui − li k, (3.37)
i∈Ik
e l’insieme degli indici dei sottoinsiemi che hanno ampiezza massima con:
Ikmax = {i ∈ Ik : kui − li k = dmax

k }. (3.38)
A questo punto si può introdurre la seguente assunzione.
Assunzione 3.2.3 Esiste un infinito sottoinsieme di indici K ⊆ {1, 2, 3, . . .}, tale che
Ikmax ∩ Ik∗ 6= ∅ per ogni k ∈ K.
La proposizione seguente mostra che, se almeno un sottoinsieme di dimensione massima

viene selezionato in un sottoinsieme infinito di iterazione, il processo di partizione di
ogni sottoinsieme generato non viene interrotto mai.
103
Proposizione 3.2.7 Si supponga che l’Assunzione 3.2.2 e l’Assunzione 3.2.3 siano
soddisfatte. Siano {D i , i ∈ Ik } la partizione generata dall’Algoritmo di Partizione
all’iterazione k-esima e dmax
k la quantità data dalla (3.37). Allora
lim dmax
k = 0. (3.39)
k→∞
Dalla precedente proposizione segue che l’Algoritmo di Partizione, con la precedente

richiesta sulla scelta dei sottoinsiemi da partizionare, genera un insieme di punti che, al
crescere delle iterazioni, tende a diventare un insieme denso su D, come è formalizzato
dal seguente risultato.

soddisfatte. Allora si ha che:
i) tutte le sequenze di insiemi {D ik } generate dall’Algoritmo di Partizione sono

strettamente annidate;
ii) per ogni x̃ ∈ D l’Algoritmo di Partizione genera una sequenza di insiemi {D ik }

strettamente annidata tale che
∞
D ik = {x̃}.
\
k=0
Dal precedente risultate seguono i seguenti corollari.
Corollario 3.2.9 Si supponga che l’Assunzione 3.2.2 e l’Assunzione 3.2.3 siano soddi-
sfatte. Sia {D i , i ∈ Ik } la partizione generata dall’Algoritmo di Partizione all’iterazione
k-esima. Per ogni x̄ ∈ D e per ogni ε > 0 esiste una iterazione k dell’Algoritmo di
Partizione in cui c’è un indice hk ∈ Ik tale che:
D hk ⊂ B(x̄; ε).
Corollario 3.2.10 Si supponga che l’Assunzione 3.2.2 e l’Assunzione 3.2.3 siano sod-
disfatte. Sia {D i , i ∈ Ik } la partizione generata dall’Algoritmo di Partizione all’itera-
zione k-esima. Per ogni minimo globale x⋆ di f (x) su D e per ogni ε > 0 esiste una
iterazione k dell’Algoritmo di Partizione in cui c’è un indice hk ∈ Ik tale che:
D hk ⊂ B(x∗ ; ǫ).
104
3.2.3 Scelta dei sottoinsiemi da partizionare: sottoinsiemi più pro-
mettenti.
Nella sottosezione precedente si è considerato il caso in cui l’Algoritmo di Partizione,
nella scelta dei sottoinsiemei da partizionare, includesse uno di dimensioni massime.
In questa sottosezione si analizza una strategia diversa in cui l’idea base è quella di
selezionare i sottoinsiemi considerati più promettenti. I punti caratterizzanti di questa
scelta dei sottoinsiemi da partizionare sono i seguenti:
- data una partizione {D i : i ∈ Ik } dell’insieme ammissibile D;
- per ogni sottoinsieme D i , i ∈ Ik , viene calcolato uno scalare Rki che fornisce
una stima del valore minimo che assume la funzione obiettivo nel sottoinsieme
considerato;
- vengono determinati gli insiemi D h , a cui corrispondono gli scalari Rkh a valore
più basso;
- uno dei precedenti insiemi viene suddiviso ulteriormente (in alcuni algoritmi
vengono suddivisi tutti).
Per incominciare ad analizzare formalmente questa seconda strategia di scelta dei

sottoinsiemi da partizionare è utile introdurre la seguente ipotesi.
Assunzione 3.2.4 Per ogni k, si ha Ik∗ = {h} dove l’indice h è tale che
Rkh = min Rki ,

i∈Ik
con i valori d’interesse Rki , i ∈ Ik , che soddisfano a:

T∞
i) per ogni sequenza strettamente annidata di insiemi {D ik }, con k=0 D
ik = {x̄},
si ha
lim Rkik = f (x̄);
k→∞
ii) in corrispondenza ad un minimo globale x∗ ∈ X ∗ esiste un indice k̄ tale che, se

D jk , jk ∈ Ik , è l’insieme per cui x∗ ∈ D jk , si ha che, per ogni k ≥ k̄,
Rkjk ≤ f (x∗ ).
La seguente proposizione caratterizza il comportamento dell’Algoritmo di Partizione

nel caso in cui utilizzi, come strategia di scelta dell’insieme da partizionare, quella de-
scritta dall’Assuzione 3.2.4. In particolare essa mostra che ogni sequenza strettamente
annidata prodotta dall’algoritmo ”converge” verso un minimo globale della funziione
obiettivo.
105
soddisfatte. Allora, per ogni sequenza strettamente annidata di insiemi {D ik } prodotta
dall’Algoritmo di Partizione, si ha che
∞
D ik ⊆ X ∗ .
\
(3.40)
k=0
(Dove X ∗ è l’insieme dei minimi globali della funzione f sull’insieme ammissibile D.)
Prova. Si procede assumendo, per assurdo, che l’Algoritmo di Partizione produca una
sequenza strettamente annidata di insiemi per cui non valga la (3.40), cioè una sequenza
per cui si abbia:
∞
D ik = {x̄},
\
k=0
con x̄ ∈
/X ∗.
Sia K ⊆ {1, 2, . . .} il sottoinsieme degli indici delle iterazioni dell’algoritmo in cui
l’insieme D ik viene suddiviso. Dalle istruzioni dell’algoritmo si ha che, per k ∈ K:
Rkik = min Rki . (3.41)

i∈Ik
Per ogni k ∈ K, sia Dkjk l’insieme che contiene il minimo globale x∗ ∈ X ∗ considerato
nel punto ii) dell’Assunzione 3.2.4. Dalla (3.41) si ha che, per ogni k ∈ K:
Rkik ≤ Rkjk . (3.42)
L’assunzione ii) implica l’esistenza di un indice k̄ tale che, per tutti gli indici k ∈ K e
k ≥ k̄, si ha:
Rkik ≤ Rkjk ≤ f (x∗ ). (3.43)
Facendo tendere k all’infinito ed utilizzando l’ipotesi i), si ottiene dalla (3.43):
lim Rkik = f (x̄) ≤ f (x∗ ),

k∈K, k→∞
/ X ∗.
che produrebbe un assurdo con il fatto che x̄ ∈
Le proprietà dell’Algoritmo di Partizione posso essere completate richiedendo la se-

guente assunzione che è un rafforzamento dell’Assunzione 3.2.4.
Assunzione 3.2.5 Per ogni k si ha Ik∗ = {h} dove l’indice h è tale che
Rkh = min Rki ,

i∈Ik
con i valori d’interesse Rki , i ∈ Ik , che soddisfano a:
106
T∞
i) per ogni sequenza strettamente annidata di insiemi {D ik }, con k=0 D
ik = {x̄},
si ha
lim Rkik = f (x̄);
k→∞
ii) per ogni minimo globale x∗ ∈ X ∗ esistono una costante δ > 0 ed un indice k̄ tali
che, se D jk , jk ∈ Ik , è l’insieme per cui x∗ ∈ D jk , si ha che, per ogni k ≥ k̄,
Rkjk ≤ f (x∗ ) − δkujk − ljk k.
Utilizzando questa nuova assunzione si può stabilire la seguente proposizione che assi-
cura che ogni minimo globale ”attrae” una sequenza di insiemi strettamente annidata
di insiemi prodotta dall’algoritmo .

soddisfatte. Allora, per ogni minimo globale x∗ ∈ X ∗ , esiste una sequenza strettamente
annidata di insiemi {D ik } prodotta dall’Algoritmo di Partizione tale che:
∞
D ik = {x∗ }.
\
(3.44)
k=0
Prova. Si procede assumendo, per assurdo, che esista un minimo globale x∗ ∈ X ∗

per cui L’Algoritmo di Partizione non produca una sequenza strettamente annidata
di insiemi per cui valga la (3.44). In altre parole si assume che, per ogni sequenza
strettamente annidata di insiemi {D ik } prodotta dall’Algoritmo di Partizione si abbia:
∞
D ik = {x̄},
\
k=0
con x̄ 6= x∗ .
Dalla precedente relazione si avrebbe, come prima conseguenza, che la sequenza di
sottoinsiemi {D jk }, considerati nel punto ii) dell’Assunzione 3.2.5 e contenenti il minimo
globale x∗ , non sarebbe strettamente annidata e, quindi, esisterebbero uno scalare ε > 0
ed un indice k̃ tali che per ogni k ≥ k̃ si avrebbe:
kujk − ljk k ≥ ε. (3.45)
Sia {D ik } una sequenza strettamente annidata di insiemi prodotta dall’Algoritmo di

Partizione e sia K ⊆ {1, 2, . . .} il sottoinsieme degli indici delle iterazioni dell’algoritmo
in cui l’insieme D ik viene suddiviso, cioè ik ∈ Ik∗ , per ogni k ∈ K. Quindi, per ogni
k ∈ K, si ha che:
Rkik = min Rki . (3.46)
i∈Ik
Il punto ii) dell’Assunzione 3.2.5, (3.45) e (3.46) implicano che per tutti gli indici k ∈ K
e k ≥ max{k̄, k̃}, si ha:
Rkik ≤ Rkjk ≤ f (x∗ ) − δkujk − ljk k ≤ f (x∗ ) − δ ε. (3.47)
107
Facendo tendere k all’infinito ed utilizzando il punto i) dell’Assunzione 3.2.5, si ottiene
dalla (3.47):
lim Rkik = f (x̄) ≤ f (x∗ ) − δ ε,
k∈K, k→∞
che produrrebbe un assurdo con il fatto che x∗ ∈ X ∗ .
Unendo la Proposizione 3.2.11 e la Proposizione 3.2.12 con la Proposizione 3.2.5 si

ottengono i seguenti corollari
zione k-esima. Esiste un minimo globale x⋆ di f (x) su D tale che, per ogni ε > 0, esiste
una iterazione k dell’Algoritmo di Partizione in cui c’è un indice hk ∈ Ik tale che:
D hk ⊂ B(x∗ ; ǫ).
zione k-esima. Per ogni minimo globale x⋆ di f (x) su D e per ogni ε > 0 esiste una
iterazione k dell’Algoritmo di Partizione in cui c’è un indice hk ∈ Ik tale che:
D hk ⊂ B(x∗ ; ǫ).
subsectionScelta dei scalari Rki che utilizzano una sovrastima della costante di Lipschitz
della funzione obiettivo.
Efficienti valori per gli scalari Rki può essere ottenuti facilmente nel caso di in cui sia
nota una sovrastima della costante di Lipschitz della funzione da minimizzare.
Prima di tutto può essere utile richiamare la definizione di funzione Lipschitziana.
Definizione 3.2.15 Dato un insieme F ⊆ Rn , una funzione f : F → R si dice

Lipschitziana su F, se esiste una costante L > 0 (chiamata costante di Lipschitz) tale
che per tutti x, y ∈ F si ha
|f (y) − f (x)| ≤ Lky − xk. (3.48)
La richiesta che la funzione obiettivo sia Lipschitziana non è una ipotesi particolarmente
restrittiva. Per esempio, la seguente proposizione mostra che, su un insieme convesso e
compatto, una funzione continuamente differenziabile è sicuramente Lipschitziana.
Proposizione 3.2.16 Sia F ⊂ Rn un insieme convesso e compatto e sia f : F → R

una funzione continuamente differenziabile. Allora la funzione f è Lipschitziana su F.
108
Prova. Ricordando il Teorema della Media si ha che, comunque scelti y, x ∈ F:
f (y) = f (x) + ∇f (x + θ(y − x))T (y − x),
con θ ∈ [0, 1]. Dalla uguaglianza precedente si ottiene:
|f (y) − f (x)| ≤ L̃ky − xk,
dove la costante L̃ è data da
L̃ = max k∇f (x)k,
x∈F
ed è ben definita dalla continuità di ∇f e dalla compatezza del insieme F.
La precedente proposizione si applica in particolare alla classe di problemi di ottimiz-

zazione che si sta trattando, cioè
min f (x) (3.49)
x ∈ D,
dove D = {x ∈ Rn : l ≤ x ≤ u}.
Nel seguito di questo sezione si assume che la funzione obiettivo f sia Lipschitziana
sull’insieme ammissibile D e che L sia la sua costante di Lipschitz o un sua sovrastima.
Dalla Definizione 3.2.15 si ha che una funzione Lipschitziana sull’insieme D soddisfa
contemporaneamente le due seguenti relazioni (si veda figura 3.3):
f (y) ≥ f (x) − Lky − xk (3.50)
f (y) ≤ f (x) + Lky − xk (3.51)
per ogni x, y ∈ D.
f(x 0 ) + L ||x - x 0 || f(x)
f(x 0 ) - L ||x - x 0||
Figura 3.3: Funzione Lipschitziana.
La prima delle due precedenti relazioni può essere sfruttata per definire gli scalari Rki
associati ai vari intervalli {D i , con i ∈ Ik }. L’idea è quella di considerare il punto
centrale xi dell’insieme D i e di usare la sottostima della funzione obiettivo data da:
fî (x, L) = f (xi ) − Lkx − xi k.
109
In particolare, per ogni i ∈ Ik , si può fare le seguenti scelte:
L
Rki = Ri = min fî (x, L) = f (xi ) − kui − li k, (3.52)
x∈D i 2
L’ultima uguaglianza segue dal fatto che per ogni x ∈ D i si ha:

v v
u n u n
ui + li 2

i
uX uX
kx − x k = t xi − = t (xi − li )2 + (xi − ui )2 + 2(xi − li )(xi − ui )
i=1
2 i=1
v
u n
(xi − li )2 + (ui − xi )2 + 2(xi − li )(ui − xi ) = kui − li k.
uX
≤t
i=1
In questo contesto si ha la seguente proposizione.
Proposizione 3.2.17 Se l’Assunzione 3.2.2 è soddisfatta allora:

- se L è la costante di Lipschitz della funzione f , gli scalari Rki definiti dalla (3.52)
soddisfano l’Assunzione 3.2.4;
- se L è una sovrastima della costante di Lipschitz della funzione f , gli scalari Rki
soddisfano l’Assunzione 3.2.5
Prova. Riguardo i punti i) di Assunzione 3.2.4 e di Assunzione 3.2.5, la Proposizione
3.2.4 assicura che ogni sequenza {D ik } strettamente annidata prodotta dall’Algoritmo
di Partizione soddisfa:
lim uik = x̄;

k→∞
lim lik = x̄;
k→∞
lim xik = x̄.
k→∞
che implicano
L i
lim Rki = lim f (xi ) − ku − li k = f (x̄),
k→∞ k→∞ 2
da cui seguono i punti i punti i) di Assunzione 3.2.4 e di Assunzione 3.2.5.
Sia x∗ un minimo globale del problema e sia {D jk } il sottoinsieme che contiene x∗ alla
k-esima iterazione. Se L è la costante di Lipschitz della funzione allora si ha:
L
f (x∗ ) ≥ f (xjk )−Lkx∗ −xjk k ≥ min f (xjk )−Lkx−xjk k = f (xjk )− kujk −ljk k = Rkjk ,
x∈D jk 2
che dimostra il punto ii) dell’Assunzione 3.2.4.
Si consideri ora il caso in cui la costante L è una sovrastima della costante di Lipschitz
cioè si abbia:
L = L̃ + δ,
110
dove L̃ è la vera costante di Lipschitz. In questo caso si ha:
δ δ L

f (x )− kujk −ljk k ≥ min f (xjk )−L̃kx−xjk k − kujk −ljk k = f (xjk )− kujk −ljk k = Rkjk ,
∗
2 x∈D jk 2 2
da cui segue il punto ii) dell’Assunzione 3.2.5.

Quando la costante di Lipschitz della funzione obiettivo non è nota, si può cercare di
utilizzare le valutazione della funzione obiettivo effettuate durante le iterazioni dell’al-
goritmi per cercare di estrarre informazioni sul comportamento globale della funzione
obiettivo. I questo caso, per ogni i ∈ Ik , si possono definire i seguenti scalari:
Lik i
Rki = f (xi ) − ku − li k. (3.53)
2
Ripetendo i passi della dimostrazione di Proposizione 3.2.17 e ricordando l’Assunzione
3.2.5 si stabilire la seguente proposizione che indica che per assicurare buone proprietà
di convergenza è sufficiente essere in grado di stimare dopo un numero finito di iterazioni
le costanti di Lipschitz locali della funzione in regioni vicino ai minimi globali.
Proposizione 3.2.18 Se l’Assunzione 3.2.2 e se le sequenze {Lik } sono limitete per

ogni i ∈ Ik , allora:
- se in corrispondenza ad un minimo globale x∗ ∈ X ∗ esiste un indice k̄ tale che,

se D jk , jk ∈ Ik , è l’insieme per cui x∗ ∈ D jk , si ha per ogni k ≥ k̄,
Ljkk jk
f (xjk ) − ku − ljk k ≤ f (x∗ ),
2
allora ogni sequenze di insiemi {D ik } strettamente annidata prodotta dall’algorit-
mo è tale che: ∞
D ik ⊆ X ∗ ;
\
k=0
- se per ogni minimo globale x∗ ∈ X ∗ esistono una costante δ > 0 ed un indice k̄

tali che, se D jk , jk ∈ Ik , è l’insieme per cui x∗ ∈ D jk , si ha per ogni k ≥ k̄,
Ljkk jk
f (xjk ) − ku − ljk k < f (x∗ ) − δkujk − ljk k,
2
allora, per ogni x∗ ∈ X ∗ , l’algoritmo produce una sequenza di insiemi {D ik }
strettamente annidata tale che
∞
D ik = {x∗ }.
\
k=0
111
3.2.4 Algoritmo di Partizione con minimizzazioni locali.
Analogamente a quanto avvenuto nel caso degli algoritmi probabilistici anche gli algo-
ritmi che partizionano l’insieme ammissibile possono sfruttare al loro interno l’efficienza
dei metodi di ottimizzazione locale in modo da migliorare le loro proprietà teoriche e
la loro effficienza computazionale. In particolare il seguente algoritmo è un esempio di
un Algoritmo di Partizione che utilizza minimizzazioni locali.
Algoritmo di Partizione Multistart.
Passo 0: Si pone D 0 = D, l0 = l, u0 = u, I0 = {0}, si sceglie un punto x0 ∈ D 0 , si

pone x∗0 = x0 e k = 0;
Passo 1: data la partizione {D i : i ∈ Ik } di D;

si identifica un sottoinsieme di indici Ik∗ ⊆ Ik ,
si pone I¯0 = Ik , Iˆ0 = Ik∗ e p = 0;
Passo 2: si sceglie un indice h ∈ Iˆp e si partiziona D h in m ≥ 2 sottointervalli
D h1 , D h2 , . . . , D hm ,
si scelgono i punti xhj ∈ D hj , per j = 1, . . . , m;
Passo 3: a partire da ogni punto xhj , j = 1, . . . , m, si effetuano delle minimizzazioni

locali ottenendo y hj , j = 1, . . . , m;
si sceglie y ∗ tale che f (y ∗ ) = minj=1,...,m f (y hj );
se f (y ∗ ) < f (x∗k ) si pone x∗k+1 = y ∗ ; altrimenti si pone x∗k+1 = x∗k ;
Passo 4: si pone:
I¯p+1 = I¯p
[
{hj } \ {h},
j=1,...,m
Iˆp+1 = Iˆp \ {h},
Ik+1 = I¯p+1 ;
Come accenato, l’utilizzazione dei metodi di ottimizzazione locale permette di realizzare

degli algoritmi con interessanti proprietà teoriche. In particolare, per quando riguarda
il precedente algoritmo, ha si il seguente risultato.
112
Proposizione 3.2.19 Si supponga che siano verificate l’Assunzione 3.2.2 ed una tra
l’Assunzione 3.2.3 e l’Assunzione 3.2.5. Se esiste un minimo globale x∗ della funzione
f su D per cui l’algoritmo di minimizzazione locale (utilizzato al Passo 3) soddisfa
la la Assunzione 3.1.1 allora esiste una iterazione k̄ in cui L’Algoritmo di Partizione
Multistart produce un punto x∗k̄ tale che:
x∗k̄ ∈ X ∗ . (3.54)
Prova. la prova segue direttamente dal Corollario 3.2.10 oppure dal Corollario 3.2.14
e dalla la Assunzione 3.1.1 dell’algoritmo locale.
3.2.5 Metodi che non utilizzano stime della costante di Lipschitz della
funzione obiettivo
Da quanto visto nella sezione precedente è sufficente ottenere, entro un numero sufficien-
temente grande di iterazioni, una sovrastima della costante di Lipschitz della funzione
obiettivo in un intorno di un minimo globale per garantire la convergenza di un metodo
di partizione verso il minimo globale. Tuttavia, anche quest’ultima richiesta pone dei
limiti sulla garanzia di ottenere un minimo globale utilizzando questi algoritmi. Questo
motiva il tentativo di definire degli algoritmi che cerchino di sfruttare l’ipotesi che la
funzione è Lipschitziana senza richiedere, però, nessuna informazione sulla costante di
Lipschitz. Tra questi metodi uno dei più significativi ed importanti è quello chiamato
Algoritmo Direct.
L’Algoritmo Direct, come gli algoritmi diagonali, partiziona l’insieme ammissibile D in
un numero crescente di sottointervalli D i = {x ∈ Rn : li ≤ x ≤ ui } con i ∈ Ik (da cui
il nome dividing rectangles”). Ad ogni iterazione, un certo numero di sottointervalli
vengono giudicati di interesse e, di conseguenza, vengono ulteriormente suddivisi. La
maggiore novità dell’Algoritmo Direct è il modo con cui giudica l’interesse di un sotto-
intervallo. Infatti gli algoritmi diagonali scelgono delle stime delle costanti di Lipschitz
locali e, sfruttando la Lipschitzianetà della funzione obiettivo, selezionano il sottointer-
vallo di maggiore interesse. Invece l’Algoritmo di Direct seleziona ogni sottointervallo
per cui esiste un valore della costante di Lipschitz della funzione obiettivo che rende il
sottointervallo considerato il più interessante.
In maniera simile a quanto fatto nella sezione precedente, il punto di partenza di questo
algoritmo è di misurare l’interesse di un intervallo D i calcolando il valore che assume
ai suoi punti estremi la sottostima della funzione obiettivo
fî (x, L̄) = f (xi ) − L̄kx − xi k,
dove xi è il punto centrale dell’insieme D i e L̄ è una stima della costante di Lipschitz

della funzione obiettivo (figura (3.4)). Gli intervalli con valori più bassi sono, quindi,
considerati di maggiore interesse.
Tuttavia i valori assunti agli estremi dei sottoinsiemi dalle funzioni fî (x, L̄) dipendono
dal particolare valore della stima L̄. Infatti per valori molto grandi di L̄ sono giudicati
113
f (xi )
fˆ i ( x , L ) = f ( x i ) − L x − x i
Di
li xi ui
Figura 3.4: Esempio della sottostima fˆ(x, L̄).
interessanti i sottoinsiemi di dimensioni massime (figura (3.5)). Per valori molto piccoli
di L̄ sono giudicati interessanti i sottoinsieme a cui corrispondono i valori più piccoli
f (xi ) (figura (3.6)). Tutti gli altri sottointervalli possono essere divisi in due gruppi: il
primo costituito da sottoinsiemi per cui esiste un valore di L̄ per cui sono considerati
interessanti (figura (3.7)) e il secondo costituito da sottoinsiemi per cui non esiste un
valore di L̄ per cui sono considerati interessanti (sottoinsieme D 3 della figura (3.7)).
f (x4)
f ( x1 ) f (x3 )
f (x2)
l D1 D2 D3 D4 u
Figura 3.5: Esempio di valutazioni dei sottoinsiemi per L̄ grande.
Formalmente l’Algoritmo Direct usa la seguente definizione di sottointervalli potenzial-

mente ottimi.
114
f (x4)
f ( x1 ) f (x3 )
f (x2)
l D1 D2 D3 D4 u
Figura 3.6: Esempio di valutazioni dei sottoinsiemi per L̄ piccolo.
f (x4)
f (x3 )
f ( x1 )
f (x2)
l D1 D2 D3 D4 u
Figura 3.7: Esempio di valutazioni dei sottoinsiemi per L̄ medio.
115
Definizione 3.2.20 Data la partizione {D i : i ∈ I} dell’insieme D, dove, per ogni
i∈I
ui + li
D i = {x ∈ Rn : li ≤ x ≤ ui }, xi = ,
2
e sia
fmin = min f (xi ).
i∈I
Un sottointervallo Dh,
h ∈ I, è detto potenzialmente ottimo se, scelto un parametro
ε > 0, esiste una costante L̄h > 0 tale che:
L̄h h L̄h i
f (xh ) − ku − lh k ≤ f (xi ) − ku − li k, per tutti i ∈ I, (3.55)
2 2
L̄h h
f (xh ) − ku − lh k ≤ fmin − ε|fmin |, (3.56)
2
Introdotta la precedente definizione, è possisibile descrivere formalmente l’Algoritmo
Direct.
116
Algoritmo Direct.
Passo 0: Si pone D 0 = D, l0 = l, u0 = u, x0 = (l0 + u0 )/2, I0 = {0} e k = 0;
Passo 1: data la partizione {D i : i ∈ Ik } di D

dato l’insieme di punti {xi = (li + ui )/2 : i ∈ Ik }
si identifica il sottoinsieme di indici Ik∗ ⊆ Ik tale che:
Ik∗ = {i ∈ Ik : D i è potenzialmente ottimo},
si pone I¯0 = Ik , Iˆ0 = Ik∗ e p = 0
Passo 2: si sceglie un indice h ∈ Iˆp e si determinano:
δ = max (uh − lh )j ,
1≤j≤n
J = {j = 1, . . . , n : (uh − lh )j = δ}
m = |J| (dove |J| è la cardinalità dell’insieme J);
Passo 3: si determinano i 2m + 1 punti dati da:

δ δ
xh 0 = xh , xhj = xh + ej , xhj+m = xh − ej , per ogni j ∈ J;
3 3
Passo 4: attraverso la Procedura di Partizione si partiziona l’insieme D h attraverso i

2m + 1 sottointervalli D h0 D hj , D hj+m , con j ∈ J, che hanno come punti centrali
i vettori xh0 , xhj , xhj+m , con j ∈ J;
Passo 5: si pone:
I¯p+1 = I¯p
[ [
{h0 } {hj , hj+m } \ {h},
j∈J
Iˆp+1 = Iˆp \ {h},
Ik+1 = I¯p+1 ,
Al Passo 1 l’algoritmo seleziona, tra tutti gli intervalli generati, quelli che sono poten-
zialmente ottimi. Per ognuno di questi, al Passo 2 determina l’insieme degli indici J
che corrispondono ai spigoli più lunghi dell’intervallo scelto. Al Passo 3, a partire dal
centro dell’intervallo, vengono generati dei nuovi punti lungo gli assi coordinati (i ver-
117
sori ej ) i cui indici appartengono a J e lungo i loro opposti. Questi nuovi punti vengono
generati a distanza dal centro pari ad un terzo dell’ampiezza massima dell’intervallo.
Al Passo 4, l’intervallo scelto viene diviso in sottointervalli che hanno come centri i
punti generati al Passo 3 ed il punto xh , centro dell’intervallo di partenza.
Per quanto riguarda la generazione dei sottointervalli che partizionano un intervallo
potenzialmente ottimo, si ha la seguente procedura.
Procedura di Partizione.
Passo 0: Dati l’intervallo D h , lo scalare δ, l’insieme J, i punti xh0 , xhj , xhj+m , con
j ∈ J, si pone D̃ 0 = D h , J˜0 = J e p = 0;
Passo 1: si determina l’indice ℓ ∈ J˜p tale che:
wℓ = min wj ,
j∈J˜p
con wj = min{f (xhj ), f (xhj+m )}.
Passo 2: si determinano gli insiemi:

δ
D hℓ = D̃ p {x ∈ Rn : (uh )ℓ −≤ (x)ℓ ≤ (uh )ℓ },
\
3
δ
D hℓ +m = D̃ p {x ∈ Rn : (lh )ℓ ≤ (x)ℓ ≤ (lh )ℓ + },
\
3
e si pone:
δ δ
D̃ p+1 = D̃ p {x ∈ Rn : (lh )ℓ + ≤ (x)ℓ ≤ (uh )ℓ − },
\
3 3
J˜p+1 = J˜p \ {ℓ};
Passo 3: se J˜p+1 6= ∅, si pone p = p + 1 e si torna al Passo 1;
Passo 4: si pone:
D h0 = D̃ p+1
e la procedura termina.
Nella precente procedura si determina la forma dei nuovi intervalli cercando di sfruttare
i valori della funzione obiettivo ottenuti nei punti generati al Passo 3 dell’Algoritmo
Direct. L’obiettivo è di associare dimensioni più grandi agli intervalli in cui al centro la
funzione obiettivo assume valori più piccoli. In questo modo si aumenta la possibilità
che, all’iterazione successiva dell’Algoritmo Direct, questi intervalli siano giudicati po-
tenzialmente ottimi. Per ottenere questo obiettivo la precedente procedura determina,
ad ogni passo, il versore ej lungo il quale si ha il valore più basso della funzione obiet-
118
tivo. Poi il sottointervallo in cui c’è il centro xh dell’intervallo di partenza viene diviso
in tre parti uguali lungo la direzione indentificata da ej .
In figura 3.8 è riportato un esempio di partizione dell’intervallo Dh , nell caso in cui il
valore più piccolo della funzione obiettivo è nel punto xh4 .

D
x = x
D D
x
x x x D D D

x x x
x D D
Figura 3.8: Suddivisione dell’intervallo Dh .
La figura 3.9 descrive il comportamento della Procedura di Partizione nel caso in cui
l’intervallo Dh4 diventa potenzialmente ottimo.

D?@ = D? = x = x
>
D D D0 /
D D
D"! D D
D"! D0 1 D3 2 D54
D$% + . ( D78 D78 D:;

# x*) x -, x '& < 6 9
Figura 3.9: Suddivisione dell’intervallo Dh4 .
L’analisi delle proprietà dell’Algoritmo Direct segue facilmente dalle seguenti due propo-
sizioni. La prima evidenzia che l’Algoritmo Direct partiziona i sottoinsiemi identificati
in maniera da soddisfare l’Assunzione 3.2.2.
Proposizione 3.2.21 Siano D h0 , D hj , D hj+m , j ∈ J, i sottointervalli generati dalla

partizione dell’intervallo D h al Passo 4 dell’Algoritmo Direct, allora l’Assunzione 3.2.2
è sodisfatta.
119
Prova. Le istruzioni della Procedura di Partizione implicano che la norma delle
diagonali dei sottoinsiemi generati D h̃ , h̃ ∈ ∪j∈J {hj , hj+m } ∪ {h0 }, soddisfano
n n
1X
kuh̃ − lh̃ k2 = (uh̃ − lh̃ )2i ≥ (uh − lh )2i
X
i=1
9 i=1
1 h
= ku − lh k2 (3.57)
9
(uh − lh )2j
kuh̃ − lh̃ k2 ≤ (uh − lh )2i +
X
i6=j
9
n
8
(uh − lh )2i − (uh − lh )2j
X
= (3.58)
i=1
9
dove j ∈ J (l’insieme J è definito al Passo 3 dell’Algoritmo Direct). Inoltre si ha che

la norma della diagonale di D h soddisfa la seguente relazione
n
h h 2
(uh − lh )2i ≤ n(uh − lh )2j ,
X
ku − l k =
i=1
da cui segue
8
)kuh − lh k2 .
kuh̃ − lh̃ k2 ≤ (1 − (3.59)
9n
Dalla (3.57), dalla (3.59) e dalle istruzioni della procedura
p di partizione segue che
l’Assunzione 3.2.2 è soddisfatta con ε1 = 1/3, ε2 = 1 − 8/(9n) e ε3 = 1/3.
La seconda proposizione mette in evidenza è il fatto che, in ogni iterazione, un parti-

colare sottoinsieme con ampiezza massima risulta sempre potenzialmente ottimo e che
quindi l’Assunzione 3.2.3 è soddisfatta.
Proposizione 3.2.22 Se {Ik∗ } è la sequenze degli insiemi di indici identificati dall’Al-

gorithmo Direct allora l’Assunzione 3.2.3 è sodisfatta.
Prova. Sia D ℓ , ℓ ∈ Ik , un sottoinsieme tale che ℓ ∈ Ikmax (con Ikmax dato dalla (3.38 ))
e f (xℓ ) ≤ f (xi ), per ogni i ∈ Ikmax , allora il sottoinsieme D ℓ è potenzialmente ottimo.
La dimostrazione segue facilmente notando che ogni costante L̄ℓ > 0 tale che:
( )
f (xℓ ) − fmin + ε|fmin | f (xℓ ) − f (xj )
L̄ℓ > 2 max , max ,
dℓ j∈Ik \Ikmax dℓ − dj
soddisfa alle richieste (3.55) e (3.56).
Utilizzando la Proposizione 3.2.21, e la Proposizione 3.2.8 si può concludere con la

seguente proposizione.
120
Proposizione 3.2.23 Tutte le sequenze di insiemi {D ik } generate dall’Algoritmo Di-
rerct sono strettamente annidate. Inoltre, per ogni x̃ ∈ D, l’algoritmo genera una
sequenza di insiemi {D ik } strettamente annidata tale che
∞
D ik = {x̃}.
\
k=0
Dalla precedente proposizione segue che l’Algoritmo Direct genera un insieme di punti
che, al crescere delle iterazioni, tende a diventare un insieme denso su D. Tuttavia, com-
putazionalmente, l’Algoritmo Direct sembra mostrare una buona capacità di visitare
prima le regioni più interessanti dal punto della localizzazione dei minimi globali.
3.3 Funzioni di tipo “Filled”

Le funzioni filled sono state introdotte allo scopo di cercare di uscire dalle zone di at-
trazione dei minimi locali e di riuscire, attraverso minimizzzazioni locali, a determinare
dei nuovi punti stazionari a cui corrispondono valori della funzione obiettivo più bassi.
Un algoritmo che utilizza le funzioni filled può essere rappresentato dal seguente schema.
Algoritmo che usa una funzione filled.
Passo 0: sia dato un punto x0 ∈ Rn ; si pone k = 0;
Passo 1: partendo da xk si applica un algoritmo di ottimizzazione locale ottenendo un

punto x∗k ∈ Rn ;
Passo 2: utilizzando x∗k si definisce una funzione filled e si applica un algoritmo di

ottimizzazione locale a questa nuova funzione Uk (x) arrestandolo appena si ottiene
un punto xk+1 6= x∗k tale che
f (xk+1 ) ≤ f (x∗k );
Determinato, ad una certa iterazione k, un minimo locale o, più in generale, un punto

stazionario x∗k , la Proposizione 1.6.2 indica la possibilità teorica di perturbare local-
mente la funzione obiettivo in maniera da ottenere una nuova funzione in cui x∗k sia un
massimo locale stretto ed in cui, invece, gli altri punti stazionari rimangano inaltera-
ti. Purtroppo l’applicazione diretta della Proposizione 1.6.2 è particolarmante difficile
per la necessità di evitare che i termini di perturbazione introducano dei nuovi punti
stazionari o nascondano i minimi globali della funzione obiettivo di partenza.
Le funzioni filled, pur traendo ispirazione dalla Proposizione 1.6.2, rinunciano ad intro-
durre dei termini di perturbazione locale che lasciano invariata la funzione obiettivo al
121
di fuori di un fissato intorno. Infatti esse modificano la funzione obiettivo in maniera
più complessa ed accettano il fatto che la funzione obiettivo sia perturbata su tutto
l’insieme di definizione.
Le prime funzioni filled risalgono alle fine degli anni ottanta. Recentemente si è avuto
un crescente interesse verso queste funzioni che ha portato alla definizione di molte
nuove funzioni filled. La caratteristica comune di tutte la funzioni filled proposte è
il fatto di essere composte da due termini ηk (x) ed φk (x). A seconda di come sono
combinati questi termini si hanno le seguenti due classi di funzioni filled:
- funzioni filled moltiplicative

Uk (x) = φk (x)ηk (x),
- funzioni filled additive

Uk (x) = φk (x) + ηk (x),
Nel seguito ci si limiterà a considerare solamente le funzioni filled additive che sono
state introdotte recentemente e che hanno mostrato di essere più efficienti dal punto di
vista computazionale.
I due termini ηk (x) ed φk (x), al di là delle particolari espressioni, giocano sempre ruoli
simili:
- la funzione del termine φk (x) è quello di eliminare i punti stazionari della funzione
obiettivo che corrispondono a valori della funzione più grandi di f (x∗k );
- la funzione del termine ηk (x) è quello di permettre che il punto x∗k possa essere
utilizzato come punto di partenza di una minimizzazione locale della funzione
filled.
Il termine φk (x) può dipendere da uno o più parametri e, come detto, cerca di eliminare
i punti stazionari della funzione f (x) che hanno valore della funzione obiettivo più alto o
uguale di f (x∗k ). Questo fatto, se unito alla garanzia che la funzione filled ha un minimo
globale, assicura che un algoritmo di minimizzazione locale è in grado di determinare
un punto stazionario della funzione filled in cui il valore della funzione obiettivo è più
basso di f (x∗k ).
Una scelta molto semplice e, relativamente intuitiva, è la seguente:
φk (x) = τ min{0, f (x) − f (x∗k ) + ̺}3 , (3.60)
dove ̺ > 0 e τ > 0 sono parametri da scegliere. Tale termine è nullo in tutti i punti x in
cui f (x) ≥ f (x∗k ) − ̺, mentre negli altri punti assume valori decrescenti all’aumentare
del valore del parametro τ ,. Nella figura (3.10) è riportato un esempio di una funzione
obiettivo e della corrispondente funzione φk (x).
Un’altra scelta proposta per il termine φk (x) è la seguente:
φk (x) = 1 − exp (−τ (f (x) − f (x∗k ) + ̺)), (3.61)
122
f ( x)
f ( x k* )
x k* x*
ϕ k ( x ) = min { 0 , f ( x ) − f ( x k* ) + ρ }
3
ϕ k (x ) = 0
x k* x*
Figura 3.10: Esempio di una funzione obiettivo e della corrispondente funzione φk (x) =
min{0, τ (f (x) − f (x∗k ) + ̺)}3 .
123
dove, di nuovo, ̺ > 0 e τ > 0 sono parametri da scegliere. Al crescere del valore
del parametro τ questo termine tende ad assumere valori pari ad uno in punti in cui
f (x) ≥ f (x∗k ) − ̺ mentre tende ad assumere valori sempre più decrescenti in punti in
cui f (x) < f (x∗k ) − ̺.
L’altro termine ηk (x), che compare nella struttura di una funzione filled, ha il ruolo di
assicurare che il vettore x∗k non sia un punto stazionario della funzione filled oppure sia
un massimo locale stretto in modo da poter utilizzare un algoritmo di minimizzazione
locale per ottenere un punto stazionario in cui la funzione filled assume un valore più
basso rispetto a quello che aveva in x∗k .
Questa proprietà può essere garantita adottando due differenti stategie per scegliere la
struttura della funzione ηk (x). Queste due startegie danno luogo a due differenti classi
di funzioni filled:
- le funzioni filled di tipo 1, in cui il termine ηk (x) cerca di garantire che, attraverso una
minimizzazione locale, si posso ottenere un significativo spostamento dal punto
x∗k ;
- le funzioni filled di tipo 2, in cui il termine ηk (x) cerca di assicurare una “buona
struttura” alla funzione filled.
3.3.1 Funzioni filled di tipo 1

La maggior parte delle funzioni filled che appartengono a questa classe utilizzano un
termine ηk (x) che trasforma il punto stazionario x∗k in un massimo locale della funzione
filled stessa. Una scelta molto utilizzata per la funzione ηk (x) è la seguente:
kx − x∗k k2
ηk (x) = exp (− ), (3.62)
γ2
dove γ > 0 è una fissata costante.
Utilizzando come φk (x) e ηk (x) le espressioni date da (3.60) e (da 3.62) si ottiene la
seguente funzione filled additiva:
kx − xk k2
Q(x; τ, ̺) = exp (− ) + min{0, τ (f (x) − f (x∗k ) + ̺)}3 . (3.63)
γ2
In figura (3.11) è descritto un esempio di una funzione obiettivo e della corrispodente

funzione Qk (x).
La prossima proposizione descrive le proprietà teoriche di una classe di funzioni filled di
tipo 1 che hanno in comune il fatto di utilizzare come termine η(x) la funzione (3.62).
Le particolari funzioni filled di questa classe si differenziano nella scelta del termine
φk (x) ed la proposizione seguente identifica le proprietà generali che questo termine
deve soddisfare per garantire interessanti proprietà teoriche alla risultante funzione
filled (nella proposizione si usa la seguente notazione φ̇(t) = dφ(t)/dt).
124
f ( x)
x k* x*
2
x − xk*
−
Qk ( x ) = e γ2
{
+ τ min 0 , f ( x ) − f ( x k* ) + ρ }
3
x k* x*
Figura 3.11: Esempio di una funzione obiettivo e della corrispondente funzione Qk (x).
125
Proposizione 3.3.1 Sia la funzione f due volte continuamente differenziabile su Rn
e sia dato un punto x0 ∈ Rn tale che l’insieme
Lf (x0 ) = {x ∈ Rn : f (x) ≤ f (x0 )}
sia compatto. Sia φ : R → R una funzione due volte continuamente diffenziabile e tale
che:
(a) φ(t) ≥ 0, per ogni t > 0;
(b) |φ̇(t)| è monotonicamente decrescente per valori positivi di t e limt→∞ t|φ̇(t)| = 0;
(c) limt→−∞ φ(t) = −∞.
Allora, per ogni punto stazionario x∗k di f (x) in Lf (x0 ) e per ogni ̺ > 0, esiste un
valore τ̄ > 0 tale che, per ogni τ ≥ τ̄ , la funzione filled definita da
kx − x∗k k2
Qk (x; τ, ̺) = exp (− ) + φ(τ (f (x) − f (x∗k ) + ̺)), (3.64)
γ2
dove γ > 0 è una costante, ha le seguenti proprietà:
(i) il punto x∗k è un massimo locale isolato della funzione filled Qk (x; τ, ̺);
(ii) Qk (x; τ, ̺) non ha punti stazionari non vincolati in {x ∈ Lf (x0 ) : f (x) ≥ f (x∗k )}
eccetto x∗k ;
(iii) se x∗k non è un minimo globale di f (x) e ̺ soddisfa la condizione
0 < ̺ < f (x∗k ) − f ∗ , (3.65)
dove f ∗ è il valore ottimo di f (x), allora tutti i minimi globali x̌ della funzione
filled Qk (x; τ, ̺) su Lf (x0 ) sono punti stazionari non vincolati ed appartengono
alla regione {x ∈ Lf (x0 ) : f (x) < f (x∗k )}.
Come detto, nella precedente proposizione non viene specificata una struttura partico-
lare per la funzione φ(t), invece si caratterizzano delle proprietà generali che una tale
funzione deve soddisfare per garantire la tesi della proposizione. Si può notare che le
scelte (3.60) e (3.61) (cioè φ(t) = min{0, t}3 e φ(t) = 1 − e−t ) soddisfano le proprietà
(a)-(c).
Il precedente risultato mostra che, per valori opportuni dei parametri τ e ̺, le funzioni
filled (3.64) presentano l’interessante caratteristica di avere come unico punto stazio-
nario nell’insieme {x ∈ Lf (x0 ) : f (x) ≥ f (x∗k )} il punto x∗k che è un massimo locale
isolato e che, quindi, non è un “punto di attrazione” di un algoritmo di minimizzazione
locale. Mentre, se x∗k non è un minimo globale di f (x), gli altri punti stazionari della
funzione filled appartenenti a Lf (x0 ) hanno valore della funzione minore di f (x∗k ).
Dal punto di vista applicativo le funzioni filled appartenenti a questa classe presentano
alcuni difetti. Il primo è costituito dall’impossibità di dimostrare che non abbiano punti
126
stazionari al di fuori dell’insieme Lf (x0 ) e che, quindi, un algoritmo di minimizzazione
locale applicato a queste funzioni filled non possa essere attratto da questi punti sta-
zionari che possono avere valori della funzione obiettivo più alti di f (x∗k ) (per esempio,
nella figura (3.12) si indentifica l’insieme Lf (x0 ) e nella figura (3.13) si indica, con le
frecce, le zone in cui una minimizzazione locale potrebbe essere attratta). L’altro pe-
sante difetto è costituito dal fatto che hanno insiemi di livello che non sono compatti
(si può osservare il comportamento della funzione filled (3.63)) e questo inficia le pro-
prietà teoriche e computazionali degli algoritmi di minimizzazione locale da utilizzare
per minimizzarle.
3.3.2 Funzioni filled di tipo 2.

Le funzioni filled appartenenti a questa classe si differenziano dalle precedenti nella
scelta della funzione ηk (x). Infatti, come già accennato, le funzioni ηk (x) utilizzate
in queste funzioni filled hanno anche il ruolo di garantire che le funzioni filled abbiano
delle strutture che possono essere facilmente minimizzate attraverso algoritmi locali. La
proprietà più importante da garantire è il fatto che le funzioni filled abbiano insiemi di
livello compatti. Per riuscire ad ottenere questa proprietà si deve rinunciare al fatto che
il punto x∗k sia trasformato in un massimo, ma ci si deve accontentare di trasformarlo
in un punto non stazionario della funzione filled.
Una scelta molto semplice utilizzata in questa classe di funzioni filled è la seguente:
ηk (x) = kx − x̃k2 , (3.66)
dove x̃ è un qualsiasi punto su Rn .

Il ruolo del termine φk (x) per queste funzioni filled è lo stesso delle funzioni filled
considerate precedentemente. In particolare una funzione filled additiva appartenente
a questa classe è la seguente
Vk (x; τ, ̺) = kx − x̃k2 + min{0, τ (f (x) − f (x∗k ) + ̺)}3 . (3.67)
Nella figura (3.14) è descritto un esempio di costruzione della precedente funzione filled
a partire da una data funzione obiettivo.
La prossima proposizione descrive le proprietà teoriche di una funzioni filled di tipo
2 che utilizzano come termine ηk (x) la (3.66) (nuovamente si usa la notazione φ̇(t) =
dφ(t)/dt).
Proposizione 3.3.2 Sia la funzione obiettivo due volte continuamente differenziabile

su Rn e sia tale che
lim f (x) = ∞. (3.68)

kxk→∞
Sia φ : R → R una funzione una volta continuamente diffenziabile e tale che:
127
f ( x)
f ( x0 )
L0 = {x ∈ R n
: f ( x ) ≤ f ( x0 ) }
x0
Figura 3.12: Esempio di un insieme Lf (x0 ) = {x ∈ Rn : f (x) ≤ f (x0 )}.
2
x − x k*
−
Qk ( x ) = e γ2
{
+ τ min 0 , f ( x ) − f ( x k* ) + ρ }
3
L0 = {x ∈ R n
: f ( x ) ≤ f ( x0 ) }
x0
Figura 3.13: l’insieme Lf (x0 ) = {x ∈ Rn : f (x) ≤ f (x0 )} riferito alla funzione filled Qk .
128
f ( x)
x k* x*
Vk ( x ) = x − ~
x
2
{
+ τ min 0 , f ( x ) − f ( x k* ) + ρ }
3
x k* x* ~
x
Figura 3.14: Esempio di una funzione obiettivo e della corrispondente funzione Vk (x).
129
(a) φ(t) < 0 per ogni t < 0, φ(0) = 0, φ(t) ≥ 0 per ogni t ≥ 0;
(b) |φ̇(t)| è monotonicamente decrescente per valori positivi di t e limt→∞ t|φ̇(t)| = 0;
(c) limt→∞ φ(t) = B ≥ 0;
(d) limt→−∞ φ(t) = −∞.
Allora la seguente la funzione filled:
Vk (x; τ, ̺) = kx − x̃k2 + φ(τ (f (x) − f (x∗k ) + ̺)) (3.69)
ha le seguenti proprietà:
(i) per ogni punto stazionario x∗k , per ogni ̺ > 0 e per ogni τ > 0 esiste un insieme
compatto ∆ tale che:
LVk (x0 , τ, ̺) = {x ∈ Rn : Vk (x, τ, ̺) ≤ Vk (x0 , τ, ̺)} ⊆ ∆. (3.70)
Per ogni punto stazionario x∗k di f (x), per ogni ̺ > 0 ed ogni ε > 0, esiste un valore
τ̄ > 0 tale che, per ogni τ ≥ τ̄ , si ha:
(ii) la funzione Vk (x; τ, ̺) non ha punti stazionari in {x ∈ LVk (x0 , τ, ̺) : f (x) ≥
f (x∗k )} eccetto in un intorno B(x̃; ε) di x̃, dove può esserci un minimo locale
isolato.
(iii) se x∗k non è un minimo globale di f (x) e ̺ soddisfa la condizione
0 < ̺ < f (x∗k ) − f ∗ , (3.71)
dove f ∗ è il valore ottimo di f (x), allora tutti i minimi globali x̌ della funzione
filled Vk (x; τ, ̺) appartengono alla regione {x ∈ LVk (x0 , τ, ̺) : f (x) < f (x∗k )}.
Anche in questa proposizione non è specificata l’espressionie della funzione φ(t), in

modo da caratterizzare scelte diverse per la funzione φk (tra quelle che sono accettabili
ci sono, di nuovo, sia φ(t) = min{0, t}3 e φ(t) = 1 − e−t ).
Si noti che il precedente risultato mostra che queste funzioni filled hanno insiemi di
livello compatti. Inoltre i punti stazionari di interesse di Vk (x; τ, ̺) appartengono al-
l’insieme LVk (x0 , τ, ̺). Perciò, ogni algoritmo che minimizza localmente la Vk (x; τ, ̺)
e che usa come punto di partenza un punto appartenente all’insieme LVk (x0 , τ, ̺), non
può essere attratto da punti stazionari che sono al di fuori di LVk (x0 , τ, ̺). Quindi
queste nuove funzioni filled superano molti dei problemi delle precedenti funzioni filled.
Tuttavia, come mostra il punto (ii) della precedente proposizione, queste funzioni filled
presentano il difetto di avere un punto di minimo locale in cui il valore della funzione
obiettivo può essere più grande o uguale al valore f (x∗k ). Sebbene si sappia dove sia que-
sto punto stazionario ”spurio” (“arbitrariamente” vicino al punto x̃) non si può evitare
che “attragga” un algoritmo di minimizzazione locale. Nella figura (3.15) è descritto un
esempio in cui una minimizzazione locale di Vk produce un punto stazionario in cui si
ha un miglioramento della funzione obiettivo. Nella figura (3.16) è invece riportato un
esempio in cui una minimizzazione locale di Vk produce un punto stazionario spurio.
130
Vk ( x ) = x − ~
x
2
{
+ τ min 0 , f ( x ) − f ( x k* ) + ρ }
3
x k* x* ~
x
Figura 3.15: Esempio in cui una minimizzazione locale di Vk produce un punto stazionario in
cui si ha un miglioramento della funzione obiettivo.
Vk ( x ) = x − ~
x
2
{
+ τ min 0 , f ( x ) − f ( x k* ) + ρ }
3
x k* ~
x x*
Figura 3.16: Esempio in cui una minimizzazione locale di Vk produce un punto stazionario
spurio.
131

Ottimizzazione Continua

Caricato da

Copyright:

Formati disponibili

Ottimizzazione Continua

Caricato da

Informazioni sul documento

Descrizione originale:

Copyright

Formati disponibili

Condividi questo documento

Condividi o incorpora il documento

Opzioni di condivisione

Hai trovato utile questo documento?

Questo contenuto è inappropriato?

Copyright:

Formati disponibili

Ottimizzazione Continua

Caricato da

Copyright:

Formati disponibili

UNIVERSITÀ di ROMA “LA SAPIENZA”

Corso di Laurea Magistrale in Ingegneria

Anno Accademico 2017 –2018

Appunti dalle lezioni di

Dipartimento di Ingegneria Informatica Automatica e Gestionale “Antonio

1 Problemi di Ottimizzazione Nonlineare 4

2 Metodi di ottimizzazione locale 29

3 Metodi di ottimizzazione globale 83

x ∈ Rn è inteso come vettore colonna;

ei ∈ Rn è il versore unitario i-esimo,

R+ insieme dei reali non negativi;

xT vettore riga ottenuto come trasposto di x;

(x)i oppure xi indicano la i-ma componente di x (quindi xi ∈ R);

xk indica il k-mo vettore di una successione (quindi xk ∈ Rn );

{xk } successione formata dai vettori xk ;

{xk }K sottosuccessione deﬁnita dall’ insieme (inﬁnito) di indici K;

kxk norma di x; in assenza di altre indicazioni, kxk è la norma euclidea,

∇f (x) gradiente di una funzione f : Rn → R calcolato in x; ∇f (x) è inteso

∂(A) frontiera dell’insieme A ⊆ Rn .

A\B l’insieme deﬁnito da {x ∈ A : x ∈

Molti problemi che nascono nell’ambito dell’Ingegneria, dell’Economia e delle Scienze

min f (x) (1.1)

Per caratterizzare i possibili punti di soluzione del precedente problema di minimizza-

Definizione 1.1.1 Un punto x⋆ ∈ F si dice punto di minimo globale di f su F se

f (x⋆ ) ≤ f (x), per ogni x ∈ F.

Definizione 1.1.2 Un punto x⋆ ∈ F si dice punto di minimo globale stretto di f su

f (x⋆ ) ≤ f (x), per ogni x ∈ F ∩ B(x⋆ ; ρ).

Definizione 1.1.4 Un punto x⋆ ∈ F si dice punto di minimo locale stretto di f su F

f (x⋆ ) < f (x), per ogni x ∈ F ∩ B(x⋆ ; ρ), x 6= x⋆ .

Si può notare che, se si ha un problema di massimizzazione cioè se si deve trovare un

f (x⋆ ) ≥ f (x), per ogni x ∈ F,

Perciò non si ha nessuna perdita di generalità a studiare ed aﬀrontare solamente

- è detto problema di minimizzazione non vincolata se F = Rn , cioè sel’insieme

min f (x) (1.2)

- viene detto, invece, problema di minimizzazione vincolata un problema in cui

F = {x ∈ Rn : g(x) ≤ 0, h(x) = 0},

in cui g : Rn → Rm e h : Rn → Rp sono vettori di funzioni assegnate. Il problema di

min f (x) (1.3)

1.2 Condizioni di esistenza

- l’insieme ammissibile F potrebbe essere vuoto;

- l’insieme ammissibile F potrebbe essere non vuoto ma la funzione obiettivo

- l’insieme ammissibile F potrebbe essere non vuoto e la funzione obiettivo potreb-

Proposizione 1.2.1 Sia F ⊂ Rn un insieme non vuoto e compatto. Sia f una

Definizione 1.2.2 Sia F ⊆ Rn e sia f : F → R; si definisce insieme di livello di f su

In particolare, se x0 ∈ F, indichiamo con L0 l’insieme di livello L (f (x0 )), ossia:

L0 := {x ∈ F : f (x) ≤ f (x0 )} . (1.4)

Proposizione 1.2.3 Sia F ⊆ Rn e sia f una funzione continua su F. Supponiamo

Proposizione 1.2.4 . Sia F ⊆ Rn e sia f una funzione continua definita su F. Allora

(ii) se {xk } è una sequenza di punti xk ∈ F tale che limk→∞ xk = x̂ ∈

(i) tutti gli insiemi di livello L(α) = {x ∈ Rn : f (x) ≤ α} sono compatti;

(ii) esiste un minimo globale di f su Rn .

Proposizione 1.2.6 Sia F un sottoinsieme limitato e aperto di Rn e sia f : F → R

(i) tutti gli insiemi di livello L(α) = {x ∈ F : f (x) ≤ α} sono compatti;

(ii) esiste un minimo globale x∗ ∈ F di f su F.

1.3 Condizioni di ottimalità locale

Si consideri per primo il caso di un problema di ottimizzazione non vicolata. Le due

Proposizione 1.3.1 (Condizione necessaria del primo ordine) Sia f continua-

In modo da caratterizzare i punti che soddisfano le precedenti condizioni necessarie del

1.3.2 Condizioni di ottimalità per problemi vincolati