How do you know a point is actually optimal?
FONC/SONC for unconstrained problems, KKT for constrained ones, and LP duality's certificate — every way this course proves a candidate solution really is the best one.
For an unconstrained problem, the first- and second-order conditions are the whole story: a zero gradient is necessary, a positive semidefinite Hessian is necessary too, and a positive DEFINITE Hessian at a zero-gradient point is sufficient for a strict local minimum. Add equality or inequality constraints and the KKT conditions take over — stationarity of the Lagrangian, primal and dual feasibility, and complementary slackness together play the same role FONC/SONC played unconstrained, provided a constraint qualification like Slater's condition holds. For a linear program specifically, duality hands you something stronger than a local check: a feasible dual solution whose objective value matches the primal's is proof the primal is globally optimal, no calculus required.
Unconstrained — FONC / SONC
Let f:\mathbb{R}^n\to\mathbb{R} be twice continuously differentiable near a point x^*.
First-order necessary condition (FONC). If x^* is a local minimum of f, then \nabla f(x^*) = \mathbf{0}.
Second-order necessary condition (SONC). If x^* is a local minimum of f, then in addition H(x^*) \succeq 0 (the Hessian at x^* is positive semidefinite).
Second-order sufficient condition (SOSC). Conversely, if \nabla f(x^*) = \mathbf{0} and H(x^*) \succ 0 (positive definite), then x^* is a strict local minimum.
Sanity check: take f(x,y) = x^2 + y^2. Then \nabla f = (2x,2y) vanishes only at x^*=(0,0), and H = \begin{pmatrix}2&0\\0&2\end{pmatrix} is positive definite everywhere, in particular at x^* — matching the known fact that the origin is f's strict global (hence local) minimum. Now take f(x,y)=x^2-y^2 at the same candidate point (0,0): the gradient still vanishes there, but H=\begin{pmatrix}2&0\\0&-2\end{pmatrix} is indefinite, not PSD, so SONC correctly rules out (0,0) as a local minimum — it is the saddle point it's known to be.
Zero gradient is necessary; a positive-definite Hessian there is sufficient for a strict local minimum.
Show proof
FONC. Suppose x^* is a local minimum but \nabla f(x^*) \ne \mathbf{0}. Let d = -\nabla f(x^*), a nonzero vector. Taylor's theorem gives, for small \alpha>0, f(x^*+\alpha d) = f(x^*) + \alpha\, \nabla f(x^*)^\top d + o(\alpha) = f(x^*) - \alpha\, \|\nabla f(x^*)\|^2 + o(\alpha). Since \|\nabla f(x^*)\|^2 > 0, the linear term is strictly negative, and for all sufficiently small \alpha>0 it dominates the o(\alpha) remainder. So f(x^*+\alpha d) < f(x^*) for such \alpha, contradicting that x^* is a local minimum. Hence \nabla f(x^*)=\mathbf 0.
SONC. Suppose \nabla f(x^*)=\mathbf 0 but H(x^*) is not positive semidefinite: there is a direction d with d^\top H(x^*) d < 0. The second-order Taylor expansion around x^*, using \nabla f(x^*)=\mathbf 0, is f(x^*+\alpha d) = f(x^*) + \tfrac{1}{2}\alpha^2\, d^\top H(x^*) d + o(\alpha^2). Since d^\top H(x^*) d < 0, the quadratic term is strictly negative and dominates the remainder for small \alpha, so f(x^*+\alpha d) < f(x^*) arbitrarily close to x^* — contradicting a local minimum. Hence H(x^*)\succeq 0.
SOSC. Suppose \nabla f(x^*) = \mathbf 0 and H(x^*)\succ 0. Positive definiteness means there is m>0 with d^\top H(x^*) d \ge m\|d\|^2 for every direction d. The same second-order expansion gives, for any d\ne\mathbf 0 and small \alpha, f(x^*+\alpha d) - f(x^*) = \tfrac12\alpha^2\, d^\top H(x^*) d + o(\alpha^2) \ge \tfrac12 m\alpha^2\|d\|^2 + o(\alpha^2). For \alpha small enough the \tfrac12 m\alpha^2\|d\|^2 term dominates the remainder, so the right side is strictly positive. Hence f(x^*+\alpha d) > f(x^*) for every direction d and every sufficiently small step, which is exactly the definition of a strict local minimum.
Constrained — the KKT conditions
Term
Lagrangian
Consider \min_x f_0(x) subject to f_i(x)\le 0 (i=1,\dots,m) and h_j(x)=0 (j=1,\dots,p), with f_0,f_i,h_j continuously differentiable. Let x^* be a local minimum at which the active constraint gradients — \{\nabla f_i(x^*) : i\in\mathcal A(x^*)\}\cup\{\nabla h_j(x^*)\}, where \mathcal A(x^*)=\{i : f_i(x^*)=0\} is the active set — are linearly independent (a constraint qualification, LICQ). Then there exist multipliers \lambda^*\in\mathbb R^m, \nu^*\in\mathbb R^p such that:
- Stationarity: $\nabla f_0(x^) + \sum_i \lambda_i^\nabla f_i(x^*)
- \sum_j \nu_j^\nabla h_j(x^) = \mathbf 0$.
- Primal feasibility: f_i(x^*)\le 0 for all i, h_j(x^*)=0 for all j.
- Dual feasibility: \lambda_i^*\ge 0 for all i.
- Complementary slackness: \lambda_i^* f_i(x^*) = 0 for all i.
Sanity check: minimize f_0(x,y)=x^2+y^2 subject to f_1(x,y)= 1-x-y\le0. Geometrically the unconstrained minimum (0,0) violates the constraint (1-0-0=1>0), so the constrained optimum sits on the boundary line x+y=1; by symmetry it's x^*=(1/2,1/2). Check KKT: active set is \{1\} (constraint tight, f_1(1/2,1/2)=0). Stationarity requires \nabla f_0(x^*)+\lambda_1^*\nabla f_1(x^*)=\mathbf 0: \nabla f_0=(1,1) (i.e. (2x,2y) at x^*), \nabla f_1=(-1,-1), so (1,1)+\lambda_1^*(-1,-1)=\mathbf 0 gives \lambda_1^*=1\ge0 — dual feasible, as required. Complementary slackness holds trivially since the constraint is tight. Every condition checks out at the geometrically correct optimum.
Stationarity, primal/dual feasibility, and complementary slackness, stated together.
Show proof
Primal feasibility (2) holds automatically since x^* is feasible.
A geometric fact used below. Call d a first-order feasible direction at x^* if \nabla f_i(x^*)^\top d < 0 for every active i\in \mathcal A(x^*) and \nabla h_j(x^*)^\top d = 0 for every j — to first order, moving from x^* along d strictly decreases every active inequality constraint (keeping it feasible) and stays on the equality constraints' tangent space. Under LICQ, the implicit function theorem lets any such d be realized by an actual feasible curve x(t) with x(0)=x^* and x'(0)=d that satisfies h_j(x(t))=0 exactly (not just to first order) and f_i(x(t))<0 for small t>0: intuitively, the active h_j's linearly independent gradients let a small correction term of order t^2 be added to x^*+td to snap the curve back onto \{h_j=0\} without disturbing the strict inequality constraints, which have first-order slack. If x^* is a local minimum, no such curve can have f_0(x(t))<f_0(x^*) for small t>0, so \left.\frac{d}{dt}\right|_{t=0}f_0(x(t)) = \nabla f_0(x^*)^\top d \ge 0. So: no first-order feasible direction d can also satisfy \nabla f_0(x^*)^\top d < 0.
Gordan's theorem of the alternative (a classical consequence of the separating-hyperplane theorem, used here as a known result): for vectors a_1,\dots,a_k\in\mathbb R^n, exactly one of the following holds — either there is d with a_\ell^\top d < 0 for every \ell, or there are \mu_1,\dots,\mu_k\ge0, not all zero, with \sum_\ell \mu_\ell a_\ell = \mathbf 0.
Apply Gordan's theorem to the list of vectors a_0=\nabla f_0(x^*), a_i=\nabla f_i(x^*) for i\in\mathcal A(x^*), and — splitting each equality constraint into the pair of inequalities h_j\le0,\ -h_j\le0, both active at x^* — a_{j+}=\nabla h_j(x^*), a_{j-}=-\nabla h_j(x^*) for each j. The previous paragraph shows the "there is d with every a_\ell^\top d<0" branch is impossible: such a d would be a first-order feasible direction (the two opposite-signed rows for each h_j force \nabla h_j(x^*)^\top d = 0 exactly, and a_i^\top d<0 for active i is the inequality condition) with \nabla f_0(x^*)^\top d<0, which was just ruled out. So the second branch holds: there exist \lambda_0\ge0, \lambda_i\ge0 (i\in\mathcal A(x^*)), \mu_j^+,\mu_j^-\ge0, not all zero, with \lambda_0\nabla f_0(x^*) + \sum_{i\in\mathcal A(x^*)}\lambda_i\nabla f_i(x^*) + \sum_j (\mu_j^+-\mu_j^-)\nabla h_j(x^*) = \mathbf 0. Write \nu_j=\mu_j^+-\mu_j^- (an unrestricted-sign real number, since \mu_j^\pm\ge0 independently).
\lambda_0>0. If \lambda_0=0, the display becomes \sum_i\lambda_i\nabla f_i(x^*)+\sum_j\nu_j\nabla h_j(x^*)=\mathbf 0 with (\lambda_{\mathcal A(x^*)},\nu) not all zero (since not everything among \lambda_0,\lambda_i,\mu_j^\pm is zero, and \lambda_0=0) — a nontrivial linear dependence among \{\nabla f_i(x^*):i\in\mathcal A(x^*)\}\cup \{\nabla h_j(x^*)\}, contradicting LICQ. So \lambda_0>0; divide the whole display by \lambda_0 to normalize \lambda_0=1.
Assemble the multipliers. Set \lambda_i^*=\lambda_i/\lambda_0 for i\in\mathcal A(x^*) and \lambda_i^*=0 for i\notin\mathcal A(x^*), and \nu_j^*=\nu_j/\lambda_0. The normalized display is exactly stationarity (1). Dual feasibility (3), \lambda_i^*\ge0, holds by construction for active i and trivially (0\ge0) for inactive i. Complementary slackness (4) holds because for active i, f_i(x^*)=0 so \lambda_i^*f_i(x^*)=0 regardless of \lambda_i^*'s value, and for inactive i, \lambda_i^*=0 makes the product 0 regardless of f_i(x^*)'s value.
Consider the convex problem \min_{x} f_0(x) \quad\text{s.t.}\quad f_i(x)\le 0\ (i=1,\dots,m), \quad Ax=b, with f_0,f_1,\dots,f_m convex and differentiable, and let p^* denote its optimal value (finite). Slater's condition holds if there is a point \tilde x with A\tilde x = b and f_i(\tilde x) < 0 for every i (strictly feasible for every inequality constraint).
If Slater's condition holds, then strong duality holds (p^*=d^*, the
common value attained by some dual-feasible (\lambda^*,\nu^*)), and
consequently the KKT conditions are not just sufficient for optimality
of a feasible x^* (which convexity alone already guarantees) but
necessary: every primal optimal x^* is paired with a dual optimal
(\lambda^*,\nu^*) satisfying stationarity, dual feasibility, and
complementary slackness (see kkt-conditions).
Sanity check: take the convex problem \min x^2 s.t. x\le -1 (so f_1(x)=x+1\le0). Slater's condition holds: \tilde x=-2 gives f_1(-2)=-1<0, strictly feasible. The optimum is x^*=-1 (the boundary, since x^2 is increasing in |x| away from 0 and the feasible set excludes 0). KKT stationarity: \nabla_x L = 2x+\lambda = 0 at x^*=-1 gives \lambda^*=2\ge0 (dual feasible), and complementary slackness \lambda^*f_1(x^*) = 2\cdot 0=0 holds since f_1(-1)=0 is tight — exactly as the theorem promises for a Slater-satisfying convex problem. Contrast a problem where Slater fails: \min x^2 s.t. x^2\le 0 (only x=0 is feasible, so no strictly feasible point exists) — here the KKT machinery built on Slater simply doesn't apply, which is the gap this theorem exists to name.
The constraint qualification that guarantees KKT is not just necessary but sufficient for convex problems.
Show proof
Step 1 — weak duality (always true, no convexity needed). Define the
Lagrangian L(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^\top(Ax-b)
and the dual function g(\lambda,\nu) = \inf_x L(x,\lambda,\nu). For any
\lambda\ge0 and any primal-feasible x, every term \lambda_i f_i(x)\le0
and \nu^\top(Ax-b)=0, so L(x,\lambda,\nu)\le f_0(x); taking the infimum
over x preserves this, so g(\lambda,\nu)\le f_0(x) for every feasible
x, hence g(\lambda,\nu)\le p^* for every dual-feasible (\lambda,\nu)
— this is weak-duality-lp's general (nonlinear) counterpart, and gives
d^*=\sup g \le p^* always.
Step 2 — Slater's condition closes the gap. Consider the set in \mathbb{R}^m\times\mathbb{R} \mathcal A = \{(u,t) : \exists x,\ Ax=b,\ f_i(x)\le u_i\ \forall i,\ f_0(x)\le t\}. Convexity of each f_i makes \mathcal A convex: given (u,t),(u',t')\in \mathcal A witnessed by x,x', the point x''=\theta x+(1-\theta)x' satisfies Ax''=b and, by convexity of each f_i, f_i(x'')\le \theta f_i(x)+(1-\theta)f_i(x') \le \theta u_i+(1-\theta)u_i', so (\theta u+(1-\theta)u',\, \theta t+(1-\theta)t')\in\mathcal A.
The point (\mathbf 0, p^*) is not in the interior of \mathcal A: any (u,t) with every u_i<0 and t<p^* in \mathcal A would exhibit a feasible x (since u_i<0 forces f_i(x)\le u_i<0) with f_0(x)\le t<p^*, contradicting p^*'s definition as the infimum. So (\mathbf 0,p^*) lies on the boundary of (the closure of) \mathcal A, and by the supporting-hyperplane theorem there is a nonzero (\lambda,\mu)\in\mathbb{R}^m\times\mathbb{R} with \lambda\ge0,\mu\ge0 such that \mu\, t + \lambda^\top u \ \ge\ \mu\, p^* \qquad \text{for every } (u,t)\in\mathcal A. \qquad(\ast)
Step 3 — \mu>0, using Slater. Suppose instead \mu=0. Then (\ast) reads \lambda^\top u \ge 0 for every u with u_i \ge f_i(x) for some feasible x; in particular at the Slater point \tilde x, u=f(\tilde x) gives \lambda^\top f(\tilde x)\ge0. But f_i(\tilde x)<0 for every i and \lambda\ge0 with \lambda\ne0 (since (\lambda,\mu)\ne0 and \mu=0) forces \lambda^\top f(\tilde x) < 0 — contradiction. So \mu>0, and dividing (\ast) by \mu we may take \mu=1 without loss of generality: t+\lambda^\top u \ge p^* for every (u,t)\in\mathcal A, with \lambda\ge0.
Step 4 — this \lambda is dual optimal with no gap. Taking, for any feasible x, u=f(x) and t=f_0(x) (a valid element of \mathcal A) gives f_0(x) + \lambda^\top f(x) \ge p^* for every x satisfying Ax=b — and since this only used Ax=b, it in fact holds with some matching \nu absorbed into the affine part, i.e. \inf_{x} \{f_0(x)+\lambda^\top f(x) + \nu^\top(Ax-b)\} \ge p^* for the appropriate \nu, i.e. g(\lambda,\nu)\ge p^*. Combined with weak duality (g(\lambda,\nu)\le p^* always), this forces g(\lambda,\nu)=p^* exactly — strong duality, with (\lambda,\nu)=(\lambda^*,\nu^*) dual optimal.
Step 5 — KKT necessity follows. Let x^* be primal optimal. Since g(\lambda^*,\nu^*)=f_0(x^*) (both equal p^*) and g(\lambda^*,\nu^*)=\inf_x L(x,\lambda^*,\nu^*)\le L(x^*,\lambda^*,\nu^*) = f_0(x^*)+\sum_i\lambda_i^* f_i(x^*), and \sum_i\lambda_i^*f_i(x^*)\le0 (feasibility and \lambda^*\ge0), the whole chain f_0(x^*) = g(\lambda^*,\nu^*) \le L(x^*,\lambda^*,\nu^*) \le f_0(x^*) must be equality throughout. Equality in \sum_i\lambda_i^*f_i(x^*)\le 0 term by term (each term is \le0) forces \lambda_i^* f_i(x^*)=0 for every i — complementary slackness. And x^* minimizing L(x,\lambda^*,\nu^*) over x (equality g(\lambda^*,\nu^*)= L(x^*,\lambda^*,\nu^*) with g defined as the infimum) at a differentiable L forces \nabla_x L(x^*,\lambda^*,\nu^*)=\mathbf 0 — stationarity. Both together with \lambda^*\ge0 (dual feasibility) and x^* feasible (primal feasibility) are exactly the KKT conditions, and they hold at every primal optimum whenever Slater's condition holds — necessity, not just sufficiency.
Symbol
L(x,\lambda,\mu)
Linear programs — the duality certificate
Term
duality
Consider the primal LP \min\ c^\top x s.t. Ax\ge b,\ x\ge0 and its dual \max\ b^\top y s.t. A^\top y\le c,\ y\ge0. For every primal-feasible x and every dual-feasible y, b^\top y \ \le\ c^\top x, i.e. every dual-feasible objective value is a lower bound on every primal-feasible objective value (equivalently, every dual value certifies that no primal-feasible point can beat it).
Sanity check: take the primal \min\ 2x_1+3x_2 s.t. x_1+x_2\ge4,\ x_1,x_2\ge0, with dual \max\ 4y s.t. y\le2,\ y\le3,\ y\ge0. The primal point x=(4,0) is feasible with value 2(4)+3(0)=8. The dual point y=2 is feasible (since 2\le2 and 2\le3) with value 4(2)=8. Here weak duality holds with equality, 8\le8. Try a worse dual point, y=1: value 4(1)=4 \le 8 — still respects the bound. No dual-feasible value ever exceeds 8, and indeed the true optimal value here is exactly 8, achieved by both, matching what strong duality (a stronger, separate fact) would additionally guarantee.
Every dual feasible value bounds every primal feasible value — instant sanity check, even far from optimal.
Show proof
Let x be primal-feasible (Ax\ge b, x\ge0) and y dual-feasible (A^\top y\le c, y\ge0). Start from the primal feasibility inequality Ax\ge b. Since y\ge0, multiplying both sides by y^\top preserves the inequality direction (a nonnegative vector dotted into a componentwise inequality preserves it): y^\top(Ax) \ \ge\ y^\top b. Now start from dual feasibility, A^\top y \le c, i.e. c - A^\top y \ge \mathbf 0. Since x\ge0, dotting with x^\top preserves the inequality: x^\top(c - A^\top y) \ \ge\ 0 \quad\Longrightarrow\quad x^\top c \ \ge\ x^\top A^\top y. But x^\top A^\top y = (Ax)^\top y = y^\top(Ax) (transposing a scalar changes nothing), so this reads c^\top x \ge y^\top(Ax). Chaining the two displayed inequalities: c^\top x \ \ge\ y^\top(Ax) \ \ge\ y^\top b = b^\top y.
If the primal LP \min\ c^\top x s.t. Ax\ge b,\ x\ge0 is feasible and
its optimal value is finite (bounded), then its dual
\max\ b^\top y s.t. A^\top y\le c,\ y\ge0 is also feasible with the
same finite optimal value: p^*=d^*, with no gap between them
(contrast weak-duality-lp, which only guarantees d^*\le p^*).
Sanity check: reuse the primal/dual pair from weak-duality-lp:
\min\ 2x_1+3x_2 s.t. x_1+x_2\ge4,\ x_1,x_2\ge0, dual
\max\ 4y s.t. y\le2,\ y\le3,\ y\ge0. The primal optimum is x^*=(4,0)
(cheaper to use all of the less-expensive x_1), value 8. The dual
optimum is y^*=2 (the tighter of the two upper bounds y\le2,\ y\le3),
value 4(2)=8. Both equal 8 exactly — strong duality holds with no
gap, exactly as predicted, and y^*=2 matches the y^*=(B^{-1})^\top c_B
construction: here c_1=2 is the binding column's cost and the single
constraint row has coefficient 1 on x_1, so y^*=c_1/1=2.
At optimality, the primal and dual objective values coincide exactly.
Show proof
This proof leans on the simplex method's own termination guarantee (see
blands-rule-anti-cycling: under Bland's rule, simplex always terminates
in finitely many pivots at an optimal basis whenever one exists) rather
than re-deriving that fact here.
Convert the primal to standard equality form by subtracting a surplus vector s\ge0: Ax - s = b, x,s\ge0, minimize c^\top x. Since the primal is feasible and bounded, the simplex method (Bland's rule, terminating finitely) reaches an optimal basic feasible solution x^* with optimal basis B (the columns of [A\ {-I}] corresponding to the basic variables). At termination, simplex's optimality test says every non-basic variable's reduced cost is nonnegative: \bar c_j = c_j - c_B^\top B^{-1}A_j \ \ge\ 0 \quad\text{for every column } A_j \text{ of } [A\ {-I}].
Define y^* := (B^{-1})^\top c_B = (c_B^\top B^{-1})^\top, a vector in \mathbb R^m (one entry per constraint row). Check dual feasibility: for every original column A_j of A, the reduced-cost condition reads c_j - (y^*)^\top A_j \ge 0, i.e. (y^*)^\top A_j \le c_j for every j — stacking over all j, this is exactly A^\top y^* \le c. For every slack/surplus column (the -e_i columns of -I), the reduced-cost condition reads 0 - (y^*)^\top(-e_i) \ge 0, i.e. y_i^*\ge0 — exactly dual feasibility's nonnegativity requirement. So y^* is dual-feasible.
Now compute the dual objective at y^*: because x^* is a basic feasible solution with B x_B^* = b (i.e. x_B^* = B^{-1}b, and every non-basic entry of x^* is 0), b^\top y^* = (Bx_B^*)^\top y^* = (x_B^*)^\top B^\top y^* = (x_B^*)^\top c_B = c_B^\top x_B^* = c^\top x^* (the middle step uses B^\top y^* = B^\top(B^{-1})^\top c_B = c_B directly from y^*'s definition, and the last step uses that x^*'s non-basic entries, where c contributes nothing extra, are all 0). So the dual objective at the feasible point y^* equals the primal optimal value exactly: b^\top y^* = c^\top x^* = p^*.
By weak duality, b^\top y^*\le p^* always — but here it's already equality, and weak duality also says no dual-feasible point can exceed p^*, so y^* is in fact dual-optimal: d^* = b^\top y^* = p^*.
Let x be primal-feasible for \min\ c^\top x s.t. Ax\ge b,\ x\ge0 and y be dual-feasible for \max\ b^\top y s.t. A^\top y\le c,\ y\ge0. Then x and y are both optimal (for their respective problems) if and only if, for every constraint, either it holds with equality ("tight") or its paired variable is zero: y_i\big(A_ix-b_i\big) = 0 \ \text{ for every row } i, \qquad x_j\big(c_j - A_j^\top y\big) = 0 \ \text{ for every column } j.
Sanity check: reuse x^*=(4,0), y^*=2 from weak-duality-lp /
strong-duality-lp's example (\min\ 2x_1+3x_2 s.t. x_1+x_2\ge4,
dual \max\ 4y s.t. y\le2,\ y\le3). Primal constraint: A_1x^*-b_1 =
(4+0)-4=0 — tight, so its complementary slackness condition
y^*\cdot0=0 holds regardless of y^*. Dual constraints: column 1 gives
c_1-A_1^\top y^* = 2-1(2)=0 — tight, consistent with x_1^*=4\ne0
(complementary slackness needs either the constraint tight or the
variable zero — here it's the constraint that's tight). Column 2 gives
c_2-A_2^\top y^* = 3-1(2)=1\ne0 — not tight, so complementary slackness
requires x_2^*=0, which indeed holds. Every pairing checks out exactly
as the theorem requires at this known-optimal pair.
A primal-dual pair is optimal exactly when each constraint pairs with a zero slack or a zero dual variable.
Show proof
Start from the same two chained inequalities used to prove weak duality
(weak-duality-lp): for primal-feasible x and dual-feasible y,
c^\top x - b^\top y = \underbrace{x^\top(c-A^\top y)}_{\ge 0 \text{ (each term } x_j(c_j-A_j^\top y)\ge0\text{)}}
\ + \ \underbrace{y^\top(Ax-b)}_{\ge 0 \text{ (each term } y_i(A_ix-b_i)\ge0\text{)}}.
(This is exactly the algebra from the weak-duality proof, kept in
unexpanded form: both bracketed sums are sums of nonnegative terms, since
x,y\ge0 and c-A^\top y\ge0, Ax-b\ge0 by feasibility.)
(\Leftarrow) If every term in both sums is individually 0 — which is exactly the complementary slackness conditions stated above — then the whole right side is 0, so c^\top x = b^\top y. Weak duality already guarantees b^\top y\le d^*\le p^*\le c^\top x for the true optimal values p^*,d^*; combined with c^\top x=b^\top y this forces c^\top x = p^* and b^\top y=d^* exactly — both x and y are optimal.
(\Rightarrow) Conversely, suppose x and y are both optimal. By
strong duality (strong-duality-lp, which applies since a feasible,
bounded LP has p^*=d^*), c^\top x = p^* = d^* = b^\top y, so the left
side of the display above is 0. But the right side is a sum of two
sums, each made of individually nonnegative terms
(x_j(c_j-A_j^\top y)\ge0 and y_i(A_ix-b_i)\ge0, from feasibility as
noted above); a sum of nonnegative terms can only equal 0 if every
term is individually 0. That is exactly the complementary slackness
conditions.