Hybrid extreme point tabu search

We develop a new hybrid tabu search method for optimizing a continuous differentiable function over the extreme points of a polyhedron. The method combines extreme point tabu search (EPTS) with traditional descent algorithms based on linear programming. The tabu search algorithm utilizes both recency-based and frequency-based memory and oscillates between local improvement and diversification phases. The hybrid algorithm iterates between using a descent algorithm to find a local minimum and tabu search to improve locally and then move to a new area of the search space. The descent algorithm acts as a form of intensification within the tabu search. This algorithm can be used on many important classes of problems in global optimization including bilinear programming, multilinear programming, multiplicative programming, concave minimization, and complementarity problems. The algorithm is applied to two practical problems: the quasistatic multi-rigid-body contact problem (QCP) in robotics and the global tree optimization (GTO) problem in machine learning. We perform computational experiments on problems of significant real world dimensions: the smallest machine learning problem tested has on the order of 10⁴⁸⁵ extreme points. The results show our method obtains high quality solutions both by comparison with the embedded descent algorithm and by comparison with a version of tabu search that does not make use of descent.