Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 14:01, 13 January 2019

Revision as of 17:16, 14 January 2019

Line 13:

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

then the function can be efficiently optimised with [[graph cut optimization]]. It is indeed possible to represent is with a non-negative weighted [[graph (discrete mathematics)|graph]], and the global minimum can be found in polynomial time by computing a [[minimum cut]] of the graph, which can be computed with algorithms such as [[Ford-FulkersonFord–Fulkerson algorithm|Ford-FulkersonFord–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds-KarpEdmonds–Karp]], and [[Boykov-KolmogorovBoykov–Kolmogorov algorithm|Boykov-KolmogorovBoykov–Kolmogorov]]'s.

If the function is not submodular, then the problem is [[NP-hard]] in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small. <ref name="review" />

Line 59:

* {{cite journal|first1=Alain|last1=Billionnet|first2=Brigitte|last2=Jaumard|title=A decomposition method for minimizing quadratic pseudo-boolean functions|journal=Operations Research Letters|volume=8|number=3|publisher=Elsevier|pages=161–163|year=1989}}

* {{cite conference|first1=Alexander|last1=Fix|first2=Aritanan|last2=Gruber|first3=Endre|last3=Boros|first4=Ramin|last4=Zabih|title=A graph cut algorithm for higher-order Markov random fields|conference=IEEE International Conference on Computer Vision|year=2011|pages=1020–1027}}

* {{cite conference|first1=Hiroshi|last1=Ishikawa|title=Higher-Order Clique Reduction Without Auxiliary Variables|conference=IEEE Conference on Computer Vision and Pattern Recognition|year=2014|publisher=IEEE|pages=1362-12691362–1269}}

* {{cite journal|first1=Vladimir|last1=Kolmogorov|first2=Carsten|last2=Rother|title=Minimizing Nonsubmodular Functions: A Review|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=29|number=7|year=2007|pages=1274-12791274–1279|publisher=IEEE}}

* {{cite conference|first1=Carsten|last1=Rother|first2=Vladimir|last2=Kolmogorov|first3=Victor|last3=Lempitsky|first4=Martin|last4=Szummer|title=Optimizing binary MRFs via extended roof duality|conference=IEEE Conference on Computer Vision and Pattern Recognition|pages=1–8|year=2007}}

Line 76:

#* <math>w_q^j</math> with <math>w_q^j + a</math>

#: where <math>a = \min \{ w_{pq}^{0j}, w_{pq}^{1j} \}</math>;

# for each <math>p = 1, \dots, n</math>, substitute:

#* <math>w_0</math> with <math>w_0 + a</math>

#* <math>w_p^0</math> with <math>w_p^0 - a</math>