Minimizzazione dell’energia
(Ottimizzazione)
Abbiamo visto che un sistema molecolare di N atomi può essere
descritto da 3N coordinate cartesiane. Se invece usiamo le
coordinate interne ci sono sei coordinate (cinque per le molecole
lineari) indipendenti che corrispondono alla rotazione e alla
traslazione della molecola mentre le altre definiscono la
configurazione e la struttura interna (i movimenti degli atomi). Per
un sistema con N atomi, l’energia è quindi una funzione di 3N–6
coordinate interne o di 3N coordinate cartesiane.
Sia che si usino i metodi della meccanica quantistica o quelli
della meccanica molecolare viene calcolata l'energia potenziale
di una delle tante configurazioni della molecola (calcolo a singolo
punto o single point).
Nasce quindi la questione di determinare quale sia la geometria,
fra tutte le conformazioni possibili, corrispondente all’energia più
bassa, cioè la geometria più stabile. Gli arrangiamenti degli atomi
di energia minima corrispondono a stati stabili del sistema, ogni
spostamento da un minimo dà una configurazione con energia
più elevata.
Superfici di energia potenziale
Nel caso più semplice, cioè quello di una molecola biatomica, l’energia
potenziale varia al variare della distanza:
Questa è una minimizzazione uni-dimensionale: l’energia dipende solo
da una coordinata, la distanza di legame r
Superfici di energia potenziale
Per sistemi con un maggior numero di atomi l’energia potenziale è una
funzione multidimensionale delle coordinate. Per esempio l’energia di
una conformazione dell’etano è funzione di 18 coordinate interne (o di 24
coordinate cartesiane) che sono richieste per specificarne
completamente la struttura.
2
H5
H1
H4
1.5
C2
C1
1
H6
0.5
H3
H2
-150
-100
-50
50
100
150
La maniera in cui varia l’energia in funzione delle coordinate è
generalmente indicata come superficie di energia potenziale (o
ipersuperficie).
Superfici di energia potenziale
E’ impossibile visualizzare l’intera superficie di energia potenziale, tranne
che in casi molto semplici in cui l’energia è funzione di solo una o due
coordinate.
Lisozima T4, 1328 atomi circa
Superficie di energia molto
complicata.
Ipersuperficie 3984-dimensionale!!
Si parla di superficie di energia potenziale non solo in sistemi in cui i
legami rimangono inalterati (come negli esempi visti), ma anche quando
si ha la rottura o formazione di legami (reazioni chimiche).
Superfici di energia potenziale
Nel molecular modelling siamo interessati nei punti di minimo del’energia
potenziale. Tali punti corrispondono infatti a stati stabili del sistema.
Ci possono essere molti punti di minimo sulla superficie. Il minimo con
l’energia più bassa in assoluto è chiamato punto di minimo globale.
Superfici di energia potenziale
Punti di interesse in una superficie di energia potenziale
Superfici di energia potenziale
Punti di sella (saddle points)
Superfici di energia potenziale
Ricerca del minimo (minimizzazione o ottimizzazione)
Quello della ricerca di un algoritmo di minimizzazione efficace è un
problema molto noto in matematica. Nei casi complessi per determinare i
minimi sulla superficie di energia potenziale in genere si ricorre ad
algoritmi matematici basati su metodi numerici. C’è una vasta letteratura
su questi metodi, qui ci soffermeremo su quegli approcci più
comunemente usati in meccanica molecolare.
Collegate alla questione della ricerca del minimo sono le risposte alle
seguenti domande:
 Quale conformazione corrisponde al minimo globale?
 Quali conformazioni sono presenti nei punti di minimo locale?
 Quali variazioni nella struttura della molecola avvengono quando si
passa da un minimo all’altro?
 Quale è la conformazione dello stato di transizione che collega due
minimi?
Superfici di energia potenziale
Punti stazionari
Sia i punti di minimo che i punti di sella sono punti stazionari.
Un punto stazionario è definito come un punto sulla superficie di energia
potenziale in cui la derivata dell'energia rispetto a tutte le coordinate è
zero.
V ( r )
0
r
Superfici di energia potenziale
Punti di minimo
Un punto di minimo oltre ad avere le derivate prime rispetto a tutte le
coordinate uguali a zero deve avere tutte le derivate seconde positive.
V
 0;
ri
 2V
0
2
ri
Quest'ultima
condizione
corrisponde ad avere la
curvatura della superficie
tutta “all'insù”
Superfici di energia potenziale
Punti di sella
Un punto di sella oltre ad avere le derivate prime rispetto a tutte le
coordinate uguali a zero deve avere tutte le derivate seconde positive
tranne che in una direzione.
Definizione rigorosa: i punti di sella sono punti stazionari con uno ed un
unico autovalore negativo della matrice Hessiana (matrice delle derivate
seconde).
Quest'ultima
condizione corrisponde
ad avere la curvatura
della superficie tutta
“all'insù” tranne che in
una direzione.
Superfici di energia potenziale
Punti di sella
I punti di sella connettono due minimi attraverso il cammino di minima
energia.
Ricerca dei punti di minimo
In termini matematici il problema è dunque quello di minimizzare una
funzione -appunto l’energia- di più variabili -le coordinate interne degli
atomi.
Qualora l’energia di un sistema di particelle possa essere rappresentata da
una funzione analitica, il minimo può essere trovato con metodi di calcolo
standard. Questo non è però generalmente possibile per sistemi molecolari
complicati nei quali l’energia varia con le coordinate in maniera complessa.
In questi casi i minimi sono localizzati usando metodi numerici nei quali le
coordinate vengono variate gradualmente producendo configurazioni con
energie sempre più basse fino al raggiungimento del minimo.
Scelta dell'algoritmo.
Ci sono molti fattori che determinano la scelta dell'algoritmo più
appropriato per un dato problema:
- veloce
Poche iterazioni ?
Poche valutazioni di V(r)?
- robusto
- che richiede poca memoria
Algoritmi di minimizzazione
Algoritmi di minimizzazione
Si possono classificare gli algoritmi di minimizzazione in due gruppi:
1) quelli che non usano le derivate dell’energia rispetto alle coordinate
Esempio:
N.B.:
- Direzione
- Passo (step)



Punto di confronto
Algoritmi di minimizzazione
Algoritmi di minimizzazione
Si possono classificare gli algoritmi di minimizzazione in due gruppi:
1) quelli che non usano le derivate dell’energia rispetto alle coordinate
2) quelli che usano le derivate dell’energia rispetto alle coordinate.
Esempio:
E ( r )
r
N.B.:
- Direzione
- Passo (step)


Algoritmi di minimizzazione
Algoritmi di minimizzazione
Molti algoritmi di minimizzazione possono solo andare in discesa lungo
la superficie di energia e quindi riescono solo a localizzare il minimo più
vicino al punto d’inizio (quindi un minimo locale).
Per localizzare più di un minimo o per localizzare l’energia minima
globale sono richiesti metodi che permettano di partire da differenti
geometrie iniziali, ognuna delle quali viene poi minimizzato.
Si confronta poi l'energia corrispondente ai vari minimi locali.
start
start
minimo locale
minimo globale
Algoritmi di minimizzazione
Minimizzazione senza l'uso di derivate: metodo del simplesso (simplex)
Non è molto efficiente, ma le derivate non sono richieste ed è piuttosto
robusto.
Il simplesso è una figura geometrica
che, in N dimensioni, consiste in
N+1 punti (vertici) interconnessi e
nelle rispettive linee, o facce
poligonali che li interconnettono.
In due dimensioni abbiamo un
triangolo
In tre dimensioni abbiamo un
tetraedro
2 D
3 D
Algoritmi di minimizzazione
Minimizzazione senza l'uso di derivate: metodo del simplesso (simplex)
Si parte con N+1 posizioni (set di coordinate) che definiscono il simplesso
iniziale.
Consideriamo una minimizzazione bidimensionale. Partiamo in tutto da tre
posizioni iniziali in corrispondenza alle quali calcoliamo il valore dell'energia.
A questo punto si inizia a far
muovere il simplesso. Ci possono
essere vari tipi di mosse:
1.
riflessione del vertice con il
valore più alto rispetto al lato
opposto
2.
riflessione ed allontanamento
rispetto al vertice con il valore
più alto
3.
contrazione lungo la
dimensione del punto con il
valore più alto




alto

basso



alto

basso
Algoritmi di minimizzazione
Minimizzazione senza l'uso di derivate: metodo del simplesso (simplex)
Dopo queste mosse ci ritroviamo
vicino ad un minimo e quindi:

4. il simplesso si contrae in tutte le
dimensioni verso il punto più basso

alto
Un'appropriata sequenza di queste 4
mosse porta sempre a convergenza

basso
Algoritmi di minimizzazione
CONFORMAZIONE 2
Atomo
X
Y
1
x21
y21
2
x22
y22
3
x23
y23
.
.
.
.
.
.
n
x2n
y2n
CONFORMAZIONE 1
Atomo
X
Y
1
x11
y11
2
x12
y12
3
x13
y13
.
.
.
.
.
.
n
x1n
y1n
CONFORMAZIONE 3
Atomo
X
Y
1
x31
y31
2
x32
y32
3
x33
y33
.
.
.
.
.
.
n
x3n
y3n
Algoritmi di minimizzazione
Metodo del simplesso: considerazioni generali
-perchè N+1 vertici per N coordinate?
-come si generano i punti di partenza?
-quando è vantaggioso da usare?
Algoritmi di minimizzazione
Criteri di Convergenza
A differenza di quello che succede con le funzioni analitiche nelle
applicazioni “reali” di molecular modelling è possibile identificare l'esatta
posizione dei minimi solo raramente, possiamo solo sperare di
raggiungere una buona approssimazione. E' necessario quindi avere dei
criteri per decidere quando il calcolo di minimizzazione è
sufficientemente vicino ad un minimo in modo da poter essere terminato.
Ogni calcolo è ovviamente limitato dalla precisione con cui vengono
immagazzinati i numeri, ma nella maggior parte dei casi ci si ferma ben
prima di questo limite.
Ci sono vari criteri tra cui scegliere (o applicare quello che si verifica per
primo). Ci si ferma quando:
- si raggiunge un massimo numero di iterazioni
- quando la differenza di energia tra due passi successivi è minore di una
certa tolleranza
- quando il passo (cioè la differenza tra due configurazioni successive) è
piccola.
Algoritmi di minimizzazione
Scelta del punto di partenza
Dipende da quello che vogliamo ottenere:
Se vogliamo ottenere la struttura di minima energia (minimo globale)
conviene partire da una struttura che probabilmente è già vicina a quel
minimo:
- es. struttura a raggi X (dai database)
- se vogliamo utilizzare i metodi della meccanica quantistica (più
pesanti) ci conviene partire da una struttura già minimizzata con i
metodi della meccanica molecolare.
Se vogliamo la geometria di tutte le strutture a bassa energia (più
minimi locali) allora possiamo partire da diverse strutture casuali
(“random”). (E' del tutto vero?)
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate
Le derivate danno informazioni riguardo la forma della superficie di
energia potenziale e se ben usate possono aumentare in maniera
significativa l’efficienza nella localizzazione del minimo. Pertanto esse,
qualora siano disponibili, vengono impiegate dai più comuni metodi di
minimizzazione. La direzione della derivata prima dell’energia (il
gradiente) indica dove abbiamo un minimo visto che la grandezza del
gradiente è relazionata alla pendenza della curva. Poiché la forza cui è
sottoposto un atomo è uguale al gradiente cambiato di segno, l’energia
del sistema può essere abbassata dal movimento di ciascun atomo in
risposta all’azione della forza agente su di esso. La derivata seconda
indica la curvatura della funzione, e può essere usata per predire dove la
funzione cambierà direzione. Per usare questo tipo di metodi è
ovviamente necessario poter calcolare le derivate dell’energia rispetto
alle variabili.
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate
Le derivate possono essere ottenute analiticamente o
numericamente. L’uso di derivate analitiche è preferibile perché
sono esatte ed in più possono essere calcolate più velocemente.
In alcuni casi può essere più efficace un algoritmo di
minimizzazione non basato sulle derivate che fare ricorso a
derivate numeriche
I metodi di minimizzazione che utilizzano le derivate possono
essere classificati secondo il più alto ordine delle derivate
impiegate. Metodi del primo ordine usano le derivate prime (cioè i
gradienti) mentre metodi del secondo ordine sfruttano derivate sia
prime che seconde.
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate: metodo “steepest descent”
Nel metodo “steepest descent” ci si muove nella direzione parallela
alla forza netta, che equivale a muoversi in linea retta per la discesa.
Il punto d’inizio per ogni iterazione k è la configurazione molecolare
ottenuta dal passaggio precedente che è rappresentata da un
vettore multidimensionale xk-1 che contiene le coordinate di tutti gli
atomi del sistema.
Per la prima iterazione il punto di partenza è la configurazione
iniziale del sistema, il vettore x1 che è fornito dall’utente. La
direzione dello spostamento dal punto iniziale è dunque definita dal
gradiente gk ed è data da un vettore unitario 3N-dimensionale (in
coordinate cartesiane) sk:
 gk
sk 
gk
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate: metodo “steepest descent”
Dopo aver definito la direzione lungo la quale muoversi occorre
decidere quanto muoversi lungo il gradiente.
Ci sono due metodi:
- line search: nella direzione del gradiente si trova il punto di minimo
(in pratica si minimizza in una dimensione)
 V V V 

V  
,
,
 xi yi z i 
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate: metodo “steepest descent”
Secondo metodo:
- si possono considerare step arbitrari: si aumenta lo step finchè le
iterazioni provocano una diminuzione dell’energia. Quando uno step
produce un aumento di energia si assume che l’algoritmo abbia
saltato la valle che contiene il minimo. La lunghezza dello step è
allora ridotta in modo da poter identificare il minimo stesso.
Algoritmi di minimizzazione
Problemi nell’uso del metodo “steepest descent”
La ricerca del minimo avviene ad ogni passo lungo una direzione che
è perpendicolare alla precedente e quindi l'approccio al minimo
assume un carattere oscillatorio che diviene piuttosto inefficiente
soprattutto in “valli” di energia strette e in prossimità del minimo in
quanto l’iterazione successiva tende ad annullare il guadagno
ottenuto con la precedente.
La minimizzazione procede rapidamente quando la geometria della
molecola è lontana dal punto di arrivo ma procede lentamente (molte
iterazioni) alla fine.
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate: metodo “conjugate gradient”
Il metodo “conjugate gradient” produce un insieme di direzioni che
non mostra il comportamento oscillatorio del metodo “steepest
descent”. Il metodo conjugate gradient usa un algoritmo che
produce una serie di line search con direzioni mutuamente
coniugate così che ad ogni successivo step si ha un raffinamento
della direzione verso il minimo. Questo sistema comporta che il
gradiente successivo è ortogonale a tutti i precedenti gradienti e che
la nuova direzione è coniugata alle precedenti e non ortogonale
come nello steepest descent.
Algoritmi di minimizzazione
Minimizzazione con l'uso di derivate: metodo al secondo ordine
Sono i metodi che fanno uso di derivate seconde (matrice
Hessiana), oltre alle derivate prime. Le derivate seconde danno
informazioni sulla curvatura della superficie. Tra questi metodi
ricordiamo il Newton-Raphson e varianti su questo metodo, che
introducono semplificazioni nel calcolo della matrice Hessiana.
Sono metodi in genere molto veloci, a volte possono essere instabili
lontano dal punto di minimo.
Algoritmi di minimizzazione
Scelta della minimizzazione
E’ dettata da un numero di fattori, compresi il peso e il tempo
computazionale, le velocità relative con cui le varie parti del calcolo
devono essere effettuate, la disponibillità delle derivate analitiche e
la robustezza del metodo.
- Metodi per sistemi molto grandi, generalmente si applica la
meccanica molecolare (Conjugate gradient)
- Metodi per sistemi di media grandezza, in cui si può anche usare
la meccanica quantistica (Metodi con derivate seconde, NR, ecc)
Si possono anche usare metodi più lenti ma più robusti lontano dal
minimo e poi passare a metodi più veloci.
Algoritmi di minimizzazione
Applicazioni della minimizzazione
- per trovare il minimo globale
- per preparare il sistema per altre simulazioni:
• rilassare le conformazioni ad energia più alta
• avere una geometria di partenza buona
- ricerca conformazionale (conformational search)
- analisi dei modi normali della molecola