Exercise 7.30 (The primal-dual method as steepest dual ascent)

We content ourselves with a high-level description of the proof. Choose an arbitrary feasible direction, say D. We can transform it to S with two moves that doesn’t make $b^{\prime }{d}^D$ smaller. Let

We delete all of $Q^{\text{−}}$ and any vertex that has a path in the graph(with balanced edges to keep it feasible. Obviously $Q^{\text{+}}:=\{v|b_v>0\}\cap \bar{S}\cap D$ is also removed. Because every vertex of $Q^{\text{+}}$ has a path to a vertex of $Q^{\text{−}}$. Note that all the outputed flow of $Q^{\text{+}}$ goes through $Q^{\text{−}}$. So ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{v\in Q^{\text{+}}}{b}_v=f_{Q^{\text{+}}}^{\mathit{out}}\le f_{Q^{\text{−}}}^{\mathit{in}}=f_{Q^{\text{−}}}^{\mathit{out}}\le {\sum }_{v\in Q^{\text{−}}}|b_v|$, the first equality comes from the fact that $Q^{\text{−}}$ weren’t markes though there is a edge from s to them. Notice the change in $b^{\prime }{d}^D$, it increases with ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{v\in Q^{\text{−}}}|b_v|-{\sum }_{v\in Q^{\text{+}}}{b}_v\ge 0$.
In a similar manner we can define: $Q^{\text{−}}:=\{v|b_v<0\}\cap \bar{D}{Q}^{\text{+}}:=\{v|b_v<0\}\cap \bar{D}$. And add all of $Q^{\text{+}}$(and other necessary vertices for feasibility) to D. Similarly

Taking these two steps, we turned D to S and only made $b^{\prime }{d}^D$ bigger. So S is optimal.