Molti algoritmi di ottimizzazione non vincolata possono essere adattati al caso vincolato, spesso attraverso l’uso di un metodo di penalità. Tuttavia, i passi di ricerca del metodo non vincolato possono essere inaccettabili per il problema vincolato, portando ad una mancanza di convergenza. Questo viene chiamato effetto Maratos.
Vincoli di uguaglianzaModifica
Metodo di sostituzioneModifica
Per problemi molto semplici, ad esempio una funzione di due variabili soggetta a un singolo vincolo di uguaglianza, è più pratico applicare il metodo di sostituzione. L’idea è di sostituire il vincolo nella funzione obiettivo per creare una funzione composta che incorpora l’effetto del vincolo. Per esempio, supponiamo che l’obiettivo sia massimizzare f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
soggetto a x + y = 10 {displaystyle x+y=10}
. Il vincolo implica y = 10 – x {\displaystyle y=10-x}
, che può essere sostituito nella funzione obiettivo per creare p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}
. La condizione necessaria del primo ordine dà ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\parziale p}{\parziale x}=10-2x=0}
, che può essere risolto per x = 5 {displaystyle x=5}
e, di conseguenza, y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Moltiplicatore di LagrangeModifica
Se il problema vincolato ha solo vincoli di uguaglianza, il metodo dei moltiplicatori di Lagrange può essere usato per convertirlo in un problema non vincolato il cui numero di variabili è il numero originale di variabili più il numero originale di vincoli di uguaglianza. In alternativa, se i vincoli sono tutti di uguaglianza e sono tutti lineari, possono essere risolti per alcune delle variabili in termini delle altre, e le prime possono essere sostituite dalla funzione obiettivo, lasciando un problema non vincolato in un numero minore di variabili.
Vincoli di disuguaglianzaModifica
Con i vincoli di disuguaglianza, il problema può essere caratterizzato in termini di condizioni di ottimalità geometrica, condizioni di Fritz John e condizioni di Karush-Kuhn-Tucker, sotto le quali problemi semplici possono essere risolvibili.
Programmazione lineareModifica
Se la funzione obiettivo e tutti i vincoli rigidi sono lineari e alcuni vincoli rigidi sono disuguaglianze, allora il problema è un problema di programmazione lineare. Questo può essere risolto con il metodo simplex, che di solito funziona in tempo polinomiale nella dimensione del problema, ma non è garantito, o con i metodi dei punti interni che sono garantiti per lavorare in tempo polinomiale.
Programmazione non lineareModifica
Se la funzione obiettivo o alcuni dei vincoli sono non lineari, e alcuni vincoli sono disuguaglianze, allora il problema è un problema di programmazione non lineare.
Programmazione quadraticaModifica
Se tutti i vincoli rigidi sono lineari e alcuni sono disuguaglianze, ma la funzione obiettivo è quadratica, il problema è un problema di programmazione quadratica. È un tipo di programmazione non lineare. Può ancora essere risolto in tempo polinomiale con il metodo dell’ellissoide se la funzione obiettivo è convessa; altrimenti il problema può essere NP hard.
Condizioni KKTModifica
Ammettendo vincoli di disuguaglianza, l’approccio KKT alla programmazione non lineare generalizza il metodo dei moltiplicatori di Lagrange. Può essere applicato in condizioni di differenziabilità e convessità.
Branch and boundEdit
L’ottimizzazione dei vincoli può essere risolta con algoritmi branch-and-bound. Questi sono algoritmi di backtracking che memorizzano il costo della migliore soluzione trovata durante l’esecuzione e lo usano per evitare parte della ricerca. Più precisamente, ogni volta che l’algoritmo incontra una soluzione parziale che non può essere estesa per formare una soluzione di costo migliore del costo migliore memorizzato, l’algoritmo torna indietro, invece di cercare di estendere questa soluzione.
Assumendo che il costo debba essere minimizzato, l’efficienza di questi algoritmi dipende da come viene valutato il costo che può essere ottenuto estendendo una soluzione parziale. Infatti, se l’algoritmo può fare marcia indietro da una soluzione parziale, una parte della ricerca viene saltata. Più basso è il costo stimato, migliore è l’algoritmo, poiché un costo stimato più basso è più probabile che sia inferiore al miglior costo della soluzione trovata finora.
D’altra parte, questo costo stimato non può essere inferiore al costo effettivo che può essere ottenuto estendendo la soluzione, poiché altrimenti l’algoritmo potrebbe fare marcia indietro mentre esiste una soluzione migliore di quella trovata finora. Di conseguenza, l’algoritmo richiede un limite superiore sul costo che può essere ottenuto dall’estensione di una soluzione parziale, e questo limite superiore dovrebbe essere il più piccolo possibile.
Una variazione di questo approccio chiamato metodo di Hansen utilizza metodi di intervallo. Implementa intrinsecamente i vincoli rettangolari.
Funzioni di delimitazione di prima sceltaModifica
Un modo per valutare questo limite superiore per una soluzione parziale è considerare ogni vincolo soft separatamente. Per ogni vincolo soft, si assume il massimo valore possibile per ogni assegnazione alle variabili non assegnate. La somma di questi valori è un limite superiore perché i vincoli soft non possono assumere un valore superiore. È esatto perché i valori massimi dei vincoli soft possono derivare da diverse valutazioni: un vincolo soft può essere massimo per x = a {\displaystyle x=a}
mentre un altro vincolo è massimo per x = b {\displaystyle x=b}
.
Ricerca della bambola russaModifica
Questo metodo esegue un algoritmo branch-and-bound su n {displaystyle n}
problemi, dove n {displaystyle n}
è il numero di variabili. Ogni problema di questo tipo è il sottoproblema ottenuto eliminando una sequenza di variabili x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}
dal problema originale, insieme ai vincoli che li contengono. Dopo il problema sulle variabili x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
è risolto, il suo costo ottimale può essere usato come upper bound durante la risoluzione degli altri problemi,
In particolare, la stima del costo di una soluzione avente x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
come variabili non assegnate si aggiunge al costo che deriva dalle variabili valutate. Praticamente, questo corrisponde a ignorare le variabili valutate e risolvere il problema su quelle non assegnate, tranne che quest’ultimo problema è già stato risolto. Più precisamente, il costo dei vincoli soft contenenti sia variabili assegnate che non assegnate viene stimato come sopra (o usando un altro metodo arbitrario); il costo dei vincoli soft contenenti solo variabili non assegnate viene invece stimato usando la soluzione ottimale del problema corrispondente, che a questo punto è già nota.
C’è somiglianza tra il metodo Russian Doll Search e la Programmazione Dinamica. Come la Programmazione Dinamica, la Ricerca della Bambola Russa risolve i sottoproblemi per risolvere l’intero problema. Ma, mentre la Programmazione Dinamica combina direttamente i risultati ottenuti sui sottoproblemi per ottenere il risultato dell’intero problema, Russian Doll Search li usa solo come limiti durante la sua ricerca.
Eliminazione del secchioModifica
L’algoritmo di eliminazione del secchio può essere adattato all’ottimizzazione dei vincoli. Una data variabile può essere effettivamente rimossa dal problema sostituendo tutti i vincoli soft che la contengono con un nuovo vincolo soft. Il costo di questo nuovo vincolo è calcolato assumendo un valore massimo per ogni valore della variabile rimossa. Formalmente, se x {displaystyle x}
è la variabile da rimuovere, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
sono i vincoli soft che la contengono, e y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
sono le loro variabili tranne x {\displaystyle x}
, il nuovo vincolo soft è definito da: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}
L’eliminazione del bucket funziona con un ordine (arbitrario) delle variabili. Ad ogni variabile è associato un secchio di vincoli; il secchio di una variabile contiene tutti i vincoli che hanno la variabile più alta nell’ordine. L’eliminazione del secchio procede dall’ultima variabile alla prima. Per ogni variabile, tutti i vincoli del bucket sono sostituiti come sopra per eliminare la variabile. Il vincolo risultante viene quindi collocato nel secchio appropriato.