Weak duality for the finite covering/packing pair

Setting common to all three statements

All three statements are parameterized by two types $I$ and $J$ (arbitrary, in arbitrary universes) each carrying a finiteness assumption (a Fintype instance). Finiteness is what makes the sums below well-defined; nothing asserts that $I$ or $J$ is nonempty, so both are allowed to be empty, in which case sums indexed by them are $0$.

The data are four real-valued functions and one real matrix, all otherwise arbitrary (no sign, boundedness, or nondegeneracy assumptions on any of them):

• $A : I \times J \to \mathbb{R}$, written $A_{i,j}$;
• $b : J \to \mathbb{R}$, written $b_j$;
• $c : I \to \mathbb{R}$, written $c_i$;
• $x : I \to \mathbb{R}$, written $x_i$;
• $y : J \to \mathbb{R}$, written $y_j$.

Two quantities are named by the bundle's own definitions, and are expanded inline throughout:

$$\text{primal objective} \;=\; \sum_{i \in I} c_i x_i, \qquad \text{dual objective} \;=\; \sum_{j \in J} b_j y_j .$$

Each of the three declarations is stated with its proof omitted, so each asserts its conclusion without supplying any justification.

---

Statement 1 — weak_duality

For every pair of finite index types $I, J$, every real matrix $A$, and every $b : J \to \mathbb{R}$, $c : I \to \mathbb{R}$, $x : I \to \mathbb{R}$, $y : J \to \mathbb{R}$, assume the two hypotheses

• (primal feasibility of $x$) both of

$$\forall j \in J: \quad b_j \le \sum_{i \in I} A_{i,j}\, x_i \qquad\text{and}\qquad \forall i \in I: \quad 0 \le x_i;$$

• (dual feasibility of $y$) both of

$$\forall i \in I: \quad \sum_{j \in J} A_{i,j}\, y_j \le c_i \qquad\text{and}\qquad \forall j \in J: \quad 0 \le y_j .$$

Then the conclusion is that the dual objective is at most the primal objective:

$$\sum_{j \in J} b_j y_j \;\le\; \sum_{i \in I} c_i x_i .$$

Note on the directions as written: the primal constraints are lower bounds ($b_j \le \sum_i A_{i,j} x_i$, one per column index $j$), the dual constraints are upper bounds ($\sum_j A_{i,j} y_j \le c_i$, one per row index $i$), and both $x$ and $y$ are required componentwise nonnegative. The inequality asserted runs from the $b$-$y$ sum up to the $c$-$x$ sum, with non-strict $\le$.

Degenerate readings. If $I$ is empty, the primal objective is $0$ and the dual-feasibility constraint $\sum_j A_{i,j} y_j \le c_i$ is vacuous, while primal feasibility reduces to $b_j \le 0$ for all $j$ ($x$'s nonnegativity clause is also vacuous); the conclusion reduces to $\sum_{j} b_j y_j \le 0$. If $J$ is empty, the dual objective is $0$ and the primal constraint $b_j \le \sum_i A_{i,j} x_i$ is vacuous, while dual feasibility reduces to $0 \le c_i$ for all $i$; the conclusion reduces to $0 \le \sum_i c_i x_i$. If both are empty the conclusion is $0 \le 0$. No hypothesis here is unsatisfiable in general: $x = 0$, $y = 0$ satisfy both feasibility conditions whenever $b_j \le 0$ and $c_i \ge 0$ for all indices.

---