teoria della dualita

teoria della dualità

Nell’ambito dell’ottimizzazione associa a un problema di ottimo (detto primale) un altro problema (detto duale), talvolta più semplice da risolvere e che comunque fornisce informazioni rilevanti sul primale, garantendo altresì determinate relazioni tra le soluzioni dei due problemi. Consideriamo nello specifico un problema di programmazione non lineare e cerchiamo il massimo della funzione f quando le variabili decisionali x_j sono soggette ai vincoli g_i(x)≤0. La dualità lagrangiana, in particolare, associa a questo problema la ricerca del minimo della funzione L(x,λ)=f(x)−∑λ_ig_i(x) con gli ulteriori vincoli λ_i≥0 e gradf(x)−∑λ_igradg_i(x) =0. Il teorema di dualità debole stabilisce che, se le funzioni f e g_i sono differenziabili, con f concava e g_i convesse, allora l’estremo inferiore di L(x,λ) è maggiore o uguale dell’estremo superiore di f. Con le stesse ipotesi e un’ulteriore condizione di qualificazione dei vincoli, il teorema di dualità forte afferma che se x⁰ è soluzione del problema primale esiste un moltiplicatore λ⁰ a componenti non negative tale che (x⁰,λ⁰) minimizza la funzione lagrangiana L(x,λ), risultando anche L(x⁰,λ⁰)= f(x⁰).

→ Programmazione matematica