Process modeling for

chemical engineers
Optimization
 Prologo
È possibile affermare che tutta l’attività professionale dell’ingegnere orbiti intorno
all’ottimizzazione.
Esistono numerosi indirizzi nell’ambito dei quali applicare l’ottimizzazione:
• progettazione delle apparecchiature,
• layout ottimale di un processo,
• individuazione delle condizioni operative nominali ottimali,
• conduzione e controllo in linea di processo,
• supervisione di processo su uno o più siti produttivi,
• ottimizzazione della catena produttiva,
• logistica dell’approvvigionamento e distribuzione,
• allocazione ottimale delle risorse umane nell’ambito dell’attività lavorativa,
• conseguimento di ottimi economici, energetici, riduzione degli inquinanti,
riduzione dell’impatto ambientale, …
• ecc.
2
Slide fornite per cortesia del Prof. D. Manca
 Prologo
Esempio: si desidera determinare lo spessore ottimale s di isolante per un
tubo di grande diametro ed elevato coefficiente di scambio termico interno.
Occorre trovare un compromesso tra risparmio energetico conseguito e costo
di investimento da effettuare per la posa del refrattario.

Svolgimento
• Calore scambiato con l’esterno A∆T
Q = UA∆T =
in presenza di refrattario [kcal/h]: 1 s
+
he k

• Costo di installazione del refrattario [€/m2]: F0 + F1s

• L’isolante ha una vita di 5 anni. Il capitale per l’acquisto e la posa in opera

viene preso in prestito da una banca. Si indica con r la percentuale del
capitale + interessi da restituire ogni anno. Quindi: r > 0.2
• Ht è il costo dell’energia dispersa [€/kcal]
• Y sono le ore di esercizio in un anno [h/y]
• Ogni anno occorre restituire alla banca [€/y]: ( F0 + F1s ) Ar

3
Slide fornite per cortesia del Prof. D. Manca
 Prologo
• Calore scambiato con l’esterno senza refrattario [kcal/h]:
Q = UA∆T = he A∆T
• Risparmio energetico annuo dovuto al refrattario [€/y]:

 he A∆T − A∆T (1 he + s k )  H tY

• Ne consegue che la funzione obiettivo nel gdl s diviene:

f obj=  he A∆T − A∆T (1 he + s k )  H tY − ( F0 + F1s ) Ar

df obj
• In questo caso il problema è risolubile analiticamente ponendo: =0
ds
• Si ottiene:
 ∆TH tY 1 
=sopt k  − 
 kF r he 
 1

• Si noti che sopt non dipende né da A né da F0 viceversa fobj dipende da

tali grandezze.
4
Slide fornite per cortesia del Prof. D. Manca
 Ottimizzazione
Nel campo dell’ottimizzazione è possibile fare distinzione tra problemi
monodimensionali e problemi multidimensionali.

• Nel primo caso si cerca l’ottimo di una funzione obiettivo dipendente da una
sola variabile (un grado di libertà).

• Nel secondo caso si cerca l’ottimo di una funzione obiettivo dipendente da più
variabili (più gradi di libertà).

Nel prosieguo si affronterà la discussione di metodi numerici volti alla risoluzione

di problemi di ottimo monodimensionale.
N.B.: gli algoritmi di ricerca monodimensionale sono utilizzabili per la ricerca
lungo una specifica direzione di miglioramento nell’ottimizzazione
multidimensionale. In realtà gli algoritmi moderni multidimensionali adottano
metodi di ricerca monodimensionale sequenziale specificatamente sviluppati e
volti alla riduzione puntuale del numero di chiamate di funzione (ad esempio
metodi SQP: Successive Quadratic Programming).

5
Slide fornite per cortesia del Prof. D. Manca
 Ottimizzazione monodimensionale
In un problema di ottimizzazione monodimensionale occorre quindi identificare il
valore della variabile x (detta anche grado di libertà) che rende ottima la funzione
obiettivo f(x).

L’ottimo del problema può essere rappresentato dal massimo o dal minimo
della funzione obiettivo.
Max f ( x) Min g ( x)

I due problemi sono assolutamente equivalenti. Infatti è sufficiente cambiare di

segno alla funzione obiettivo per passare da un problema di minimo ad uno di
massimo e viceversa:
Max f ( x) ≡ Min − f ( x)
Min g ( x) ≡ Max − g ( x)

Nel prosieguo si considereranno soltanto problemi di minimo di funzioni.

6
Slide fornite per cortesia del Prof. D. Manca
 Ottimizzazione monodimensionale
Utilizzando in modo non corretto le conoscenze di analisi classica si potrebbe
pensare che per risolvere il problema:

Min f ( x)

sia sufficiente risolvere il problema equivalente: df ( x) =0

dx
Niente di più sbagliato. Si rammenta che la condizione summenzionata è
necessaria per identificare un punto estremante di una funzione continua e
derivabile. Tale condizione però non copre casi specifici quali ad esempio:

f(x) f(x) f(x)

x x x

7
Slide fornite per cortesia del Prof. D. Manca
 Funzione unimodale
Definizione: una funzione viene detta unimodale in un intervallo [xa, xb] se
esiste un solo punto di minimo xM appartenente a tale intervallo.

N.B.: nella definizione di funzione unimodale non vengono fatte ipotesi di

continuità o di derivabilità della funzione.

N.B.: una funzione che presenti più punti di minimo o che sia costante e minima
anche in un sottointervallo non è unimodale.

Esempi di funzioni unimodali:

f(x) f(x) f(x)

x x x
xa xM xb xa xM xb xa xM xb

8
Slide fornite per cortesia del Prof. D. Manca
 Intervallo di incertezza
Definizione: l’intervallo [xa, xb] all’interno del quale la funzione è unimodale è
detto intervallo di incertezza.

Definizione: una funzione è unimodale nell’intervallo di incertezza [xa, xb] se

dati due punti x1 e x2 con xa < x1 < x2 < xb si ha contemporaneamente che:

• ponendo x2 < xM risulta f(x1) > f(x2)

• ponendo x1 > xM risulta f(x1) < f(x2)

f(x) f(x)

x x
xa x1 x2 xM xb xa xM x1 x2 xb

9
Slide fornite per cortesia del Prof. D. Manca
 Riduzione intervallo di incertezza
Corollario: data una funzione unimodale nell’intervallo [xa, xb] e due punti
x1 e x2 con xa < x1 < x2 < xb è possibile ridurre l’intervallo di incertezza [xa, xb] nel
seguente modo:

• se f(x1) < f(x2) l’intervallo di incertezza diventa: [xa, x2]

• se f(x1) > f(x2) l’intervallo di incertezza diventa: [x1, xb]

• se f(x1) = f(x2) l’intervallo di incertezza diventa: [x1, x2]

f(x) f(x)

x x
xa x1 x2 xM xb xa xM x1 x2 xb
N.B.: numericamente può accadere che la funzione non risulti unimodale anche
se lo è teoricamente (a livello di analisi classica) nell’intervallo [xa, xb]. Ciò accade
quando i punti x1, x2 sono troppo vicini e forniscono lo stesso valore della
funzione
10
obiettivo anche se al loro interno non cade il punto di minimo.
Slide fornite per cortesia del Prof. D. Manca
 Intervallo di definizione
Definizione: la distanza δ minima al di sotto della quale la funzione cessa di
essere numericamente unimodale viene detta intervallo di definizione.

Stima dell’ordine di grandezza dell’intervallo di definizione δ

Si supponga che la funzione f(x) approssimi l’andamento di una parabola in un

opportuno intorno del punto di minimo: xM. Allora si ha:
1
f ( x) ≈ f ( xM ) + ( x − xM ) f ′′ ( xM ) Espansione di Taylor: in corrispondenza del
2

2! minimo il termine f’(xM)=0

1
( x − xM ) f ′′ ( xM )
2
La parabola approssima la funzione in xM se il termine
2!
è trascurabile rispetto a f(xM). Indicando con ε il macheps, ciò accade se:

1
( x − xM ) f ′′ ( xM ) < ε f ( xM )
2

2!

2 f ( xM )
ovvero se: x − xM ≈ δ < ε xM
xM2 f ′′( xM )
11
Slide fornite per cortesia del Prof. D. Manca
 Intervallo di definizione
Si noti che l’intervallo di definizione, ovvero l’intervallo all’interno del quale cade il
punto di minimo della funzione obiettivo, può essere determinato con una
precisione proporzionale alla radice quadrata del macheps.

Al contrario nel caso dell’azzeramento di una funzione l’intervallo di definizione

all’interno del quale cade la soluzione del problema è confrontabile con il
macheps.

12
Slide fornite per cortesia del Prof. D. Manca
 Classificazione metodi risolutivi
Nella ottimizzazione monodimensionale di funzioni è possibile individuare due
famiglie di metodi risolutivi:

• Metodi di confronto: si sfruttano soltanto confronti tra valori della funzione

obiettivo.

• Metodi di approssimazione: si approssima la funzione obiettivo con altre

funzioni più semplici e si cerca il punto di ottimo di tali funzioni.

Esiste anche un’altra possibile classificazione:

Metodi sequenziali: la valutazione della funzione obiettivo viene condotta

sequenzialmente. Ogni valutazione permette di decidere quale azione successiva
intraprendere.

Metodi paralleli: è possibile eseguire più valutazioni di funzione prima di

prendere una decisione sulla strategia successiva. In generale questi metodi
richiedono molti più calcoli di funzione. Sono interessanti nel caso di utilizzo su
computer multiprocessore.
13
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
Domanda: sapendo che una funzione è unimodale entro un certo intervallo
quanti punti sono necessari per ridurre l’intervallo di incertezza nel caso di ottimo
monodimensionale?

f(x)
Tre punti non sono sufficienti per
ridurre l’intervallo di incertezza

x
xa x1 xb

14
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza

È necessario aggiungere un quarto punto

interno all’intervallo di incertezza

Ora è possibile affermare che il punto di

ottimo cade comunque nell’intervallo [x1, xb]
f(x)

x
xa x1 x2 xb

15
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
È quindi possibile eliminare xa. Il nuovo intervallo ha già tre punti a disposizione.
Occorre quindi aggiungere un solo nuovo punto all’interno dell’intervallo attuale
di incertezza per procedere con le iterazioni.

f(x)

x
xa x1 x2 xb

16
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
Problema: come conviene posizionare i primi due punti interni e quelli successivi
affinché, dopo un assegnato numero di iterazioni, risulti minimo il massimo
intervallo finale di incertezza?

Se si cerca di risolvere il problema con un approccio diretto la soluzione non è

affatto banale.

Viceversa è relativamente facile risolvere il problema cercando di individuare quali

saranno le condizioni finali della sequenza iterativa.

17
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
Alla fine del processo iterativo, per poter prendere l’ultima decisione, dovremo
basarci comunque su due prove.

Domanda: qual è la scelta ottimale che rende minimo il massimo intervallo

finale di incertezza con due prove?

Risposta: questo problema è facile da risolvere. Le due prove devono essere

simmetriche all’interno dell’intervallo (perché altrimenti non minimizzerebbero il
massimo intervallo di incertezza finale) e il più possibile vicine fra loro.

18
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
Se ad esempio si sceglie un posizionamento dei due punti finali come nel caso (a)
è possibile osservare che l’intervallo finale di incertezza La è maggiore che nel
caso (b) che ha ampiezza Lb.
La

Caso (a)

La

L
b

Caso (b)

L
b

19
Slide fornite per cortesia del Prof. D. Manca
 Riduzione dell’intervallo di incertezza
N.B.: la minima distanza finale tra le due prove deve essere al più pari
all’intervallo di definizione δ.

LN LN

20
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
Se il numero totale di iterazioni richiesto è N le ultime due prove dovranno
trovarsi a distanza δ fra loro ed essere centrate nel penultimo intervallo di
ampiezza LN−1 in modo che l’intervallo finale abbia ampiezza LN.

N.B.: di queste due prove una, x̂ , deve provenire da un’iterazione precedente

(non necessariamente la N−1) e una sarà viceversa l’ultima prova xN.

δ
xN x̂

LN LN

LN-1

 δ 
È possibile osservare che: LN −1= 2 LN − δ= LN  2 − 
 LN 

21
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
A sua volta l’intervallo LN−1 è ricavato dall’intervallo LN−2.

LN−2
xN − 2 xN −1

LN xN −1 xN

δ
LN

LN LN−1

xN δ xN − 2 Nel caso la prova xN−1 sia

migliore della prova xN−2.

LN Nel caso la prova xN−2 sia

LN-1 migliore della prova xN−1.

N.B.: in entrambi i casi si ha LN−2 = LN−1 + LN.

22
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
La combinazione delle due relazioni individuate al passo N – 1 e N – 2
  δ 
L =
 N −1 2 LN − δ= LN  2 − 
  LN 
 L= L + L
 N −2 N −1 N

 
porta a: LN − 2= 3LN − δ= LN  3 − δ 
 LN 

Iterando il procedimento è possibile scrivere:

 δ 
LN −3 = LN − 2 + LN −1 = 2 LN −1 + LN = LN  5 − 2 
 LN 

23
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
È possibile evincere la sequenza:

 δ   δ   δ   δ 
LN −1 LN  2 −
= L
=
 N −2 LN  3 − L
=
 N −3 LN  5 − 2 L
=
 N −4 LN  8 − 3  
 LN   LN   LN   LN 

Astraendo si ottiene la seguente formula generale:

 δ 
LN − j LN  Fj +1 − Fj −1
=  1, , N − 1
j=
 LN 
i Fi
0 1
1 1
Dove i coefficienti Fj sono i numeri di Fibonacci (Leonardo Pisano) 2 2
3 3
caratterizzati dalla relazione: 4 5
5 8
6 13
Fi +1 =
Fi + Fi −1 con F0 = 1, F1 =
1 7 21
8 34
9 55
10 89

24
 Nota storica
Il Liber Abbaci

Leonardo Pisano (Pisa, 1170–1250) detto Fibonacci in quanto figlio di Guglielmo

Bonaccio. Il padre era il rappresentante dei mercanti della Repubblica di Pisa. Fu
educato in nord Africa.

Nel 1202 apparve ad opera di Leonardo Pisano un libro assai importante, dal
titolo Liber Abbaci, cioè il libro dell’abaco, o abbaco, ovvero un “manuale per far
di conto”, un capolavoro nel campo della letteratura matematica che ebbe molta
influenza sullo sviluppo delle scienze matematiche in Europa.

Nell’introduzione all’opera, l’autore raccomanda caldamente l’uso delle cifre arabe

nelle opere scientifiche redatte nei conventi, al di fuori dei quali però erano
sconosciute. In realtà le cifre arabe erano già state introdotte dal monaco
Gerberto, più tardi noto come papa Silvestro II (999-1003).

La particolarità del libro di Leonardo Pisano risiede nel fatto che per risolvere
molti problemi della vita quotidiana si ricorre all’uso dell’algebra, di origine araba.
Tratto da Snijders, 1969
25
Slide fornite per cortesia del Prof. D. Manca
 Nota storica
Tra i problemi posti da Fibonacci nel suo Liber Abbaci c’è quello delle sette
vecchie che si recano a Roma, ognuna con sette muli, ogni mulo carico di sette
sacchi, ogni sacco contenente sette pani, per ogni pane sette coltelli, ogni coltello
in sette foderi. Ci si domanda quanti oggetti sono stati trasportati globalmente e
l’autore fornisce la risposta applicando il concetto di “serie geometrica” con valore
iniziale 7 e ragione 7 i cui 6 termini devono essere sommati ottenendo 137,256
oggetti.

Altro problema è quello dei conigli: se una coppia di conigli mette al mondo ogni
mese una coppia di piccoli, che dopo due mesi producono a loro volta una nuova
coppia di conigli, quante coppie di conigli si avranno dopo un anno supponendo
nulla la mortalità dell’ecosistema?

Gennaio 1 Luglio 13
Febbraio 1 Agosto 21
Marzo 2 Settembre 34
Aprile 3 Ottobre 55
Maggio 5 Novembre 89
Giugno 8 Dicembre 144

26
Slide fornite per cortesia del Prof. D. Manca
 Nota storica
La successione prodotta temporalmente dalla prima coppia di conigli rispetta la
regola: Fi +1 =
Fi + Fi −1 con F0 =1, F1 =
1
Il rapporto tra due numeri adiacenti della successione di Fibonacci converge
rapidamente alla sezione aurea.

È possibile dimostrare che:

Fi −1 5 −1
lim= ≅ 0.6180339887498948482045868343656
i →∞ F
i 2
Fi 5 +1
lim= ≅ 1.6180339887498948482045868343656
i →∞ F
i −1 2
tali rapporti rappresentano la sezione aurea ovvero la porzione di segmento che
è media proporzionale tra l’intero e il resto (o il duale come rappresentato nella
figura a destra)
x 1–x 1 x–1

1 x
27
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
 δ 
Se nella formula generale=
LN − j LN  Fj +1 − Fj −1  si pone j = N – 1 si ottiene:
 LN 

 δ 
=L1 LN  FN − FN − 2 
 LN 

ecco risolto il problema di individuazione dell’intervallo iniziale. Inoltre vale:

L1 + δ FN − 2
LN =
FN
Quindi assegnati: l’intervallo iniziale di incertezza L1, il numero di iterazioni N da
effettuare e l’intervallo di definizione δ è possibile determinare l’ampiezza
ottimale LN del segmento che rende minimo il massimo intervallo di incertezza
finale.

N.B.: il metodo di Fibonacci prende il nome dal matematico italiano a causa dei
coefficienti, presenti nella formula iterativa, che appartengono alla sequenza
omonima. Fibonacci non è però l’ideatore del metodo.
28
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
Esempio: se l’intervallo di incertezza iniziale è xa = 0 e xb = 18, quale sarà il
valore minimo del massimo intervallo finale usando 4 prove e sapendo che δ = 1 ?
L + δ FN − 2
Applicando la formula generale: LN = 1
FN
si ottiene nello specifico:
L1 + δ F2 18 + 1 ⋅ 2
=L4 = = 4
F4 5

 δ 
Inoltre ricordando che =
LN − j LN  Fj +1 − Fj −1  le ampiezze degli intervalli
 LN 
intermedi valgono:

 δ   1
j =2 ⇒ L2 =L4  F3 − F1  =4  3 − 1  =11
 LN   4 
 δ   1
j =1 ⇒ L3 =L4  F2 − F0  =4  2 − 1  =7
 LN   4

29
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
Esempio: è possibile anche percorrere la strada opposta. Ovvero, assegnati δ ed
LN determinare il numero di iterazioni necessarie per poter partire da un
intervallo di incertezza iniziale, L1, sufficientemente grande. Si supponga ad
esempio di avere assegnato:
δ=
1.E − 7 1.E − 5
LN =

È possibile determinare la seguente tabella:

N L1
5 0.0000797
10 0.0008866
15 0.0098323
20 0.1090419
25 1.2092932
30 13.4112671
35 148.7332313
40 1649.4768114

N.B.: aumentando il numero di iterazioni del metodo è possibile utilizzare

inizialmente un intervallo di incertezza più ampio.
30
Slide fornite per cortesia del Prof. D. Manca
 Metodo di Fibonacci
PRO
1. Garantisce la convergenza ad un minimo relativo.
2. Rende minimo il massimo intervallo finale di incertezza.

CONTRO

1. Ha sempre la stessa efficienza indipendentemente dalla funzione

considerata. Mentre ciò è un pregio per funzioni molto complicate risulta
viceversa uno svantaggio con funzioni molto semplici. In particolare quando
l’intervallo di incertezza è molto piccolo spesso la funzione può essere
ragionevolmente approssimata con una parabola.

2. Richiede la conoscenza di un intervallo di incertezza.

3. Richiede la conoscenza dell’intervallo di definizione δ.

4. Se la ricerca viene interrotta non è più il metodo che rende minimo il

massimo intervallo finale di incertezza.

31
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
Nei moderni programmi di calcolo il metodo di Fibonacci non viene praticamente
più utilizzato. Si preferisce una variante più elastica: il metodo della sezione
aurea basato sempre sul concetto del confronto.

L’idea è quella che, dato un intervallo di incertezza generico, è opportuno

sfruttare la presenza del punto interno già disponibile (proveniente dai passi
precedenti). Il metodo si basa su 2 idee di base:

1. Affinché il nuovo punto sia posizionato in modo ottimale occorre che i due
punti interni (quello precedente e quello nuovo) siano simmetrici rispetto al
centro. Risulta quindi: L j −=
1 L j + L j +1
2. Si impone quindi che la velocità di riduzione degli intervalli sia costante:
L j −1 Lj
= = φ
Lj L j +1
Dalle due relazioni si ottiene: 1 + 1 = φ quindi: φ 2 − φ − 1 =0
φ
Risulta: φ = 5 + 1 =1.61803398874989484820458683 ovvero la sezione aurea.
2
32
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
È possibile osservare che il metodo della sezione aurea può essere ottenuto da
quello di Fibonacci. Infatti se si trascura il termine δ / LN si ottiene:

 δ  LN − j Fj +1
LN − j LN  Fj +1 − Fj −1
=  =
 LN  LN − j +1 Fj

e come precedentemente riportato, il rapporto di due numeri di Fibonacci

adiacenti tende velocemente alla sezione aurea.

Algoritmo:

Dato l’intervallo di incertezza iniziale L1 le prime due prove interne vanno poste a
distanza L1 / φ dagli estremi. Si procede così iterativamente.

33
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
Sequenza operativa:

1. Si identifica l’intervallo iniziale L1, definito dai due punti estremi xa e xb

all’interno del quale la funzione è unimodale ed è situato il minimo
L1
2. Si calcola quindi l’ampiezza del nuovo intervallo: L2 =
φ
3. Si posizionano i due punti interni: x1 = xb – L2 e x2 = xa + L2

4. Si restringe l’intervallo di incertezza eliminando uno o entrambi i punti esterni

xa e xb a seconda che siano valide le seguenti condizioni:

• se f(x1) < f(x2) l’intervallo di incertezza diventa: [xa, x2]

• se f(x1) > f(x2) l’intervallo di incertezza diventa: [x1, xb]

• se f(x1) = f(x2) l’intervallo di incertezza diventa: [x1, x2]

5. Si riordinano i punti residui e si calcola il nuovo intervallo L3 utilizzando la

formula del punto 2 opportunamente aggiornata. La procedura viene iterata.
34
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
Esempio: è dato un intervallo di incertezza con xa = 0 e xb = 18. Quindi L1 = 18.

L1 18 L2 11.1246 L3 6.8753
L=
2 = = 11.1246 L=
3 = = 6.8753 L=
4 = = 4.2492
φ 1.618 φ 1.618 φ 1.618

Si rammenta che nel caso del metodo di Fibonacci a parità di condizioni si aveva:
=LFib
2 11=LFib
3 7=LFib
4 4

N.B.: è possibile osservare come avendo programmato il metodo di Fibonacci per

fermarsi dopo 4 iterazioni, se si arriva effettivamente alla quarta prova tale
metodo è migliore rispetto a quello della sezione aurea (4 vs 4.2492).

Viceversa se si blocca il metodo di Fibonacci (programmato per 4 prove) alla

terza prova si vede che il metodo della sezione aurea è migliore rispetto a quello
di Fibonacci (7 vs 6.8753).

L’efficienza del metodo della sezione aurea, così come quella del metodo di
Fibonacci, è indipendente dalla funzione da ottimizzare.
35
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
Si definisce rapporto di riduzione, α, il rapporto tra l’intervallo finale di
incertezza LN e quello iniziale L1:
LN
α=
L1

Nel caso del metodo della sezione aurea il rapporto di riduzione vale:

LN 1
α
= = N −1
L1 φ

Conseguentemente il numero totale N di iterazioni necessario per ottenere uno

specifico rapporto di riduzione, α, è:

log α
N = 1−
log φ

36
Slide fornite per cortesia del Prof. D. Manca
 Metodo della sezione aurea
PRO
1. Garantisce la convergenza ad un minimo relativo.
2. È sempre efficiente qualunque sia il momento in cui si interrompe la ricerca.
3. Non richiede la conoscenza dell’intervallo di definizione δ.

CONTRO

1. Ha sempre la stessa efficienza indipendentemente dalla funzione

considerata. Mentre ciò è un pregio per funzioni molto complicate risulta
viceversa uno svantaggio con funzioni molto semplici. In particolare quando
l’intervallo di incertezza è molto piccolo spesso la funzione può essere
ragionevolmente approssimata con una parabola.

2. Richiede la conoscenza di un intervallo di incertezza.

37
Slide fornite per cortesia del Prof. D. Manca
 Metodi di approssimazione
I metodi di approssimazione utilizzano alcuni punti della funzione obiettivo, già
calcolati, per effettuare un’interpolazione esatta.

Viene poi usato il modello che interpola esattamente la funzione per stimare il
valore di x per cui essa risulta minima.

Per poter effettuare una interpolazione esatta occorre che la funzione

interpolante soddisfi i seguenti requisiti:

• deve rappresentare al meglio la funzione che si desidera interpolare.

• deve essere facile risolvere il sistema che permette di determinare i suoi

parametri.

• deve essere facile utilizzare la funzione interpolante per effettuare una

previsione.

• in molti casi deve essere facile stimare con la funzione interpolante le derivate
prime e seconde.

38
Slide fornite per cortesia del Prof. D. Manca
 Metodo di approssimazione parabolica
Nel caso specifico dell’ottimizzazione la funzione interpolante deve soddisfare un
ulteriore requisito:

• deve essere tale da permettere di stimare facilmente il valore in cui essa risulta
minima.

Conseguentemente, la sola funzione interpolante che ragionevolmente rispetta le

specifiche summenzionate è la parabola:

P2 ( x) = a2 x 2 + a1 x + a0
a1
Che ha minimo in: x = −
2a2
Se la funzione obiettivo passa per i punti (xa, ya), (xb, yb), (xc, yc), l’equazione della
parabola è:
yb − ya
P2 ( x) = ya + ( x − xa ) + λ ( x − xa )( x − xb )
xb − xa

λ=
( yc − ya )( xb − xa ) − ( yb − ya )( xc − xa )
( xb − xa )( xc − xa )( xc − xb )
39
Slide fornite per cortesia del Prof. D. Manca
 Metodo di approssimazione parabolica
Il punto di stazionarietà della derivata prima della parabola (minimo) lo si ottiene
a partire dai coefficienti:
a2 = λ
β λ ( xa + xb )
a1 =−
y − ya
a0 =ya − β xa + λ xa xb β =b
xb − xa

Si ottiene che: xMIN =

a1 1 β
− = xa + xb − 
2a2 2  λ
Occorre al contempo verificare che il punto xMIN sia effettivamente un minimo
controllando la concavità della parabola. Si deve avere: a2= λ > 0

In caso contrario il metodo non funziona, cioè non converge al punto di ottimo
del problema.

Iterando il procedimento, il punto xMIN sostituisce il peggiore dei tre punti

utilizzati per determinare i coefficienti della parabola. Non vi è certezza di
convergenza.
40
Slide fornite per cortesia del Prof. D. Manca
 Metodo di approssimazione parabolica

f(x) y = ax 2 + bx + c

x
x1 xMIN x2 x3

Individuato il punto di minimo della parabola ([Link] VERDE) calcolo f(xMIN) relativo alla curva
([Link] AZZURRO) e basandomi anche sugli altri tre punti (ROSSI) a disposizione, relativi alla
curva f(x) unimodale, determino il nuovo intervallo xMIN,…x3 cui appartiene il punto di minimo
della funzione ([Link] GIALLO). Avendo a disposizione tre punti posso iterare la procedura di
interpolazione valutando la nuova parabola passante per tali punti. Prima però pongo x4 = xMIN

41
Slide fornite per cortesia del Prof. D. Manca
 Metodo di approssimazione parabolica

f(x)

y = ax 2 + bx + c

x
xMIN
x4 x2 x3
Individuato il punto di minimo della parabola ([Link] VERDE) calcolo f(xMIN) relativo alla curva
([Link] AZZURRO) e basandomi anche sugli altri tre punti (ROSSI) a disposizione, relativi alla
curva f(x) unimodale, determino il nuovo intervallo xMIN,…x3 cui appartiene il punto di minimo
della funzione ([Link] GIALLO). Avendo a disposizione tre punti posso iterare la procedura di
interpolazione valutando la nuova parabola passante per tali punti. Prima però pongo x5 = xMIN.
E così via…
42
Slide fornite per cortesia del Prof. D. Manca
 Metodo di approssimazione parabolica
PRO

1. La velocità di convergenza è superiore a quella di un metodo lineare, quindi

è molto buona. L’ordine di convergenza del metodo è 1.3.

CONTRO

1. Il metodo può divergere.

2. Non sempre la funzione obiettivo è approssimabile con una parabola.

Qualora la funzione obiettivo non sia approssimabile con una parabola è
questa una delle possibili cause di divergenza del metodo.

43
Slide fornite per cortesia del Prof. D. Manca
 Considerazioni generali sui metodi di ottimizzazione

Un buon programma per la ricerca del minimo monodimensionale di una funzione

deve contenere sempre diversi algoritmi. La scelta del metodo efficiente è ovvia
perché non esistono alternative (metodo di approssimazione parabolica). Il
metodo robusto viene scelto fra il metodo di Fibonacci e quello della sezione
aurea.

Si auspica che un metodo di ottimizzazione monodimensionale soddisfi le

seguenti caratteristiche: robustezza, accuratezza ed efficienza.

N.B.: è assai difficile trovare sia a livello public domain che in commercio librerie
per l’ottimizzazione monodimensionale in grado di soddisfare le caratteristiche
summenzionate (la libreria BzzMath© rappresenta un’ottima eccezione).

44
Slide fornite per cortesia del Prof. D. Manca
 Considerazioni generali sui metodi di ottimizzazione

Robustezza
• il metodo deve riuscire a trovare con buona probabilità il minimo assoluto in
una funzione con più minimi relativi;
• deve riuscire a risolvere problemi in cui la funzione e/o le sue derivate
presentino discontinuità;
• deve riuscire a risolvere problemi in cui la funzione non è mai approssimabile
ad una parabola con derivata seconda positiva;
• deve riuscire a risolvere problemi in cui la funzione non è definita in qualche
intervallo.
Accuratezza
• il metodo deve riuscire a trovare la soluzione in modo preciso.
Efficienza
• il metodo deve avere convergenza quadratica con funzioni che siano ben
approssimabili con una parabola e buona velocità di convergenza in caso
contrario.

45
Slide fornite per cortesia del Prof. D. Manca
 Ricerca dell’intervallo di incertezza
Come visto in precedenza, i metodi di ricerca monodimensionale dell’ottimo di
una funzione unimodale sono sicuri ed efficienti quando sia noto l’intervallo di
incertezza.

In generale si preferisce lasciare all’utente l’assegnazione dell’intervallo di

incertezza.

Qualora tale intervallo non sia noto, non esistono metodi sicuri per la sua
individuazione. Alcuni algoritmi richiedono all’utente un solo punto. Da lì
individuano un secondo punto (perturbazione opportuna del primo) e quindi si
spostano nella direzione in cui la funzione diminuisce (se il problema è di
minimizzazione). Si rammenta infatti che con due soli punti non è detto che
l’intervallo sotteso sia quello di incertezza.

Con tre punti distinti si è sicuri di avere individuato l’intervallo di incertezza solo
se il punto interno ha il valore della funzione obiettivo inferiore a quello dei due
punti estremi (e se naturalmente la funzione è unimodale).

46
Slide fornite per cortesia del Prof. D. Manca
 Criteri di stop
Con riferimento ai criteri volti a bloccare la procedura di ricerca dell’ottimo, le
considerazioni qualitative condotte nel caso dell’azzeramento di funzioni valgono
anche per l’ottimizzazione monodimensionale.

I criteri di stop che è opportuno utilizzare sono:

1. Limite massimo sul numero di iterazioni dell’algoritmo di ricerca

2. Verifica dell’intervallo di incertezza [xa, xb]. Bloccare i calcoli se risulta:

xb − xa < xTolAbs + xTolRel ⋅ ( xa + xb )

N.B.: nel caso dello zero di una funzione xTolRel può essere dell’ordine del
macheps mentre nel caso dell’ottimizzazione deve essere dell’ordine della radice
quadrata del macheps.

3. I calcoli vengono interrotti quando la funzione obiettivo scende sotto un

valore assegnato dall’utente (valore assoluto o miglioramento percentuale).

47
Slide fornite per cortesia del Prof. D. Manca
 Letture aggiuntive
Leonardo Pisano detto Fibonacci
Leonardo Pisano is better known by his nickname Fibonacci. He was the son of Guilielmo and a member of the
Bonacci family. Fibonacci himself sometimes used the name Bigollo, which may mean good-for-nothing or a traveller.
As stated:
Did his countrymen wish to express by this epithet their disdain for a man who concerned himself with questions of
no practical value, or does the word in the Tuscan dialect mean a much-travelled man, which he was?
Fibonacci was born in Italy but was educated in North Africa where his father, Guilielmo, held a diplomatic post. His
father's job was to represent the merchants of the Republic of Pisa who were trading in Bugia, later called Bougie and
now called Bejaia. Bejaia is a Mediterranean port in northeastern Algeria. The town lies at the mouth of the Wadi
Soummam near Mount Gouraya and Cape Carbon. Fibonacci was taught mathematics in Bugia and travelled widely
with his father, recognising and the enormous advantages of the mathematical systems used in the countries they
visited. Fibonacci writes in his famous book Liber abaci (1202):
When my father, who had been appointed by his country as public notary in the customs at Bugia acting for the Pisan
merchants going there, was in charge, he summoned me to him while I was still a child, and having an eye to
usefulness and future convenience, desired me to stay there and receive instruction in the school of accounting.
There, when I had been introduced to the art of the Indians' nine symbols through remarkable teaching, knowledge
of the art very soon pleased me above all else and I came to understand it, for whatever was studied by the art in
Egypt, Syria, Greece, Sicily and Provence, in all its various forms.
Fibonacci ended his travels around the year 1200 and at that time he returned to Pisa. There he wrote a number of
important texts which played an important role in reviving ancient mathematical skills and he made significant
contributions of his own. Fibonacci lived in the days before printing, so his books were hand written and the only way
to have a copy of one of his books was to have another hand-written copy made. Of his books we still have copies of
Liber abaci (1202), Practica geometriae (1220), Flos (1225), and Liber quadratorum. Given that relatively few hand-
made copies would ever have been produced, we are fortunate to have access to his writing in these works. However,
we know that he wrote some other texts which, unfortunately, are lost. His book on commercial arithmetic Di minor
guisa is lost as is his commentary on Book X of Euclid's Elements which contained a numerical treatment of irrational
numbers which Euclid had approached from a geometric point of view.

48
Slide fornite per cortesia del Prof. D. Manca
 Leonardo Pisano
One might have thought that at a time when Europe was little interested in scholarship, Fibonacci would have been
largely ignored. This, however, is not so and widespread interest in his work undoubtedly contributed strongly to his
importance. Fibonacci was a contemporary of Jordanus but he was a far more sophisticated mathematician and his
achievements were clearly recognised, although it was the practical applications rather than the abstract theorems
that made him famous to his contemporaries.
The Holy Roman emperor was Frederick II. He had been crowned king of Germany in 1212 and then crowned Holy
Roman emperor by the Pope in St Peter's Church in Rome in November 1220. Frederick II supported Pisa in its
conflicts with Genoa at sea and with Lucca and Florence on land, and he spent the years up to 1227 consolidating his
power in Italy. State control was introduced on trade and manufacture, and civil servants to oversee this monopoly
were trained at the University of Naples which Frederick founded for this purpose in 1224.
Frederick became aware of Fibonacci's work through the scholars at his court who had corresponded with Fibonacci
since his return to Pisa around 1200. These scholars included Michael Scotus who was the court astrologer, Theororus
the court philosopher and Dominicus Hispanus who suggested to Frederick that he meet Fibonacci when Frederick's
court met in Pisa around 1225.
Johannes of Palermo, another member of Frederick II's court, presented a number of
problems as challenges to the great mathematician Fibonacci. Three of these problems
were solved by Fibonacci and he gives solutions in Flos which he sent to Frederick II.
We give some details of one of these problems below.
After 1228 there is only one known document which refers to Fibonacci.
This is a decree made by the Republic of Pisa in 1240 in which a salary is awarded to:
... the serious and learned Master Leonardo Bigollo ....
This salary was given to Fibonacci in recognition for the services that he had given to
the city, advising on matters of accounting and teaching the citizens.

49
Slide fornite per cortesia del Prof. D. Manca
 Leonardo Pisano
Liber abaci, published in 1202 after Fibonacci's return to Italy, was dedicated to Scotus. The book was based on the
arithmetic and algebra that Fibonacci had accumulated during his travels. The book, which went on to be widely
copied and imitated, introduced the Hindu-Arabic place-valued decimal system and the use of Arabic numerals into
Europe. Indeed, although mainly a book about the use of Arab numerals, which became known as algorism,
simultaneous linear equations are also studied in this work. Certainly many of the problems that Fibonacci considers
in Liber abaci were similar to those appearing in Arab sources.
The second section of Liber abaci contains a large collection of problems aimed at merchants. They relate to the price
of goods, how to calculate profit on transactions, how to convert between the various currencies in use in
Mediterranean countries, and problems which had originated in China.
A problem in the third section of Liber abaci led to the introduction of the Fibonacci numbers and the Fibonacci
sequence for which Fibonacci is best remembered today:-
A certain man put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be
produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the
second month on becomes productive?
The resulting sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... (Fibonacci omitted the first term in Liber abaci). This
sequence, in which each number is the sum of the two preceding numbers, has proved extremely fruitful and appears
in many different areas of mathematics and science. The Fibonacci Quarterly is a modern journal devoted to studying
mathematics related to this sequence.
Many other problems are given in this third section, including these types, and many many more:
A spider climbs so many feet up a wall each day and slips back a fixed number each night, how many days does it
take him to climb the wall. A hound whose speed increases arithmetically chases a hare whose speed also increases
arithmetically, how far do they travel before the hound catches the hare. Calculate the amount of money two people
have after a certain amount changes hands and the proportional increase and decrease are given.

50
Slide fornite per cortesia del Prof. D. Manca
 Leonardo Pisano
There are also problems involving perfect numbers, problems involving the Chinese remainder theorem and problems
involving summing arithmetic and geometric series.
Fibonacci treats numbers such as 10 in the fourth section, both with rational approximations and with geometric
constructions.
A second edition of Liber abaci was produced by Fibonacci in 1228 with a preface, typical of so many second editions
of books, stating that:-
... new material has been added [to the book] from which superfluous had been removed...
Another of Fibonacci's books is Practica geometriae written in 1220 which is dedicated to Dominicus Hispanus who we
mentioned above. It contains a large collection of geometry problems arranged into eight chapters with theorems
based on Euclid's Elements and Euclid's On Divisions. In addition to geometrical theorems with precise proofs, the
book includes practical information for surveyors, including a chapter on how to calculate the height of tall objects
using similar triangles. The final chapter presents what Fibonacci called geometrical subtleties [1]:-
Among those included is the calculation of the sides of the pentagon and the decagon from the diameter of
circumscribed and inscribed circles; the inverse calculation is also given, as well as that of the sides from the
surfaces. ... to complete the section on equilateral triangles, a rectangle and a square are inscribed in such a triangle
and their sides are algebraically calculated ...
In Flos Fibonacci gives an accurate approximation to a root of 10x + 2x2 + x3 = 20, one of the problems that he was
challenged to solve by Johannes of Palermo. This problem was not made up by Johannes of Palermo, rather he took
it from Omar Khayyam's algebra book where it is solved by means of the intersection of a circle and a hyperbola.
Fibonacci proves that the root of the equation is neither an integer nor a fraction, nor the square root of a fraction.
He then continues:-
And because it was not possible to solve this equation in any other of the above ways, I worked to reduce the
solution to an approximation.

51
Slide fornite per cortesia del Prof. D. Manca
 Leonardo Pisano
Without explaining his methods, Fibonacci then gives the approximate solution in sexagesimal notation as
[Link].33.4.40 (this is written to base 60, so it is 1 + 22/60 + 7/602 + 42/603 + ...). This converts to the decimal
1.3688081075 which is correct to nine decimal places, a remarkable achievement.
Liber quadratorum, written in 1225, is Fibonacci's most impressive piece of work, although not the work for which he
is most famous. The book's name means the book of squares and it is a number theory book which, among other
things, examines methods to find Pythogorean triples. Fibonacci first notes that square numbers can be constructed
as sums of odd numbers, essentially describing an inductive construction using the formula n2 + (2n+1) = (n+1)2.
Fibonacci writes:-
I thought about the origin of all square numbers and discovered that they arose from the regular ascent of odd
numbers. For unity is a square and from it is produced the first square, namely 1; adding 3 to this makes the second
square, namely 4, whose root is 2; if to this sum is added a third odd number, namely 5, the third square will be
produced, namely 9, whose root is 3; and so the sequence and series of square numbers always rise through the
regular addition of odd numbers.
To construct the Pythagorean triples, Fibonacci proceeds as follows:-
Thus when I wish to find two square numbers whose addition produces a square number, I take any odd square
number as one of the two square numbers and I find the other square number by the addition of all the odd numbers
from unity up to but excluding the odd square number. For example, I take 9 as one of the two squares mentioned;
the remaining square will be obtained by the addition of all the odd numbers below 9, namely 1, 3, 5, 7, whose sum
is 16, a square number, which when added to 9 gives 25, a square number.
Fibonacci also proves many interesting number theory results such as:
there is no x, y such that x2 + y2 and x2 - y2 are both squares.
and x4 - y4 cannot be a square.
He defined the concept of a congruum, a number of the form ab(a + b)(a - b), if a + b is even, and 4 times this if a
+ b is odd. Fibonacci proved that a congruum must be divisible by 24 and he also showed that for x, c such that x2 +
c and x2 - c are both squares, then c is a congruum. He also proved that a square cannot be a congruum.

52
Slide fornite per cortesia del Prof. D. Manca
 Leonardo Pisano
As stated in [2]:-
... the Liber quadratorum alone ranks Fibonacci as the major contributor to number theory between Diophantus and
the 17th-century French mathematician Pierre de Fermat.
Fibonacci's influence was more limited than one might have hoped and apart from his role in spreading the use of the
Hindu-Arabic numerals and his rabbit problem, Fibonacci's contribution to mathematics has been largely overlooked.
As explained in [1]:-
Direct influence was exerted only by those portions of the "Liber abaci" and of the "Practica" that served to introduce
Indian-Arabic numerals and methods and contributed to the mastering of the problems of daily life. Here Fibonacci
became the teacher of the masters of computation and of the surveyors, as one learns from the "Summa" of Luca
Pacioli ... Fibonacci was also the teacher of the "Cossists", who took their name from the word 'causa' which was first
used in the West by Fibonacci in place of 'res' or 'radix'. His alphabetic designation for the general number or
coefficient was first improved by Viète ...
Fibonacci's work in number theory was almost wholly ignored and virtually unknown during the Middle ages. Three
hundred years later we find the same results appearing in the work of Maurolico.
The portrait above is from a modern engraving and is believed to not be based on authentic sources.

Article by: J J O'Connor and E F Robertson

[Link]

53
Slide fornite per cortesia del Prof. D. Manca
 Bibliografia
• Atkinson K. E., “Elementary Numerical Analysis”, John Wiley & Sons, (1993)

• Buzzi Ferraris G., “Metodi numerici e Software in C++”, Addison Wesley, (1998)

• Comincioli V., “Analisi numerica. Metodi Modelli Applicazioni”, McGraw-Hill, (1990)

• Livio M., “La sezione aurea”, Rizzoli, (2002)

• Snijders C. J., “La sezione aurea”, Muzzio, (1985)

• [Link]

• [Link]

• [Link]

54