摘要
最小体积覆盖椭球问题是一个基本的凸优化问题.本文给出最小体积覆盖椭球问题的新性质—对算法依坐标轴光滑性,据此提出一种坐标轴下降算法来计算最小体积覆盖椭球并证明该算法的收敛速度是全局次线性收敛且局部线性收敛的.从计算时间角度来看,该算法优于经典的Frank-Wolfe算法,并且这种优势对于高维数据集尤为明显.更进一步,我们发现该算法在计算最小体积覆盖椭球问题方面比随机坐标轴下降算法更有优势.最后通过大规模数值算例测试来验证我们得到的理论结果.
The minimum volume enclosing ellipsoid(MVEE)is a basic convex optimization problem.This paper describes some new properties such as“algorithmic coordinate-wise smoothness”of this model and proposes a steepest descent type algorithm,the coordinate gradient descent(CGD)algorithm,to address the MVEE problem.We prove that the CGD algorithm is sublinearly convergent.Moreover,it is shown to converge in a linear rate locally,and slightly faster than the FW type algorithms,especially in the cases of large dimensions.At last,we compare our algorithm with the random coordinate descent(RCD)method and show that the RCD algorithm is less efficient than the CGD algorithm in computing the MVEE.The numerical tests support our theoretical results.
出处
《中国科学：数学》
CSCD
北大核心
2021年第12期2065-2086,共22页
Scientia Sinica：Mathematica
基金
国家自然科学基金(批准号:71601117和71704101)
上海市软科学项目(批准号:19692104600)
教育部人文社科项目(批准号:17YJC630094)资助项目。
关键词
最小体积覆盖椭球
一阶导数算法
坐标轴下降
minimum volume enclosing ellipsoid
first-order algorithm
coordinate descent
