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.[1]
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.[2][3][4] However, iterative methods of relaxation have been used to solve Lagrangian relaxations.[lower-alpha 1]
Definition
A relaxation of the minimization problem
- [math]\displaystyle{ z = \min \{c(x) : x \in X \subseteq \mathbf{R}^{n}\} }[/math]
is another minimization problem of the form
- [math]\displaystyle{ z_R = \min \{c_R(x) : x \in X_R \subseteq \mathbf{R}^{n}\} }[/math]
with these two properties
- [math]\displaystyle{ X_R \supseteq X }[/math]
- [math]\displaystyle{ c_R(x) \leq c(x) }[/math] for all [math]\displaystyle{ 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.[1]
Properties
If [math]\displaystyle{ x^* }[/math] is an optimal solution of the original problem, then [math]\displaystyle{ x^* \in X \subseteq X_R }[/math] and [math]\displaystyle{ z = c(x^*) \geq c_R(x^*)\geq z_R }[/math]. Therefore, [math]\displaystyle{ x^* \in X_R }[/math] provides an upper bound on [math]\displaystyle{ z_R }[/math].
If in addition to the previous assumptions, [math]\displaystyle{ c_R(x)=c(x) }[/math], [math]\displaystyle{ \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.[1]
Some relaxation techniques
- Linear programming relaxation
- Lagrangian relaxation
- Semidefinite relaxation
- Surrogate relaxation and duality
Notes
- ↑ 1.0 1.1 1.2 (Geoffrion 1971)
- ↑ 2.0 2.1 Goffin (1980).
- ↑ Murty (1983), pp. 453–464.
- ↑ Minoux (1986).
- ↑ Minoux (1986), 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)
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.
- 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.
- Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. Translated by Steven Vajda from Programmation mathématique: Théorie et algorithmes. Paris: Dunod. 1983.
- 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.
- Nemhauser, G. L.; Rinnooy Kan, A. H. G.; Todd, M. J., eds (1989). Optimization. Handbooks in Operations Research and Management Science. 1. Amsterdam: North-Holland Publishing Co.. ISBN 978-0-444-87284-5.
- 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.
Original source: https://en.wikipedia.org/wiki/Relaxation (approximation).
Read more |