[proofplan] The proof is the equality case of a universal bound. In the minimisation case, the certificate says every feasible value is at least $L$, while the produced feasible point has value exactly $L$, so no feasible point can have smaller objective value. The maximisation case is the same argument with the inequalities reversed: every feasible value is at most $U$, and the produced feasible point reaches that bound. [/proofplan] [step:Use the lower-bound certificate to compare every feasible solution with $F_0$] Assume the minimisation hypotheses. Let $F \in \mathcal F$ be arbitrary. Since $L$ is a valid lower-bound certificate, \begin{align*} L \le c(F). \end{align*} Since $c(F_0)=L$, substitution gives \begin{align*} c(F_0) \le c(F). \end{align*} Because this holds for every $F \in \mathcal F$, the feasible point $F_0$ is a minimiser of $c$ on $\mathcal F$. [guided] We prove optimality by comparing the candidate $F_0$ against an arbitrary feasible competitor. Let $F \in \mathcal F$ be arbitrary. The lower-bound certificate is precisely the statement that no feasible objective value can fall below $L$: \begin{align*} L \le c(F). \end{align*} The algorithm has also produced a feasible point $F_0 \in \mathcal F$ whose objective value attains this bound: \begin{align*} c(F_0)=L. \end{align*} Substituting $c(F_0)$ for $L$ in the certificate inequality gives \begin{align*} c(F_0) \le c(F). \end{align*} Since $F \in \mathcal F$ was arbitrary, every feasible solution has objective value at least $c(F_0)$. This is exactly the definition that $F_0$ minimises $c$ over $\mathcal F$. [/guided] [/step] [step:Identify the minimum value in the minimisation case] Since $F_0 \in \mathcal F$ and $F_0$ is a minimiser, the minimum exists and is attained at $F_0$. Therefore \begin{align*} \min_{F \in \mathcal F} c(F)=c(F_0)=L. \end{align*} [/step] [step:Use the upper-bound certificate to compare every feasible solution with $F_0$] Assume the maximisation hypotheses. Let $F \in \mathcal F$ be arbitrary. Since $U$ is a valid upper-bound certificate, \begin{align*} c(F) \le U. \end{align*} Since $c(F_0)=U$, substitution gives \begin{align*} c(F) \le c(F_0). \end{align*} Because this holds for every $F \in \mathcal F$, the feasible point $F_0$ is a maximiser of $c$ on $\mathcal F$. [/step] [step:Identify the maximum value in the maximisation case] Since $F_0 \in \mathcal F$ and $F_0$ is a maximiser, the maximum exists and is attained at $F_0$. Therefore \begin{align*} \max_{F \in \mathcal F} c(F)=c(F_0)=U. \end{align*} This proves both the minimisation and maximisation forms of the principle. [/step]