A hybrid of tabu search and local descent algorithms with applications in artificial intelligence
We introduce the idea of combining a fast local descent method with with a robust tabu search method. A descent algorithm will stop when it reaches a local minimum. To move beyond this local minimum and search for better solutions, we have developed a hybrid algorithm. Tabu search is used to move away from a local minimum encountered by a descent algorithm and into a new search space. We alternate between the two search methods until some stopping criteria is met. Two different hybrid algorithms are introduced. 
The first hybrid algorithm, HEPTS, is a combination of a Frank-Wolfe type local descent algorithm and a tabu search on the extreme points of a polyhedral region. HEPTS can be applied to any problem with linear constraints for which an extreme point solution is desired. There is no restriction on what type of objective function can be posed; nonlinear, non-differentiable, or even non-continuous. We develop three new error functions for minimizing the error of a decision tree. The decision tree can be formulated as an optimization problem with linear constraints for which an extreme point solution is desired. Our algorithm is then applied to the decision tree problem. 
Our second hybrid algorithm, HMITS, is a combination of a block coordinate type local descent algorithm and a tabu search on binary variables. HMITS can be applied to a large class of mixed integer optimization problems. We propose a new formulation for a decision tree in which each decision is a support vector machine. Three benefits of support vector machines are maximal margins, mapping of data to a higher dimension to construct nonlinear discriminants, and problem size depending only on the number of training data, not the dimension of that data. These last two benefits are gained only by considering the dual problem. We then apply HMITS to three-decision trees of support vector machines.