Relaxation technique (mathematics)
Encyclopedia
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 method
s of relaxation
, such as successive over-relaxation
(SOR); iterative methods of relaxation are used in solving problems in differential equation
s, linear least-squares, and linear programming
. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.
is another minimization problem of the form
with these two properties
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.
is an optimal solution of the original problem, then 
and 
.
Further
provides an upper bound on 
, which implies that 
.
If an optimal solution for the relaxed problem is feasible for the original problem, then it is optimal for the original problem.
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...
. A relaxation is an approximation
Approximation theory
In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby...
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
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
relaxation of an integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
problem removes the integrality constraint and so allows non-integer rational solutions. A Lagrangian relaxation
Lagrangian relaxation
In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem...
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
Branch and bound
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
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 method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
s of relaxation
Relaxation method
In numerical mathematics, relaxation methods are iterative methods for solving systems of equations, including nonlinear systems.Relaxation methods were developed for solving large sparse linear systems, which arose as finite-difference discretizations of differential equations...
, such as successive over-relaxation
Successive over-relaxation
In numerical linear algebra, the method of successive over-relaxation is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process.It was devised simultaneously by David...
(SOR); iterative methods of relaxation are used in solving problems in differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s, linear least-squares, and linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.
Definition
A relaxation of the minimization problem
is another minimization problem of the form
with these two properties
-
-
for all 
.
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 is an optimal solution of the original problem, then and .Further
provides an upper bound on , which implies that .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 relaxationLagrangian relaxationIn the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem...
- Semidefinite relaxation
- Surrogate relaxation and duality