Nonlinear optimization simplified by hypersurface deformation.

A general strategy is advanced for simplifying nonlinear optimization problems, the "ant-lion" method. This approach exploits shape modifications of the cost-function hypersurface which distend basins surrounding low-lying minima (including global minima). By interwining hypersurface deformation with steepest-descent displacements, the search is concentrated just on a small relevant subset of all minima. Specific calculations demonstrating the value of this method are reported for the partitioning of two classes of irregular but nonrandom graphs, the "prime- factor" graphs, and the "pi" graphs. We also indicate how this approach can be applied to the traveling salesman problem and to design layout optimization, and that it may be useful in combination with simulated annealing strategies.