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

作     者：陶杰 张威 卢超 Mark Goh Jie Tao;Wei Zhang;Chao Lu;Mark Goh

作者机构：上海理工大学管理学院上海200093 Center of Excellence in Modelling and Simulation for Next Generation PortsNational University of SingaporeSingapore 117602Singapore 上海大学管理学院上海200444 Business SchoolNational University of SingaporeSingapore 117592Singapore 

出 版 物：《中国科学：数学》 (Scientia Sinica：Mathematica)

年 卷 期：2021年第51卷第12期

页      面：2065-2086页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金(批准号:71601117和71704101) 上海市软科学项目(批准号:19692104600) 教育部人文社科项目(批准号:17YJC630094)资助项目 

主　　题：最小体积覆盖椭球 一阶导数算法 坐标轴下降 

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