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.

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. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.

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

1. $X_{R}\supseteq X$
2. $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

• Linear programming relaxation
• Lagrangian relaxation
• Semidefinite relaxation
• Surrogate relaxation and duality

References

• Buttazzo, G. (1989). Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations. Pitman Res. Notes in Math. 207. Harlow: Longmann.
• Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. JSTOR 2028848.
• 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.
• Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. Translated by Steven Vajda from Programmation mathématique: Théorie et algorithmes. Paris: Dunod. 1983. MR 2571910.
• 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.
• Nemhauser, G. L.; 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. 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);
• Rardin, Ronald L. (1998). Optimization in operations research. Prentice Hall. ISBN 978-0-02-398415-0.
• Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus. Berlin: Walter de Gruyter. ISBN 978-3-11-014542-7.