6.3 Ottimizzazione con vincoli di disuguaglianza: sufficienza delle condizioni di Kuhn-Tucker

Abbiamo visto in precedenza che sia per un problema di massimizzazione non vincolata sia per un problema di massimizzazione con un vincolo di uguaglianza le condizioni del primo ordine sono sufficienti per un punto di ottimo globale quando le funzioni oggetto e vincolo soddisfano appropriate condizioni di concavità/convessità. Lo stesso vale per un problema di ottimizzazione con un vincolo di disuguaglianza . Precisamente, abbiamo il seguente risultato.

Proposizione
Consideriamo il problema

maxx f (x) con gi(x£ ci per i = 1,...,m.

Supponiamo che

  •  f  sia derivabile su tuttto il suo dominio e concava e
  • gi sia derivabile su tutto il suo dominio e quasiconvessa per i = 1, ..., m.

Se esistono numeri l1, ..., lm ed un valore di x* tali che (x*, l) soddisfa le condizioni di Kuhn-Tucker allora x* è soluzione del problema.

La condizione che la funzione obiettivo sia concava è un po' troppo restrittiva per risultare utile in alcune applicazioni economiche. Specificatamente, l'assunto che vorremmo imporre sulla funzione di utilità di un consumatore è che essa debba essere quasiconcava. Il prossimo risultato è utile in questo caso.

Proposizione
Consideriamo il problema

maxx f (x) con gi(x£ ci per i = 1,...,m.
Supponiamo che

  •  f  sia derivabile due volte e quasiconcava e
  • gi derivabile in tutto il suo dominio e quasiconvessa per i = 1,...,m.

Se esistono numeri l1, ..., lm e un valore di x* tali che (x*, l) soddisfa le condizioni di Kuhn-Tucker e ( f ¢1(x*),..., f ¢n(x*)) ¹ (0,...,0) allora x* è soluzione del problema.

Combinando queste condizioni con le condizioni per le quali le condizioni di Kuhn-Tucker sono necessarie ne deduciamo che un insieme di condizioni per le quali le condizioni di Kuhn-Tucker sono sia necessarie che sufficienti è che la funzione obiettivo sia concava e tutte le funzioni vincolo siano convesse.

(Se avete di fronte un problema di minimizzazione, ricordate che potete trasformarlo in uno di massimizzazione moltiplicando la funzione oggetto per -1. Dunque per un problema di minimizzazione la condizione sulla funzione obiettivo nel primo risultato di sopra è che essa deve essere convessa, e la condizione nel secondo risultato è che essa deve essere quasiconvessa.)

Riepilogo delle condizioni necessarie e sufficienti per problemi di ottimizzazione

Esempio
Consideriamo il problema

maxx-(x - 2)2 con x ³ 1,

che può essere riscritto in questo modo

maxx-(x - 2)2 con 1-x £ 0.

La funzione oggetto è concava ed il vincolo è lineare, quindi concavo. Dunque le condizioni di Kuhn-Tucker sono sia necessarie che sufficienti: l'insieme di soluzioni per il problema è lo stesso delle soluzioni delle condizioni di Kuhn-Tucker.

Le condizioni di Kuhn-Tucker sono

-2(x - 2) + l  = 0
x-³ 0, l ³ 0, e l(1 - x = 0.

Dall'ultima condizione abbiamo l = 0 o x = 1.

  • x = 1: 2 + l = 0, o l = -2, che viola l ³ 0.
  • l = 0: -2(x - 2) = 0; l'unica soluzione è x = 2.

Così le condizioni di Kuhn-Tucker hanno un'unica soluzione, (xl) = (2, 0). Quindi il problema ha un'unica soluzione x = 2.

Esempio
Consideriamo il problema

maxx-(x - 2)2 con x ³ 3,
che si può riscrivere

maxx-(x - 2)2 con 3-x £ 0.

Come nell'esempio precedente, le funzione oggetto è concava e la funzione vincolo è lineare, quindi concava, dunque l'insieme delle soluzioni del problema è lo stesso delle soluzioni delle condizioni di Kuhn-Tucker.

Le condizioni di Kuhn-Tucker sono

-2(x-2) + l  = 0
x-³ 0, l ³ 0, e l(3 - x = 0.

Dall'ultima condizione abbiamo l = 0 o x = 3.

  • x = 3: -2 + l = 0, o l = 2.
  • l = 0: -2(x - 2) = 0; da x ³ 3 questa non ha soluzioni compatibili con le altre condizioni.

Allora le condizioni di Kuhn-Tucker hanno un'unica soluzione, (xl) = (3, 2). Il problema quindi ha un'unica soluzione, x = 3.

Esempio
Abbiamo precedentemente considerato il problema

maxx_1,x_2 -(x1 - 4)2 - (x2 - 4)2 con x1 + x2 £ 4 e x1 + 3x2 £ 9.

La funzione oggetto è concava, ed i vincoli sono entrambi lineari, quindi concavi, allora le soluzioni del problema sono le stesse delle condizioni di Kuhn-Tucker.

Avevamo precedentemente trovato che le condizioni di Kuhn-Tucker sono

-2(x1 - 4) - l1 - l2  = 0
-2(x2 - 4) - l1 - 3l2  = 0
x1 + x2 £ 4, l1 ³ 0, e l1(x1 + x2 - 4)  = 0
x1 + 3x2 £ 9, l2 ³ 0, e l2(x1 + 3x2 - 9)  = 0.

Quali sono le soluzioni per queste condizioni? Proviamo i vari casi:

  • x1 + x2 = 4 e x1 + 3x2 = 9. In questo caso abbiamo x1 = 3/2 e x2 = 5/2. Quindi le prime due equazioni sono

    - l1 - l2 = 0
    - l1 - 3l2 = 0

    vale a dire l1 = 6 e l2 = -1 e ciò viola la condizione l2 ³ 0.

  • x1 + x2 = 4 e x1 + 3x2 < 9, così che l2 = 0. Allora le prime due equazioni implicano che x1 = x2 = 2 e l1 = 4. Tutte le condizioni sono soddisfatte, dunque (x1x2l1l2) = (2, 2, 4, 0) è una soluzione.
  • x1 + x2 < 4 e x1 + 3x2 = 9, allora l1 = 0. Allora le prime due equazioni implicano che x1 = 12/5 e x2 = 11/5, violando x1 + x2 < 4.
  • x1 + x2 < 4 e x1 + 3x2 < 9, dunque l1 = l2 = 0. Allora le prime due equazioni implicano che x1 = x2 = 4, violando x1 + x2 < 4.

Così (x1x2l1l2) = (2, 2, 4, 0) è l'unica soluzione per le condizioni di Kuhn-Tucker. Quindi l'unica soluzione del problema è (x1x2) = (2, 2).

Esempio
Consideriamo il problema

maxx,y xy con x + y £ 6, x ³ 0, e y ³ 0.

Le funzioni vincolo sono concave, dunque le condizioni di Kuhn-Tucker sono necessarie. Inoltre, la funzione obiettivo è continua e l'insieme vincolare è compatto dunque, per il Teorema del Valore Estremo, il problema ammette soluzione. Le soluzioni del problema perciò sono le soluzioni delle condizioni del primo ordine stesse che segnalano i valori più alti della funzione. (Alternativamente, possiamo richiamare la sufficienza delle condizioni di Kuhn-Tucker: la funzione obiettivo è quasiconcava (ma non concava) nell'insieme vincolare (le sue curve di livello sono iperboli equilatere) e le funzioni vincolo sono lineari, quindi quasiconvesse, così se x* risolve le condizioni di Kuhn-Tucker e Ñ f (x*) ¹ (0, 0), allora x* è soluzione del problema. Notate che questo argomento lascia aperto la stato dei punti x* che risolvono le condizioni di Kuhn-Tucker e soddisfano Ñ f (x*) = (0, 0)---non si determina quando essi siano soluzione o non lo siano.)

La Lagrangiana è

L(xy) = xy - l1(x + y - 6) + l2x + l3y.

Le condizioni di Kuhn-Tucker sono

y - l1 + l2  = 0
x - l1 + l3  = 0
l1 ³ 0, x + y £ 6, l1(x + y - 6)  = 0
l2 ³ 0, x ³ 0, l2x  = 0
l3 ³ 0, y ³ 0, l3y  = 0.

  • Se x > 0 e y > 0, allora l2 = l3 = 0, quindi l1 = x = y dalle prime due condizioni. Quindi x = y = l = 3 dalla terza condizione. Questi valori soddisfano tutte le condizioni.
  • Se x = 0 e y > 0, allora l3 = 0 dall'ultima condizione e l1 = x = 0 dalla seconda condizione. Ma ora dalla prima condizione l2 = -y < 0, contraddicendo l2 ³ 0.
  • Se x > 0 e y = 0, allora l2 = 0, ed un analogo argomento porta ad una contraddizione.
  • Se x = y = 0, allora l1 = 0 dal terzo insieme di condizioni, così l2 = l3 dalla prima e seconda condizione. Questi valori soddisfano tutte le condizioni.

Concludiamo che vi sono due soluzioni alle condizioni di Kuhn-Tucker, (xyl1l2l3) = (3, 3, 3, 0, 0) e (0, 0, 0, 0, 0). Dato che il valore della funzione oggetto in (3, 3) è più grande del valore della funzione oggetto in (0, 0), la soluzione del problema è (3, 3).

Notate che l'argomento in questo esempio si applica a qualsiasi problema della forma

maxx u(x) con p·x £ w, x ³ 0,
dove u è quasiconcava, p un vettore, e w uno scalare.

Esercizi


Copyright © 1997-2002 by Martin J. Osborne