Generalità matematiche sugli strumenti utilizzati nei soft-

• IPOPT (Interior Point OPTimizer) è una libreria software per l’ottimizzazione non lineare su larga scala di sistemi continui. È stato progettato per trovare soluzioni (locali) di problemi di ottimizzazione matematica.

• KNITRO è una libreria software di ottimizzazione in grado di trovare soluzioni sia per modelli continui (con o senza vincoli), sia modelli discreti (con variabili intere o binarie). KNITRO è stato sviluppato in primo luogo per trovare la soluzione ottima locale su larga scala di problemi continui non lineari.

• SNOPT (Sparse Nonlinear OPTimizer) è una libreria software commerciale per risol- vere problemi di ottimizzazione (lineare e non lineare) su larga scala. È particolar- mente efficiente nel trovare la soluzione di problemi non lineari le cui funzioni e i cui gradienti sono computazionalmente costosi da valutare.

3.2

Introduzione a GPOPS-II

3.2.1

Sommario

GPOPS−II(General Pseudospectral Optimal Control Software, v2) è un software general pur- pose capace di risolvere varie tipologie di problemi di controllo ottimo non lineari, tempo continuo, e multi-fase.

GPOPS−IIutilizza metodi pseudo-spettrali di ottimizzazione: si avvale di un metodo di quadratura gaussiano pseudo-spettrale con punti di Radau di tipo hp-adattivo, dove la collocazione avviene per mezzo di punti di quadratura Gauss-Legendre-Radau.

GPOPS−IIè stato sviluppato per lavorare su problemi di Programmazione non lineare (NonLinear Programming, NLP), utilizzando i risolutori SNOPT e IPOPT, entrambi inclusi con il software, ed integrandosi perfettamente con MATLAB senza l’utilizzo di software aggiuntivi.

GPOPS−IIimpiega la discretizzazione finita sparsa per la stima tutte le derivate prime e seconde richieste dai risolutori NLP.

Il software è stato progettato per essere estremamente flessibile, permettendo all’utilizza- tore di formulare il problema di controllo ottimo in maniera intuitiva e strutturata. GPOPS−IIè stato scritto da Michael A. Patterson e Anil V. Rao, e rappresenta un grande passo avanti nella risoluzione numerica dei problemi di controllo ottimo.

Il software è disponibile online nel sito http://www.gpops.org/.

3.2.2

Generalità matematiche sugli strumenti utilizzati nei software di

controllo ottimo

Il Controllo Ottimo viene utilizzato in varie applicazioni che includono l’ottimizzazione della traiettoria, il controllo dell’assetto e la guida di un veicolo. Come viene definito da Kirk, “L’obiettivo di un problema di controllo ottimo è di determinare i segnali di controllo che

porteranno un processo a soddisfare i vincoli fisici e allo stesso tempo minimizzare (o massimizzare) alcuni indici di performance”.

Ad eccezione di casistiche particolari, spesso i problemi di controllo ottimo non possono essere risolti analiticamente, e bisogna affidarsi a metodi di risoluzione numerica. I meto- di numerici che risolvono problemi di controllo ottimo possono racchiusi in due categorie: metodi indiretti e metodi diretti.

In un metodo indiretto, il calcolo delle variazioni9 _{è applicato per determinare le con-}

dizioni necessarie del primo ordine per un soluzione ottima. Attraverso il calcolo delle variazioni, il problema di controllo ottimo viene trasformato un un problema al contor- no Hamiltoniano: in questo caso, la soluzione viene approssimata utilizzando uno dei vari approcci numerici esistenti; i più comuni approcci numerici sono i metodi di shoo- ting10 e di shooting multiplo11, metodi alle differenze finite12 e metodi di collocazione13. Sebbene i metodi indiretti hanno il vantaggio di ottenere un’approssimazione molto ac- curata e possono stabilire quanto sia vicina l’approssimazione alla soluzione ottima, sono caratterizzati da numerosi svantaggi.

In un metodo diretto, le funzioni continue del tempo (gli stati e/o i controlli) del pro- blema di controllo ottimo vengono approssimate ed il problema viene trascritto in un problema di programmazione non lineare a dimensione finita; si distinguono metodi in cui vengono approssimate solo le variabili di controllo (metodi di parametrizzazione delle variabili di controllo) e metodi che approssimano le variabili di stato e di controllo (metodi di parametrizzazione delle variabili di stato e controllo).

GPOPS−II[41] utilizza metodi diretti di collocazione, dove le variabili di stato e di con- trollo vengono parametrizzate utilizzando un insieme di funzioni trial (basis), imponendo un insieme di vincoli algebrici-differenziali ad un numero finito di punti di collocazione. In un metodo diretto di collocazione locale, l’intervallo di tempo è diviso in sotto-intervalli ed un polinomio fisso di basso grado viene utilizzato per l’approssimazione in ciascun sotto-intervallo. La convergenza della discretizzazione numerica è raggiunta incrementan- do il numero di sotto-intervalli. Nella collocazione locale vengono usate due categorie di discretizzazioni: metodi Runge-Kutta, che usano polinomi a tratti; metodi di collocazione ortogonali, che usano polinomi ortogonali.

Un metodo nuovo di collocazione sono i metodi pseudo-spettrali, dove le funzioni basis sono tipicamente polinomi di Chebyshev o Lagrange, e i punti di collocazione sono ottenuti da regole di quadratura Gaussiana molto accurate: questi metodi sono basati su metodi spettrali e tipicamente hanno una velocità di convergenza più alta (esponenziale) rispetto ai metodi tradizionali, utilizzando un basso numero di punti di discretizzazione.

Il metodo pseudo-spettrale di Radau (Radau Pseudospectral Method, RPM) è un metodo di trascrizione diretta che usa la parametrizzazione delle variabili di stato e controllo da polinomi globali (polinomi di Lagrange) e la collocazione di vincoli differenziali con punti Legendre-Gauss-Radau (LGR): un approfondimento teorico del metodo RPM può essere trovato nei riferimenti [42], [43], [44] e [45]. Questo metodo differisce da quello di Lobatto nel fatto che le equazioni della dinamica non vengono collocate al punto finale. Questo metodo fornisce un approccio per ottenere un’approssimazione accurata delle variabili

9_{Il calcolo delle variazioni si occupa della ricerca dei punti estremali (massimi e minimi) dei}

funzionali.

10_{I metodi shooting approssimano la soluzione a partire dalla conoscenza della derivata prima.} 11_{I metodi di shooting multiplo dividono l’intero intervallo in sotto-intervalli ed usano i metodi}

shooting su ognuno di questi.

12_{I metodi alle differenze finite consiste nella risoluzione di un sistema non lineare formato da}

equazioni alle differenze

13_{I metodi di collocazione utilizzano delle funzioni approssimanti e dei punti che soddisfano}

l’equazione scelta (i nodi di collocazione)

co-stato per il problema tempo continuo, utilizzando i moltiplicatori KKT14 del NLP; le variabili co-stato nel punto finale possono essere stimati con accuratezza usando una quadratura Radau. Rispetto al metodo pseudo-spettrale di Gauss, RPM differisce sul fatto che le equazioni dinamiche vengono collocate nel punto iniziale, e quindi viene fornita un’approssimazione delle variabili di controllo al punto iniziale.

Il metodo pseudo-spettrale di Radau utilizzato da GPOPS−II ha molteplici vantaggi: l’implementazione del metodo è semplice ed ogni cambiamento nei vincoli pò essere aggiunto nella formulazione senza lavoro aggiuntivo; una soluzione accurata può essere trovata utilizzando risolutori NLP sparsi ben-posti, senza la necessità di una stima iniziale sulle variabili co-stato o la derivazione delle condizioni necessarie; le variabili co-stato possono essere stimate direttamente dai moltiplicatori KKT del NLP; inoltre, il metodo presenta la tipica convergenza esponenziale dei metodi spettrali, utilizzando un numero minore di punti di collocazione e minor costo computazionale rispetto agli altri metodi. GPOPS−IIutilizza metodi di collocazione di quadratura gaussiane hp-adattivi per miglio- rare la precisione dei risultati attraverso la stima degli errori. Un metodo hp-adattivo è un metodo ibrido che varia sia il numero di intervalli della griglia (mesh) di discretizzazio- ne h (influisce sulla reticolazione della griglia) che il grado del polinomio approssimante ciascun intervallo della griglia p (definisce l’ordine dei polinomi utilizzati per appros- simare gli elementi della griglia) in modo da ottenere la precisione desiderata. In un metodo hp-adattivo è possibile sfruttare la convergenza esponenziale dei metodi globa- li di quadratura gaussiana nelle regioni in cui la soluzione è liscia, introducendo punti griglia solo in prossimità di discontinuità potenziali, o nelle regioni in cui la soluzione cambia rapidamente. Questi metodi di collocazione sono stati sviluppati per ridurre in maniera significativa le dimensioni dell’approssimazione discretizzata del problema e per ottenere maggiore efficienza di calcolo nella risoluzione dei problemi di NLP: all’inizio furono sviluppati come metodi ad elementi finiti per risolvere equazioni differenziali par- ziali [46], [47], [48] e [49]; negli ultimi anni i metodi hp-adattivi sono stati sviluppati per risolvere problemi di controllo ottimo [50] e [51]. GPOPS−II utilizza un perfezionamento della griglia hp-adattivo dove possono essere variati il grado del polinomio, il numero di intervalli della griglia e la larghezza di ciascun intervallo.

I problemi di programmazione non lineare sono spesso difficili da risolvere. Nonostante i rapidi progressi nelle loro performance, gli algoritmi più efficienti disponibili attualmente non sono ancora in grado di fornire garanzie di successo o di alte prestazioni per ogni categoria di applicazione possibile. GPOPS−II approssima le derivate delle funzioni del controllo ottimo, sia la prima che la seconda, e le rende disponibili a dei risolutori NLP (NLP solver) che risolvono il problema generale; il software mette a disposizione due possibili alternative:

• SNOPT (Sparse Nonlinear OPTimizer) [52], che utilizza un algoritmo di Programma- zione Quadratica Sequenziale (SQP) [53]. L’idea base dei metodi SQP è risolvere un problema NLP approssimando in maniera quadratica la funzione obiettivo e linear- mente i vincoli. SNOPT usa un approccio di ricerca lineare e, nelle sue impostazioni predefinite, impiega un’approssimazione quasi-Newton dell’hessiano.

IPOPT (Interior Point OPTimizer) [54], che implementa un metodo Interior-Point primale-duale [53]. i metodi Interior-Point (o metodi barriera) rappresentano una classe di algoritmi per la risoluzione di problemi di ottimizzazione convessa15_(non) 14_{I moltiplicatori di Karush–Kuhn–Tucker sono una generalizzazione dei moltiplicatori di La-}

grange per la risoluzione di un problema di programmazione non lineare, dove il problema sono presenti anche vincoli di disuguaglianza

15_{I problemi di programmazione convessa sono problemi di minimo in cui la funzione obiettivo}

lineare. Questi metodi si sono ispirati agli algoritmi di Karmarkar sviluppati da Na- rendra Karmarkar nel 1984 per la programmazione lineare. L’elemento di base del metodo consiste in una funzione barriera usata per codificare l’insieme conves- so. Contrariamente al metodo del simplesso, questo raggiunge la soluzione ottima attraversando l’interno della regione di ammissibilità.

Ricapitolando, la risoluzioni di problemi di controllo ottimo con GPOPS−II : • comincia con la definizione del problema di controllo tempo-continuo;

• utilizza il metodo di quadratura gaussiana con punti di collocazione Legendre- Gauss-Radau;

• fornisce un problema di programmazione non lineare al solver desiderato (SNOPT o IPOPT) per la risoluzione finale;

• utilizza un metodo hp-adattivo di collocazione per raggiungere la precisione desi- derata.

Grazie alla strategia seguita, questo software riesce a garantire una convergenza espo- nenziale, introduce punti griglia vicino le discontinuità o dove la soluzione cambia rapi- damente, riduce il numero di punti di collocazione nell’approssimazione discreta grazie all’utilizzo di metodi hp-adattivi, fornendo minor carico ai solver NLP ed ottenendo una convergenza più veloce.