relaxation (approximation)

In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an 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.{{harvtxt|Geoffrion|1971}}

The modeling strategy of relaxation should not be confused with iterative methods of relaxation, such as successive over-relaxation (SOR); iterative methods of relaxation are used in solving problems in differential equations, linear least-squares, and linear programming.{{sfnp|Goffin|1980}}{{sfnp|Murty|1983|pp=453–464}}{{sfnp|Minoux|1986}} However, iterative methods of relaxation have been used to solve Lagrangian relaxations.{{efn|Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. {{sfnp|Goffin|1980}}{{sfnp|Minoux|1986|loc=Section 4.3.7, pp. 120–123}}Shmuel Agmon (1954)Theodore Motzkin and Isaac Schoenberg (1954)L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)}}

Definition

A relaxation of the minimization problem

: $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 \in X_R \subseteq \mathbf{R}^{n}\}$

with these two properties

$X_R \supseteq X$
$c_R(x) \leq c(x)$ for all $x \in X$ .

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.

= Properties=

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

If in addition to the previous assumptions, $c_R(x)=c(x)$ , $\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.

Some relaxation techniques

Notes

References

{{cite book|author=Buttazzo |first=G. |title = Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations |series=Pitman Res. Notes in Math. 207|publisher=Longmann|location=Harlow |year=1989}}
{{cite journal|last1=Geoffrion |first1=A. M. |title=Duality in Nonlinear Programming: A Simplified Applications-Oriented Development|journal=SIAM Review |volume=13 |year=1971 |number=1 |pages=1–37 |doi=10.1137/1013001 |jstor=2028848}}
{{cite journal

| last1=Goffin | first1=J.-L.

| title=The relaxation method for solving systems of linear inequalities

| journal=Mathematics of Operations Research

| volume=5

| date=1980

| number=3

| pages=388–414

| jstor=3689446

| doi=10.1287/moor.5.3.388

| mr=594854}}

{{cite book|last=Minoux|first=M.|title=Mathematical programming: Theory and algorithms |publisher=A Wiley-Interscience Publication. John Wiley & Sons|location=Chichester|year=1986|isbn=978-0-471-90170-9 |mr=868279}} Translated by Steven Vajda from {{cite book |year=1983 |place=Paris |publisher=Dunod |title=Programmation mathématique: Théorie et algorithmes |mr=2571910}}
{{cite book|last=Murty|first=Katta G. |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|location=New York|year=1983|isbn=978-0-471-09725-9|mr=720547}}
{{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|series=Handbooks in Operations Research and Management Science |volume=1|publisher=North-Holland Publishing Co.|location=Amsterdam|year=1989|isbn=978-0-444-87284-5 |mr=1105099}}

W. R. Pulleyblank, Polyhedral combinatorics (pp. 371–446);

George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);

Claude Lemaréchal, Nondifferentiable optimization (pp. 529–572);

{{cite book|title=Optimization in operations research|first=Ronald L.|last=Rardin|publisher=Prentice Hall|date=1998|isbn=978-0-02-398415-0}}

{{cite book|title=Relaxation in Optimization Theory and Variational Calculus|last=Roubíček|first=T.|publisher=Walter de Gruyter|location=Berlin|year=1997|isbn=978-3-11-014542-7}}

Category:Mathematical optimization

Category:Approximations