Short answers, pulled from the story.
Local search is a heuristic method for solving computationally hard optimization problems by moving iteratively through a space of candidate solutions. Starting from an initial solution, the algorithm examines neighboring solutions that differ by the smallest possible change and moves to a better one, repeating until no improvement is found or a time limit is reached.
Local search has been applied to the traveling salesman problem, the Boolean satisfiability problem, the vertex cover problem, the nurse scheduling problem, the k-medoid clustering problem, and the Hopfield Neural Networks problem, among others. It is also used across fields including artificial intelligence, operations research, engineering, and bioinformatics.
WalkSAT, the 2-opt algorithm for the traveling salesman problem, and the Metropolis-Hastings algorithm are all examples of local search algorithms. Hill climbing is the specific form of local search where the algorithm always selects the neighbor that maximizes the criterion.
Local search can become stuck at a locally optimal point where no neighboring solution is better than the current one, even though a superior global solution exists elsewhere in the search space. Strategies to escape this include restarts with different initial conditions, randomization, iterated local search, reactive search optimization, and simulated annealing.
Local search does not guarantee that the solution it returns is globally optimal. It is typically an approximation or incomplete algorithm; the true optimum may lie in a region of the search space that the algorithm never visits. It does function as an anytime algorithm, returning the best solution found if interrupted at any point.
Local search explicitly explores a discrete neighborhood of candidate solutions and does not require a differentiable objective function, while gradient descent relies on computing the gradient of an objective function to determine the direction of improvement. Although both are iterative methods, gradient descent is not considered part of the local search family.