Quadratic pseudo-Boolean optimization

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form : f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) in the binary variables x_p \in \{0, 1\} \; \forall p \in V = \{1, \dots, n\} , with E \subseteq V \times V . If f is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if f contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in polynomial time. QPBO is a useful tool for inference on Markov random fields and conditional random fields, and has applications in computer vision problems such as image segmentation and stereo matching.

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) in the binary variables x_p \in \{0, 1\} \; \forall p \in V = \{1, \dots, n\} , with E \subseteq V \times V .

If f is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if f contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in polynomial time. QPBO is a useful tool for inference on Markov random fields and conditional random fields, and has applications in computer vision problems such as image segmentation and stereo matching.

Partial optimality: if f is submodular, then QPBO produces a global minimum exactly, equivalent to graph cut, and all variables have a non-undefined value; if submodularity is not satisfied, the result will be a partial solution \mathbf{x} where a subset \hat{V} \subseteq V of the variables have a non-undefined value. A partial solution is always part of a global solution, i.e. there exists a global minimum point \mathbf{x^*} for f such that x_i = x_i^* for each i \in \hat{V} .

Persistence: given a solution \mathbf{x} generated by QPBO and an arbitrary assignment of values \mathbf{y} to the variables, if a new solution \hat{\mathbf{y}} is constructed by replacing y_i with x_i for each i \in \hat{V} , then f(\hat{\mathbf{y}}) \le f(\mathbf{y}) .

Notes

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1320606498 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001320606498 · captured 1762367224.0 · version history

Cite this page as: encyclopegia.org, “Quadratic pseudo-Boolean optimization”, snapshot enwiki-001320606498. https://encyclopegia.org/a/quadratic-pseudo-boolean-optimization

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.