Appunti di Optimization Methods

Algoritmi di ottimizzazione non vincolata

T T T∗ 0 X− )= =d Q(x x α d Qd α d Qdi i k kk k ki=0Osserviamo che alla iterazione intermedia abbiamo:k-esima k 0= + + +x x α d ... α dk−1 k−10 0Da cui, analogamente, otteniamo: k−1T Tk 0 X− ) = = 0d Q(x x α d Qdi ik ki=0Pertanto, combinando questi due risultati, il passo per la direzione è dato da:d kT ∗ 0− )d Q(x xk=α Tk d QdkkT ∗ k k 0−x −+ )d Q(x x xk= Td QdkkT T∗ Hk k 0− −) )d Q(x x d Q(x xHk k H= +T THHd Qd d Qdk kk k HHHCAPITOLO 2. ALGORITMI DI OTTIMIZZAZIONE NON VINCOLATA 60T ∗ k−(Qx )d Qxk= Td QdkkT k−(c )d Qxk= Td Qdkk Tk−∇f (x ) dk= Td QdkkQuesto risultato mostra che il generico coefficiente è il punto di minimo di lungoα fkla corrispondente direzione (ovvero coincide con il passo ottimo lungo la direzioned αk kin corrispondenza di ). Pertanto, la soluzione ottima può essere

determinata∗kd x xkmediante minimizzazioni esatte unidimensionali lungo le direzioni coniugate.

Proposizione (metodo delle direzioni coniugate). Sia è una matrice sim-Qmetrica e definita positiva e sia un insieme di direzioni mutua-d , ..., d n−10mente coniugate rispetto a Consideriamo e ,n k+1 k0 ∈ = +Q. x x x α dR k kTcon . Allora, chiamando valgono due proprietà:

1. k−∇f d(x ) k∇f= = (x ),kα gTk kd Qd kki. per ogniT −= 0 = 0, 1.g d i ..., kik1. Esiste tale che .∗k≤ =k n x xDim:⚠ i. Sia Allora:i < k. k−1k i X= +x x α dj jj=iMoltiplicando entrambi i membri per e sottraendo otteniamo:Q ck−1k i X−c −c= +Qx Qx α Qdj jj=iPoiché allora abbiamo:−=g Qx c, k−1X= +g g α Qdk i j jj=iMoltiplicando entrambi i membri per possiamo scrivere:Td ik−1T T TX= +d g d g α d Qdk i j ji i ij=iPer ipotesi quando Quindi otteniamo:T 6= 0 =d Qd j i.ji T T T= +d

g d g α d Qdk i i ii i i

CAPITOLO 2. ALGORITMI DI OTTIMIZZAZIONE NON VINCOLATA 61

Sostituendo il valore assunto per α possiamo scrivere:

α T−g dT T Tii H= +d g d g d QdHk i iTi i i HHd Qd HiHi HHT T−= d g d gi ii i=0ii.

Supponiamo che siano state completate iterazioni. Allora cintroviamo in: n−1n 0 X= +x x α di ii=0

Per il punto precedente per ogni (conT −= 0 = 0, 1).g d j < n j ..., njn

Questo significa che è ortogonale ad ogni direzione (cong dn jInoltre, per ipotesi, le direzioni sono mutuamente−= 0, 1).j ..., nconiugate e quindi linearmente indipendenti.

Perciò, necessariamente da cui Quindi otteniamon −= 0 = 0.g Qx cn, ovvero dopo iterazioni abbiamo raggiunto l’ottimo globale.∗n =x x nC.V.D.

Dalla proposizione precedente abbiamo ottenuto che, assumendo note direzioni mu-ntuamente coniugate, possiamo determinare il punto di minimo di al più in iterazio-f nni.Il problema algoritmico del metodo delle

direzioni coniugate è quello di calcolare l'insieme delle direzioni. A tale scopo, per costruire direzioni mutuamente, ..., d_nn-10 metodo del gradiente coniugate, possiamo adottare una soluzione iterativa detta coniugato. In particolare, chiamando ed ipotizzando, allora k∇f - g= (x) = g dk 0 0 scegliendo: T 2-g kg kdk k+1k= α βTk k+1 kg k 2d Qdk kk Possiamo calcolare la nuova direzione come -g= +d β dk+1 k+1 k+1 k Questo algoritmo garantisce che le direzioni così costruite sono mutuamente, ..., d n-10 coniugate. Algoritmo 5 Metodo del gradiente coniugato. Fissiamo un punto iniziale, supponiamo e poniamo 1: n0 ∈ -g= = 0.x d kR 0 0 while do 2: kg k 6 = 0k Calcoliamo il passo .2kg k 3: α = kα Tk d Qd kk Determiniamo un nuovo punto .4: k+1 k= +x x α dk k Aggiorniamo il gradiente .5: α = +g g α Qdk+1 k k k Calcoliamo .2kg k 6: β =β k+1 2kg k Valutiamo la nuova direzione .k 7: -g= +d β

dk+1 = k+1 - k

Poniamo8: = + 1.k k

CAPITOLO 2. ALGORITMI DI OTTIMIZZAZIONE NON VINCOLATA 62

Osserviamo che il metodo è esatto e termina in passi (ovvero in passi raggiunge unn nottimo del problema). Se è grande però (ad esempio per problemi ad alta dimensio-nnalità), potrebbe risultare troppo costoso eseguire tutti i passi dell'algoritmo. In questo caso, possiamo introdurre un criterio di arresto in modo da ridurre il tempokg k ≤ εkdi calcolo (ovvero ci accontentiamo di un'approssimazione dell'ottimo definendo unatolleranza ε). Questo criterio rende l'algoritmo iterativo.

I punti generati dal metodo del gradiente coniugato sono ottenuti mediante ricerche dilinea esatte lungo direzioni di discesa, per cui si ha che il valore della funzione obiettivodecresce in modo monotono. Tale algoritmo è spesso utilizzato per problemi quadraticie sistemi lineari.

Vediamo come possiamo estendere il metodo del gradiente coniugato

al caso generale non lineare. min (x)fnx∈R

In questo caso, la scelta della dimensione del passo deve essere effettuata mediante una procedura di ricerca lineare (Line Search). Inoltre, nel caso generale non possiamo garantire la convergenza in iterazioni (proprietà particolare del caso quadrato-nco), perciò necessariamente dobbiamo prevedere una tolleranza per il criterio di arresto, ovvero: kk∇f ≤(x )k ε

Per quanto riguarda , questo deve essere espresso in modo tale che non dipenda dalla matrice Sono state proposte molte regole di aggiornamento differenti, ognuna delle quali produce un schema algoritmico leggermente diverso (invece nel caso quadratico tutte le scelte di sono equivalenti). In particolare, consideriamo l’aggiornamento: k+1 2k∇f (x )k=β k+1 kk∇f 2(x )k

Un algoritmo basato sull’aggiornamento così definito è denominato metodo del Fletcher-Reeves gradiente

coniugato di ed è una delle realizzazioni del metodo delgradiente coniugato non lineare più efficienti. Lo schema di ricerca lineare utilizzato per la selezione di è cruciale per ottenere ver-α ksioni convergenti dell’algoritmo. In particolare, la regola di Armijo da sola non è suffi-ciente a garantire che la direzione sia una direzione di disce-−g= +d β dk+1 k+1 k+1 ksa. In particolare, per avere una direzione di discesa è necessario garantire la seguentecondizione (condizione sufficiente di discesa):

T T2−kg k= + 0d g β d g <k+1 k+1 k+1 k+1k+1 kOsserviamo che: k 2k∇f (x + )kα dk kk+1 k−∇f −∇f= (x ) + = (x + ) +d β d α d dk+1 k+1 k k k kkk∇f 2(x )kPerciò, sia che sono funzioni di .k 2k∇f d(x +α )kk∇f= (x + ) = k kg α d β αk+1 k k k+1 kk 2k∇f (x )kQuesto significa che il soddisfacimento della condizione sufficiente

di discesa dipende effettivamente da α e quindi dalla ricerca di linea effettuata lungo la direzione δ. La ricerca lineare con il metodo di Armijo non è sufficiente a garantire la condizione di discesa. Invece, si può dimostrare che se scegliamo un passo in modo tale da soddisfare le condizioni di Wolfe, allora possiamo garantire la proprietà di discesa nell'algoritmo del gradiente coniugato di Fletcher-Reeves.

CAPITOLO 2. ALGORITMI DI OTTIMIZZAZIONE NON VINCOLATA

2.7 Metodo di Wolfe

Il metodo di Armijo non impone alcuna condizione sul gradiente ∇f. Tuttavia, alcuni metodi di ricerca lineare impongono delle condizioni di pendenza nel punto. In particolare, il metodo di Wolfe definisce due diversi criteri:

Condizione di Wolfe debole:

• αk ≤ γ (condizione di Armijo).
• ∇f_k·∇x_k ≥ γ∇f₀·∇x₀ (γ, 1).

Σ∇f d σ◦ k k k k

Condizione di Wolfe forte:

• con (condizione di Armijo).T 12k k k≤ ∇f ∈(x + ) (x ) + (x ) (0, )f α d f γ;α d γ◦ k k k kconT Tk k|∇f | ≥ | ∈(x + ) (x ) (γ, 1).α d d σ|∇f d σ◦ k k k k

In particolare, nella condizione di Wolfe debole si accettano tutti i valori di tali che α krisulti soddisfatta la condizione del metodo di Armijo (che rappresenta la condizione diriduzione sufficiente) e la tangente alla curva in abbia pendenza positiva (cioè φ(α) α kè crescente) oppure abbia pendenza negativa (cioè è decrescente), ma minoreφ(α) φ(α)di Tk |.(x )