Iterative Search Algorithms
Michael H. Veatch · 2021
An iterative search algorithm for an optimization problem is one that starts with a feasible solution and applies some procedure to the current solution to find another one, which becomes the current solution. This chapter introduces some principles of algorithm design and assessment, focusing on iterative algorithms. It lays out terminology for iterative and other types of algorithms. In contrast to iterative search algorithms, a constructive algorithm assigns some variables at each iteration and does not find a complete solution until the algorithm finishes. The concepts of improving directions and local optimality conditions are covered. A fundamental distinction is whether optimality of a solution can be checked using just local information. Computational complexity of algorithms and what we mean by a correct algorithm are briefly introduced.