Linear programming, why Lagrangian sets lower bound for the value function of original

Question

Suppose we have the following linear programming problem in standard form:

$$ \min c^Tx $$ $$ \text{s.t.}\quad Ax=b, x\ge 0 $$

Make the above problem unconstrained via the Lagrangian method, with multiplier $p$

$$\min c^Tx + p^T(b-Ax) $$ $$ \text{s.t.}\quad x\ge 0$$

My question:

Why does the relaxed (i.e. Lagrangian) problem's value function is weakly less than the value function of the original problem (see below)? Can someone explain this intuitively or geometrically?

$$h(p)=\min\,[c^Tx+p^T(b-Ax)]\,\leq\, c^Tx^*+p^T(b-Ax^*)=c^Tx^*$$

Answer 1

Let

$$ L(x, \lambda) := c^T x + \lambda(b-Ax) $$

then you can define a function $g$ with

$$ g(\lambda):= \min_{x\ge 0} L(x,\lambda) $$

and, by definition of this function, $g(\lambda) \le L(x,\lambda)$ for any $x\ge 0$ and any $\lambda$ (this follows from having the "min" in the definition of $g$)

Now the optimum for the initial problem (if it exists) verifies $x^*\ge 0$ so that it must verify the inequality:

$$ g(\lambda) \le L(x^*, \lambda) $$

Now, since it must also verifies $Ax^*=b$, you have $L(x^*,\lambda)=c^Tx^*$.

Making things explicit, you recover the inequality:

$$ \min_{x\ge0}\,\, [c^T+\lambda(b-Ax)] \le c^T x^*.$$

Answer 2

This is true for two reasons:

1. $c'x+p'(\underbrace{b-Ax}_{=0}) \le c' x $
2. $\{x\mid Ax=b,x \ge 0 \}\subset \{x\mid x \ge 0 \}$

In other words, the second formulation satisfies the definition of a relaxation, and the lower bound follows.

Answer 3

The following equivalent form allows a natural economical interpretation.

$$ \min c^\top x \\ s.t. \ \ A x \geq b, x \geq 0 $$

This form is similar to the famous "diet problem".

The vector x represents different types of food ingredients that must be bought in order to produce meals that satisfy basic nutritional requirements, represented by each row of $A x \geq b$.

In the diet problem, these would represent minimum amounts of calories, proteins, different vitamins, etc.

The producer wants to meet these requirements as cheaply as possible. While doing that, it could happen that some requirements are exceeded - for instance, the cheapest diet is tight on protein, but has spare vitamins, iron, etc, above the minimum amount.

Now, imagine that a vitamin company comes along and proposes to purchase for a positive price $p_i$ any excess nutrients $a_i x - b_i$ the producer might have ($a_i$ is the ith row of A).

Can you see that this business proposition is always beneficial to the producer? The income from excess nutrients possibly reduces the cost objective, while not increasing it. The worst it can happen is that we have zero prices for the nutrients in excess. In this case, the costs are the same.