计算最小体积覆盖椭球的坐标轴下降算法

• 作者: 陶杰 张威 卢超 Mark Goh
• 来源期刊: 中国科学（数学）
• 关键词: 最小体积覆盖椭球 一阶导数算法 坐标轴下降
• 年，卷（期）: 2021,（12）
• 所属期刊栏目: 论文
• 页码范围: 2065-2086
• 页数: 22页
• 语种: 中文
• DOI: 10.1360/SCM-2018-0795

摘要

最小体积覆盖椭球问题是一个基本的凸优化问题.本文给出最小体积覆盖椭球问题的新性质—对算法依坐标轴光滑性,据此提出一种坐标轴下降算法来计算最小体积覆盖椭球并证明该算法的收敛速度是全局次线性收敛且局部线性收敛的.从计算时间角度来看,该算法优于经典的Frank-Wolfe算法,并且这种优势对于高维数据集尤为明显.更进一步,我们发现该算法在计算最小体积覆盖椭球问题方面比随机坐标轴下降算法更有优势.最后通过大规模数值算例测试来验证我们得到的理论结果.