Schema per l’implementazione di vincoli non lineari

Per poter includere nell’ottimizzatore i vincoli non lineari si sono fatte prove su alcuni dei metodi esposti nel Cap. 2.3.2:

- I metodi basati sulla “feasibility” si sono dimostrati totalmente ineffi- cienti; unica eccezione per problemi di ottimizzazione particolarmente semplici, o meglio, con vincoli poco stringenti.

- I metodi basati sull’ Exterior Penalty Function si sono comportati di- scretamente anche in problemi pi`u complessi: si sono riscontrate diffi- colt`a numeriche legate alla scelta del parametro di penalizzazione (µ), in parte superate adottando una versione in cui detto numero varia con l’iter.

- I metodi basati sull’Augmented Lagrangian Penalty Function (ALPF) sono risultati soddisfacenti: si sono fatte prove con diverse versioni, in seguito riportiamo quella che si `e mostrata pi`u efficace.

4 – Implementazione del problema di ottimizzazione di traiettorie

Descrizione di un algoritmo basato su ALPF

Il metodo che ci accingiamo a descrivere affonda le sue radici nel LANCELOT, un algoritmo in Fortran introdotto da Conn[2]_{, di cui esistono numerose in-}

terpretazioni e varianti.

La versione che viene riportata `e quella applicata nel pacchetto di ottimiz- zazione sviluppato ed `e stata opportunamente modificata per adattarsi il meglio possibile all’ottimizzatore PSO con cui deve dialogare.

Come anticipato nel paragrafo 2.3.2 la ricerca dell’ottimo vincolato viene ricondotta alla soluzione del problema equivalente:

min x φ(x, γ, λ, s, µ), φ(x, γ, λ, s, µ) = f (x) + p X i=1 λi· hi(x) + m X j=1 γj · (gj(x) + s2j)+ + 1 2µ · " _p X i=1 (hi(x))2+ m X j=1 (gj(x) + s2j) 2 #

Nel seguito si supporr`a di non avere vincoli di disuguaglianza: `e possibile ri- dursi facilmente a questo caso utilizzando la procedura descritta da Bhatti[6]

o da Conn[2]_{; le difficolt`a nell’implementare i vincoli derivano principalmente}

dalle equazioni di uguaglianza e nell’ambito di questo studio riteniamo im- portante focalizzare l’attenzione su questo aspetto.

La funzione di penalizzazione considerata ha la seguente espressione:

φ(x, λ, µ) = f (x) + p X i=1 λi· hi(x) + 1 2µ · p X i=1 (hi(x))2 (4.1)

L’algoritmo che `e stato creato si basa su due cicli, uno esterno e l’altro in- terno. Inizialmente vengono introdotti i valori di partenza del numero di penalizzazione e dei moltiplicatori di Lagrange e le costanti che serviranno ad aggiornarli durante la simulazione.

Il ciclo esterno fissa cos`ı µk e λk ad ogni sua iterazione (k = 0 se siamo

al passo immediatamente successivo all’inizializzazione). Noti questi valori possiamo ricavare dall’ Eq. (4.1) la funzione penalizzata in funzione delle sole variabili di ottimizzazione, x: ci siamo quindi ricondotti ad un proble- ma di ottimizzazione non vincolata equivalente. Questo problema pu`o essere

4 – Implementazione del problema di ottimizzazione di traiettorie

risolto (tramite un ciclo interno) con un generico risolutore di ottimizzazione non vincolata, come ad esempio l’algoritmo basato sulla PSO. Il criterio di convergenza del ciclo interno si basa su valori soglia definiti nel ciclo esterno e dipendenti dal numero di iterazione k: il pi`u importante di questi, ωk, rappre-

senta la tolleranza entro la quale considerare uguali due iterazioni successive. Terminata la ricerca dell’ottimo del problema equivalente si verifica se i vin- coli sono rispettati: se verificano le condizioni obiettivo il ciclo termina. Se questo non avviene possono presentarsi due casi:

1. I vincoli, pur non rispettando il valore soglia obiettivo, rientrano co- munque in un valore di tolleranza, ηk, stabilito nel ciclo esterno al-

l’iterazione k-ma; la ricerca sta andando nella giusta “direzione” e si prosegue aggiornando i moltiplicatori di Lagrange.

2. I vincoli non sono rispettati e non rientrano neanche nei valori di so- glia ηk: in questo caso non si aggiornano i moltiplicatori di Lagrange

ma il parametro di penalizzazione per indurre la soluzione verso valori ammissibili.

Riportiamo schematicamente i passi della procedura. 1. Inizializzazione.

Vengono specificate le seguenti costanti, definite come strettamente positive:

ηs, ωs, αω βω, αη βη, (4.2)

e

τ < 1, ω∗  1 η∗  1 (4.3)

I coefficienti di (4.2) e (4.3) sono costanti necessarie ad aggiornare, in maniera opportuna, il numero di penalizzazione (tramite τ ), i molti- plicatori di Lagrange (indirettamente, tramite i valori di tolleranza sui vincoli), le tolleranze sui vincoli (ηs, αη, βη, η∗) e sulla convergenza (ωs,

αω, βω, ω∗); I valori numerici di questi parametri sono stati scelti in

basi ad alcuni dati trovati nel pacchetto GADS di MATLAB e a diverse prove effettuate durante questo studio.

4 – Implementazione del problema di ottimizzazione di traiettorie

diretto: sono i valori obiettivo delle tolleranze sui vincoli e sulla con- vergenza.

Inoltre si specifica un parametro di penalit`a iniziale, positivo:

µ0 < 1. (4.4)

Ed infine si ricavano i seguenti valori:

ω0 = ωsµα0ω (4.5)

η0 = ηsµ αη

0 . (4.6)

2. Iterazione interna.

Consiste nel risolvere il problema di ottimizzazione definito dalla (2.10), utilizzando gli appositi valori del parametro di penalizzazione e dei mol- tiplicatori di Lagrange. L’ottimizzatore, di tipo PSO nel nostro caso, si avvarr`a di un suo ciclo interno, le cui iterazioni vengono identificate con l’indice i, che terminer`a quando saranno soddisfatte, per un certo numero di iterazioni consecutive, le generiche condizioni di convergenza: | efk(xi) − efk(xi−1)| ≤ ωk (4.7)

dove con ef ci riferiamo alla funzione obiettivo da minimizzare (φ(x) nel nostro caso), il pedice k indica il numero di iterazione del ciclo esterno, l’apice i `e il numero dell’iterazione interna all’ottimizzatore e xi `e il vettore di variabili in corrispondenza del quale si ha la soluzione ottima del passo i-mo. Da sottolineare che, alla k-ma iterazione avremo dei valori del parametro di penalizzazione e dei moltiplicatori di Lagrange ben definiti (µk e λk), per cui la funzione φ che compare in (2.10) `e

funzione della sola variabile x. La soluzione dell’ottimizzatore sar`a in corrispondenza di x∗_k.

3. Test di convergenza. Se si verifica:

|h(x∗_k)| ≤ η∗, (4.8)

il ciclo esterno termina.

4 – Implementazione del problema di ottimizzazione di traiettorie

Se si verifica

|h(x∗

k)| ≤ ηk, (4.9)

allora `e necessario eseguire il passo 4, altrimenti si va al passo 5. 4. Aggiornamento del valore dei moltiplicatori di Lagrange.

Si pone: λk+1 = λk+ 2µk· h(x∗k) (4.10) µk+1 = µk (4.11) ξ = max  η∗, 1 2µk  (4.12) ωk+1 = ωkξβω (4.13) ηk+1 = ηkξβη (4.14)

5. Aggiornamento del parametro di penalizzazione. Si pone: λk+1 = λk (4.15) µk+1 = τ · µk (4.16) ξ = max  η∗, 1 2µk  (4.17) ωk+1 = ωsξαω (4.18) ηk+1 = ηsξαη (4.19)

Questi passi vengono ripetuti finch`e non `e verificata la convergenza al passo 3, oppure fino al raggiungimento di un certo numero di iterazioni nel ciclo esterno.

Lo schema dell’algoritmo `e riportato in Fig. 4.1.