ALGORITMI DI
OTTIMIZZAZIONE MONO E MULTI
OBIETTIVO
In questi ultimi anni si è avuto un crescendo nell’utilizzo di algoritmi di ottimizzazione, in quanto durante il processo di progettazione, sta avendo sempre più importanza la fase di ottimizzazione.
Per questo motivo è stata creata una grande varietà di algoritmi, ognuno con le proprie caratteristiche, e quindi adatti a tipologie di ottimizzazione diverse tra loro.
In questa sezione verranno mostrati alcuni
algoritmi, facendo riferimento soprattutto
alle differenze tra loro e tra i loro campi di
applicazione più caratteristici.
Per riuscire a comprende meglio le differenze tra i vari algoritmi è utile dare due definizione che vengono usualmente usate per classificare gli algoritmi:
• robustezza;
• accuratezza.
Per robustezza di un algoritmo di ottimizzazione si intende la capacità di trovare il massimo assoluto della funzione obiettivo.
Per accuratezza di un algoritmo di ottimizzazione si intende la capacità di avvicinarsi al vero valore del massimo assoluto della funzione obiettivo
In base alle definizioni date precedentemente (robustezza, accuratezza, velocità di convergenza) e all’utilizzo o meno del gradiente della funzione obiettivo è possibile definire la seguente tabella:
r
∇f x = f K x
f xn ( 0) ( , , )
1
∂
∂
∂
∂
Algoritmi che usano il gradiente
Algoritmi che NON usano il gradiente
Robustezza Bassa Alta
Accuratezza Alta Bassa
Velocità di convergenza
Alta Bassa
r
∇ = M
f x
f x f xn ( 0)
1
∂
∂
∂
∂
Valore locale (accuratezza ⇑, robustezza ⇓)
Dà la direzione di massimo incremento della funzione ⇒ velocità in convergenza
Necessita una notevole quantità di calcoli aggiuntivi (derivate parziali)
i
i i m
i i m
i X
i
m i
i m
i X
x
u x X
f u
x X
f x
f
x
X f u
x X
f x
f
m m
∆
∆
−
−
∆
≅ +
∆
−
∆
≅ +
2
) (
) (
: centrate finite
Differenze
) (
) (
: avanti in
finite Differenze
∂
∂
∂
∂
Attenzione: non sempre è possibile definire il gradiente Variabili discrete o di categoria (parametrizzazione)
x F(x)
x* F(x*)
F’- F’+
Derivata sinistra diversa da derivata destra
• Esiste una grande varietà di algoritmi di ottimizzazione che sfruttano il gradiente della funzione obiettivo (Cauchy, Powell, Newton, Quasi-Newton, BFGS, SQP, ecc.).
• Le caratteristiche più interessante che accomuna questi metodi è l’accuratezza della soluzione trovata.
• Noi studieremo:
– Cauchy – Newton
– Quasi-Newton (Broyden-Fletcher-Goldfarb-Shanno) – Sequential Quadratic Programming
[ ]
i j j
i
n n n
n n
n
x x
f x
x f
x x
f x
x f
x x
f x
x f x x x f
x x f
x f
x f
f
∂
∂
= ∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
∂ =
= ∂
∂ =
= ∂
∂
∂
=
∇
⇒ ℜ ℜ
2 2
2
1 2
1 2
1 1
2
*
* 2
* 1
*
Simmetrica
hessiana Matrice
: e sufficient Condizione
0 ) ( )
( )
(
0 ) (
: : necessaria Condizione
K
M O
M
K K
H
[ ]
⇒
⇒
⇒
=
sella indefinita
relativo Massimo
negativa definita
relativo Minimo
positiva definita
) (x* H
positivi sono
autovalori gli
tutti
0
se positiva definita
è matrice Una
=
− I A
A λ
LAGRANGE DI
TORI MOLTIPLICA
dei utilizzo
, ,
1 0
) (
: Min
a uguaglianz di
Vincoli
m j
x g
f
j
n
= K
=
⇒ ℜ ℜ
Esempio n=2 m=1 MIN f(x1,x2)
g(x1,x2)=0
x1
x2 g=0
Direzioni ammissibili Direzione non
ammissibile
x1* x2*
necessaria condizione
0 / 0
/
univoco è
scelto cioè
) , (
) , (
0 ) , ( se
) , ( in 0
) , ( )
, (
0 )
, ( )
, ( )
, (
0 ) ,
(
: che tale e ammissibil direzione
esiste
0
*
*
1 2 2
1
1 2
2 1 1
2 1 1
* 2
* 1 2
* 2
* 1 1 2
* 2
* 1 2
* 2
* 1 2
* 2
* 1 2 1
* 2
* 1 1
2
* 2
* 1 2 1
* 2
* 1 1
* 2
* 1
2
* 2 1
* 1
2 2 1
1
=
∂
∂
∂
− ∂
∂
∂
∂
∂
=
∂
∂
∂
∂
∂
− ∂
∂
= ∂
∂
∂
∂
∂
−
=
∂ ≠
∂
∂ = + ∂
∂
= ∂
⇒
∂ = + ∂
∂ + ∂
= +
+
∂ = + ∂
∂
= ∂
x
x
x g x
f x
g x
f
x dx f x g
x g x
df f
dx dx dx
x x x
g
x x x
g dx
x x x
g
x x dx
x x x
dx g x
x x dg g
dx x
x x dx g
x x x
x g x g
dx x
dx x
g
x dx dx f
x df f
=
∂ =
∂
∂ = + ∂
∂
= ∂
∂
∂
∂ = + ∂
∂
= ∂
∂
∂
+
=
=
∂ = + ∂
∂
∂
∂ = + ∂
∂
∂
∂
∂
∂
− ∂
=
=
∂
∂
∂
∂
∂
− ∂
∂
∂
=
0
0 0 ) , ( )
, , (
LAGRANGE DI
FUNZIONE 0 ) , (
0 0
Lagrange di
tore moltiplica /
/ / 0 /
0 ) , ( )
, ( MIN
2 2
2
1 1
1
2 1 2
1
2 1
2 2
1 1
2 2
1 2 2 1
2 1 2
1
*
*
L g
x g x
f x
L
x g x
f x
L
x x f x
x L
x x g
x g x
f
x g x
f
x g
x f
x g x
g x f
x f
x x g x
x f
x x
λ
λ λ
λ λ
λ λ λ
∑∑
∑
∑
= =
=
=
⇒
⇒ ⇒
∂
∂
= ∂
=
∂ =
∂
∂ = + ∂
∂
= ∂
∂
∂
+
=
=
=
⇒ ℜ ℜ
n
i
n
j
j i j
i
j m
j
j m
j
j j m
n j
n
dx x dx
x Q L
L g
x g x
f x
L
x g
x f x
x L
m j
x g
f
1 1
2
1 1
1 1 1
1
1 1
1
massimo negativa
definita
minimo positiva
definita e
sufficient condizione
0
0 necessaria
condizione
) ( )
( )
, ,
, , ,
(
, ,
1 0
) (
: MIN
M M K
K
K
λ
λ λ
λ λ
Interpretazione moltiplicatori di Lagrange
db df
dx df x db f
x f
x g
x g x
f x
g x
f
x dx g g
d db
g d db
g
n x i
g x
f
x g b x
g
b x
g x
f
i i n
i
i i
i i
i i
n
i
i i i
i
n
*
*
1
1
ottimo di
punto nel
quindi e
1
~ /
0
~
~ ~
~ 0
, , 1 0
0 )
~( )
(
)
~( :
) ( MIN
λ
λ λ
λ
λ λ
λ
=
∂ =
= ∂
∂
= ∂
∂
∂
∂ =
− ∂
∂
= ∂
∂ + ∂
∂
∂
∂
= ∂
=
=
=
=
∂ = + ∂
∂
∂
=
−
=
=
⇒ ℜ ℜ
∑
∑
=
=
K
Ciò significa che il moltiplicatore di Lagrange è un indicatore della sensibilità del punto di ottimo dei confronti del vincolo di uguaglianza
Vincoli di disuguaglianza
Anch’essi possono essere risolti con l’utilizzo dei moltiplicatori di Lagrange.
=
=
∂ =
∂
=
= +
=
∂ =
∂
∂ = + ∂
∂
= ∂
∂
∂
+
=
= +
=
=
≤
⇒ ℜ ℜ
∑
∑
=
=
m j
y y
y x L
m j
y x
g y
x G y
L x
n i
x x x g
x y f
x x L
y x G x
f y
x L
y x
g y
x G
m j
x g
x f
j j j
j j
j j
i j m
j j i
i
m
j
j j j j
j j
n
, , 1 0
2 ) , , (
, , 1 0
) ( )
, ( )
, , (
, , 1 )
( )
( )
, , (
) , ( )
( )
, , (
0 )
( )
, (
in re trasforma può
si vincolo il
, , 1 0
) (
: ) ( MIN
2 1
1 2
K
K K K
λ λ
λ λ
λ λ
λ λ
Interpretazione dei moltiplicatori di Lagrange (caso vincoli disuguaglianza)
0 0
2 1
<
<
g 0 g
1 =
g g2 = 0
1 > 0
g g2 > 0
g
1∇ ∇ g
2S
vincoli) dei
e diminuzion la
dà (mi
consentita direzione
0 0 vincoli 2
0
2 1
2 2
1 1
2 2
1 1
⇒
<
∇
<
∇
∇ +
∇
=
∇
−
∇ +
∇ +
∇
−
=
∇ +
∇
g S
g S
g S
g S
f S
g g
f
g f
T T
T T
T T
λ λ
λ λ
λ
Ciò significa che se i moltiplicatori sono maggiori di 0 non c’è nessuna direzione consentita per far diminuire la funzione all’interno dei vincoli (minori di zero)
Condizioni di Kuhn-Tucker (condizione necessaria)
≥
=
≤
=
=
∇
−
∇ +
∇
=
=
=
≤
⇒ ℜ ℜ
0 0 0
0
0 ,
, 1 0
) (
, ,
1 0
) (
: ) ( MIN
j k
j j j
T T
k j
n
h g
g
h g
f
p k
x h
m j
x g
x f
λ λ
β λ
K
K
x0
f(xi)
∇
∇∇
∇ f(xi)
Algoritmo (xi+1)
Convergenza?
i=i+1
Si parte sempre da una soluzione conosciuta
4 3 1
2 1
1 1
max )
5 ) 4
) ( )
( )
3
) (
) ( )
) ( 2
) 1
a Convergenz
ε ε
ε ε
∂ ≤
∂
≤
−
≤
−
− ≤
≥
+ +
+
i i i
i i
i
i i
x f x x
x f x
f
x f
x f x
f
ntot i
Step ottimale lungo una direzione
( )
0 0
0 :
*
1
1
=
∇
∂ =
= ∂
∂
∂
=
∂ +
= ∂
∂
∂
∂ =
∂
∂
⇒ ∂
∂ =
∂
+
=
⇒ ℜ ℜ
∑
∑
=
=
i T ij
n
j j
ij ij
ij j
n
j
j j
i n
S f
x s f f
s s
x x
x x
f f
S x
x f
λ
λλ λ λ
λ λ
λ
s
xi
Algoritmo di Cauchy
Il metodo di Cauchy è uno degli algoritmi base che utilizzano il gradiente della funzione obiettivo.
i i
i i i
i
i i
S S
x x
x f S
x
r r r
r
r r
r
direzione la
lungo ottimale
passo
con
: punto nuovo
del calcolo
3) Punto
) ( direzione
della calcolo
2) Punto
partenza di
punto del
scelta
1) Punto
*
* 1
1
λ
λ +
=
∇
=
+
ESEMPIO
0
2 . 1
8 . 0 1
1 5 1 1
1
5 1 1
2 5
) 1 , 1 ( ) (
1 1 2 Iterazione
0
1 1 1
1 1 0 0
1 2
) , ( ) (
1 1 1 ) 1
(
1 Iterazione
2 2
1
2 4
1 /
/
0 punto 0
dal partendo
2 2
) , ( MIN
3
2
* 2 2 3
* 2 2
2 2 2
2 2
2 2
2 2
2
1
* 1 1 2
* 1 1
2 1 1 1 1
1 1
1 1
1
2 1
2 1
2 1
1
2 2 2 1 2
1 2
1 2 1
≠
∇
=−
+
=−
+
=
⇒ =
−
−
= +
+
−
= +
=
−∇
=
≠
∇
=−
+ −
= +
=
⇒ =
−
=
−
= +
=−
−∇
=
= −
∇
+ +
−
+
= +
∂
∂
∂
= ∂
∇
=
+ +
+
−
=
f
S x
x
f S
x f
f S
f
S x
x
f S x
f
f S
x f
x x
x x
x f
x f f
x
x x x x
x x x
x f
λ
λ λ
λ λ
λ λ
λ
λ λ
λ λ λ λ
2 0 . 0
2 . 0
4 . 1
1 2
. 0
2 . 1 0 2 . 1
8 . 0
2 . 1 08 . 0 04 . 0 ) 2 . 0 2 . 1 , 2 . 0 8 . 0 ( ) (
2 . 0
2 . 0 3 Iterazione
4
3
* 3 3 4
* 3 3
2 3 3
3 3
3 3
3 3
≠
−
= −
∇
=−
+ −
=−
+
=
=
− ⇒
−
= +
+
−
= +
=−
−∇
=
f
S x
x
f S x
f
f S
λ
λ λ
λ λ
λ λ
Algoritmo del gradiente coniugato (Fletcher-Reeeves)
Ottimizza una forma quadratiche di ordine n in n steps (meglio che Cauchy)
( )
[ ]
1 1
1 1 1
1 1
* 1 1
* 1 1
* 1 1
1 1
* 1
1 2
1
1
* 1 1
2
1 1
1
) (
do esplicitan
0 quindi
0
: valere deve
ideale step
lo vogliamo quando
2 ) 1 (
2
S S
f S S
S
B x
S
B S
x S
f S
x S x
S x
x
B x
f S
c x B x
x x
f
T T T
T T
x T
n T
T
A A
A A
A A
− ∇ + =
= −
= +
+
=
∇
= −
+
=
−
−
=
−∇
=
⇒ ℜ ℜ
+ +
=
λ
λ λ λ
λ
( )
( ) ( )
( )
1 1
2 2
1 1
2 2
2
2 1
2 1
1 1 2 1
2 2 2
1 2
2
1 2 2
1 2
1 2
1 2
1 2
1 2
* 2 1
1 2
1 2 2
1
2 1
2 1 2
1 2 2
2
0 poichè
0 0
) (
) simmetrica (A
1 Eq.
do consideran
) (
) (
) (
: come calcolata
essere può
gradienti i
tra differenza La
) 1 ( 0
0 0
coniugate siano
, affinchè scelgo
f f
f f
S f
f f
f S
f f
S f S
f f
f f
f
S f
f f
x x
B x
B x
f f
S x f
x
S f
S
S S
S S S
f S
T T T
T T T
T T
T T
T T T
T
∇
∇
∇
= ∇
∇
∇
− ∇
=
=
∇
−
=
∇
∇
=
∇ +
∇
−
∇
∇
−
∇
∇
=
−
∇
∇
−
∇
−
= +
− +
=
∇
−
∇
=
−
∇
−
−
= +
∇
−
= +
−∇
=
β
β β
β λ β
β β
β
A A
A A A
A
1 1
1 2
2
3 3
3 3
3 2
3 1
3 3
1 3 2
3 3
3
ricorsiva formula
la trovare può
si a conseguenz di
0
: come vede
si
0 0
: ) (coniugate imponendo
i determinat vengono
,
−
−
−
∇
∇
∇
= ∇
+
−∇
=
∇
∇
∇
= ∇
=
=
=
+ +
−∇
=
i T
i
i T i i
i i i
i
T T T
T
f f
f f
S f
S
f f
f f
S S
S S
S S
f S
β
β β
σ σ β
σ β
A A
1. Scelta del punto iniziale X
12. Calcolo della prima direzione S
13. Calcolo del punto X
2:
4. Calcolo della direzione S
i5. Calcolo del nuovo punti X
i+16. Convergenza?
1 1
1
f ( x ) f
S = −∇ = −∇
1
* 1 1
2
x S
x = + λ
2 1 1
2
−
∇ −
+ ∇
−∇
= i
i i i
i S
f f f
S
i i i
i
