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

Definition

A relaxation of the minimization problem

$z=\min \{c(x):x\in X\subseteq {𝐑}^n\}$

is another minimization problem of the form

$z_R=\min \{c_R(x):x\in X_R\subseteq {𝐑}^n\}$

with these two properties

1. $X_R\supseteq X$
2. $c_R(x)\le 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^{*})\ge c_R(x^{*})\ge 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)$, $\mathrm{\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

• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite book Translated by Steven Vajda from Template:Cite book
• Template:Cite book
• Template:Cite book
  • 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);
• Template:Cite book
• Template:Cite book