[proofplan] [Weak duality](/theorems/2549) says that every feasible dual value is a lower bound for every feasible primal cost. We first compare the particular dual certificate $D_0$ against an arbitrary primal object $P$ to prove that no primal object has cost below $\operatorname{cost}(P_0)$. We then compare an arbitrary dual certificate $D$ against the particular primal object $P_0$ to prove that no dual certificate has value above $\operatorname{value}(D_0)$. [/proofplan] [step:Compare the returned dual certificate with every primal object] Let $P \in \mathcal P$ be arbitrary. Applying the weak duality hypothesis with this $P$ and with $D = D_0$ gives \begin{align*} \operatorname{value}(D_0) \leq \operatorname{cost}(P). \end{align*} Using the assumed equality $\operatorname{value}(D_0) = \operatorname{cost}(P_0)$, we obtain \begin{align*} \operatorname{cost}(P_0) \leq \operatorname{cost}(P). \end{align*} Since $P \in \mathcal P$ was arbitrary, $P_0$ minimizes $\operatorname{cost}$ over $\mathcal P$. [guided] We want to prove that $P_0$ is a primal optimum, meaning that its cost is no larger than the cost of any feasible primal object. Let $P \in \mathcal P$ be arbitrary. The weak duality hypothesis applies to every pair consisting of a feasible primal object and a feasible dual certificate, so it applies to the pair $(P, D_0)$. Therefore \begin{align*} \operatorname{value}(D_0) \leq \operatorname{cost}(P). \end{align*} The special feature of the returned pair is that the lower bound supplied by $D_0$ exactly equals the cost of $P_0$: \begin{align*} \operatorname{value}(D_0) = \operatorname{cost}(P_0). \end{align*} Substituting this equality into the previous inequality gives \begin{align*} \operatorname{cost}(P_0) \leq \operatorname{cost}(P). \end{align*} Because $P$ was an arbitrary element of $\mathcal P$, this inequality holds for every feasible primal object. Hence $P_0$ minimizes $\operatorname{cost}$ over $\mathcal P$. [/guided] [/step] [step:Compare every dual certificate with the returned primal object] Let $D \in \mathcal D$ be arbitrary. Applying the weak duality hypothesis with $P = P_0$ and this $D$ gives \begin{align*} \operatorname{value}(D) \leq \operatorname{cost}(P_0). \end{align*} Using the assumed equality $\operatorname{cost}(P_0) = \operatorname{value}(D_0)$, we obtain \begin{align*} \operatorname{value}(D) \leq \operatorname{value}(D_0). \end{align*} Since $D \in \mathcal D$ was arbitrary, $D_0$ maximizes $\operatorname{value}$ over $\mathcal D$. [/step] [step:Conclude primal and dual optimality from the two universal inequalities] The first step proved that for every $P \in \mathcal P$, \begin{align*} \operatorname{cost}(P_0) \leq \operatorname{cost}(P). \end{align*} The second step proved that for every $D \in \mathcal D$, \begin{align*} \operatorname{value}(D) \leq \operatorname{value}(D_0). \end{align*} Thus $P_0$ is an optimal primal solution and $D_0$ is an optimal dual certificate. [/step]