大规模数据集轴向椭球覆盖问题的积极集算法

An active set algorithm for the axis-aligned ellipsoidcovering problem on large-scale datasets

对求解大规模数据集的最小体积轴向椭球(Minimum Volume Axis-Aligned Ellipsoid, MVAE)覆盖问题进行研究。基于机器学习中序列最小优化(Sequence Minimal Optimization, SMO)算法的思想,设计一种近似求解MVAE的二阶SMO-型算法,使用对偶目标函数的二阶近似选择最小工作集,并且每次迭代只更新所选工作集对应可行解的两个分量。结合积极集加速策略,给出求解MVAE覆盖问题的一个积极集算法,进一步提高算法处理大规模数据集的计算效率。数值实验结果表明,所提算法能快速有效地处理大规模数据集的MVAE覆盖问题。

The minimum volume axis-aligned ellipsoid(MVAE)covering problem of large-scale datasets is studied.Based on the idea of sequence minimal optimization(SMO)algorithm in machine learning,a second-order SMO-type algorithm for approximately solving MVAE is designed.The algorithm uses a second-order approximation of the dual objective function to select the minimum working set,and it updates only two components of the feasible solution corresponding to the selected working set at each iteration.In order to further improve the computational efficiency of the algorithm to deal with large-scale datasets,an active set algorithm for solving the MVAE covering problem is proposed by combining an active set acceleration strategy.Numerical experimental results show that the proposed algorithm can quickly and efficiently handle the MVAE covering problem of large-scale datasets.