Weak duality

<h2 id="uses">Uses</h2>
<p>Many primal-dual <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> are based on the principle of weak duality.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="weak-duality-theorem">Weak duality theorem</h2>
<p>Consider a <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> problem, 
</p>
<table><tbody><tr><td>                                                                                                              maximize                                          x                      ∈                                                                        R                                                                          n                                                                                                                                                                                  c                                      ⊤                                                  x                                                                                      subject to                                                                            A                x                ≤                b                ,                                                                                  x                ≥                0                ,                                                          {\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b,\\&x\geq 0,\end{aligned}}}  </td> <td></td> <td>1</td></tr></tbody></table>
<p>where 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is 
  
    
      
        m
        ×
        n
      
    
    {\displaystyle m\times n}
  
 and 
  
    
      
        b
      
    
    {\displaystyle b}
  
 is 
  
    
      
        m
        ×
        1
      
    
    {\displaystyle m\times 1}
  
. The <i>dual</i> problem of (1) is
</p>
<table><tbody><tr><td><p>                                                                                                              minimize                                          y                      ∈                                                                        R                                                                          m                                                                                                                                                                                  b                                      ⊤                                                  y                                                                                      subject to                                                                                              A                                      ⊤                                                  y                ≥                c                ,                                                                                  y                ≥                0.                                                          {\displaystyle {\begin{aligned}{\underset {y\in \mathbb {R} ^{m}}{\text{minimize}}}\quad &b^{\top }y\\{\text{subject to}}\quad &A^{\top }y\geq c,\\&y\geq 0.\end{aligned}}}  </p></td> <td></td> <td>2</td></tr></tbody></table>
<p>The weak duality theorem states that 
  
    
      
        
          c
          
            ⊤
          
        
        
          x
          
            ∗
          
        
        ≤
        
          b
          
            ⊤
          
        
        
          y
          
            ∗
          
        
      
    
    {\displaystyle c^{\top }x^{*}\leq b^{\top }y^{*}}
  
 for every solution 
  
    
      
        
          x
          
            ∗
          
        
      
    
    {\displaystyle x^{*}}
  
 to the primal problem (1) and every solution 
  
    
      
        
          y
          
            ∗
          
        
      
    
    {\displaystyle y^{*}}
  
 to the dual problem (2).
</p><p>Namely, if 
  
    
      
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        ,
        .
        .
        .
        .
        ,
        
          x
          
            n
          
        
        )
      
    
    {\displaystyle (x_{1},x_{2},....,x_{n})}
  
 is a feasible solution for the primal maximization <a href="/facts/Linear_program/GduXFQxT">linear program</a> and 
  
    
      
        (
        
          y
          
            1
          
        
        ,
        
          y
          
            2
          
        
        ,
        .
        .
        .
        .
        ,
        
          y
          
            m
          
        
        )
      
    
    {\displaystyle (y_{1},y_{2},....,y_{m})}
  
 is a feasible solution for the dual minimization linear program, then the weak duality theorem can be stated as

∑
          
            j
            =
            1
          
          
            n
          
        
        
          c
          
            j
          
        
        
          x
          
            j
          
        
        ≤
        
          ∑
          
            i
            =
            1
          
          
            m
          
        
        
          b
          
            i
          
        
        
          y
          
            i
          
        
      
    
    {\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}}
  
, where 
  
    
      
        
          c
          
            j
          
        
      
    
    {\displaystyle c_{j}}
  
 and 
  
    
      
        
          b
          
            i
          
        
      
    
    {\displaystyle b_{i}}
  
 are the coefficients of the respective objective functions.
</p><p>Proof:

cTx 
= xTc
≤ xT<i>A</i>Ty
≤ bTy

</p>
<h3>Generalizations</h3>
<p>More generally, if 
  
    
      
        x
      
    
    {\displaystyle x}
  
 is a feasible solution for the primal maximization problem and 
  
    
      
        y
      
    
    {\displaystyle y}
  
 is a feasible solution for the dual minimization problem, then weak duality implies 
  
    
      
        f
        (
        x
        )
        ≤
        g
        (
        y
        )
      
    
    {\displaystyle f(x)\leq g(y)}
  
 where 
  
    
      
        f
      
    
    {\displaystyle f}
  
 and 
  
    
      
        g
      
    
    {\displaystyle g}
  
 are the objective functions for the primal and dual problems respectively.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Convex_optimization/7D6U4MTN">Convex optimization</a></li>
<li><a href="/facts/Max%25E2%2580%2593min_inequality/48pXX4sN">Max–min inequality</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Boyd, S. P., Vandenberghe, L. (2004). Convex optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. <a href="978-0-521-83378-3" target="_blank">978-0-521-83378-3</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR 2542013. <a href="978-3-642-02885-4" target="_blank">978-3-642-02885-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749. <a href="9781420010749" target="_blank">9781420010749</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Weak duality open-in-new

Weak duality