[proofplan]
The proof is the conic weak-duality identity written with the dual slack. For a primal feasible point $x$ and a dual feasible point $y$, the difference between the primal and dual objective values equals the cone pairing of $x$ with the dual slack $c-A^*y$. Since the slack lies in $K^*$ and $x$ lies in $K$, this pairing is nonnegative. Hence zero gap is equivalent to [complementary slackness](/theorems/2559), and once one feasible pair has zero gap, direct [weak duality](/theorems/2549) rules out any better feasible value on either side.
[/proofplan]
[step:Express the objective gap as the slack pairing]
Let $s \in E$ denote the dual slack associated to $y$, defined by
\begin{align*}
s := c-A^*y.
\end{align*}
Since $x$ is primal feasible, $Ax=b$. Using the definition of the adjoint $A^*$, we have
\begin{align*}
(b,y)_F = (Ax,y)_F = (x,A^*y)_E = (A^*y,x)_E.
\end{align*}
Therefore
\begin{align*}
(c,x)_E-(b,y)_F = (c,x)_E-(A^*y,x)_E = (c-A^*y,x)_E = (s,x)_E.
\end{align*}
Thus the primal-dual objective gap at the feasible pair $(x,y)$ is exactly the pairing of the primal point with the dual slack.
[guided]
The useful quantity is the dual slack, so define $s \in E$ by
\begin{align*}
s := c-A^*y.
\end{align*}
This vector measures how far the dual constraint is from being tight. Because $x$ is primal feasible, it satisfies $Ax=b$. Therefore the dual objective value can be rewritten using the constraint:
\begin{align*}
(b,y)_F = (Ax,y)_F.
\end{align*}
Now we use the defining property of the adjoint map $A^*:F \to E$: for every $z \in E$ and every $w \in F$,
\begin{align*}
(Az,w)_F = (z,A^*w)_E.
\end{align*}
Applying this with $z=x$ and $w=y$ gives
\begin{align*}
(Ax,y)_F = (x,A^*y)_E.
\end{align*}
Since the [inner product](/page/Inner%20Product) on $E$ is symmetric, $(x,A^*y)_E=(A^*y,x)_E$. Hence
\begin{align*}
(b,y)_F = (A^*y,x)_E.
\end{align*}
Substituting this into the difference of objective values gives
\begin{align*}
(c,x)_E-(b,y)_F = (c,x)_E-(A^*y,x)_E.
\end{align*}
By bilinearity of the inner product in the first argument,
\begin{align*}
(c,x)_E-(A^*y,x)_E = (c-A^*y,x)_E.
\end{align*}
Using the definition of $s$, this becomes
\begin{align*}
(c,x)_E-(b,y)_F = (s,x)_E.
\end{align*}
So the whole primal-dual gap is encoded by a single cone pairing between the primal variable $x$ and the dual slack $s$.
[/guided]
[/step]
[step:Use feasibility to obtain weak duality for every feasible pair]
Let $z \in K$ be any primal feasible point, and let $w \in F$ be any dual feasible point. Define the dual slack associated to $w$ by
\begin{align*}
s_w := c-A^*w.
\end{align*}
Dual feasibility means $s_w \in K^*$, and primal feasibility means $z \in K$ and $Az=b$. Repeating the gap identity with $z$ and $w$ gives
\begin{align*}
(c,z)_E-(b,w)_F = (s_w,z)_E.
\end{align*}
Since $s_w \in K^*$ and $z \in K$, the definition of the dual cone gives
\begin{align*}
(s_w,z)_E \geq 0.
\end{align*}
Therefore every primal feasible value dominates every dual feasible value:
\begin{align*}
(b,w)_F \leq (c,z)_E.
\end{align*}
[/step]
[step:Identify equality of objectives with complementary slackness]
For the given feasible pair $(x,y)$, the identity from the first step gives
\begin{align*}
(c,x)_E-(b,y)_F = (c-A^*y,x)_E.
\end{align*}
If $(c,x)_E=(b,y)_F$, then the left-hand side is zero, so
\begin{align*}
(c-A^*y,x)_E=0.
\end{align*}
Conversely, if
\begin{align*}
(c-A^*y,x)_E=0,
\end{align*}
then the same identity gives
\begin{align*}
(c,x)_E-(b,y)_F=0,
\end{align*}
and hence
\begin{align*}
(c,x)_E=(b,y)_F.
\end{align*}
[/step]
[step:Conclude optimality from zero gap]
Assume now that $x$ and $y$ are feasible and
\begin{align*}
(c-A^*y,x)_E=0.
\end{align*}
By the previous step,
\begin{align*}
(c,x)_E=(b,y)_F.
\end{align*}
Let $z \in K$ be any primal feasible point. Applying weak duality from the second step to the feasible pair $(z,y)$ gives
\begin{align*}
(b,y)_F \leq (c,z)_E.
\end{align*}
Since $(b,y)_F=(c,x)_E$, we obtain
\begin{align*}
(c,x)_E \leq (c,z)_E.
\end{align*}
Thus $x$ attains the minimum primal objective value.
Let $w \in F$ be any dual feasible point. Applying weak duality from the second step to the feasible pair $(x,w)$ gives
\begin{align*}
(b,w)_F \leq (c,x)_E.
\end{align*}
Since $(c,x)_E=(b,y)_F$, we obtain
\begin{align*}
(b,w)_F \leq (b,y)_F.
\end{align*}
Thus $y$ attains the maximum dual objective value. The common optimal value is
\begin{align*}
(c,x)_E=(b,y)_F.
\end{align*}
This proves both optimality statements and equality of the primal and dual optimal values.
[/step]
