Programmazione non lineare

La programmazione non lineare (PNL) è una branca della programmazione matematica e della ricerca operativa che si occupa di problemi di ottimizzazione in cui la funzione obiettivo e/o almeno uno dei vincoli sono funzioni non lineari delle variabili decisionali.

La PNL è una generalizzazione della programmazione lineare e consente di modellare una più ampia classe di sistemi e processi reali, in cui le relazioni tra le variabili non sono strettamente proporzionali (cioè sono descritte da curve, non da rette).

Oggetto e finalità

La programmazione non lineare viene utilizzata per trovare soluzioni ottimali in situazioni in cui:

• La dipendenza dell'indicatore obiettivo (profitto, costi, efficienza, ecc.) dai parametri controllabili è non lineare (ad esempio, rendimenti decrescenti di scala, costi quadratici).
• I vincoli sulle risorse o sui processi tecnologici sono descritti da relazioni non lineari (ad esempio, reazioni chimiche, leggi fisiche, dipendenze economiche).

I problemi di PNL emergono in numerosi ambiti:

• Progettazione ingegneristica (ottimizzazione di strutture e processi).
• Economia e finanza (ottimizzazione del portafoglio tenendo conto del rischio, modellazione dei mercati).
• Tecnologia chimica (ottimizzazione dei regimi dei reattori).
• Machine Learning (addestramento di reti neurali, metodo dei vettori di supporto).
• Gestione dei processi produttivi. Logistica (con costi non lineari).

Formulazione matematica del problema di PNL

Il problema generale della programmazione non lineare è formulato come segue:

Si cerca di trovare un insieme di valori delle variabili decisionali che massimizzi o minimizzi una funzione obiettivo non lineare. I valori delle variabili devono soddisfare un sistema di vincoli, che possono essere espressi sia sotto forma di disuguaglianze (ad esempio, "la quantità A deve essere minore o uguale a B") sia sotto forma di uguaglianze (ad esempio, "la quantità C deve essere esattamente uguale a D"). È importante che almeno una delle funzioni che descrivono l'obiettivo o i vincoli sia non lineare. Spesso vengono aggiunte condizioni di non negatività delle variabili, ovvero il requisito che i loro valori siano maggiori o uguali a zero.

L'insieme di tutti gli insiemi di valori delle variabili che soddisfano i vincoli costituisce la regione ammissibile (RA).

Differenze rispetto alla programmazione lineare

La programmazione non lineare si differenzia significativamente dalla programmazione lineare (PL):

• Non linearità: La funzione obiettivo o i vincoli (o entrambi) contengono dipendenze non lineari.
• Proprietà della RA: La regione ammissibile nella PNL può essere non convessa (a differenza della PL, dove la RA è sempre un poliedro convesso).
• Proprietà dell'ottimo: La soluzione ottimale nella PNL non si trova necessariamente in un vertice della RA; può trovarsi sul confine o all'interno della regione. Nella PNL possono esistere ottimi locali che non sono ottimi globali.
• Complessità della soluzione: I problemi di PNL sono generalmente molto più difficili da risolvere rispetto ai problemi di PL. Non esiste un unico algoritmo universale, analogo al metodo del simplesso, per tutti i problemi di PNL.

Principali difficoltà e sfide della PNL

La risoluzione dei problemi di programmazione non lineare è associata a una serie di difficoltà:

• Presenza di estremi locali: La maggior parte dei metodi di PNL garantisce solo il ritrovamento di un ottimo locale (una soluzione migliore in un certo intorno). La ricerca dell'ottimo globale (la soluzione migliore in tutta la RA) è un problema complesso, specialmente per i problemi non convessi.
• Non convessità: Se il problema non è convesso (la funzione obiettivo o la RA sono non convesse), possono esistere molteplici ottimi locali e i metodi del gradiente standard possono "bloccarsi" in uno di essi.
• Complessità computazionale: Gli algoritmi per la risoluzione della PNL richiedono spesso risorse computazionali significativamente maggiori rispetto alla PL.

Classi importanti di problemi di PNL

Nonostante la complessità generale, esistono importanti sottoclassi di problemi di PNL per le quali sono stati sviluppati metodi di soluzione efficienti:

• Programmazione convessa: Problema di minimizzazione di una funzione convessa su un insieme convesso di soluzioni ammissibili (o di massimizzazione di una funzione concava). Proprietà chiave: qualsiasi minimo locale è anche un minimo globale. Ciò semplifica notevolmente la ricerca della soluzione ottimale.
• Programmazione quadratica: La funzione obiettivo è quadratica e tutti i vincoli sono lineari.
• Programmazione separabile: La funzione obiettivo e i vincoli possono essere rappresentati come somme di funzioni, ciascuna delle quali dipende da una sola variabile.

Metodi di soluzione dei problemi di PNL

Metodi di soluzione dei problemi di programmazione non lineare (PNL)

I. Metodi di ottimizzazione senza vincoli:

• Metodi del gradiente (metodo della discesa più rapida, metodo dei gradienti coniugati);
• Metodo di Newton e metodi quasi-newtoniani (ad esempio, BFGS);
• Metodi basati sull'approssimazione dell'Hessiano.

II. Metodi di ottimizzazione con vincoli:

• Metodi di trasformazione:
  • Metodo delle funzioni di penalità (penalty methods);
  • Metodo delle funzioni barriera (barrier methods).
• Metodi di ricerca diretta della direzione:
  • Metodo delle direzioni ammissibili.
• Metodi basati sulle condizioni di ottimalità:
  • Metodi di Karush-Kuhn-Tucker (condizioni KKT);
  • Metodo dei moltiplicatori di Lagrange.
• Metodi iterativi:
  • Programmazione quadratica sequenziale (SQP);
  • Metodi dei punti interni.

III. Metodi di ottimizzazione globale:

• Metodi euristici e metaeuristici:
  • Algoritmi genetici;
  • Ricottura simulata;
  • Ricerca con divieti (tabu search).
• Metodi deterministici:
  • Ramificazione e limitazione (branch and bound);
  • Algoritmi di ottimizzazione globale per problemi con struttura speciale.

Vedi anche

• Ricerca operativa
• Ottimizzazione
• Programmazione lineare
• Programmazione convessa
• Funzione obiettivo
• Vincoli
• Regione ammissibile

Bibliografia

• Bazaraa M., Shetty C. Programmazione non lineare. Teoria e algoritmi. — Mosca: Mir, 1982.
• Fiacco A., McCormick G. Programmazione non lineare. Metodi di minimizzazione sequenziale senza vincoli. — Mosca: Mir, 1972.
• Himmelblau D. Programmazione non lineare applicata. — Mosca: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)