Read-back 3 — exact_cs_optimal

Setting and binders. Types $I$ and $J$, implicit and at arbitrary universes, each assumed finite (Fintype), with no nonemptiness assumption. Universally quantified data: a real matrix $A = (A_{i,j})_{i \in I, j \in J}$, vectors $b \in \mathbb{R}^{J}$, $c \in \mathbb{R}^{I}$, and candidate vectors $x \in \mathbb{R}^{I}$, $y \in \mathbb{R}^{J}$. No sign or structural hypothesis on $A$, $b$, $c$.

The four hypotheses, fully expanded.

1. $h_p$ — $x$ is primal-feasible: $\ b_j \le \sum_{i \in I} A_{i,j} x_i$ for every $j \in J$, and $0 \le x_i$ for every $i \in I$. (Feasibility only; no optimality is assumed of $x$.)
2. $h_d$ — $y$ is dual-feasible: $\ \sum_{j \in J} A_{i,j} y_j \le c_i$ for every $i \in I$, and $0 \le y_j$ for every $j \in J$. (Feasibility only.)
3. $h_{pcs}$ — the approximate-complementary-slackness predicate for the primal, with its parameter $\alpha$ instantiated at the literal $1$. Written out, it says: for every $i \in I$,

$$x_i > 0 \ \Longrightarrow\ \left( \frac{c_i}{1} \ \le\ \sum_{j \in J} A_{i,j} y_j \ \ \text{ and }\ \ \sum_{j \in J} A_{i,j} y_j \ \le\ c_i \right).$$

Since $c_i / 1 = c_i$, the two inequalities sandwich the same quantity from both sides, so at $\alpha = 1$ this hypothesis says exactly: for every index $i$ with $x_i$ strictly positive, the $i$-th dual row sum equals $c_i$, i.e. $\sum_{j} A_{i,j} y_j = c_i$ — the $i$-th dual constraint is tight. The upper inequality here duplicates what $h_d$ already gives for all $i$; the substantive content at $\alpha = 1$ is the lower inequality. The condition is triggered only by strictly positive coordinates: for any $i$ with $x_i = 0$ nothing at all is asserted about $\sum_j A_{i,j} y_j$ beyond dual feasibility. (Under $h_p$, coordinates of $x$ are $\ge 0$, so "$x_i > 0$" and "$x_i \ne 0$" coincide here; nevertheless the predicate as written keys on strict positivity.) 4. $h_{dcs}$ — the approximate-complementary-slackness predicate for the dual, with its parameter $\beta$ instantiated at the literal $1$. Written out: for every $j \in J$,

$$y_j > 0 \ \Longrightarrow\ \left( b_j \ \le\ \sum_{i \in I} A_{i,j} x_i \ \ \text{ and }\ \ \sum_{i \in I} A_{i,j} x_i \ \le\ 1 \cdot b_j \right).$$

Since $1 \cdot b_j = b_j$, at $\beta = 1$ this says exactly: for every index $j$ with $y_j$ strictly positive, the $j$-th primal constraint holds with equality, i.e. $\sum_{i} A_{i,j} x_i = b_j$. Here the lower inequality duplicates what $h_p$ already gives for all $j$; the substantive content is the upper inequality. Again only strictly positive coordinates trigger the condition: for $j$ with $y_j = 0$ nothing beyond primal feasibility is asserted about $\sum_i A_{i,j} x_i$.

So hypotheses 3 and 4 together are the exact (unrelaxed) complementary-slackness conditions in both directions, each conditioned on strict positivity of the corresponding coordinate of the other problem's... more precisely: positivity of $x_i$ forces tightness of dual constraint $i$, and positivity of $y_j$ forces tightness of primal constraint $j$. Nothing asserts that any coordinate is positive, so both hypotheses are vacuously satisfied when $x = 0$ and $y = 0$ respectively.

Conclusion — a conjunction of two optimality claims. The statement concludes that both of the following hold.

• $x$ is primal-optimal: $x$ is primal-feasible (as in $h_p$) and for every $x' \in \mathbb{R}^{I}$ satisfying $b_j \le \sum_{i} A_{i,j} x'_i$ for all $j \in J$ and $0 \le x'_i$ for all $i \in I$,

$$\sum_{i \in I} c_i x_i \ \le\ \sum_{i \in I} c_i x'_i .$$

So $x$ attains the minimum of $\sum_i c_i x_i$ over the whole primal-feasible set — an attained global minimum, not a local or approximate one, and with no multiplicative or additive slack.

• $y$ is dual-optimal: $y$ is dual-feasible (as in $h_d$) and for every $y' \in \mathbb{R}^{J}$ satisfying $\sum_{j} A_{i,j} y'_j \le c_i$ for all $i \in I$ and $0 \le y'_j$ for all $j \in J$,

$$\sum_{j \in J} b_j y'_j \ \le\ \sum_{j \in J} b_j y_j .$$

So $y$ attains the global maximum of $\sum_j b_j y_j$ over the whole dual-feasible set.

Both quantifiers range over the entire function spaces $\mathbb{R}^{I}$ and $\mathbb{R}^{J}$, with feasibility as the hypothesis of the implication. The conclusion does not state the equality of the two optimal values; it states only the two optimality properties. Uniqueness of optima is not claimed.

Degenerate cases silently included.

• $I$ empty: every sum over $i$ is $0$; $x$ is the unique empty function. Then $h_p$ reduces to $b_j \le 0$ for all $j \in J$; $h_d$'s first clause is vacuous, leaving only $y_j \ge 0$; $h_{pcs}$ is vacuous (no index $i$ exists). $h_{dcs}$ says: for each $j$ with $y_j > 0$, $b_j \le 0$ and $0 \le b_j$, i.e. $b_j = 0$. The conclusion then asserts that the empty $x$ minimizes the value $0$ over the primal-feasible set (a one-point set here) and that $y$ maximizes $\sum_j b_j y_j$ over all $y' \ge 0$.
• $J$ empty: every sum over $j$ is $0$; $y$ is the unique empty function. Then $h_p$ reduces to $x_i \ge 0$ for all $i$; $h_d$ reduces to $0 \le c_i$ for all $i$; $h_{dcs}$ is vacuous (no index $j$); $h_{pcs}$ says: for each $i$ with $x_i > 0$, $c_i \le 0$ and $0 \le c_i$, i.e. $c_i = 0$. The conclusion then asserts that $x$ minimizes $\sum_i c_i x_i$ over all $x' \ge 0$ and that the empty $y$ maximizes the value $0$.
• Both empty: all four hypotheses are vacuous or trivially true, both objectives are $0$, and both optimality claims are over one-point feasible sets.
• $x = 0$ and/or $y = 0$ (allowed whenever feasible): the corresponding slackness hypothesis carries no content, and the conclusion still asserts full global optimality of that vector.