___________________________________________ 8 OTTIMIZZAZIONE NON LINEARE VINCOLATA (NON LINEAR PROGRAMMING, NLP) ___________________________________________

___________________________________________

8

OTTIMIZZAZIONE NON LINEARE VINCOLATA (NON LINEAR PROGRAMMING, NLP)

___________________________________________

8.1 Sostituzione diretta

8.2 Condizioni necessarie di estremalità locale

8.3 Ottimizzazione quadratica (Quadratic Programming, QP)

8.4 Metodi con funzione di penalità, metodi di barriera e metodo delle Lagrangiane aumentate

8.5 Successive Linear Programming (SLP) 8.6 Successive Quadratic Programming (SQP) 8.7 Metodo del gradiente ridotto generalizzato

8.8 Vantaggi e svantaggi rispettivi per i metodi NLP presentati 8.9 Software disponibile per NLP

8.10 Uso del software NLP

IL CAPITOLO 1 PRESENTA alcuni esempi di vincoli che si trovano nei problemi di ottimizzazione. I vincoli sono classificati come vincoli di disuguaglianza o vincoli di uguaglianza, lineari o non lineari. Il Capitolo 7 descrive il metodo del simplesso per risolvere problemi con funzioni obiettivo lineari e vincoli lineari. Questo capitolo tratta problemi più complessi, che coinvolgono la minimizzazione (o massimizzazione) di una funzione obiettivo non lineare soggetta a vincoli lineari o non lineari:

   

 

 

1 2

Minimizzare:

soggetta a: 1, 2, ..., 1, 2, ...,

T n

i i

j j

f x x x

h b i m

g c j r



 

 

x x

x x

(8.1)

I vincoli di disuguaglianza nel problema (8.1) possono essere trasformati in vincoli di uguaglianza, come spiegato nel paragrafo 8.4, quindi ci concentriamo prima sui problemi che coinvolgono solo vincoli di uguaglianza.

8.1 SOSTITUZIONE DIRETTA

Un metodo utile a trattare solo uno o due vincoli di uguaglianza lineari o non lineari consiste, quando possibile, nel ricavare un’espressione esplicita per una variabile ed eliminare tale variabile dalla formulazione del problema. Questo si fa per sostituzione diretta nella funzione obiettivo e nelle equazioni dei vincoli. In molti problemi, eliminare un vincolo di uguaglianza con manipolazioni algebriche è spesso vantaggioso rispetto a un approccio in cui viene mantenuto il vincolo e si adopera una procedura di ottimizzazione vincolata. Per esempio, supponiamo di dover minimizzare la seguente funzione obiettivo soggetta ad un unico vincolo di uguaglianza

  1² 2²

1 2

Minimizzare: 4 5 soggetta a: 2 3 6

f x x

x x

 

 

x (8.2)

Sia x₁ che x₂si possono eliminare facilmente. Risolvendo per x₁,

1 2

6 3 2 x  x

 (8.3)

possiamo sostituire x₁ nella funzione obiettivo ottenendo una nuova funzione obiettivo nella sola variabile x₂:

 2 14 2² 36 2 36

f x  x  x  (8.4)

Il vincolo del problema originale è stato ora eliminato, e f x è una funzione non vincolata con  2

un solo grado di libertà (una variabile indipendente). L’uso dei vincoli per eliminare le variabili è l’idea principale del metodo del gradiente ridotto generalizzato, come discusso nella sezione 8.7.

Possiamo ora minimizzare la funzione obiettivo (8.4), impostando la derivata prima uguale a zero, e risolvendo per il valore ottimale di x₂:

 2 *

2 2

2

28 36 0 1.286

df x x x

dx    

FIGURA 8.1

Rappresentazione grafica di una funzione di due variabili ridotta a funzione di una sola variabile per sostituzione diretta. Il minimo non vincolato si trova nel punto (0,0), al centro delle linee di livello.

Una volta ottenuto x , si ricava direttamente ^*₂ x dal vincolo nel problema (8.2): ₁^*

*

* 2

1

6 3 1.071 2

x   x 

L'interpretazione geometrica del problema precedente richiede la visualizzazione della funzione obiettivo come superficie di un paraboloide in uno spazio tridimensionale, come mostra la figura 8.1. La proiezione della curva di intersezione del paraboloide con il piano 2x₁3x₂ 6, che rappresenta il vincolo, sul piano x ₁ 0, che nello spazio tridimensionale rappresenta uno dei piani coordinati, è una parabola. Cercheremo quindi il minimo della parabola risultante. La procedura di eliminazione appena eseguita equivale quindi a proiettare la curva intersezione sul piano x ₁ 0. Detta curva si può equivalentemente proiettare sul piano x ₂ 0, eliminando per sostituzione la variabile x₂ anziché x₁. Domanda: si ottiene lo stesso risultato per x^*?

In problemi in cui ci sono n variabili ed m vincoli di uguaglianza, possiamo provare ad eliminare m variabili per sostituzione diretta. Se tutti i vincoli di uguaglianza si possono rimuovere, e non vi sono vincoli di disuguaglianza, la funzione obiettivo si può derivare rispetto a ciascuna delle rimanenti (n − m) variabili e porre le derivate uguali a zero. In alternativa, si può adoperare un codice numerico per l'ottimizzazione non vincolata ed ottenere x^*. Se la funzione obiettivo è convessa (come nell'esempio precedente) ed i vincoli formano una regione convessa, ogni punto stazionario sarà un minimo globale. Sfortunatamente, pochissimi sono i problemi nella pratica che assumono questa forma così semplice e consentono di eliminare tutti i vincoli di uguaglianza.

Pertanto, in questo capitolo discuteremo cinque importanti metodi per risolvere problemi di ottimizzazione nonlineare vincolata:

1. Soluzione analitica delle condizioni necessarie di ottimalità (par. 8.2) 2. Metodi di penalità e metodi di barriera (par. 8.4)

3. Successive Linear Programming, SLP (par. 8.5) 4. Successive Quadratic Programming, SQP (par. 8.6) 5. Metodo del gradiente generalizzato (par. 8.7)

Il primo di questi metodi è di solito praticabile solo per problemi piccoli con poche variabili, ma quando è applicabile può generare molte informazioni utili. Gli altri sono approcci di tipo numerico, che vanno programmati su di un elaboratore elettronico.

8.2 CONDIZIONI NECESSARIE DEL PRIMO ORDINE PER L'ESISTENZA DI UN ESTREMO LOCALE

Per introdurre l'argomento, consideriamo il seguente esempio.

__________________________________________________________________________

ESEMPIO 8.1 INTERPRETAZIONE GRAFICA DI UN PROBLEMA DI OTTIMIZZAZIONE VINCOLATA

 

 

1 2 1 2

2 2

1 2 1 2

Minimizzare: ,

soggetta a: , 1 0

f x x x x

h x x x x

 

   

Soluzione. Il problema è illustrato graficamente in figura E8.1a. La regione di ammissibilità è la circonferenza di raggio unitario. Le linee di livello della funzione obiettivo lineare sono rette parallele a quella riportata in figura. La linea di livello con il valore minimo che abbia un punto in comune con la circonferenza tocca la stessa nel punto x^*  0.707, 0.707 , che rappresenta il minimo globale. Il problema si può risolvere analiticamente come problema non vincolato, eliminando x₁ o x₂ facendo uso dell'equazione del vincolo.

Sussistono relazioni notevoli fra i gradienti di f e di h in x^*, se x^*è un minimo locale. I gradienti sono:

 

 

*

*

1 2

1,1

2 ,2 1.414, 1.414

f

h x x

 

    

x

x x

e sono mostrati in figura E8.1b. Il gradiente della funzione obiettivo,  x , è ortogonale ^f

 

al piano tangente al vincolo in x^*. In generale,  x è sempre ortogonale a questo piano ^h

 

tangente, quindi ^{ x e f}

 

 

hanno versi opposti. Ciò equivale a dire che i due vettori sono multipli l'uno dell'altro:

 

 

f h

 x    x (a)

dove   ^* 1 1.414 prende il nome di moltiplicatore di Lagrange per il vincolo h = 0.

FIGURA E8.1a

Circonferenza di ammissibilità con linea di livello della funzione obiettivo e vincolo

FIGURA E8.1b

Gradienti nel punto di ottimo e in un punto non di ottimo.

Le relazioni di cui all'equazione (a) debbono valere in qualsiasi punto di ottimo locale di qualsiasi problema di ottimizzazione con vincoli di uguaglianza che coinvolge funzioni sufficientemente regolari. Per vedere perché, consideriamo il punto non ottimale x¹ in figura E8.1b.  x non è ortogonale al piano tangente al vincolo in ^f

 

perciò la proiezione del gradiente deve essere nulla. Ciò naturalmente si verifica solo se

 

 x è ortogonale al piano tangente. f

__________________________________________________________________________

La relazione (a) nell'esempio 8.1 si può riscrivere come

 

 

f h

 x    x  (8.5)

dove  ^* 0.707. Introduciamo adesso una nuova funzione, ^L ^x, , detta funzione Lagrangiana:

 ^,    

L x   f x  h x (8.6)

L'equazione (8.5) diventa quindi

 , _ *, *_ 0

xL _

 x  _x  (8.7)

perciò il gradiente della funzione Lagrangiana rispetto ad x , valutato in





L'equazione (8.7), insieme con la condizione di ammissibilità

 

h x  (8.8)

costituiscono le condizioni necessarie del primo ordine per l'ottimalità. Lo scalare  prende il nome di moltiplicatore di Lagrange.

Uso delle condizioni necessarie per trovare l'ottimo

Le condizioni necessarie del primo ordine (8.7) ed (8.8) si possono usare per la ricerca di una soluzione ottima. Si assuma che x^* e  siano incognite. La funzione Lagrangiana per il problema ^* nell'esempio 8.1 è

 ^{, 1 2}





L x     x x x x 

Si pongono le derivate parziali prime di L rispetto ad x uguali a zero, per scrivere

1 1

1 2 0

L x

x

    

 (8.9)

2 2

1 2 0

L x

x

    

 (8.10)

La condizione di ammissibilità (8.8) è

2 2

1 2 1 0

x x   (8.11)

Le condizioni necessarie del primo ordine per questo problema, (8.9)(8.11), consistono in tre equazioni nelle tre incognite x x  . La loro risoluzione fornisce 1, ,2 

1 2

1 x x  2

 (8.12)

che mostra che in questo caso x₁ e x₂ sono uguali all'estremo. Sostituendo la (8.12) nella (8.11):

2 2

1 1

4 4 1

 

ovvero

2  2 1 (8.13)

pertanto

0.707

   e

1 2 0.707

x x   (8.14)

il segno meno corrisponde al minimo di f, il segno più corrisponde al massimo.

__________________________________________________________________________

ESEMPIO 8.2 USO DEI MOLTIPLICATORI DI LAGRANGE Consideriamo il problema introdotto nell'equazione (8.2):

  1² 2²

Minimizzare: f x 4x 5x (a)

  1 2

soggetta a: h x  0 2x 3x 6 (b)

Soluzione. Sia

 , 4 1² 5 2² 2 1 3 2 6

L x   x  x   x  x  (c)

Applichiamo le condizioni necessarie (8.9) − (8.11)

 

1 1

, 8 2 0

L x

x

 

   



x (d)

 

2 2

, 10 3 0

L x

x

 

   



x (e)

 

1 2

, 2 3 6 0

L x x

 

   



x (f)

Per sostituzione, x  ₁ 4 e x₂  3 10 perciò la (f) diventa

2 3 3 6 0

4 10

  

    

   

   

da cui infine

*

* 1

* 2

4.286 1.071 1.286 x

x

  





__________________________________________________________________________

8.2.1 Problemi contenenti solo vincoli di uguaglianza

Un problema generale di ottimizzazione non lineare (NLP) vincolata con soli vincoli di uguaglianza, con m vincoli ed n variabili, si può scrivere

 

 

Minimizzare:

soggetta a: _{j j}, 1,..., f

h b j m

x

x (8.15)

dove xx1,...,x_n è il vettore delle variabili decisionali, e ciascun valore b è una costante. _j Assumiamo che l'obiettivo f e le funzioni di vincolo h siano dotate di derivate parziali prime _j continue. In corrispondenza di ciascun vincolo h_j definiamo un moltiplicatore di Lagrange b_j _j e sia λ  1,...,_m il vettore di questi moltiplicatori. La funzione Lagrangiana per il problema è

     

1

, ^m _{j j j}

j

L f h b



 

    

x λ x x (8.16)

e le condizioni necessarie del primo ordine sono

1

0, 1,...,

m j

j

i i j i

L f h

i n

x x _ x

       

    ^(8.17)

  ^{, 1,...,}

j j

h x b j m (8.18)

Si noti che ci sono n + m equazioni nelle n + m incognite x e λ . Nel par. 8.6 descriveremo una importante classe di algoritmi NLP detti Successive Quadratic Programming, che risolvono le (8.17)−(8.18) con una variante del metodo di Newton.

Il problema (8.15) deve soddisfare certe condizioni, dette di qualifica dei vincoli, affinché le (8.17)−(8.18) siano applicabili. Un requisito (Luenberger, 1984) è che i gradienti dei vincoli di uguaglianza, valutati in x^*, siano linearmente indipendenti. A questo punto possiamo enunciare formalmente le condizioni necessarie del primo ordine.

Condizioni necessarie del primo ordine per un estremo

Sia x^*un minimo o un massimo locale per il problema (8.15), e si assuma che i gradienti dei vincoli ^hj

 









primo ordine (8.17)−(8.18).

Esempi che illustrano che cosa può accadere quando i gradienti dei vincoli sono linearmente dipendenti in x^* sono riportati da Luenberger (1984). È importante ricordare che tutti i massimi e minimi locali di un problema NLP soddisfano le condizioni necessarie del primo ordine se i gradienti dei vincoli sono linearmente indipendenti. Inoltre, poiché tali condizioni sono necessarie ma non sufficienti, una soluzione delle equazioni (8.17)−(8.18) non necessariamente rappresenta un minimo o un massimo. Può trattarsi infatti anche di un punto di flesso o di sella. Questo è esattamente ciò che accade nel caso non vincolato, dove non vi sono funzioni di vincolo h  . Nel _j 0 caso non vincolato le equazioni (8.17)−(8.18) si riducono a

 

f x 0

cioè la classica condizione di gradiente nullo (si veda par. 4.5). Per stabilire se un punto che soddisfa le condizioni necessarie del primo ordine sia o meno un minimo o un massimo, è necessario fare ricorso alle condizioni sufficienti del secondo ordine. Queste ultime sono discusse più avanti nel capitolo.

Moltiplicatori di Lagrange e sensitività

L'analisi di sensitività nella ottimizzazione non lineare (NLP) indica quanto una soluzione ottima cambia al cambiare dei dati del problema. I dati comprendono qualsiasi parametro presente nella funzione obiettivo o nelle equazioni dei vincoli. In particolare, i moltiplicatori di Lagrange λ ^* forniscono informazioni utili sull'influenza di variazioni nei secondi membri delle equazioni dei vincoli, in analogia con quanto accade nei problemi di programmazione lineare, che possono inquadrarsi come casi particolari di programmazione non lineare o NLP. Per illustrare l'applicazione dei moltiplicatori di Lagrange in ottimizzazione non lineare, consideriamo di nuovo l'esempio 8.1, in cui il secondo membro dell'equazione del vincolo, cioè il raggio della circonferenza del vincolo, viene definito come parametro b e perturbato.

 

 

1 2 1 2

2 2

1 2 1 2

Minimizzare: , soggetta a: ,

f x x x x

h x x x x b

 

  

La soluzione ottimale di questo problema è ora funzione del parametro b, e possiamo quindi denotarla come x b x b , e analogamente per il valore ottimale del moltiplicatore, 1   , 2  ^ ^{b . Le}

condizioni necessarie del primo ordine (8.9)−(8.11) si riscrivono in questo caso come 1 2  x1 0

1 2  x2 0

2 2

1 2

x x b la cui soluzione è (controllare!)

    ^{1 2}

* *

1 2

2 x b x b    b

    ^{1 2}

* b 2b ^

  

Queste formule restituiscono il risultato precedentemente ricavato per b = 1. Il valore della funzione obiettivo in corrispondenza del minimo, a volte chiamato valore ottimo della funzione, è

      ^{1 2}  ^{1 2}

* * *

1 2 2 2

2

V b x b x b     b   b La derivata del valore ottimo della funzione è

 2 ^{1 2 *} 

dV b b

db

    

cioè il negativo del valore del moltiplicatore di Lagrange nel punto di ottimo è dV db . Pertanto, se risolviamo il problema per uno specifico valore di b (per esempio b = 1) il valore ottimo della funzione per b prossimo a 1 può approssimarsi al primo ordine con la serie di Taylor

      

 

1 1 1

2 1 1

2

V b V b

b

   

   

Per vedere quanto siano utili i moltiplicatori di Lagrange, consideriamo il problema generale (8.15), con i secondi membri b_i

 

Minimizzare: f x

 

soggetta a: h_i x b_i, i1,...,m (8.19) Sia bb1,...,b_m il vettore dei termini noti, e V b il valore ottimale della funzione obiettivo. Se  

b è uno specifico vettore dei termini noti, e





 

j

j

V b

  

 b

b (8.20)

I vincoli con i massimi valori assoluti di  sono quelli per i quali il valore del secondo membro ha _j l'effetto maggiore sul valore ottimo della funzione, almeno nell'intorno di b . Per questa valutazione è importante adottare una formulazione adimensionale o normalizzata del problema, poiché le unità adottate per le variabili possono determinare valori numerici diversi per ordine di grandezza, il che può rivelarsi fuorviante.

8.2.2 Problemi contenenti solo vincoli di disuguaglianza

Le condizioni necessarie del primo ordine per problemi con vincoli di disuguaglianza sono dette condizioni di Kuhn−Tucker (o anche condizioni Karush−Kuhn−Tucker). Il concetto di cono aiuta a comprendere le condizioni di Kuhn Tucker (KTC). Dicesi cono un insieme R di punti tali che, se x appartiene ad R, anche x appartiene ad R per   . Un cono convesso è un cono che costituisce 0 un insieme convesso. Un esempio di cono convesso in due dimensioni è rappresentato in figura 8.2.

In due e tre dimensioni, la definizione di cono convesso coincide con il significato usuale del termine.

Dalle precedenti definizioni si può dimostrare che l'insieme di tutte le combinazioni lineari non negative di un insieme finito di vettori è un cono convesso, cioè che l'insieme

 1 1 2 2 _{m m}, _i 0, 1, ... , 

R x x x   x    x   i m

è un cono convesso. I vettori x x₁, ₂, ... ,x_m si dicono generatori del cono. Per esempio, il cono di figura 8.2 è generato dai vettori [2, 1] e [2, 4]. Perciò, qualsiasi vettore che può esprimersi come combinazione lineare non negativa di questi vettori giace nel cono. In figura 8.2 il vettore [4, 5] nel cono è dato da [4, 5] = 1×[2, 1] + 1×[2, 4].

Condizioni di Kuhn−Tucker: interpretazione geometrica

Le condizioni di Kuhn−Tucker sono basate su questo fatto: in corrispondenza di ogni ottimo vincolato, nessun piccolo cambiamento nelle variabili del problema può migliorare il valore della funzione obiettivo. Per illustrare questa affermazione, consideriamo il seguente problema NLP:

    ² ²

Minimizzare: f x  x2  y1

 

 

 

2 1

2 3

soggetta a: , 0

, 2

, 0

g x y y x

g x y x y

g x y y

   

  

 

FIGURA 8.2

La regione ombreggiata costituisce un cono convesso.

Il problema è illustrato geometricamente in figura 8.3. È evidente che l'ottimo si trova all'intersezione dei primi due vincoli, al punto (1,1). Poiché questi vincoli di disuguaglianza funzionano come vincoli di uguaglianza nel punto (1,1), essi si chiamano vincoli costrittivi (binding in inglese) o attivi nel punto. Il terzo vincolo vale come disuguaglianza rigorosa nel punto (1,1), ed è perciò inattivo o non costrittivo (nonbinding in inglese). Definiamo ora direzione ammissibile di ricerca un vettore tale che uno spostamento infinitesimo lungo detto vettore non viola alcun vincolo.

Nel punto (1,1) l'insieme di tutte le direzioni ammissibili giace fra la retta x + y − 2 = 0 e la tangente a y x ² in (1,1), cioè la retta y = 2 x − 1. In altri termini, l'insieme delle direzioni ammissibili è il cono generato da queste rette. Detto cono è ombreggiato in figura. Il vettore −f punta nella direzione della massima velocità di variazione di f, ed ogni piccolo spostamento che forma un angolo (definito quale positivo) di meno di 90° con −f farà diminuire f. Perciò, all'ottimo, non può esistere alcuna direzione ammissibile che formi un angolo minore di 90° rispetto a −f.

Consideriamo adesso la figura 8.4, in cui sono tracciati i vettori gradiente dei vincoli, g1 e

g2 . Notiamo che −f è contenuto nel cono generato da g1 e g2. Che succederebbe se così non fosse? Se −f fosse appena sopra g2, esso formerebbe un angolo di meno di 90° con una direzione ammissibile, appena al di sotto della retta x + y − 2 = 0. Se −f fosse appena sotto g1, esso formerebbe un angolo di meno di 90° con una direzione ammissibile, appena al di sopra della retta y = 2 x − 1.

FIGURA 8.3

Geometria di un problema di ottimizzazione vincolata. La regione ammissibile si trova fra i vincoli costrittivi ed i contorni stessi.

Nessuno dei due casi può verificarsi in un punto di ottimo, ed entrambi i casi sono esclusi se e solo se −f si trova nel cono generato da g1 e g2. Naturalmente, ciò equivale a richiedere che f sia all'interno del cono generato da −g1 e −g2. Da ciò discende la formulazione usuale delle KTC:

Se f e tutte le g sono derivabili, condizione necessaria affinché un punto x^* sia un minimo vincolato per il problema

Minimizzare: f x 

 

soggetta a: g_j x c_j, j1,...,r è che, in ogni x^*, f giaccia nel cono generato dai negativi dei gradienti dei vincoli attivi.

Formulazione algebrica delle condizioni di Kuhn−Tucker

Il risultato precedente si può formulare in termini algebrici. Affinché f giaccia nel cono sopra descritto, esso deve essere una combinazione lineare dei negativi dei gradienti dei vincoli attivi;

cioè, devono esistere dei moltiplicatori di Lagrange u tali che ^*_j

FIGURA 8.4

Gradiente della funzione obiettivo contenuto in un cono convesso.

 ^{* *j j} ^*

j I

f u g



 

 ^x   ^x  ^(8.21)

dove

*_j 0,

u  j I (8.22)

ed I è l'insieme degli indici dei vincoli di disuguaglianza attivi.

Questi risultati si possono riformulare includendo tutti i vincoli, definendo il moltiplicatore u ^*_j pari a zero se ^gj

 

 

 

 

* *

j j j

u g x c  è zero per ogni j. Questa proprietà, cioè che i vincoli di disuguaglianza inattivi hanno moltiplicatori uguali a zero, si chiama scarto complementare. Le condizioni (8.21) ed (8.22) diventano quindi

 

 

1

0

r

j j

j

f u g



 ^x   ^x  ^(8.23)

 

*_j 0, *_{j j} * _j 0

u  u g x c  (8.24a)

 

j j

g x c j r (8.24b)

Le relazioni (8.23) e (8.24) sono la forma usuale in cui sono enunciate le relazioni di Kuhn−Tucker.

Moltiplicatori di Lagrange

Le condizioni KTC sono connesse strettamente con i risultati classici dei moltiplicatori di Lagrange per problemi con vincoli di uguaglianza. Si formi la Lagrangiana

     

1

, ^r _{j j j}

j

L f u g c



 

    

x u x x

dove gli u sono interpretati come moltiplicatori di Lagrange per i vincoli di disuguaglianza _j

j  j

g x c . Allora, le equazioni (8.23) ed (8.24) affermano che L x u deve essere stazionaria  ^,

rispetto ad x in





8.2.3 Problemi contenenti sia vincoli di uguaglianza che di disuguaglianza

Quando sono presenti sia vincoli di uguaglianza che di disuguaglianza, le condizioni KTC si enunciano come segue: si abbia il problema

 

Minimizzare: f x (8.25)

 

soggetta a: h_i x b_i, i1,...,m (8.26a) e g_j x c_j, j1,...,r (8.26b) Si definiscano i moltiplicatori di Lagrange _i associati con i vincoli di uguaglianza, ed i moltiplicatori di Lagrange u associati con i vincoli di disuguaglianza, e si formi la Lagrangiana _j

       

1 1

, , ^m _{i i i} ^r _{j j j}

i j

L f h b u g c

 

 

       

x λ u x x x (8.27)

Allora, se x^* è un minimo locale del problema (8.25)−(8.26), esistono i vettori di moltiplicatori di Lagrange λ e ^* u tali che ^* x^* è un punto di stazionarietà per la funzione L x λ u , cioè







  

 

 

1 1

, , ^{m r}

x i i j j

i j

L f h u g

 

 ^{x λ u}   ^x   ^x   ^x ^{0 (8.28)} e sussiste lo scarto complementare per le disuguaglianze:

 

*_j 0, *_{j j} * _j 0, 1, ...,

u  u g x c  j r (8.29)

_________________________________________________________________________

ESEMPIO 8.3 APPLICAZIONE DEL METODO DEI MOLTIPLICATORI DI LAGRANGE CON VINCOLI DI DISUGUAGLIANZA NON LINEARI

Si risolva il problema

  1 2

Minimizzare: f x x x

  1² 2²

soggetta a: g x x x 25 (a)

con il metodo dei moltiplicatori di Lagrange.

Soluzione. La funzione Lagrangiana è

 ^{, 1 2}





L x u x x u x x  (b)

Le condizioni necessarie per un punto di stazionarietà sono

 

2 1

1

1 2

2

2 2

1 2

2 2

1 2

2 0

2 0

25

25 0

L x ux

x

L x ux

x

L x x

u

u x x

   



   



   



  

(c)

Le cinque soluzioni simultanee del sistema (c) sono in Tabella E8.3. Come le calcolereste?

Le colonne due e tre della Tabella E8.3 riportano le componenti di x^* che rappresentano le soluzioni stazionarie del problema. Si noti che le soluzioni con u sono 0 minimi, quelle con u sono massimi, e 0 u è un punto di sella. Questo succede perché 0 massimizzare f equivale a minimizzare −f, e le condizioni KTC per il problema dell'equazione (a) con f sostituito da −f sono le equazioni (c) con u che può assumere valori negativi. In figura E8.3 sono rappresentate tratteggiate le linee di livello della funzione obiettivo (iperboli), e la regione di ammissibilità è delimitata dall'area ombreggiata racchiusa dalla circonferenza ^g ^{x 25}. I punti B e C corrispondono ai due minimi, D ed E ai due massimi, ed A al punto di sella di ^{f x .}  

TABELLA E8.3

Soluzioni dell'esempio 8.3 con il metodo dei moltiplicatori di Lagrange

U x₁ x₂ Punto C ^{f x}   ^Note

0 0 0 A 25 0 sella

0.5 ^3.54

3.54





3.54 3.54





B C

0 0

−12.5

−12.5

minimo minimo

−0.5 ^3.54 3.54





3.54 3.54





D E

0 0

+12.5 +12.5

massimo massimo

FIGURA E8.3

__________________________________________________________________________

Moltiplicatori di Lagrange e analisi di sensitività

A ciascuna iterazione, gli algoritmi NLP formano nuove stime non solo delle variabili decisionali x^* ma anche dei moltiplicatori di Lagrange λ ed u. Se in una iterazione tutti i vincoli sono soddisfatti e le condizioni KTC sono soddisfatte entro una specificata tolleranza, l'algoritmo si arresta. In un ottimo locale, i valori dei moltiplicatori forniscono utili informazioni sulla sensitività.

Nel problema NLP (8.25)−(8.26), sia V b c il valore ottimale della funzione obiettivo f in un ^* ^,

minimo locale, visto come funzione dei secondi membri b e c delle equazioni dei vincoli. Sotto opportune ipotesi (Luenberger, 1984, Cap. 10) si ha

*

* , 1, ...,

i

i

V i m

b

  

 (8.30a)

*_j *, 1, ...,

j

u V j r

c

 

 (8.30b)

I moltiplicatori di Lagrange forniscono quindi la sensitività del valore ottimo della funzione obiettivo rispetto ai secondi membri delle equazioni dei vincoli. Tale informazione è spesso di gran valore. Per esempio, se il secondo membro di una equazione di un vincolo di disuguaglianza rappresenta la capacità produttiva di un processo e questo vincolo risulta attivo, il valore ottimale

del moltiplicatore corrispondente u misura il decremento del costo minimo in funzione ^*_j dell'aumento della capacità produttiva. Questo si definisce valore marginale della capacità produttiva. In una situazione in cui vi sono diversi vincoli attivi sulle capacità produttive, il confronto dei moltiplicatori corrispondenti può dettare la priorità rispetto ad interventi di incremento della capacità produttiva. Esempi di uso dei moltiplicatori di Lagrange per analisi di sensitività sono riportati nel capitolo 7.

I moltiplicatori di Lagrange sono molto utili per l'analisi di sensitività ai parametri per i problemi con più vincoli. Per esempio, in una tipica raffineria si producono una serie di prodotti diversi che devono soddisfare (o superare) determinate specifiche in termini di purezza come richiesto dai clienti. Supponiamo di effettuare una ottimizzazione vincolata per una funzione obiettivo che include diverse variabili che si ritrovano nel modello della raffineria, cioè quelle nell'impianto di cracking catalitico, nella colonna di distillazione, e così via, e giungiamo a determinare un ottimo economico dipendente dai vincoli esistenti sulla purezza dei prodotti. Dati i valori ottimali delle variabili ed i moltiplicatori di Lagrange corrispondenti alla purezza dei prodotti, ci si può quindi porre la domanda: come cambierebbero i profitti se il disciplinare di produzione fosse rilassato ovvero reso più rigoroso? Rispondere a questa domanda richiede semplicemente l'esame del moltiplicatore di Lagrange esistente per ogni vincolo. Come esempio, si consideri il caso in cui vi sono tre principali prodotti (A, B, e C) e i valori dei moltiplicatori di Lagrange corrispondenti a ciascuno dei tre vincoli di disuguaglianza sono calcolati come:

0.001 1.0 0.007

A

B C

u u u

 

 

 

I valori degli u mostrano che (a meno della scala) soddisfare una richiesta aggiuntiva di una unità ^*_j di prodotto B costa molto di più che per gli altri due prodotti.

Problemi di programmazione convessa

Le condizioni KTC costituiscono condizioni non solo necessarie, ma anche sufficienti di ottimalità per problemi convessi regolari. Nel problema (8.25)−(8.26), se la funzione obiettivo

 

f x e le funzioni dei vincoli di disuguaglianza g sono convesse, e le funzioni dei vincoli di _j uguaglianza sono lineari, allora la regione di ammissibilità del problema è convessa, e ogni minimo locale è un minimo globale. Inoltre, se x^* è una soluzione ammissibile, se tutte le funzioni che definiscono il problema hanno derivate prime continue in x^*, e se i gradienti dei vincoli attivi in x^* sono indipendenti, allora x^* è ottimale se e solo se le condizioni KTC sono soddisfatte in x^*.

Considerazioni pratiche

Molti problemi reali non soddisfano queste condizioni di convessità. In applicazioni tipiche dell'ingegneria chimica, i vincoli di uguaglianza spesso consistono in relazioni ingresso-uscita di unità di processo, relazioni che, spesso, sono non lineari. La convessità della regione di ammissibilità può essere garantita solo se questi vincoli di uguaglianza sono tutti lineari. Ancora, spesso non è facile stabilire se un vincolo di disuguaglianza o una funzione obiettivo siano o meno convessi. Perciò, spesso non è facile stabilire se un punto che soddisfa le condizioni KTC sia un ottimo locale o un ottimo globale o un punto di sella. Per problemi con poche variabili, a volte possiamo trovare tutte le soluzioni KTC analiticamente e scegliere quella che ha il miglior valore per la funzione obiettivo. Altrimenti, la maggior parte degli algoritmi numerici si limitano ad arrestarsi allorquando le condizioni KTC sono verificate entro una specificata tolleranza. L'utente di