关键词: 条件梯度算法, 经典远离步, 成对远离步, 最小闭包球, 支持向量数据描述

Abstract: The Minimum Enclosing Ball(MEB) problem is a classical optimization problem in machine learning and computational geometry,where the objective is to find a ball with the smallest radius enclosing a given set of data points.By combining the classic away-step and the pairwise away-step directions,an improved double away-step conditional gradient(DACG) algorithm is proposed for solving the MEB problem of a set of m data points in an n-dimensional space.Compared to other variants of the double-choice conditional gradient algorithm with away-step,this improved algorithm abandons the use of the traditional toward-step direction from the original conditional gradient algorithm.Instead,at each iteration,it selects the step direction by comparing the exact objective function improvement under the classic away-step and the pairwise away-step directions.The linear polynomial time complexity of the DACG algorithm for solving the (1+∈)-approximate solution of the MEB problem is O(mn/∈).Numerical experimental results show that the DACG algorithm clearly improves the computational efficiency of solving the MEB problem for high-dimensional large-scale datasets.In particular,compared with the classic away-step conditional gradient algorithm,the number of iterations of the DACG algorithm can be reduced by 31.8% to 46.5%,and the running time can be saved by 30.5% to 54.5%.Moreover,numerical experiments further extended the application of the DACG algorithm to support vector data description in machine learning,demonstrating its effectiveness on real-world datasets.

Key words: Conditional gradient algorithm, Classic away-step, Pairwise away-step, Minimum enclosing ball, Support vector date description