Quadratic pseudo-Boolean optimization

Quadratic pseudo-Boolean optimisation (QPBO) is a <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> method for minimizing quadratic <a href="/facts/Pseudo-Boolean_function/U0zWqAL8">pseudo-Boolean functions</a> in the form

f
        (
        
          x
        
        )
        =
        
          w
          
            0
          
        
        +
        
          ∑
          
            p
            ∈
            V
          
        
        
          w
          
            p
          
        
        (
        
          x
          
            p
          
        
        )
        +
        
          ∑
          
            (
            p
            ,
            q
            )
            ∈
            E
          
        
        
          w
          
            p
            q
          
        
        (
        
          x
          
            p
          
        
        ,
        
          x
          
            q
          
        
        )
      
    
    {\displaystyle 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 <a href="/facts/Binary_data/PSFa5S2Q">binary variables</a> 
 
 
 
 
 x
 
 p
 
 
 ∈
 {
 0
 ,
 1
 }
 
 ∀
 p
 ∈
 V
 =
 {
 1
 ,
 …
 ,
 n
 }
 
 
 {\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}}
 
, with 
 
 
 
 E
 ⊆
 V
 ×
 V
 
 
 {\displaystyle E\subseteq V\times V}
 
. If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is <a href="/facts/Pseudo-Boolean_function/U0zWqAL8">submodular</a> then QPBO produces a global optimum equivalently to <a href="/facts/Graph_cut_optimization/BHn61p1N">graph cut optimization</a>, while if 
 
 
 
 f
 
 
 {\displaystyle f}
 
 contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.
QPBO is a useful tool for inference on <a href="/facts/Markov_random_field/DJazwaeP">Markov random fields</a> and <a href="/facts/Conditional_random_field/TNuLaGzM">conditional random fields</a>, and has applications in <a href="/facts/Computer_vision/Tl2Yyk66">computer vision</a> problems such as <a href="/facts/Image_segmentation/jofAhbxa">image segmentation</a> and <a href="/facts/Stereo_cameras/gyYagbWd">stereo matching</a>.

Quadratic pseudo-Boolean optimization open-in-new

Quadratic pseudo-Boolean optimization