Programmazione non lineare

Nei problemi di ottimizzazione non lineare la funzione obiettivo e/o le funzioni dei vincoli sono non lineari. Esistono alcuni problemi non lineari che possono essere trasformati in problemi lineari

In generale però, i problemi non lineari restano tali e si affrontano con determinati metodi. Possono essere di due tipi:

• Se il problema si dice non vincolato.
• Se Il problema si dice vincolato:

Si pone sempre , altrimenti l’insieme potrebbe risultare vuoto, oppure potrebbero esserci vincoli ridondanti.

I problemi non vincolati sono problemi in cui effettivamente l’insieme ammissibili coincide con tutto lo spazio.

Nelle applicazioni sono considerati non vincolati i problemi con insieme ammissibile aperto.

In tal caso infatti i punti di ottimo sono interni e possono essere caratterizzati solo dall’andamento della funzione obiettivo.

Problemi non vincolati

Sia dato un problema di PNL non vincolata:

Una soluzione locale deve soddisfare una condizione necessaria di ottimalità. Si osserva che i punti che soddisfano una condizione necessaria di ottimalità non sono forzatamente soluzioni del problema: potrebbero ad esempio essere di max e non di minimo

Condizioni di Ottimalità

Condizioni Necessarie e Sufficienti

• Una condizione necessaria puo servire a restringere l’insieme di punti in cui cercare la soluzione e a costruire algoritmi che soddisfano la condizione necessaria.

• Una condizione sufficiente puo servire a dimostrare che un punto ottenuto per via numerica sia una soluzione ottima

Condizione Necessaria del Primo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile in , allora in

La condizione necessaria fornisce i punti stazionari candidati ad essere punti minimali.

Se il problema è convesso, la condizione diventa necessaria e sufficiente.

Condizione Sufficiente del Secondo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile due volte in , allora in e la matrice hessiana è semidefinita positiva

Condizione Necessaria del Secondo Ordine

Sia un punto interno della regione ammissibile e , e differenziabile due volte in :

• Se la matrice hessiana è definita positiva, allora è punto di minimo locale;
• Se la matrice hessiana è definita negativa allora è punto di massimo locale;
• Se la matrice hessiana è indefinita, allora è un punto di sella
• Se la matrice hessiana è semidefinita non si può dire niente

Regolarità dei vincoli di uguaglianza

Condizione di Ottimalità del primo ordine

Forma Equivalente

Funzione Lagrangiana

Link to original

Problemi con vincoli di uguaglianza e disuguaglianza

Regolarità dei vincoli

Condizioni KKT

Condizioni di ottimalità del primo ordine-KKT

Teorema: Condizioni di Karush-Kuhn-Tucker

Funzione Lagrangiana

Schema Condizioni Ottimalità

Problema Convesso

Link to original