Relaxation (approximation)

<h2 id="definition">Definition</h2>
A relaxation of the minimization problem

z
        =
        min
        {
        c
        (
        x
        )
        :
        x
        ∈
        X
        ⊆
        
          
            R
          
          
            n
          
        
        }
      
    
    {\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}

is another minimization problem of the form

z
          
            R
          
        
        =
        min
        {
        
          c
          
            R
          
        
        (
        x
        )
        :
        x
        ∈
        
          X
          
            R
          
        
        ⊆
        
          
            R
          
          
            n
          
        
        }
      
    
    {\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}

with these two properties

<ol><li>
 
 
 
 
 X
 
 R
 
 
 ⊇
 X
 
 
 {\displaystyle X_{R}\supseteq X}
 
</li>
<li>
 
 
 
 
 c
 
 R
 
 
 (
 x
 )
 ≤
 c
 (
 x
 )
 
 
 {\displaystyle c_{R}(x)\leq c(x)}
 
 for all 
 
 
 
 x
 ∈
 X
 
 
 {\displaystyle x\in X}
 
.</li></ol>
The first property states that the original problem's feasible domain is a subset of the relaxed problem's feasible domain. The second property states that the original problem's objective-function is greater than or equal to the relaxed problem's objective-function.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h3>Properties</h3>
If 
 
 
 
 
 x
 
 ∗
 
 
 
 
 {\displaystyle x^{*}}
 
 is an optimal solution of the original problem, then 
 
 
 
 
 x
 
 ∗
 
 
 ∈
 X
 ⊆
 
 X
 
 R
 
 
 
 
 {\displaystyle x^{*}\in X\subseteq X_{R}}
 
 and 
 
 
 
 z
 =
 c
 (
 
 x
 
 ∗
 
 
 )
 ≥
 
 c
 
 R
 
 
 (
 
 x
 
 ∗
 
 
 )
 ≥
 
 z
 
 R
 
 
 
 
 {\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}
 
. Therefore, 
 
 
 
 
 x
 
 ∗
 
 
 ∈
 
 X
 
 R
 
 
 
 
 {\displaystyle x^{*}\in X_{R}}
 
 provides an upper bound on 
 
 
 
 
 z
 
 R
 
 
 
 
 {\displaystyle z_{R}}
 
.
If in addition to the previous assumptions, 
 
 
 
 
 c
 
 R
 
 
 (
 x
 )
 =
 c
 (
 x
 )
 
 
 {\displaystyle c_{R}(x)=c(x)}
 
, 
 
 
 
 ∀
 x
 ∈
 X
 
 
 {\displaystyle \forall x\in X}
 
, the following holds: If an optimal solution for the relaxed problem is feasible for the original problem, then it is optimal for the original problem.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="some-relaxation-techniques">Some relaxation techniques</h2>
<ul><li><a href="/facts/Linear_programming_relaxation/s26bWxAr">Linear programming relaxation</a></li>
<li><a href="/facts/Lagrangian_relaxation/bzP6jEup">Lagrangian relaxation</a></li>
<li>Semidefinite relaxation</li>
<li>Surrogate relaxation and duality</li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Buttazzo, G. (1989). Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations. Pitman Res. Notes in Math. 207. Harlow: Longmann.</li>
<li>Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F1013001">10.1137/1013001</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2028848">2028848</a>.</li>
<li>Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". <a href="/facts/Mathematics_of_Operations_Research/VWfG5pal">Mathematics of Operations Research</a>. 5 (3): 388–414. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1287%2Fmoor.5.3.388">10.1287/moor.5.3.388</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/3689446">3689446</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0594854">0594854</a>.</li>
<li>Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-90170-9. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0868279">0868279</a>. Translated by Steven Vajda from Programmation mathématique: Théorie et algorithmes. Paris: Dunod. 1983. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2571910">2571910</a>.</li>
<li>Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-09725-9. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0720547">0720547</a>.</li>
<li><a href="/facts/George_L._Nemhauser/wJ6yUBJS">Nemhauser, G. L.</a>; Rinnooy Kan, A. H. G.; Todd, M. J., eds. (1989). Optimization. Handbooks in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-87284-5. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1105099">1105099</a>.
<ul><li><a href="/facts/W._R._Pulleyblank/vC30DT70">W. R. Pulleyblank</a>, Polyhedral combinatorics (pp. 371–446);</li>
<li>George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);</li>
<li><a href="/facts/Claude_Lemar%25C3%25A9chal/aMcoIXVJ">Claude Lemaréchal</a>, Nondifferentiable optimization (pp. 529–572);</li></ul></li>
<li>Rardin, Ronald L. (1998). Optimization in operations research. Prentice Hall. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-02-398415-0.</li>
<li>Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus. Berlin: Walter de Gruyter. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-11-014542-7.</li></ul>

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

<ol>
<li id="fn:1">Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. <a href="https://doi.org/10.1137%2F1013001" target="_blank">https://doi.org/10.1137%2F1013001</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Goffin (1980). - Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Mathematics of Operations Research. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854. <a href="https://doi.org/10.1287%2Fmoor.5.3.388" target="_blank">https://doi.org/10.1287%2Fmoor.5.3.388</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Murty (1983), pp. 453–464. - Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. MR 0720547. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0720547" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0720547</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Minoux (1986). - Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0868279" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0868279</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. [2][5][6][7][8] <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. <a href="https://doi.org/10.1137%2F1013001" target="_blank">https://doi.org/10.1137%2F1013001</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. <a href="https://doi.org/10.1137%2F1013001" target="_blank">https://doi.org/10.1137%2F1013001</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Relaxation (approximation) open-in-new

Relaxation (approximation)