最小闭包球问题近似算法的加速策略

Speed-up strategies of approximation algorithm for the minimum enclosing ball problem

结合最小闭包球(Minimum Enclosing Ball,MEB)问题近似算法的加速策略,到求解MEB问题的序列最小最优化(Sequential Minimal Optimization,SMO)近似算法中,分析给出基于远离步策略、确定并除去内部点策略及割平面法策略和积极集策略的SMO-型算法。数值实验结果表明,远离步策略能够有效减少核心集的大小,其他策略均能不同程度的提高算法的运行速度,积极集策略是最快的加速策略。

By incorporating speed-up strategies to the sequential minimal optimization （SMO） method for the minimum enclosing ball （MEB） problem, several SMO-type algorithms are proposed respectively based on the away steps strategy, the identification and elimination of interior points, the cutting plane method and the active set strategy. The numerical results show that the away steps strategy can effectively reduce the size of core set and all other strat- egies can improve running speed of the algorithm. In particular, the active set strategy is the fastest speed-up strategy.