PROGRAMMAZIONE NON LINEARE

PROGRAMMAZIONE NON LINEARE

. Il termine "p. matematica" indica l'analisi dei problemi del tipo: trovare il massimo (o il minimo) di una "funzione obiettivo" quando le variabili sono soggette a vincoli costituiti da uguaglianze e da disequazioni. Quando la funzione obiettivo e i vincoli sono lineari, si parla di p. lineare; tutti gli altri casi rientrano nella p. non lineare.

La p. non l. rappresenta già oggi un importante strumento nel campo degli studi economici e della ricerca operativa e anche in taluni settori della fisica. È facile prevedere che in futuro la sua sfera di applicazione si amplierà considerevolmente, nella misura in cui aumenterà l'efficacia dei suoi metodi.

La vastissima gamma di problemi profondamente diversi per struttura e complessità che rientrano nella p. non l. spiega come non sia possibile, almeno allo stato attuale, parlare di una teoria completa o anche solo di un'impostazione sistematica. Le ricerche si sviluppano prevalentemente secondo approcci diversificati, tendenti a individuare gli algoritmi più efficienti per risolvere singoli problemi e classi più o meno ristrette di problemi.

Gli sviluppi teorici e pratici della p. non l. sono imperniati sul teorema di Kuhn-Tucker, che consente in sostanza di generalizzare il classico metodo dei moltiplicatori di Lagrange alla determinazione di massimi e minimi condizionati a diseguaglianze. Il teorema può essere formulato come segue.

Data una funzione f(x), con x vettore reale a n componenti, e m funzioni f_j(x), se esiste un vettore x≥ 0 tale che si abbia: f_j(x) 〈 0 (j = 1, ..., m), allora condizione necessaria perché nell'insieme S definito dalle condizioni

la funzione f(x) abbia un minimo nel punto x = x⁰, è che esista un vettore u⁰ a m componenti tale che si abbia

per ogni x ≥ 0 e per ogni u ≥ 0, dove la funzione di n + m variabili Φ(x, u) è così definita:

In altri termini, il punto (x⁰, u⁰) è un "punto-sella" della funzione Φ.

Il teorema copre tutti i problemi che rientrano nella p. non l.; infatti, con passaggi ovvi si può sempre trasformare, per es., un problema di massimo in un problema di minimo (basta moltiplicare per − 1 la funzione obiettivo), invertire il segno delle disuguaglianze, sostituire un'equazione con due diseguaglianze e rimpiazzare variabili libere con altre soggette alla condizione di non-negatività.

Il teorema di Kuhn-Tucker assume però valore operativo solo se le funzioni f(x) e f_j(x) sono differenziabili e se l'insieme S definito dai vincoli [1] soddisfa una "condizione di regolarità" che può essere formulata come segue.

Sia −x un vettore arbitrario appartenente alla frontiera di S. Indichiamo con J(−x) l'insieme dei valori dell'indice j tali che f_j(−x) = 0, e con I(−x) l'insieme dei valori dell'indice i tali che ù₂ = 0, ù_i (i = 1, ..., n) essendo le componenti del vettore −x. Con queste definizioni la condizione di regolarità può essere enunciata nei seguenti termini: per ogni −x appartenente alla frontiera di S, a qualsiasi vettore X di componenti X₁, ..., X_n che verifica le diseguaglianze lineari omogenee

(dove f_j(−x) è il vettore-riga la cui componente h-esima è la derivata parziale ∂f_j/∂x_h, calcolata nel punto −x) corrisponde un arco differenziabile x = x(θ), 0 ≤ θ ≤ 1, contenuto in S con x(0) = −x, e un numero positivo λ tale che [dx/dθ] = λX, in cui la derivata s'intende calcolata nel punto −x.

In tali ipotesi, il teorema di Kuhn-Tucker può enunciarsi come segue: condizione necessaria perché il vettore x1⁰ di componenti x1⁰, ..., xn⁰, appartenente all'insieme S, definito dai vincoli [1] sia minimante di f in detto insieme è che esista un vettore u di componenti u₁, ..., u_m tali che risultino verificate le seguenti relazioni:

dove le funzioni ∂f/∂x_i, ∂f_j/∂x_i e f_j s'intendono calcolate nel punto x = x⁰.

È importante osservare che i moltiplicatori lagrangiani u_j hanno un significato preciso. Difatti, se ai vincoli fj′(x) ≤ 0 si sostituiscono i vincoli f_j(x) ≤ a_j e se s'indica con ϕ(a) il minimo di f(x) sotto tali condizioni e sotto la condizione di non-negatività di x, si ha:

Pertanto, in vicinanza del punto a = 0, le u_j forniscono una misura approssimata delle conseguenze di una piccola modificazione dei vincoli sul minimo valore della funzione obiettivo. In particolare, se u_j > 0, il vincolo f_j(x) ≤ 0 risulta effettivo, in quanto incide sul minimo, se invece u_j = 0, il vincolo potrebbe essere omesso senza alterare il risultato.

Per completare l'esposizione del teorema di Kuhn-Tucker è opportuno precisare che la condizione di regolarità sopra enunciata è soddisfatta, per es., se le f_j sono funzioni lineari. Non è soddisfatta, invece, per citare un contro-esempio, se f₁ = − (i − x₁)³ + x₂, nel punto x₁ = 1, x₂ = 0, per X₁ = 1, X₂ = 0. Infatti, se si considera, per es., il problema: minimizzare la funzione f(x) = − x₁, sotto i vincoli

si constata che la soluzione: x₁ = 1, x₂ = o non soddisfa le condizioni di Kuhn-Tucker.

Per quanto riguarda le sue applicazioni, il teorema di Kuhn-Tucker è di particolare utilità quando l'insieme S è convesso (ossia se, per due vettori arbitrari x¹, x² ∈ S si ha, per ogni t, 0 ≤ t ≤ 1: tx¹ + (1 − t)x² ∈ S) e la funzione obiettivo è convessa in tale insieme; cioè quando sussiste la disuguaglianza:

I problemi nei quali questi requisiti sono soddisfatti costituiscono la cosiddetta "p. convessa" la quale occupa un posto di rilievo nella p. non l., in quanto le condizioni di Kuhn-Tucker sono non solo necessarie, ma anche sufficienti. Pertanto ogni soluzione del sistema [4] fornisce un minimo globale di f in S.

I problemi più semplici di p. convessa non l. sono quelli detti di "p. quadratica" in cui la funzione obiettivo è costituita dalla somma di una funzione lineare e di una forma quadratica semidefinita positiva: f(x) = a^Tx + x^TBx (con a^T vettore-riga a n componenti e B matrice simmetrica di ordine n semidefinita positiva) e i vincoli sono lineari: Cx − d ≥ 0, con C matrice m × n e d vettore a m componenti. Indicando le componenti di a, B, c e d rispettivamente con a_i, b_ij, c_ji, d_j e dopo avere introdotto le variabili addizionali y_i e v_j, al fine di trasformare le disuguaglianze in equazioni, si ottiene dalle condizioni di partenza e dalle condizioni [4] il seguente sistema:

Il vettore x risultante dalla soluzione di questo sistema è minimante della funzione obiettivo sotto i vincoli dati.

Sono stati ideati vari algoritmi iterativi che consentono di risolvere il sistema [5]. Il più semplice, anche se probabilmente non il più rapido, proposto da H. M. Markowitz e Ph. Wolfe, consiste in sostanza nella ripetuta applicazione del metodo del simplesso cosiddetto della prima fase, con l'avvertenza di tenere conto delle condizioni non lineari x_iy_i = 0 e u_jv_j = 0, evitando d'introdurre nella base quelle variabili che violerebbero tali condizioni.

Si consideri, a titolo di esempio, il seguente problema: minimizzare f(x) = − 8x₁ − 10x₂ + 3x²₁ + 3x₁x₂ + x²₂, sotto i vincoli

Poiché la matrice

è semidefinita positiva (anzi, definita positiva), si tratta di un problema di programmazione quadratica.

Il sistema [5] si scrive come segue:

Seguendo il metodo di Markowitz-Wolfe, si considera dapprima il sub-problema:

Anche senza impiegare il metodo del simplesso, si trova in questo caso immediatamente una soluzione-base accettabile che verrà usata in seguito. Tale soluzione è: x₁ = x₂ = 0, v₁ = 5, v₂ = 7.

Introducendo le variabili artificiali z₁ e z₂ che dovranno risultare nulle nella soluzione finale, si passa ora al problema di programmazione lineare: minimizzare g (z) = z₁ + z₂, sotto i vincoli

di cui una soluzione-base accettabile è: v₁ = 5, v₂ = 7, z₁ = 8, z₂ = 10, con tutte le altre variabili nulle. Nel risolvere tale problema si può procedere secondo il metodo del simplesso con l'unica modifica di non introdurre nella base nessuna variabile la cui "complementare" è variabile-base, dove per variabili complementari s'intendono le coppie (x_i, y_i) e (u_j, v_j). Con questo metodo si perviene rapidamente alla soluzione finale, che è data da: x₁ = 59/122, x₂ = 159/122, u₂ = 145/122, v₁ = 15/122, y₂ = y₂ = u₁ = v₂ = z₁ = z₂ = 0

Sostituendo nella funzione f(x) a x₁ e x₂ i valori trovati, si ottiene: min f (x) = − 12,61.

La p. quadratica occupa un posto importante nella p. non l., perché può fornire in taluni casi una soluzione approssimata a problemi più complessi, se si sostituiscono alla funzione obiettivo i primi due termini del suo sviluppo in serie di Taylor (a condizione che la forma quadratica risultante sia semidefinita positiva) e ai vincoli i primi termini dello stesso sviluppo.

Se la forma quadratica che figura nella funzione obiettivo non è semidefinita positiva il problema è più complicato, perché allora le condizioni di Kuhn-Tucker non sono sufficienti.

Si consideri, a titolo di esempio, lo stesso problema di prima, con la funzione obiettivo così modificata: f(x) = − 8x₁ − 10x₂ + x²₁ + 3x₁x₂ + x²₂. La matrice B essendo ora

non è semidefinita positiva. Soltanto la prima equazione del sistema [6] è modificata: il coefficiente di x₁ è ora 2 invece di 6. Ma anziché una sola soluzione, adesso se ne hanno tre:

Alla prima soluzione corrisponde il minimo ricercato, la seconda rappresenta un punto-sella e la terza un minimo locale ma non globale di f.

Per superare le difficoltà inerenti alla non-sufficienza delle condizioni di Kuhn-Tucker nella p. quadratica non convessa (nella quale, cioè, la forma quadratica non è semidefinita positiva), K. Ritter ha ideato un algoritmo iterativo efficiente che appare suscettibile anche di applicazioni a problemi più complicati. Il principio su cui si fonda tale algoritmo è il seguente: anzitutto viene individuato un minimo locale (ossia un punto che non soddisfa solo le condizioni di Kuhn-Tucker, ma anche altre condizioni supplementari, intese ad assicurare la convessità della funzione obiettivo negl'intorni del punto stesso) quindi, utilizzando le informazioni così ottenute si opera un "taglio", ossia si stabilisce una nuova disequazione lineare che non è soddisfatta dalla soluzione trovata, ma che dev'essere soddisfatta dal minimo globale. Si risolve poi il problema della ricerca di un minimo locale col nuovo vincolo aggiunto a quelli precedenti e così via, fino a giungere al minimo globale.

Illustriamo succintamente il metodo sulla scorta dell'esempio esposto. Si consideri il minimo locale:

Poiché per questa soluzione risulta v₁ = v₂ = 0, si utilizzano le equazioni

per esprimere x₁ e x₂ in funzione di v₁ e v₂:

Sostituendo queste espressioni nella funzione obiettivo, si ottiene:

Si prendono ora i termini lineari in v₁ e v₂ e si esamina il problema: minimizzare f sotto i vincoli

al variare di τ.

Si trova con facilità (considerando le condizioni di Kuhn-Tucker) che, per 0 ≤ τ ≤ 289/245, tale minimo corrisponde al punto v₁ = v₂ = 0, ossia corrisponde al minimo locale già individuato, mentre per τ = 289/245 il minimo si ottiene con v₁ = 0, v₂ = (49/17)τ, ed è uguale a:

D'altra parte, la soluzione minimante suddetta è accettabile, ossia compatibile con la condizione di non-negatività di x₁ e x₂, per τ ≥ 153/98. Poiché nella regione definita dalle condizioni:

la funzione obiettivo non può assumere valori minori di quello assunto nel punto accettabile della sua frontiera

ogni punto di minimo globale del problema originario deve necessariamente soddisfare la condizione:

Si torna quindi al problema originario con l'aggiunta di questa nuova condizione. Per inciso si può osservare che non è più necessario conservare il vecchio vincolo 2x₁ + 3x₂ ≤ 5, il quale è reso superfluo dal nuovo vincolo, che è più restrittivo. Il nuovo problema conduce rapidamente alla constatazione che la soluzione già individuata (x₁ = 2,5, x₂ = 0) è effettivamente minimante. Infatti, non si possono introdurre altri "tagli".

Per i problemi di p. non l. di tipo diverso e più complesso, in cui i vincoli in tutto o in parte non sono lineari e/o la funzione obiettivo non è lineare o quadratica, vanno segnalati in particolare due approcci che spesso si rivelano efficaci e che, pur basati su principi diversi, possono integrarsi a vicenda.

Col primo approccio si cerca di ottenere una successione di vettori x⁰, x¹, ..., tale che: f(x⁰) > f(x¹) ..., con x⁰, x¹, ... ∈ S, mediante transizioni del tipo: x^t+1 = x^t + d_ts^t, in cui le direzioni s^t dipendono dal gradiente della funzione obiettivo f calcolato nel punto xt e dalla frontiera dell'insieme S e del coefficiente d_t è scelto in modo tale che x^t+1 soddisfi le condizioni suddette e dia luogo a un apprezzabile decremento della funzione obiettivo. In talune versioni di questo metodo ci si serve dei vincoli per esprimere m variabili in funzione delle altre n − m, in analogia al metodo del simplesso della p. lineare. Tra gli studiosi che hanno contribuito agli sviluppi di questo approccio vanno segnalati Ph. Wolfe, R. Fletcher, G. Zoutendijk e J. Abadie.

L'altro approccio, legato ai nomi di C. W. Carroll, A. V. Fiacco e G. P. McCormick, D. Davies e altri, consiste nell'incorporare i vincoli nella funzione obiettivo mediante una "funzione-penalità", seguendo un procedimento sequenziale. Più precisamente, iniziando con una costante k > 0, da determinare, si risolve il problema di minimo non condizionato: minimizzare F(x, k) = f(x) + kG(x), dove G(x) è la funzione-penalità che è minima quando x ∈ S, ossia quando sono soddisfatti i vincoli del problema originario. Ci si serve del punto di minimo come partenza o per un nuovo problema. in cui il valore di k viene ridotto. Esempi di funzioni-penalità sono:

con v_j = 0 se f_j ≤ 0, v_j = 1 se f_j > 0, w_i = 0 se x_i ≥ 0, w_i = 1 se x_i 〈 0.

Bibl.: H. W. Kuhn, A. W. Tucker, Non-linear programming, in Proceedings of the second Berkeley Symposium on mathematics, statistics and probability, Berkeley 1950; K. J. Arrow, L. Hurwicz e H. Uzawa, Studies in linear and nonlinear programming, Stanford 1958; K. P. Künzi, W. Krelle, Nonlinear programming (a cura di J. Abadie), Amsterdam 1967; E. M. L. Beale, Mathematical programming in practice, Londra 1968; A.V. Fiacco, G. P. McCornick, Nonlinear programming: sequential unconstrained minimization technique, New York 1968; R.T. Rockafellar, Convex analysis, Princeton 1969; Autori vari, Integer and nonlinear programming (a cura di J. Abadie), Amsterdam 1970.