OTTIMIZZAZIONE

OTTIMIZZAZIONE. -1. Generalità e sviluppo storico

Con o. s'intende l'operazione di ottenere il valore ottimo di una qualche grandezza.

Per la risoluzione dei problemi di o. occorre innanzitutto poter misurare la grandezza in oggetto, alterarla e giudicare se lo stato ottenuto è più vicino o più lontano dall'ottimo di quello precedente. In generale i problemi di o. si dividono in problemi di minimizzazione, in cui l'ottimo è il minimo della grandezza in oggetto, e in problemi di massimizzazione, in cui l'ottimo cercato coincide con un massimo.

In generale la teoria dell'o. tratta di problemi in cui si può agire su un sistema identificando i valori ("ottimizzatori") di certe variabili in modo da raggiungere il valore ottimo di un certo obbiettivo nel rispetto di alcuni vincoli. Si noti che possono esistere più ottimizzatori che conducono allo stesso valore ottimo.

Classici problemi di o. furono posti nell'antichità da Galileo (il problema della brachistocrona, risolto poi da Giovanni Bernoulli nel 1696) e formano una parte centrale dell'"analisi dei punti critici" coi lavori di Cauchy e di Lagrange. Una particolare branca di problemi di o., il calcolo delle variazioni, fu studiata da Lagrange e continuata da Eulero, Weierstrass e negli anni Trenta da tre scuole diverse, quella di Chicago, formatasi attorno a G.A. Blis, quella di Pisa, attorno a L. Tonelli e quella di Monaco, imperniata sui lavori di C. Caratheodory. Negli ultimi anni sono stati posti e risolti problemi di programmazione matematica, di programmazione dinamica, di controllo ottimo e di teoria dei giochi. Ciascuno di questi problemi assume una forma diversa a seconda che si debba identificare un ottimo assoluto o globale oppure un ottimo relativo o locale. Un'altra importante suddivisione di questi problemi si ha a seconda che essi siano deterministici o stocastici, ossia a seconda che le variabili in gioco siano note con certezza o descritte in forma probabilistica.

Nella quasi totalità dei problemi elencati non è possibile trovare una soluzione analitica e si deve ricorrere a tecniche numeriche. Questo fatto spiega il grande sviluppo degli studi nel campo dell'o. conseguente all'introduzione dei calcolatori elettronici.

2. Problemi deterministici. - A) Minimizzazione di una funzione. - Sia ϕ(x), ϕ: Rⁿ → R, ove Rⁿ è lo spazio euclideo n-dimensionale, si ricerchi, per es., un minimizzatore x* ∈ X ⊂ Rⁿ di ϕ(x) con X assegnato. La ricerca di un massimo si riconduce alla ricerca di un minimo di − ϕ(x). Il problema si scinde in due serie di sottoproblemi a seconda che si tratti di una ricerca di un minimizzatore locale oppure globale, che sono i due problemi fondamentali.

Problema di minimo locale (L). - Trovare x* ∈ X ⊂ Rⁿ tale che esista una sfera aperta di centro x* e raggio δ sufficientemente piccolo, S(x*) ≤ ϕ(x), per ogni x ∈ S(x*, δ) ⋂ X.

Problema di minimo globale (G). - Trovare x* ∈ X ⊂ Rⁿ tale che ϕ(x*) ≤ ϕ(x), per ogni x ∈ X.

Sia X = {x ∈ Rⁿ: h(x) = 0, g(x) ≥ 0} ove h: Rⁿ → R^m e g: Rⁿ → R^m. Se h(x) = g(x) = 0, X = Rⁿ, si ha il "problema di minimizzazione libera" (La₁); se g(x) = 0, si ha un problema con "vincoli di uguaglianza" (La₂); se h(x) = o, si ha un problema con ("vincoli di disuguaglianza" (La₃); nel caso generale se h(x) ≠ 0, g(x) ≠ 0, si ha un problema con "vincoli misti" (La₄).

Per il problema L è possibile ottenere condizioni per l'esistenza di minimi. Per il problema G ciò è possibile solo in alcuni casi particolari, come, per es., quando la funzione ammette un solo minimo, che è il minimo globale, come è nel caso di una funzione convessa.

Nel caso del problema L presentiamo il classico risultato (teorema di Kuhn-Tucker) che nel caso particolare h(x) = 0 e g(x) = 0 assume le forme note nell'analisi classica (condizioni di Cauchy e teorema di Lagrange).

c_I) Condizione necessaria (del primo ordine). - Se x* ∈ X è un minimizzatore locale di ϕ(x) e se h(x) e g (x) ivi differenziabili soddisfano alla seguente condizione c₂) esistono i vettori I* ∈ R^m e u* ∈ R^m tali che

è la cosiddetta "funzione lagrangiana" e ???ℒ è il gradiente di ℒ rispetto a x.

c₂) Condizione di indipendenza lineare. - Se nel punto x⁰ i vettori, h_i(x), i = 1, ..., w; g_j(x), j = i, ..., m sono linearmente indipendenti, allora h(x) e g(x) soddisfano alla qualificazione dei vincoli in xo. La qualificazione dei vincoli assicura la non-degenerazione della funzione lagrangiana.

c₃) Condizione sufficiente (del secondo ordine). - Se esistono i vettori x* ∈ Rⁿ, I* ∈ R^m, u* ∈ R^m che soddisfano alla condizione c₁, le funzioni ϕ(x), h(x), g(x) sono C², le funzioni h(x) e g(x) soddisfano a c₂, e per ogni vettore non nullo y con 〈y, ???h*_j> = 0 (j = 1, ... w) oppure con 〈y, ???g*_j> ≥ 0 per ogni j per il quale u*_j > 0, oppure con 〈y, ???g*_j> ≥ 0 per ogni j per il quale g_j(x*_j) = u*_j = 0 si ha:

ove si è indicata con ???²ℒ la matrice hessiana della funzione lagrangiana calcolata rispetto a x.

Notiamo che solo in casi molto semplici le condizioni riportate permettono l'identificazione in forma analitica dei minimi. In generale si dovrà ricorrere a metodi numerici. Tali metodi numerici sono agevolati se invece di usare le condizioni lagrangiane si ricorre al metodo delle "funzioni di penalizzazione" introdotto da R. Courant.

Per il problema L a₂ si ha il seguente risultato:

c₄) Se ϕ(x) ed [h(x)]² sono semicontinue inferiormente in Rⁿ, ϕ(x) → + ∞ per ∥ x ∥ → + ∞, {K_n} è una successione di matrici con K_n → + ∞ per n → ∞ e {x_n} è la corrispondente successione di minimi delle funzioni

esiste una sottosuccessione }x′_n} ⊂ {x_n} tale che x′_n → x* per n → ∞, ove x* è il minimo di ϕ(x) in X = X¹.

Varie generalizzazioni del risultato c₄) sono state proposte per risolvere il problema La₃: i "metodi di penalizzazione esterna e interna" (A. V. Fiacco-G. P. McCormick), il "metodo dei centri" (Huard) e il "metodo delle troncazioni" (Fiacco e McCormick).

B) Minimizzazione di un funzionale. - Si propone il problema della minimizzazione o massimizzazione del funzionale

rispetto alle funzioni x(t), con opportune ipotesi su ϕ e x ed eventualmente ulteriori vincoli. Questo problema forma l'oggetto del calcolo delle variazioni.

C) Minimizzazione di un Funzionale con vincoli differenziali. (Teoria del controllo ottimo). - Si ricerchi il minimo del funzionale

col vincolo espresso dalla seguente equazione differenziale ordinaria:

Per la soluzione di questo problema esiste il seguente metodo basato sul cosiddetto "principio di massimo" di L. S. Pontrjagin.

Si consideri la seguente funzione hamiltoniana:

Si hanno i risultati seguenti.

C₁) Se x*(t) ed u*(t) sono le soluzioni del problema di minimo, allora sono soddisfatte le seguenti condizioni del primo ordine espresse dalle seguenti equazioni alle derivate parziali:

con le seguenti condizioni al contorno:

C₂) Se x*(t) e u*(t) soddisfano le condizioni c₁ e inoltre la matrice

è definita positiva lungo la traiettoria

allora u*(t) è il controllo ottimo cercato e x*(t) la corrispondente soluzione ottima.

Il problema presentato ammette notevoli variazioni quando al posto dell'equazione differenziale ordinaria si considerano equazioni con ritardi, equazioni funzionali, equazioni alle differenze finite ed equazioni alle derivate parziali. Nel caso delle equazioni alle derivate parziali l'intero problema muta profondamente la sua struttura e tecnica risolutiva (J. Lions).

Il problema ammette oltre al vincolo differenziale altri vincoli sia sul controllo u sia sul vettore x.

Nel caso di problemi discreti in certe situazioni è utile formulare il problema nella schematizzazione della programmazione dinamica.

D) Teoria dei giochi matriciali. - E un problema di o. in. cui nella sua forma più tipica (gioco competitivo) due o più "giocatori" competono tra di loro se il gioco ha "somma zero", ossia il totale delle somme guadagnabili è costante e ha in particolare valore zero e viene divisa fra i giocatori. In questo caso esiste una strategia ottima per ciascun giocatore che nel caso particolare di due giocatori massimizza il minimo guadagno del giocatore e simultaneamente minimizza il massimo guadagno dell'avversario. Se X è l'insieme delle strategie del primo giocatore, Y quello del secondo e K(x, y) la funzione guadagno del gioco occorre risolvere il seguente problema d'identificare x ∈ X ed y ∈ Y tali che

Situazioni e teorie più generali si hanno per n giocatori e/o per giochi a somma non nulla.

E) Teoria dei giochi differenziali. - Problema analogo al precedente in cui i giocatori agiscono in un contesto dinamico, ossia devono scegliere funzioni-strategia. È una generalizzazione a una situazione competitiva della teoria del controllo ottimo.

3. Problemi stocastici. - Tutti i problemi elencati nel § 2 in contesto deterministico hanno la loro controparte stocastica. Esistono pertanto versioni probabilistiche di tutti i problemi citati, dalla minimizzazione di funzioni ai giochi differenziali stocastici.

4. Algoritmi numerici. - Gli aspetti numerici della soluzione dei vari problemi elencati variano drasticamente a secondo che si debba identificare un minimizzatore locale o uno globale e a seconda che si tratti di un problema libero o vincolato.

Nel caso del problema A) si possono seguire metodi indiretti (basati sulla soluzione numerica del sistema di equazioni che definiscono le condizioni del primo ordine) o meglio metodi iterativi diretti che, data una condizione iniziale x⁰ ∈ .Rⁿ, costruiscono una successione {xⁿ} convergente a un minimizzatore locale x*, mediante la regola x^k+1 = x^k + α_kp^k dove α_k e p^k indicano rispettivamente il "passo" e la "direzione " dell'iterazione k. Scegliendo opportunamente il passo α_k si garantisce che la successione {xⁿ} è "di discesa".

I vari metodi differiscono sulla scelta della direzione. Per es. nel classico metodo del gradiente

metodi recenti sono quelli "a metrica variabile" e "a direzioni coniugate" che presentano una velocità di convergenza anche d'ordine 2.

Esistono metodi che non richiedono il calcolo del gradiente della funzione pur conservando alta velocità di convergenza e metodi basati su ricerche casuali.

L'analogo problema della minimizzazione globale richiede o l'analisi sequenziale di tutti i minimi della funzione o la costruzione di un metodo di discesa globale che garantisca il passaggio da un minimo x¹ a uno (se esiste) x² con ϕ(x²) 〈 ϕ(x¹).

Anche nei problemi di minimi vincolati non è utile utilizzare metodi indiretti. In genere sono aperte due strade: metodi che riducono il problema a una successione di minimizzazioni libere attraverso funzioni di penalizzazione e metodi che fanno uso determinante di vincoli (metodi simplex-like). Il più tipico di questi metodi è il "metodo del simplesso" che si applica alla soluzione di problemi di programmazione lineare e analoghi metodi per la risoluzione di problemi di programmazione quadratica o in generale convessa (metodi del gradiente ridotto generalizzato, ecc.).

Un recente sviluppo in questo campo è costituito dai metodi di programmazione lineare funzionale in cui classi di problemi di o. possono essere ricondotti alla soluzione di famiglie di problemi di programmazione lineare.

Analoghe considerazioni si applicano alla soluzione numerica di problemi di controllo ottimo.

Bibl.: D.J. Wilde, C.S. Beightler, Foundations of optimization, Englewood Cliffs, N.J., 1967; A.V. Fiacco, G.P. McDormick, Non-linear programming, New York 1968; J. Céa, Optimisation: théorie et algoritmes, Parigi 1971; Minimization algorithms: mathematical theory and computer results, a cura di G.P. Szegö, New York 1972; D.G. Luenberger, Introduction to linear and non-linear programming, Reading, Mass., 1973; M.R. Hestenes, Optimization theory, New York 1975.