Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 20:34, 22 lug 2019

Versione attuale delle 09:22, 18 mar 2025

(7 versioni intermedie di 6 utenti non mostrate)

Riga 1:

'''Quadratic pseudo-Boolean optimisation''' ('''QPBO''') è un metodo di [[ottimizzazione (matematica)|ottimizzazione]] discreta di [[funzione pseudo-booleana|funzioni pseudo-booleane]] quadratiche non [[Funzione_pseudoFunzione pseudo-booleana#Submodularità|submodulari]] nella forma

:<math> f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) </math>

Riga 9:

== Ottimizzazione di funzioni non submodulari ==

Se i coefficienti <math>w_{pq}</math> dei termini quadratici soddifano la condizione di submodularità

:<math> w_{pq}(0, 0) + w_{pq}(1, 1) \le w_{pq}(0, 1) + w_{pq}(1, 0) </math>

allora la funzione può essere ottimizzata tramite [[graph cut]]. È infatti possibile rappresentarla tramite un [[grafo]] a pesi non negativi, e il minimo globale può essere determinato in tempo polinomiale tramite un taglio minimo del grafo, che può essere calcolato efficientemente con algoritmi come quelli di [[algoritmo di Ford-Fulkerson|Ford-Fulkerson]], [[algoritmo di Edmonds-Karp|Edmonds-Karp]], e [[algoritmo di Boykov-Kolmogorov|Boykov-Kolmogorov]].

Se la condizione di submodularità non è soddisfatta, il problema nel caso generale è [[NP-hard]] e non può sempre essere risolto esattamente in tempo polinomiale con un semplice graph cut. È possibile approssimare la [[funzione obiettivo]] con una funzione simile, ma submodulare, ad esempio eliminando i termini non submodulari o sostituendoli con un'approssimazione submodulare, ma tale approccio produce generalmente risultati sub-ottimali la cui qualità è accettabile solo se il numero di termini non submodulari è relativamente piccolo.<ref name="review" />

Riga 23:

* ''Ottimalità parziale'': se <math>f</math> è submodulare, QPBO calcola il minimo globale esatto in maniera equivalente a graph cut e tutte le variabili nella soluzione assumono un valore non indefinito, mentre se la condizione di submodularità non è soddisfatta il risultato sarà una soluzione parziale <math>\mathbf{x}</math> nella quale solo per un sottinsieme <math>\hat{V} \subseteq V</math> delle variabili assume un valore non indefinito. Tale soluzione parziale è sempre parte di una soluzione ottimale, ovvero esiste un punto di minimo globale <math>\mathbf{x^*}</math> di <math>f</math> tale che <math>x_i = x_i^*</math> per ogni <math>i \in \hat{V}</math>.

* ''Persistenza'': dati una soluzione <math>\mathbf{x}</math> prodotta da QPBO e un qualsiasi assegnamento di valori <math>\mathbf{y}</math> alle variabili del problema, se si costruisce una nuova soluzione <math>\hat{\mathbf{y}}</math> sostituendo <math>y_i</math> con <math>x_i</math> per ogni <math>i \in \hat{V}</math>, si ha <math>f(\hat{\mathbf{y}}) \le f(\mathbf{y})</math>.<ref name="review" />

Riga 45 ⟶ 44:

== Termini di ordine superiore ==

L'ottimizzazione di funzioni pseudo-booleane di ordine superiore, ovvero contenenti termini dipendenti da tre o più variabili, è in generale un problema difficile. È sempre possibile ridurre in tempo polinomiale una [[funzione di ordine superiore]] a una funzione quadratica equivalente rispetto al problema di ottimizzazione (problema noto come ''higher-order [[cricca (teoria dei grafi)|clique]] reduction'', HOCR), e il risultato di tale riduzione può essere ottimizzato con QPBO. Metodi generali per la riduzione di funzioni arbitrarie sono basati su opportune tecniche di sostituzione di sotto-espressioni e in generale richiedono l'introduzione di variabili ausiliarie.<ref name="fix" /> In pratica, per la maggior parte dei termini di ordine superiore è possibile calcolare in maniera esatta una riduzione senza aggiunta di variabili ausiliarie, risultando in un problema di ottimizzazione più semplice; per i restanti termini irriducibili è possibile calcolare una riduzione esatta con metodi più generali, aggiungendo variabili ausiliarie, oppure eseguendo una riduzione approssimata senza aggiungere nuove variabili.<ref name="elc" />

== Note ==

Riga 74 ⟶ 73:

== Bibliografia ==

* {{cita pubblicazione|autore1=Alain Billionnet, Brigitte Jaumard|titolo=A decomposition method for minimizing quadratic pseudo-boolean functions|url=https://archive.org/details/sim_operations-research-letters_1989-06_8_3/page/161|rivista=Operations Research Letters|volume=8|numero=3|editore=Elsevier|pp=161–163161-163|anno=1989|cid=billionnet}}

* {{cita conferenza|autore1=Alexander Fix|autore2=Aritanan Gruber|autore3=Endre Boros|autore4=Ramin Zabih|rivista=A graph cut algorithm for higher-order Markov random fields|conferenza=IEEE International Conference on Computer Vision|anno=2011|pp=1020–10271020-1027|cid=fix}}

* {{cita conferenza|autore=Hiroshi Ishikawa|titolo=Higher-Order Clique Reduction Without Auxiliary Variables|conferenza=IEEE Conference on Computer Vision and Pattern Recognition|anno=2014|editore=IEEE|pp=1362-1269|cid=elc}}

* {{cita pubblicazione|autore1=Vladimir Kolmogorov|autore2=Carsten Rother|titolo=Minimizing Nonsubmodular Functions: A Review|rivista=IEEE Transactions on Pattern Analysis and Machine Intelligence|volvolume=29|nonumero=7|mese=luglio|anno=2007|pp=1274-1279|editore=IEEE|cid=review}}

* {{cita conferenza|autore1=Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, Martin Szummer|titolo=Optimizing binary MRFs via extended roof duality|conferenza=IEEE Conference on Computer Vision and Pattern Recognition|pp=1–81-8|anno=2007|cid=rother}}

== Collegamenti esterni ==