Lagrange relaxation

Remark

Here, we consider an optimization problem of the form where is some set and .

Remark

Constraints for a problem like can thus either be of the form or simply be encapsulated in . Constraints of the form are called explicit while the rest are called implicit. It is clear that any explicit constraint just as well can be made implicit, but for reasons we will see later we here distinguish between them.

Definition: Relaxed Lagrange problem

Given a with , the corresponding relaxed Lagrange problem with respect to the explicit contraints of is The elements of are called Lagrange multipliers.

We can see this as instead of having as a constraint, we make it contribute to the cost, so that breaking the constraint makes the solution more costly. This is the sense in which we "relax" the problem; some previously nonfeasible solutions might become feasible.

Definition: Lagrangian

The Lagrangian for is

Definition: Global optimality conditions

A pair satisfies the global optimality conditions whenever

  1. ,
  2. ,
  3. ,
  4. .
Theorem

Whenever satisfy the global optimality conditions, is optimal.

Proof:
By (4) we know , so by (1), and (3), for any , and is feasible since , so it is indeed optimal.

Definition: Dual objective function

The dual objective function for is

Theorem: Weak duality

If and , then .

Proof:
We have since and .

Definition: Dual problem

The dual problem to is

Lemma

If , , and , then and are optimal to and , respectively.

Proof:
For any , by the previous theorem we have so is optimal to , and for any we have so is optimal to .

Theorem

A pair satisfies the global optimality conditions for if and only if

  1. is optimal to ,
  2. is optimal to ,
  3. .

Proof:
: Suppose satisfy the global optimality conditions. Then, by a previous theorem, is optimal. Also, so by the previous lemma, is also optimal.
: Suppose (1)-(3) are satisfied. Then and by feasibility. Also, so from (3) we get and

Theorem

is a concave function on .

Proof:
Take and . Then