Strong duality

<h2 id="sufficient-conditions">Sufficient conditions</h2>
<p>Each of the following conditions is sufficient for strong duality to hold:
</p>
<ul><li>
  
    
      
        F
        =
        
          F
          
            ∗
            ∗
          
        
      
    
    {\displaystyle F=F^{**}}
  
 where 
  
    
      
        F
      
    
    {\displaystyle F}
  
 is the <a href="/facts/Perturbation_function/nD2oGPlj">perturbation function</a> relating the primal and dual problems and 
  
    
      
        
          F
          
            ∗
            ∗
          
        
      
    
    {\displaystyle F^{**}}
  
 is the <a href="/facts/Convex_conjugate/DGDWBrDL">biconjugate</a> of 
  
    
      
        F
      
    
    {\displaystyle F}
  
 (follows by construction of the <a href="/facts/Duality_gap/xwCQ15DL">duality gap</a>)</li>
<li>
  
    
      
        F
      
    
    {\displaystyle F}
  
 is convex and lower <a href="/facts/Semi-continuity/4unJbWdW">semi-continuous</a> (equivalent to the first point by the <a href="/facts/Fenchel%25E2%2580%2593Moreau_theorem/PP3KnpNF">Fenchel–Moreau theorem</a>)</li>
<li>the primal problem is a <a href="/facts/Linear_optimization/GduXFQxT">linear optimization problem</a></li>
<li><a href="/facts/Slater%2527s_condition/m31PPgAy">Slater's condition</a> for a <a href="/facts/Convex_optimization/7D6U4MTN">convex optimization problem</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li></ul>
<h2 id="strong-duality-and-computational-complexity">Strong duality and computational complexity</h2>
<p>Under certain conditions (called "constraint qualification"), if a problem is polynomial-time solvable, then it has strong duality (in the sense of <a href="/facts/Lagrangian_duality/lXqeKfnK">Lagrangian duality</a>). It is an open question whether the opposite direction also holds, that is, if strong duality implies polynomial-time solvability.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Convex_optimization/7D6U4MTN">Convex optimization</a></li>
<li><a href="/facts/Linear_programming/GduXFQxT">Linear programming#Duality</a></li>
<li><a href="/facts/Dual_linear_program/Qm3r26pm">Dual linear program</a></li></ul>

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

<ol>
<li id="fn:1"><p>Borwein, Jonathan; Lewis, Adrian (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples (2 ed.). Springer. ISBN 978-0-387-29570-1. <a href="978-0-387-29570-1" target="_blank">978-0-387-29570-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 3, 2011. <a href="978-0-521-83378-3" target="_blank">978-0-521-83378-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv:1012.5568 [math.OC]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Strong duality open-in-new

Strong duality