基于二阶序列最小优化的最小闭包球近似算法

对求解大规模高维数据集的最小闭包球问题进行研究。基于机器学习中训练支持向量机的序列最小优化(Sequential Minimal Optimization,SMO)算法,提出一种近似计算最小闭包球的二阶SMO-型算法。利用Lagrangian对偶函数的二阶泰勒展开式计算新的工作集,每次迭代只更新工作集所对应可行解的两个分量,构造新的可行解,并建立二阶SMO-型算法的多项式时间复杂度。数值实验结果表明,对于大规模高维数据集,二阶SMO-型算法比一阶SMO-型算法运行速度更快,尤其结合了加速技术的二阶SMO-型算法计算效率更高。

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

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