Programmazione non lineare - Nonlinear programming

In matematica , la programmazione non lineare ( PNL ) è il processo di risoluzione di un problema di ottimizzazione in cui alcuni vincoli o la funzione obiettivo sono non lineari . Un problema di ottimizzazione è quello di calcolo degli estremi (massimi, minimi o punti stazionari) di una funzione obiettivo su un insieme di variabili reali incognite e condizionato al soddisfacimento di un sistema di uguaglianze e disequazioni , collettivamente denominati vincoli . È il sottocampo dell'ottimizzazione matematica che si occupa di problemi che non sono lineari.

Applicabilità

Un tipico problema non convesso è quello di ottimizzare i costi di trasporto selezionando un insieme di metodi di trasporto, uno o più dei quali mostrano economie di scala , con varie connettività e vincoli di capacità. Un esempio potrebbe essere il trasporto di prodotti petroliferi data una selezione o una combinazione di oleodotti, cisterne ferroviarie, autocisterne, chiatte fluviali o navi cisterna costiere. A causa delle dimensioni economiche dei lotti, le funzioni di costo possono presentare discontinuità oltre a variazioni uniformi.

Nella scienza sperimentale, alcune semplici analisi dei dati (come l'adattamento di uno spettro con una somma di picchi di posizione e forma note ma magnitudine sconosciuta) possono essere eseguite con metodi lineari, ma in generale anche questi problemi sono non lineari. Tipicamente, si ha un modello teorico del sistema in studio con parametri variabili al suo interno e un modello dell'esperimento o degli esperimenti, che possono anche avere parametri sconosciuti. Si cerca di trovare numericamente un adattamento migliore. In questo caso spesso si vuole una misura della precisione del risultato, così come il miglior adattamento stesso.

Definizione

Siano n , m e p numeri interi positivi. Lasciate che X sia un sottoinsieme di R ⁿ , lasciate f , g _io , e h _j essere funzioni a valori reali su X per ogni i in { 1 , ..., m } e ogni j in { 1 , ..., p }, con a almeno uno tra f , g _i e h _j non è lineare.

Un problema di minimizzazione non lineare è un problema di ottimizzazione della forma

${\displaystyle {\begin{allineato}{\text{riduci a icona}}&f(x)\\{\text{soggetto a }}&g_{i}(x)\leq 0{\text{ per ogni }}i\ in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ per ogni }}j\in \{1,\dotsc ,p\}\\&x\in X. \end{allineato}}}$

Un problema di massimizzazione non lineare è definito in modo simile.

Possibili tipi di set di vincoli

Esistono diverse possibilità per la natura dell'insieme di vincoli, noto anche come insieme ammissibile o regione ammissibile .

Un problema irrealizzabile è quello per il quale nessun insieme di valori per le variabili di scelta soddisfa tutti i vincoli. Cioè, i vincoli sono reciprocamente contraddittori e non esiste alcuna soluzione; l'insieme ammissibile è l' insieme vuoto .

Un problema ammissibile è quello per il quale esiste almeno un insieme di valori per le variabili di scelta che soddisfano tutti i vincoli.

Un problema illimitato è un problema ammissibile per il quale la funzione obiettivo può essere resa migliore di qualsiasi dato valore finito. Quindi non esiste una soluzione ottimale, perché esiste sempre una soluzione ammissibile che fornisce un valore della funzione obiettivo migliore di qualsiasi data soluzione proposta.

Metodi per risolvere il problema

Se la funzione obiettivo è concava (problema di massimizzazione) o convessa (problema di minimizzazione) e l'insieme dei vincoli è convesso , il programma viene chiamato convesso e nella maggior parte dei casi possono essere utilizzati metodi generali di ottimizzazione convessa .

Se la funzione obiettivo è quadratica ei vincoli sono lineari, vengono utilizzate tecniche di programmazione quadratica .

Se la funzione obiettivo è un rapporto tra una funzione concava e una convessa (nel caso di massimizzazione) e i vincoli sono convessi, allora il problema può essere trasformato in un problema di ottimizzazione convesso utilizzando tecniche di programmazione frazionaria .

Sono disponibili diversi metodi per risolvere problemi non convessi. Un approccio consiste nell'utilizzare formulazioni speciali di problemi di programmazione lineare. Un altro metodo prevede l'utilizzo di tecniche branch and bound , dove il programma è suddiviso in sottoclassi da risolvere con approssimazioni convesse (problema di minimizzazione) o lineari che formano un limite inferiore sul costo complessivo all'interno della suddivisione. Con successive divisioni si otterrà ad un certo punto una soluzione effettiva il cui costo è pari al miglior limite inferiore ottenuto per una qualsiasi delle soluzioni approssimate. Questa soluzione è ottimale, anche se forse non unica. L'algoritmo può anche essere interrotto anticipatamente, con la certezza che la migliore soluzione possibile rientri in una tolleranza dal miglior punto trovato; tali punti sono detti ε-ottimali. La terminazione in punti ε-ottimali è in genere necessaria per garantire una terminazione finita. Ciò è particolarmente utile per problemi grandi e difficili e problemi con costi o valori incerti in cui l'incertezza può essere stimata con una stima di affidabilità appropriata.

In condizioni di differenziabilità e vincolo , le condizioni di Karush–Kuhn–Tucker (KKT) forniscono le condizioni necessarie affinché una soluzione sia ottimale. Anche in convessità queste condizioni sono sufficienti. Se alcune delle funzioni non sono differenziabili, sono disponibili versioni subdifferenziali delle condizioni di Karush–Kuhn–Tucker (KKT) .

Esempi

Esempio bidimensionale

La regione blu è la regione ammissibile . La tangenza della retta con la regione ammissibile rappresenta la soluzione. La linea è la migliore linea di contorno realizzabile (luogo con un dato valore della funzione obiettivo).

Un semplice problema (mostrato nel diagramma) può essere definito dai vincoli

x ₁ ≥ 0

x ₂ ≥ 0

x ₁ ² + x ₂ ² ≥ 1

x ₁ ² + x ₂ ² ≤ 2

con una funzione obiettivo da massimizzare

f ( x ) = x ₁ + x ₂

dove x = ( x ₁ , x ₂ ).

Esempio tridimensionale

La tangenza della superficie superiore con lo spazio vincolato al centro rappresenta la soluzione.

Un altro semplice problema (vedi diagramma) può essere definito dai vincoli

x ₁ ² − x ₂ ² + x ₃ ² ≤ 2

x ₁ ² + x ₂ ² + x ₃ ² 10

con una funzione obiettivo da massimizzare

f ( x ) = x ₁ x ₂ + x ₂ x ₃

dove x = ( x ₁ , x ₂ , x ₃ ).

Guarda anche

• Adattamento curvo
• Minimizzazione dei minimi quadrati
• Programmazione lineare
• nl (formato)
• Minimi quadrati non lineari
• Elenco dei software di ottimizzazione
• Programmazione quadratica con vincoli quadratici
• Werner Fenchel , che ha creato le basi per la programmazione non lineare

Riferimenti

Ulteriori letture

• Avriel, Mardocheo (2003). Programmazione non lineare: analisi e metodi. Editore di Dover. ISBN  0-486-43227-0 .
• Bazaraa, Mokhtar S. e Shetty, CM (1979). Programmazione non lineare. Teoria e algoritmi. John Wiley & Figli. ISBN  0-471-78610-1 .
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemarechal, Claude ; Sagastizabal, Claudia A. (2006). Ottimizzazione numerica: Aspetti teorici e pratici . Universitext (Seconda ed. riveduta della traduzione del 1997 ed. francese). Berlino: Springer-Verlag. pp. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2265882 .
• Luenberger, David G. ; Sì, Yinyu (2008). Programmazione lineare e non lineare . Serie internazionale di ricerca operativa e scienze gestionali. 116 (Terza ed.). New York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2. MR  2423726 .
• Nocedal, Jorge e Wright, Stephen J. (1999). Ottimizzazione numerica. Springer. ISBN  0-387-98793-2 .
• Jan Brinkhuis e Vladimir Tikhomirov, Ottimizzazione: approfondimenti e applicazioni , 2005, Princeton University Press

link esterno

• Glossario di programmazione matematica