[proofplan] We prove the contrapositive at the level of a single feasible solution. If a locally optimal solution were not globally optimal, the completeness hypothesis for the neighbourhood system would produce a neighbouring feasible solution with strictly larger objective value. This contradicts the defining inequality for local optimality, so no locally optimal solution can fail to be globally optimal. [/proofplan] [step:Assume a locally optimal solution fails to be globally optimal] Let $F_0 \in \mathcal{F}$ be locally optimal, meaning that $w(F') \leq w(F_0)$ for every $F' \in N(F_0)$. Assume, for contradiction, that $F_0$ is not globally optimal. By definition of not being globally optimal for this maximisation problem, there exists $G \in \mathcal{F}$ such that \begin{align*} w(G) > w(F_0). \end{align*} [guided] Fix a feasible solution $F_0 \in \mathcal{F}$ and assume that it is locally optimal. This means that every feasible solution lying in its neighbourhood has objective value no larger than the objective value of $F_0$: \begin{align*} w(F') \leq w(F_0) \quad \text{for every } F' \in N(F_0). \end{align*} To prove that $F_0$ is globally optimal, we argue by contradiction. Suppose $F_0$ is not globally optimal. Since this is a maximisation problem with objective function $w: \mathcal{F} \to \mathbb{R}$, not being globally optimal means precisely that some feasible solution has strictly larger objective value. Thus there exists $G \in \mathcal{F}$ such that \begin{align*} w(G) > w(F_0). \end{align*} This strict inequality is the only fact about global non-optimality that will be needed. [/guided] [/step] [step:Use completeness of the neighbourhood system to produce an improving neighbour] Since $F_0$ is not globally optimal, the completeness hypothesis applied to $F_0$ gives a feasible solution $F_1 \in N(F_0)$ such that \begin{align*} w(F_1) > w(F_0). \end{align*} [/step] [step:Contradict local optimality and conclude global optimality] Because $F_1 \in N(F_0)$ and $F_0$ is locally optimal, we must have \begin{align*} w(F_1) \leq w(F_0). \end{align*} This contradicts the strict improvement \begin{align*} w(F_1) > w(F_0). \end{align*} Therefore the assumption that $F_0$ is not globally optimal is false. Hence every locally optimal feasible solution $F_0 \in \mathcal{F}$ satisfies \begin{align*} w(G) \leq w(F_0) \quad \text{for every } G \in \mathcal{F}, \end{align*} so every locally optimal feasible solution is globally optimal. [/step]