Motivating Duality: Bounding the Primal Objective

The primal linear program in standard form is

$$\max\ \mathbf{c}^T \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0}.$$

Solving such an LP exactly can be expensive. A useful weaker question: can we cheaply produce an upper bound on the optimal objective value?

The simplest tactic is to scale a constraint. Take the $i$-th constraint, $\mathbf{a}_i^T \mathbf{x} \leq b_i.$ For any $y_i \geq 0,$ multiplying preserves the direction of the inequality:

$$y_i\, \mathbf{a}_i^T \mathbf{x} \leq y_i b_i.$$

We require $y_i \geq 0$ because a negative multiplier would flip $\leq$ to $\geq.$

If the scaled coefficient vector dominates $\mathbf{c}$ componentwise, i.e., $y_i\, \mathbf{a}_i \geq \mathbf{c},$ then since $\mathbf{x} \geq \mathbf{0},$

$$\mathbf{c}^T \mathbf{x} \leq y_i\, \mathbf{a}_i^T \mathbf{x} \leq y_i b_i.$$

Therefore $y_i b_i$ is a guaranteed upper bound on the primal objective at every feasible $\mathbf{x}$ — and hence on the optimal value.

For example, for $\max\ 2x_1 + 5x_2$ subject to $3x_1 + 10x_2 \leq 30,\ \mathbf{x} \geq \mathbf{0},$ choose $y_1 = 1.$ Since $3 \geq 2,$ $10 \geq 5,$ and $\mathbf{x} \geq \mathbf{0},$

$$2x_1 + 5x_2 \leq 3x_1 + 10x_2 \leq 30.$$

The optimal value is at most $30.$