[proofplan] The proof is an order argument. In the minimisation case, the certificate supplies a universal lower bound on all feasible objective values, and the feasible point $F_0$ attains that bound. Therefore every feasible value is at least $w(F_0)$. The maximisation case is the same argument with the inequality reversed: the certificate supplies a universal upper bound, and $F_0$ attains it. [/proofplan] [step:Use the lower-bound certificate to compare every feasible value with $w(F_0)$] Assume the minimisation hypotheses. Let $F \in \mathcal F$ be arbitrary. Since $C_0 \in \mathcal C_{\min}$ satisfies the certificate inequality, we have \begin{align*} w(F) \ge L(C_0). \end{align*} Since $F_0 \in \mathcal F$ satisfies $w(F_0) = L(C_0)$, substitution gives \begin{align*} w(F) \ge w(F_0). \end{align*} Because $F \in \mathcal F$ was arbitrary, this proves \begin{align*} w(F_0) \le w(F) \end{align*} for every $F \in \mathcal F$. Hence $F_0$ is a minimiser of $w$ over $\mathcal F$. [guided] Assume the minimisation hypotheses. The certificate $C_0$ is fixed, so the number $L(C_0) \in \mathbb R$ is also fixed. Its role is to give a lower bound that is valid uniformly over the whole feasible family: for every feasible object $F \in \mathcal F$, \begin{align*} w(F) \ge L(C_0). \end{align*} Now use the special feasible object $F_0 \in \mathcal F$. The hypothesis says that $F_0$ attains the certified lower bound: \begin{align*} w(F_0) = L(C_0). \end{align*} Therefore the previous inequality may be rewritten, for each $F \in \mathcal F$, as \begin{align*} w(F) \ge w(F_0). \end{align*} This is exactly the defining comparison for a minimiser: no feasible object has objective value strictly smaller than the objective value of $F_0$. Since the choice of $F \in \mathcal F$ was arbitrary, we have \begin{align*} w(F_0) \le w(F) \end{align*} for every $F \in \mathcal F$. Hence $F_0$ is a minimiser of $w$ over $\mathcal F$. [/guided] [/step] [step:Use the upper-bound certificate to compare every feasible value with $w(F_0)$] Assume the maximisation hypotheses. Let $F \in \mathcal F$ be arbitrary. Since $C_0 \in \mathcal C_{\max}$ satisfies the certificate inequality, we have \begin{align*} w(F) \le U(C_0). \end{align*} Since $F_0 \in \mathcal F$ satisfies $w(F_0) = U(C_0)$, substitution gives \begin{align*} w(F) \le w(F_0). \end{align*} Because $F \in \mathcal F$ was arbitrary, this proves \begin{align*} w(F_0) \ge w(F) \end{align*} for every $F \in \mathcal F$. Hence $F_0$ is a maximiser of $w$ over $\mathcal F$. [/step]