PROGRAMMAZIONE NON LINEARE

PROGRAMMAZIONE NON LINEARE

(App. IV, III, p. 70)

Sia nel campo metodologico, sia in quello computazionale, si sono registrati negli ultimi tempi notevoli progressi. Ci si limiterà qui a trattare, con la necessaria concisione, i seguenti argomenti: 1) risultati teorici: programmazione quadratica e problemi lineari di complementarità, dualità, analisi di stabilità e sensitività; 2) risultati computazionali: modifiche alle procedure newtoniane e quasi-newtoniane, procedure di regioni fiduciarie.

Diversi altri argomenti meriterebbero, per la loro importanza, di essere inclusi nella trattazione, quali gli sviluppi dei metodi conici e tensoriali di ottimizzazione, dei subgradienti generalizzati e, nell'ambito delle procedure computazionali, quelle che si rifanno al calcolo parallelo e all'uso di processori vettoriali. Questi campi di ricerca, tuttavia, sono ancora oggetto di sperimentazione e non sono ancora così ben definiti come quelli che vengono qui presi in considerazione.

Da un punto di vista generale, si può dire che nella p.n.l. ferve una vasta e intensa attività di ricerca, anche se forse è lecito lamentare la mancanza di un'impostazione sistematica, di una teoria generale. Al momento attuale, l'unico elemento comune che caratterizza impostazioni e problematiche piuttosto eterogenee sembra essere costituito dal teorema di Kuhn-Tucker con le sue derivazioni.

Programmazione quadratica e problemi lineari di complementarità. - Si consideri una funzione obiettivo quadratica e dei vincoli lineari di diseguaglianza,

(v. App. IV, iii, p. 70), problema che qui viene richiamato per illustrarne altri aspetti.

Introducendo i vettori di moltiplicatori u e y, si forma la funzione di Lagrange del problema:

Differenziando rispetto a x, ponendo il gradiente uguale a zero e ricordando le condizioni di Kuhn-Tucker si ottiene il seguente sistema:

Le soluzioni del problema [3] sono i punti di Kuhn-Tucker del problema originario, che potranno essere punti di massimo, punti di minimo o punti di sella, a seconda delle proprietà delle matrici B e C. Occorre osservare, inoltre, che se B non è una matrice simmetrica, la [3] non è più riconducibile a un problema di programmazione quadratica. Considerato autonomamente, è detto problema lineare di complementarità e, ovviamente, a seconda dei casi, può ammettere nessuna, una o più soluzioni. Generalmente viene espresso nella seguente forma più compatta:

Questa formulazione può essere generalizzata agevolmente a operatori non lineari. Essa permette di esprimere molti problemi delle scienze economiche e statistiche, d'ingegneria e di fisica in modo uniforme. A titolo di esempio si possono citare i problemi di equilibrio di un'economia o di un mercato, la meccanica strutturale, i problemi di trasporto e quelli di arresto ottimale. Anche una vasta gamma di problemi appartenenti alla sfera dell'ottimizzazione e del calcolo numerico può essere ricondotta al problema lineare di complementarità o alle sue generalizzazioni, come per es. certi problemi di programmazione lineare, di mini-max, di teoria dei giochi, come anche certe ineguaglianze variazionali.

Una procedura di base, che garantisce la determinazione di una soluzione (o l'indicazione che non esiste soluzione) del problema [4] se la matrice M è copositiva-più, è quella detta di Lemke. Una matrice è detta copositiva-più, se essa è copositiva, cioè se y^TMy≠0 per ogni vettore y a componenti non negative e se, inoltre, nel caso in cui y^TMy = 0, allora y^T(M + M^T) = 0. Questa classe rappresenta una leggera restrizione della classe delle matrici copositive, la quale a sua volta contiene quale sottoinsieme la classe delle matrici positive semidefinite.

Di maggiore interesse sono però i risultati ottenuti da O. L. Mangasarian, Cottle e Pang dal 1976 in poi. Questi autori hanno dimostrato (nella formulazione di Mangasarian) che se il problema [4] ha una soluzione non degenere (nell'equazione complementare nessun prodotto scalare ha i due fattori uguali a zero), allora esistono matrici Z₁, Z₂ ε Z e vettori r, s, c≥+0 tali che:

L'insieme delle matrici Z è costituito da tutte le matrici quadrate con elementi non positivi fuori della diagonale principale.

La soluzione del problema lineare di complementarità è data allora dalla soluzione del seguente programma lineare:

Questo risultato di grande importanza teorica non è di agevole applicazione computazionale, essendo tutt'altro che facile individuare le matrici e i vettori che soddisfano le condizioni [5]. Tuttavia, per molte classi di problemi tali strutture sono identificabili; inoltre l'importanza di questo sviluppo risiede nella possibilità di ricondurre problemi di p.n.l. a problemi lineari, risolvibili in modo efficiente anche in presenza di molte variabili e di numerosi vincoli.

Dualità. - La teoria della dualità riguarda la formulazione di condizioni di ottimalità utilizzando variabili duali, indicate anche come moltiplicatori di Lagrange generalizzati. Le variabili duali, a certe condizioni, costituiscono anch'esse le soluzioni di problemi di ottimizzazione. Per es., se il problema originario, detto primale, soddisfa delle condizioni di regolarità (precisate in App. IV, iii, p. 70), ed è un problema convesso (cioè un problema consistente nella minimizzazione di una funzione obiettivo convessa in un insieme definito dai vincoli che è convesso), allora è possibile ottenere dalle variabili duali la soluzione ottima del problema primale.

Il risultato è interessante perché in molti casi la risoluzione del problema duale è più facile di quella del primale. La dualità viene ampiamente sfruttata in problemi di programmazione lineare e quadratica, anche per superare certe difficoltà computazionali, legate per es. alla degenerazione. Se il problema primale non è convesso, tuttavia, la dualità, in linea generale, non porta a problemi equivalenti. Un approccio per affrontare questa situazione è costituito dalla convessificazione del problema primale, la quale non è altro che un rilassamento dello stesso; di qui la denominazione di rilassamento lagrangiano. Sono stati fatti diversi tentativi di usare quest'approccio a scopo computazionale, ma i risultati non sono sufficientemente generali per essere operativi per ampie classi di problemi.

Analisi di stabilità e sensibilità. - Raramente, nelle applicazioni pratiche, il problema da minimizzare è noto con precisione in tutti i suoi particolari. Spesso è più opportuno considerarlo come membro di una classe di problemi perturbati. Si consideri:

dove le componenti del vettore ϑ(x) possono assumere valori qualsiasi in intervalli dati. I valori effettivi di queste componenti non sono noti, ed essi non sono neanche caratterizzati da una distribuzione statistica; altrimenti si tratterebbe di un problema di ottimizzazione stocastica. Tale problema può essere efficacemente affrontato in virtù di alcuni importanti risultati riguardanti le applicazioni da punto a insieme e si possono indicare per le diverse perturbazioni di ϑ(x) i limiti entro i quali la soluzione del problema [7] resta ottima, se è tale per ϑ(x) = 0. Inoltre è possibile valutare la stabilità della soluzione nei riguardi di mutamenti in qualsiasi elemento del problema.

È ovvia l'importanza di poter valutare, data una soluzione ottima del problema, in quale intorno essa rimane valida e, se qualche elemento subisce variazioni, in quale modo il cambiamento incida sulla struttura e sul valore della soluzione ottima.

La teoria, associabile in massima parte con i risultati conseguiti da A.V. Fiacco e colleghi, sviluppa queste caratterizzazioni sulla base del teorema di Kuhn-Tucker e della teoria della dualità; i moltiplicatori di Lagrange generalizzati forniscono a tale riguardo importanti elementi conoscitivi. In tempi più recenti, Mangasarian ha ottenuto risultati più generali, non legati né alle condizioni di regolarità dei vincoli, né alla convessità. Essi scaturiscono dalle proprietà dei problemi lineari di complementarità e si fondano sul fatto che, in un intorno sufficientemente piccolo di un punto di ottimo, la funzione obiettivo non lineare può essere approssimata, per il teorema di Taylor, da una quadratica e i vincoli da funzioni lineari. In tale intorno è quindi possibile utilizzare la teoria dei problemi lineari di complementarità la quale a sua volta, come detto sopra, è riconducibile, sia pure con qualche difficoltà, alla teoria della programmazione lineare. In particolare, i risultati riguardanti la stabilità dei problemi lineari e la loro analisi di sensitività sono ben noti e agevolmente interpretabili. Infine, i diversi approcci usati, che hanno permesso di ottenere risultati nuovi e importanti, hanno interagito coi problemi di origine. Così, la programmazione lineare ha beneficiato di alcuni concetti emersi da specializzazioni dei risultati conseguiti da Fiacco sulla stabilità e viceversa.

Modifiche alle procedure newtoniane e quasi-newtoniane. - I problemi non lineari vengono risolti in pratica, come si è accennato sopra, mediante un'approssimazione quadratica della funzione obiettivo e un'approssimazione lineare dei vincoli. Se su questo problema approssimato viene definita una funzione lagrangiana, si ottiene un problema non vincolato che può essere risolto mediante iterazioni basate sul gradiente. Gli aggiornamenti delle approssimazioni possono essere effettuati dopo ogni iterazione o dopo aver raggiunto un punto di ottimo dell'approssimazione data, supposto che tale punto esista. Nella prima di queste strategie, che è stata la più seguita nel decennio precedente, a ogni iterazione il punto x ricavato viene utilizzato per operare un aggiornamento della funzione lagrangiana e, quindi, del gradiente per eseguire un nuovo passo.

In quest'ultimo decennio, invece, si è gradualmente imposta la procedura alternativa di mantenere l'approssimazione sino al raggiungimento di un punto di ottimalità del problema approssimato, risolvendo a ogni iterazione un problema di programmazione quadratica. I risultati sono migliorati notevolmente, sia che venga utilizzata la matrice hessiana calcolata nel punto d'iterazione, sia che venga utilizzata un'approssimazione della stessa, costruita combinando linearmente matrici di rango uno o due e detta procedura di aggiornamento BFGS (iniziali degli autori Broyden, Fletcher, Goldfarb e Shanno). In quest'ultimo caso le iterazioni assomigliano a quelle della regula falsi e la procedura viene qualificata come quasi-newtoniana.

Due aspetti ancora non risolti soddisfacentemente riguardano la ricerca lineare del passo e la procedura dell'insieme attivo per determinare i vincoli che sono effettivamente operanti in un punto d'iterazione. La prima procedura determina il passo nella direzione di diminuzione di una funzione, postulando un problema di minimizzazione. Infatti dalla soluzione del problema quadratico si ottiene generalmente non il nuovo punto d'iterazione, ma una direzione lungo la quale occorre muoversi per conseguire una diminuzione della funzione obiettivo. La determinazione dell'ampiezza dello spostamento viene eseguita mediante la ricerca lineare del passo. La seconda procedura considera quali vincoli valgano come eguaglianze a un punto d'iterazione per preservarli come ''insieme attivo'' sino al successivo punto d'iterazione. Se i vincoli non sono lineari, tale procedura può comportare difficoltà rilevanti.

Procedure di regioni fiduciarie. - Un altro filone di ricerca riguarda la definizione di insiemi fiduciari. Invece di affidarsi a una ricerca lineare del passo per conseguire una riduzione della funzione obiettivo, in quest'approccio si preferisce definire un vincolo aggiuntivo, in genere di forma ipersferica, che definisce appunto una regione fiduciaria, entro la quale l'approssimazione operata è sufficientemente buona. Infatti, se la regione fiduciaria è abbastanza piccola, lo sviluppo in serie di Taylor della funzione obiettivo e dei vincoli sarà relativamente preciso. In quest'ambito, quindi, o viene individuato un punto di minimo all'interno della regione per il problema approssimato, punto che è di minimo locale anche per il problema originale, oppure la procedura identifica un punto sulla frontiera della regione fiduciaria. In quest'ultimo caso si assume il punto così trovato per effettuare una nuova iterazione, se sono soddisfatte certe condizioni, e si modifica la regione fiduciaria. Qualora le condizioni non fossero soddisfatte, si ripeterebbe l'iterazione dopo avere ristretto la regione fiduciaria. L'applicabilità del metodo è alquanto limitata, perché è necessario che i vincoli siano definiti come diseguaglianze, mentre per molte procedure è più agevole trattare vincoli di eguaglianza.

Possibili soluzioni a queste difficoltà nelle procedure computazionali potrebbere risultare dall'uso di algoritmi che sfruttino il problema lineare di complementarità. Esso, infatti, può essere applicato in un contesto di approssimazioni quadratiche e lineari dei vincoli, come descritto sopra, se la regione fiduciaria viene definita mediante diseguaglianze lineari, diseguaglianze che sono gestite agevolmente. Questo procedimento potrebbe costituire, in certi casi, un modo efficiente per superare le difficoltà che si possono incontrare nel metodo dell'insieme attivo e nella ricerca lineare del passo.

Bibl.: Mathematics of the decision sciences, part 1, a cura di G.B. Dantzig e A.F. Veinott Jr., Providence 1968; O.L. Mangasarian, Simplified characterizations of linear complementary problems solvable as linear programs, in Math. of. O.R., 4 (1979); Id., Locally unique solutions of quadratic programs, linear and nonlinear complementary problems, in Mathematical Programming, 19 (1980); Mathematical programming: the state of the art, a cura di A. Bachem, M. Grötschel e B. Korte, Vienna 1983; A.V. Fiacco, Introduction to sensitivity and stability analysis in nonlinear programming, San Diego 1983; P.E. Gill, W. Murray, M.H. Wright, Practical optimization, ivi 1983; Numerical optimization, a cura di P.T. Boggs, R.H. Byrd e B. Schnabel, Filadelfia 1985; K.G. Murty, Linear complementarity, linear and nonlinear programming, Berlino 1988.