Relaxation (approximation) explained

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 R ^{n} \}

is another minimization problem of the form

z _{R} = min \{c _{R(x)} : x \in X _{R} \subseteq 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 ^{*)\geq} _{R(x} 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

• Book: Buttazzo . Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations . Pitman Res. Notes in Math. 207. Longmann. Harlow . 1989.
• Geoffrion . A. M. . Duality in Nonlinear Programming: A Simplified Applications-Oriented Development. SIAM Review . 13 . 1971 . 1 . 1–37 . 2028848.
• Goffin . J.-L.. The relaxation method for solving systems of linear inequalities. Mathematics of Operations Research. 5. 1980. 3. 388–414. 3689446. 10.1287/moor.5.3.388. 594854.
• Book: Minoux, M.. Mathematical programming: Theory and algorithms . A Wiley-Interscience Publication. John Wiley & Sons. Chichester. 1986. 978-0-471-90170-9 . 868279. Translated by Steven Vajda from Book: 1983 . Paris . Dunod . Programmation mathématique: Théorie et algorithmes . 2571910.
• Book: Murty, Katta G. . 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. John Wiley & Sons. New York. 1983. 978-0-471-09725-9. 720547.
• Book: Optimization. G. L.. Nemhauser. George L. Nemhauser. A. H. G.. Rinnooy Kan. M. J.. Todd. Handbooks in Operations Research and Management Science . 1. North-Holland Publishing Co.. Amsterdam. 1989. 978-0-444-87284-5 . 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);

• Book: Rardin, Ronald L.. Optimization in operations research. Prentice Hall. 1998. 978-0-02-398415-0.
• Book: Roubíček, T.. Relaxation in Optimization Theory and Variational Calculus. Walter de Gruyter. Berlin. 1997. 978-3-11-014542-7.