Skip to content
Torna ai risultati

Programmazione non lineare

Introdotto da
Jorge Nocedal & Stephen Wright
Anno
2006
Tipo
Continuous mathematical optimization
Famiglia
Mathematical programming

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La programmazione non lineare (PNL) è una branca dell'ottimizzazione matematica che si occupa di problemi in cui la funzione obiettivo o almeno un vincolo è non lineare.

Formalizzata in modo esaustivo da Jorge Nocedal e Stephen Wright nel loro testo fondamentale del 2006, la PNL comprende algoritmi basati sul gradiente — inclusi la programmazione quadratica sequenziale (SQP), i metodi a punto interno e gli approcci quasi-Newton — per trovare soluzioni ottimali localmente o globalmente a problemi decisionali continui che sorgono nell'ingegneria, nell'economia e nelle scienze fisiche.

L’intuizione alla base del metodo

Immaginate di scendere un paesaggio collinare e nebbioso rimanendo all'interno di una regione recintata. Non potete vedere l'intero terreno, quindi percepite la pendenza sotto i vostri piedi (gradiente), regolate la direzione del passo per scendere e controllate ad ogni movimento di non aver superato la recinzione (vincoli). Se la recinzione si piega o le colline si sovrappongono, i semplici percorsi rettilinei non funzioneranno — dovete curvare il vostro percorso. La programmazione non lineare formalizza esattamente questo processo, sostituendo l'intuitiva camminata in collina con regole matematicamente rigorose per la dimensione del passo e la direzione.

Storia

I fondamenti teorici della programmazione non lineare risalgono alle condizioni KKT derivate da Karush (1939) e Kuhn e Tucker (1951). Gli algoritmi pratici hanno accelerato durante gli anni '60-'80 con lo sviluppo dei metodi SQP, degli approcci lagrangiani aumentati e degli aggiornamenti quasi-Newtoniani inclusi BFGS (1970). La seconda edizione di Numerical Optimization di Nocedal e Wright del 2006 è diventata un riferimento definitivo, sintetizzando la teoria della convergenza, i framework di ricerca lineare e regione di fiducia, e i metodi a punto interno in un trattamento moderno coerente.

Quando usarlo

Utilizzare la programmazione non lineare quando l'obiettivo o i vincoli non possono essere linearizzati senza una perdita materiale di accuratezza e le variabili decisionali sono continue. Le impostazioni tipiche includono la progettazione ingegneristica con vincoli di leggi fisiche, l'ottimizzazione di portafoglio con misure di rischio non lineari e la regressione con forme di modello non lineari. Le ipotesi chiave sono che f e c siano almeno due volte continuamente differenziabili (per i risolutori basati sul gradiente) e che le qualificazioni dei vincoli siano soddisfatte. Quando le variabili sono intere, si applicano estensioni di programmazione non lineare a interi misti (MINLP). Per problemi convessi, i metodi a punto interno garantiscono l'ottimalità globale; per problemi non convessi, esistono solo garanzie locali.

Limiti e considerazioni

  • I problemi non convessi offrono solo garanzie di ottimalità locale; le soluzioni globali richiedono strategie di ricerca globale aggiuntive.
  • Richiede che l'obiettivo e i vincoli siano lisci (almeno differenziabili); i problemi non lisci necessitano di metodi subdifferenziali specializzati.
  • Il costo computazionale cresce sostanzialmente con la dimensione del problema quando è richiesta la valutazione esatta dell'Hessiana.
  • Le qualificazioni dei vincoli possono fallire (ad esempio, in punti fattibili degeneri), facendo perdere alle condizioni KKT il loro fondamento teorico.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Gestisce un'ampia classe di problemi del mondo reale in cui le approssimazioni lineari o quadratiche sono insufficienti.
  • Teoria algoritmica matura con garanzie di convergenza ben studiate per istanze convesse.
  • Efficienti risolutori basati sul gradiente (SQP, punto interno) si adattano a migliaia di variabili nella pratica.
  • Il framework lagrangiano unificato accoglie naturalmente vincoli misti di uguaglianza e disuguaglianza.

Applicazioni

  • Ingegneria strutturale e aerospaziale: minimizzazione del peso soggetta a vincoli di stress e deflessione.
  • Gestione del portafoglio: massimizzazione del rendimento atteso soggetta a un budget di varianza (rischio) non lineare.
  • Progettazione di processi chimici: ottimizzazione della resa del reattore soggetta a vincoli termodinamici e di sicurezza.
  • Apprendimento automatico: addestramento di reti neurali e modelli kernel tramite risolutori PNL non vincolati o vincolati.
  • Sistemi energetici: problemi di flusso di potenza ottimale nella distribuzione della rete elettrica con vincoli fisici non lineari.

Come funziona

Come funziona

1

L'analista definisce un obiettivo scalare f(x) da minimizzare o massimizzare sulle variabili decisionali x in R^n, insieme a vincoli di uguaglianza c_i(x) = 0 e vincoli di disuguaglianza c_j(x) >= 0. Identificare quali vincoli sono attivi in una soluzione candidata e se le condizioni di regolarità (qualificazioni dei vincoli) sono soddisfatte è critico in questa fase e determina quale teoria di ottimalità si applica.

Formula
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

Le condizioni di Karush-Kuhn-Tucker (KKT) forniscono le condizioni necessarie di primo ordine per un ottimo locale. Esse richiedono la stazionarietà del Lagrangiano, la complementarità per i moltiplicatori di disuguaglianza (lambda_j c_j = 0), la fattibilità duale (lambda_j >= 0) e la fattibilità primale. Gli algoritmi costruiscono iterativamente iterazioni che soddisfano queste condizioni in modo progressivamente più stringente, con condizioni di sufficienza di secondo ordine che confermano che un punto stazionario è effettivamente un minimo locale.

Formula
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

Ad ogni iterazione k un algoritmo calcola una direzione di ricerca p_k — tipicamente tramite un'approssimazione quasi-Newtoniana B_k dell'Hessiana (ad esempio, BFGS) o un sistema esatto di derivate seconde — e una lunghezza del passo alpha_k che soddisfa le condizioni di Wolfe o Armijo. I metodi SQP risolvono un sottoproblema quadratico per p_k, mentre i metodi a punto interno aggiungono termini barriera per gestire i vincoli di disuguaglianza e guidare le iterazioni verso l'interno fattibile.

Formula
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

La terminazione si verifica quando sia la norma del gradiente del Lagrangiano sia la massima violazione dei vincoli scendono al di sotto delle tolleranze prescritte (epsilon e delta). Poiché la PNL è generalmente non convessa, gli algoritmi possono convergere a ottimi locali; sono raccomandati riavvii multipli da diversi punti di partenza o strategie di ricerca globale (branch-and-bound, multistart) quando è richiesta l'ottimalità globale.

Formula
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

Errori comuni

  • Ignorare le qualificazioni dei vincoli e applicare ciecamente le condizioni KKT in punti degeneri o infattibili porta a soluzioni spurie.
  • L'uso di variabili mal scalate causa approssimazioni dell'Hessiana mal condizionate e una convergenza lenta o fallita.
  • Accettare il primo minimo locale trovato senza riavvii multipli in contesti non convessi può far perdere significativamente l'ottimo globale.
  • Le approssimazioni del gradiente a differenze finite introducono errori numerici; la differenziazione analitica o automatica è fortemente preferita.

Domande frequenti

Ogni programma lineare è anche un programma non lineare?

Sì. La programmazione lineare è un caso speciale di PNL in cui sia l'obiettivo che tutti i vincoli sono affini. Tuttavia, la PL ammette gli algoritmi del simplesso e a punto interno che sfruttano la linearità e sono molto più efficienti dei risolutori PNL generali; usare un risolutore PNL generale per una PL è uno spreco ma matematicamente valido.

Quando posso fidarmi che un punto KKT sia un minimo globale?

Quando la PNL è convessa — il che significa che f è convessa e l'insieme ammissibile è un insieme convesso — qualsiasi punto KKT è un minimo globale. Per problemi non convessi questa garanzia non vale, e un punto KKT è solo un minimo locale (sotto condizioni di sufficienza di secondo ordine). Sono necessari metodi di ottimizzazione globale come branch-and-bound o rilassamenti convessi in caso contrario.

Qual è la differenza tra i metodi SQP e a punto interno?

SQP risolve iterativamente sottoproblemi di programmazione quadratica che approssimano localmente la PNL ed è spesso preferito per problemi di piccole-medie dimensioni con molti vincoli attivi. I metodi a punto interno (barriera) rimangono strettamente all'interno della regione ammissibile e tendono a scalare meglio per problemi grandi e sparsi. Entrambi convergono superlinearmente sotto appropriate condizioni di regolarità.

Metodi correlati

Fonti

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN: 978-0-387-30303-1
    Copiato.