Approximate complementary slackness: $(\alpha,\beta)$-slack feasible pairs are $\alpha\beta$-close

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 2 — approx_complementary_slackness

For every pair of finite index types $I, J$, every real matrix $A$ and every $b, c, x, y$ as above, and additionally two real numbers $\alpha, \beta$, assume the six hypotheses

1. $1 \le \alpha$;
2. $1 \le \beta$;
3. (primal feasibility of $x$) $\forall j \in J: b_j \le \sum_{i \in I} A_{i,j} x_i$, and $\forall i \in I: 0 \le x_i$;
4. (dual feasibility of $y$) $\forall i \in I: \sum_{j \in J} A_{i,j} y_j \le c_i$, and $\forall j \in J: 0 \le y_j$;
5. ($\alpha$-approximate primal complementary slackness) for every $i \in I$ with $x_i > 0$ (strictly), both

$$\frac{c_i}{\alpha} \;\le\; \sum_{j \in J} A_{i,j}\, y_j \qquad\text{and}\qquad \sum_{j \in J} A_{i,j}\, y_j \;\le\; c_i;$$

6. ($\beta$-approximate dual complementary slackness) for every $j \in J$ with $y_j > 0$ (strictly), both

$$b_j \;\le\; \sum_{i \in I} A_{i,j}\, x_i \qquad\text{and}\qquad \sum_{i \in I} A_{i,j}\, x_i \;\le\; \beta\, b_j .$$

Then the conclusion is

$$\sum_{i \in I} c_i x_i \;\le\; (\alpha \beta) \cdot \sum_{j \in J} b_j y_j ,$$

i.e. the primal objective is at most the product $\alpha\beta$ times the dual objective (the product is formed first and then multiplied by the dual objective).

Points of literal detail. The two complementary-slackness hypotheses are conditioned on strict positivity: indices $i$ with $x_i = 0$ and indices $j$ with $y_j = 0$ are entirely unconstrained by them (and by nonnegativity, $x_i < 0$, $y_j < 0$ cannot occur). Hypothesis 5 is stated with a division, $c_i/\alpha$; since $\alpha \ge 1$, the divisor is nonzero, so no division-by-zero convention is in play. The upper bound in hypothesis 5, $\sum_j A_{i,j} y_j \le c_i$, is already asserted for all $i$ by dual feasibility (hypothesis 4), and the lower bound in hypothesis 6, $b_j \le \sum_i A_{i,j} x_i$, is already asserted for all $j$ by primal feasibility (hypothesis 3); the two clauses therefore repeat, on the positive coordinates, conditions the feasibility hypotheses impose everywhere.

Degenerate readings. At $\alpha = 1$ the primal clause reads $c_i \le \sum_j A_{i,j} y_j \le c_i$, i.e. exact equality $\sum_j A_{i,j} y_j = c_i$ for every $i$ with $x_i > 0$; at $\beta = 1$ the dual clause reads $b_j \le \sum_i A_{i,j} x_i \le b_j$, i.e. $\sum_i A_{i,j} x_i = b_j$ for every $j$ with $y_j > 0$. At $\alpha = \beta = 1$ the conclusion reads $\sum_i c_i x_i \le \sum_j b_j y_j$, the reverse inequality of Statement 1's conclusion. If $I$ is empty, the primal objective is $0$, hypotheses 4-first-clause and 5 are vacuous, primal feasibility reduces to $b_j \le 0$ for all $j$, and the conclusion reduces to $0 \le \alpha\beta \sum_j b_j y_j$. If $J$ is empty, the dual objective is $0$ and the conclusion reduces to $\sum_i c_i x_i \le 0$; in that case hypothesis 5 says, for each $i$ with $x_i > 0$, that $c_i/\alpha \le 0$ and $0 \le c_i$, which together with $\alpha \ge 1$ forces $c_i = 0$. Nothing rules out $b_j < 0$ or $c_i < 0$, so the products $\beta b_j$ and $c_i / \alpha$ may be negative and the scaled bounds are then weaker, not stronger, than the unscaled ones.

---