View source for C-theorem

In [[mathematical optimization]] and related fields, '''relaxation''' is a [[mathematical model|modeling strategy]].  A relaxation is an [[approximation theory|approximation]] of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.

For example, a [[linear programming]] relaxation of an [[integer programming]] problem  removes the integrality constraint and so allows non-integer rational solutions. A [[Lagrangian relaxation]] of a complicated problem in combinatorial optimization penalizes violations of some constraints, allowing an easier relaxed problem to be solved. Relaxation techniques complement or supplement [[branch and bound]] algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.<ref name="Geoff">{{harvtxt|Geoffrion|1971}}</ref>

The modeling strategy of relaxation should not be confused with [[iterative method]]s of [[relaxation method|relaxation]],  such as [[successive over-relaxation]] (SOR); iterative methods of relaxation are used in solving problems in [[partial differential equation|differential equation]]s, [[linear least squares (mathematics)|linear least-squares]], and [[linear programming]].<ref name="Murty">{{cite book|last=Murty|first=Katta&nbsp;G.|authorlink=Katta G. Murty|chapter=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)| title=Linear programming|publisher=John Wiley & Sons, Inc.|location=New York|year=1983|pages=453–464|isbn=0-471-09725-X|mr=720547|ref=harv}}</ref><ref>{{cite journal|last=Goffin|first=J.-L.|title=The relaxation method for solving systems of linear inequalities|journal=Math. Oper. Res.|volume=5|year=1980|number=3|pages=388–414|jstor=3689446|doi=10.1287/moor.5.3.388|mr=594854|ref=harv}}</ref><ref name="Minoux">{{cite book|last=Minoux|first=M.|authorlink=Michel Minoux|title=Mathematical programming: Theory and algorithms|note=With a foreword by Egon Balas|edition=Translated  by Steven Vajda from the (1983 Paris: Dunod) French|publisher=A Wiley-Interscience Publication. John Wiley & Sons, Ltd.|location=Chichester|year=1986|pages=xxviii+489|isbn=0-471-90170-9|mr=868279|ref=harv|id=(2008 Second ed., in French: ''Programmation mathématique: Théorie et algorithmes''. Editions Tec & Doc, Paris,  2008. xxx+711 pp. ISBN 978-2-7430-1000-3}}. {{MR|2571910}})</ref> However, iterative methods of relaxation have been used to solve Lagrangian relaxations.<ref>Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. {{harvtxt|Goffin|1980}} and {{harvtxt|Minoux|1986}}|loc=Section 4.3.7, pp. 120–123  cite [[Shmuel Agmon]] (1954), and [[Theodore Motzkin]] and [[Isaac Schoenberg]] (1954), and L. T. Gubin, [[Boris T. Polyak]], and E. V. Raik (1969).</ref>

== Definition ==
A ''relaxation'' of the minimization problem

: <math>z = \min \{c(x) : x \in X \subseteq \mathbf{R}^{n}\}</math>

is another minimization problem of the form

:<math>z_R = \min \{c_R(x) : x \in X_R \subseteq \mathbf{R}^{n}\}</math>

with these two properties

# <math>X_R \supseteq X</math>
# <math>c_R(x) \leq c(x)</math> for all <math>x \in X</math>.

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.<ref name="Geoff"/>

=== Properties===
If <math>x^*</math> is an optimal solution of the original problem, then <math>x^* \in X \subseteq X_R</math> and <math>z = c(x^*) \geq c_R(x^*)\geq z_R</math>. Therefore <math>x^* \in X_R</math> provides an upper bound on <math>z_R</math>.

If in addition to the previous assumptions, <math>c_R(x)=c(x)</math>, <math>\forall x\in X</math>, 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.<ref name="Geoff"/>

==Some relaxation techniques==
*[[Linear programming relaxation]]
*[[Lagrangian relaxation]]
<!-- NO this is an ITERATIVE METHOD, not a relaxation strategy,  *[[Successive over-relaxation]] -->
*[[Semidefinite relaxation]]
* [[Surrogate relaxation]] and [[surrogate duality|duality]]

==Notes==
<references/>

==References==
* {{cite article |last1=Geoffrion |first1=A. M. |title=Duality in Nonlinear Programming: A Simplified Applications-Oriented Development| url=http://www.jstor.org/pss/2028848 |journal=SIAM Review |volume=13 |year=1971 |number=1 |pages=1–37|jstor=2028848|ref=harv}}.

* {{cite journal|last=Goffin|first=J.-L.|title=The relaxation method for solving systems of linear inequalities|journal=Math. Oper. Res.|volume=5|year=1980|number=3|pages=388–414|jstor=3689446|doi=10.1287/moor.5.3.388|mr=594854|ref=harv}}

* {{cite book|last=Minoux|first=M.|authorlink=Michel Minoux|title=Mathematical programming: Theory and algorithms|note=With a foreword by Egon Balas|edition=Translated  by Steven Vajda from the (1983 Paris: Dunod) French|publisher=A Wiley-Interscience Publication. John Wiley & Sons, Ltd.|location=Chichester|year=1986|pages=xxviii+489|isbn=0-471-90170-9|mr=868279|ref=harv|id=(2008 Second ed., in French: ''Programmation mathématique: Théorie et algorithmes''. Editions Tec & Doc, Paris,  2008. xxx+711 pp. ISBN 978-2-7430-1000-3}}. {{MR|2571910}})|

* {{cite book|title=Optimization|editor1-first=G. L.|editor1-last=Nemhauser|editor1-link=George L. Nemhauser|editor2-first=A. H. G.|editor2-last=Rinnooy Kan|editor3-first=M. J.|editor3-last=Todd|editor3-link=Michael J. Todd (mathematician)|series=Handbooks in Operations Research and Management Science|volume=1|publisher=North-Holland Publishing Co.|location=Amsterdam|year=1989|pages=xiv+709|isbn=0-444-87284-1|mr=1105099|ref=harv}}
<!-- ** [[J. E. Dennis, Jr.]] and [[Robert B. Schnabel]], A view of unconstrained optimization (pp. 1–72);
** [[Donald Goldfarb]] and [[Michael J. Todd (mathematician)|Michael J. Todd]], Linear programming (pp. 73–170);
** Philip E. Gill, Walter Murray, Michael A. Saunders, and [[Margaret H. Wright]], Constrained nonlinear programming (pp. 171–210);
** [[Ravindra K. Ahuja]], [[Thomas L. Magnanti]], and [[James B. Orlin]], Network flows (pp. 211–369); -->
** [[W. R. Pulleyblank]], Polyhedral combinatorics (pp.&nbsp;371–446);
** George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp.&nbsp;447–527);
** [[Claude Lemaréchal]], Nondifferentiable optimization (pp.&nbsp;529–572);
<!-- ** [[Roger J-B Wets]], Stochastic programming (pp. 573–629);
** A. H. G. Rinnooy Kan and G. T. Timmer, Global optimization (pp. 631–662);
** P. L. Yu, Multiple criteria decision making: five basic concepts (pp. 663--699). -->

* {{cite book|title=Optimization in operations research|first=Ronald L.|last=Rardin|year=1997|publisher=Prentice Hall|copyright=1998|pages=919|isbn=0-02-398415-5}}

{{DEFAULTSORT:Relaxation (Approximation)}}
[[Category:Mathematical optimization]]
[[Category:Relaxation (approximation)| ]]
[[Category:Approximations]]