Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 35

Lagrangian duality provides a particularly fruitful framework for relaxation. It works as follows:

 – choose an inequality in the LP and remove it from the LP;

 – add this inequality to the objective function with a multiplier that penalizes the objective function if the solution found does not satisfy the inequality.

This relaxation often produces a very good relaxation value, far better than continuous relaxation.

Consider the following LP:

[1.11]

To each constraint i ∈ I, we assign a real number λ_i ≥ 0 called the Lagrange multiplier. We also define the vector λ = (λ_i, 0 i ∈ I). The Lagrangian function is then defined as

This function has the two vector arguments x and λ and takes values in ℝ. Suppose that the PL is such that the problem min_x∈S (x, λ) has an optimal solution for every λ ≥ 0.

More details are given in Chapter 7. Now consider the following LP [FLE 10]:

[1.12]

We obtain the optimal solution (0, 1.1, 4.4)T, which gives the optimal cost as z* = 6.6.

By relaxing the third constraint (x₁ + x₂ ≥ 4.4) and keeping the integrality constraints on the variables xi, we obtain the following LP by adding the expression λ(4.4 − x₁ − x₃) to the objective function, where λ is the Lagrangian relaxation coefficient, which is updated at each iteration of the method:

[1.13]

The last constraint is added to bound the variables xi. This guarantees that the problem is bounded for every λ > 0. The coefficient λ is updated as follows: λ^k+1 = max It can be shown that λ tends to 1 and z tends to 8.4.