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 \mathbb R{mathinline}.  In local search, for every {mathinline} \mathbf x \in S{mathinline}, we must give some {mathinline}N_{\mathbf x}{mathinline} to be the neighborhood of {mathinline} \mathbf x{mathinline}.  Then given some initial feasible solution {mathinline} \mathbf x_0{mathinline}, for {mathinline} n = 1,2,\ldots{mathinline}, we let
{mathdisplay}
\mathbf x_{n} = \mathop{arg\, min}{\mathbf x \in N_{\mathbf x_{n-1}}} f(\mathbf x)
{mathdisplay}