Per prima cosa consideriamo un problema ad una dimensione con un solo vincolo di non negatività:
maxx f (x) con x ³ 0.Nella soluzione x* abbiamo
f ¢(x*) £ 0, x* ³ 0 e x* f ¢(x*) = 0(x* f ¢(x*) = 0 implica x* = 0 o f ¢(x*) = 0).
Ora consideriamo un problema con più variabili:
maxx f (x) con x ³ 0.In questo caso nella soluzione x*, per ogni j, xj* = 0 ovvero f j¢(x*) = 0, o
f j¢(x*) £ 0, x*j ³ 0, e xj*· f j¢(x*) = 0 per j = 1,...,n,oppure, in una notazione più compatta,
Ñ f (x*) £ 0, x* ³ 0, e x*·Ñ f (x*) = 0.
Ora consideriamo il problema generale
maxx f (x) con gj(x) £ cj per j = 1, ..., m e xi ³ 0 per i = 1, ..., n.Sia
M(x) = f (x) - åj=1mlj[gj(x) - cj].Notate che i vincoli di non negatività non sono inclusi in questa Lagrangiana. Le condizioni del primo ordine per questo problema sono le seguenti condizioni di Kuhn-Tucker:
L'ultima condizione per ogni riga di queste condizioni è detta condizione di complementary slackness.
Mi¢(x*) £ 0, xi* ³ 0, e xi*·Mi¢(x*) = 0 per i = 1,...,n gj(x*) £ cj, lj ³ 0, e lj·[gj(x*) - cj] = 0 per j = 1,...,m.
Queste condizioni hanno lo stesso contenuto delle originali condizioni di Kuhn-Tucker per la Lagrangiana L(x) = f (x) - åj=1mlj[gj(x) - cj] + åj=1nlj+mxj, che include esplicitamente le funzioni vincolo che contengono i vincoli di non negatività. (Verificherete questo fatto in un esercizio.)
(Notate che, come prima, possiamo applicare queste condizioni ad un problema di minimizzazione moltiplicando la funzione obiettivo per -1.)
|