Dual part of complementary slackness The proof of the complementary slackness of
P: min $c^Tx $ @ $Ax = b, x \geq 0$
D: max $b^Ty $ @ $A^Ty \leq c$
Goes something like $c^Tx = b^T y = y^TAx \Leftrightarrow c^Tx-y^TAx = 0 \Leftrightarrow x^T(c - A^Ty) = 0$
And since $x \geq 0, c-A^Ty \geq 0$ we must have that each term of the elementwise product $x \circ (c-A^Ty)$ is $0$. I' wondering about the dual variant:
$Ax = b \Leftrightarrow x^TA^Ty = b^Ty \Leftrightarrow y^T(b-Ax) = 0$
But $y$ isn't necesarilly non-negative, and in fact $b-Ax = 0$. So what's the argument for each term in the elementwise product $y \circ (b-Ax)$ being $0$?
 A: You've already said it: $b-Ax=0$. So each term of $y \circ (b-Ax)$ is zero because the right-hand side is always zero.
Technically speaking, the term "complementary slackness" is not used to refer to the equality constraints $Ax=b$ and their Lagrange multipliers $y$. There is nothing "slack" about them: even the slightest perturbation $b$ will render $x$ infeasible. For any perturbation of $b$, no matter how small, the optimal value $x$ must change, and therefore the optimal value $c^Tx=b^Ty$ is likely to change as well. Thus the individual values of $y$ are rarely nonzero.
In contrast, not all perturbations of $c$ are the same. For instance, suppose that for some row $i$ we have $a_i^T y < c_i$; that is, suppose that it has non-zero slack. Then any perturbation $\Delta c$ larger than $a_i^T y - c_i$&emdash;a negative value&emdash;will have no affect on feasibility or optimality; the optimal pair $(x,y)$ will not change. Thus $x_i$, the corresponding Lagrange multiplier for the dual constraint $a_i^Ty<c_i$, must be zero.
On the other hand, suppose $a_i^T y = c_i$ for some row $i$; that is, suppose it has no slack. Then any positive perturbation of $c_i$ will (almost always) render $y$ suboptimal; the optimal value will (almost always) increase. On the other hand, any negative perturbation of $c_i$ will render $y$ infeasible; the optimal value will (almost always) decrease. Thus $x_i$, the corresponding Lagrange multiplier, will usually be positive.
I know this is a bit of a handwave; it's possible to put more meat on this description. But hopefully it's enough to help you understand why we do treat inequality constraints specially.
