h1. Local Search

Suppose we are given some optimization problem
{mathdisplay}
\begin{aligned}
&\min & f(\mathbf x)\\ 
&\text{subject to}& \mathbf x &\in S
\end{aligned}
{mathdisplay}
where {mathinline} S \subset \mathbb R^n{mathinline} and {mathinline} f \colon S \to \R{mathinline}.  The idea of local search is as follows:  for every {mathinline} \mathbf x \in S{mathinline}, define {mathinline}N_{\mathbf x}{mathinline} to be the neighborhood of {mathinline} \mathbf x{mathinline}.