基于LBFGS的求解最小闭包球的光滑化方法-论文.pdf

《基于LBFGS的求解最小闭包球的光滑化方法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、系统科学与数学J．Sys．Sci．＆Math．Scis33(5)(2013，5)，617—625基于LBFGS的求解最小闭包球的光滑化方法叶峰刘三阳刘红卫周水生(西安电子科技大学数学系，西安710071)摘要考虑在n维空间中求m个球的最小闭包球(theSmallestEnclosingBall，SEB)问题．首先将SEB问题转化为一个含有函数max(0，z)的等价无约束非光滑凸优化问题，然后利用光滑化技巧和有限内存BFGS方法来求解高维空间中的SEB问题，并分析了方法的收敛性．数值实验结果表明文中给出的算法是有效的

2、．关键词SEB问题，极大极小问题，非光滑优化，光滑逼近，有限内存BFGS方法MR(2000)主题分类号90C47ASMooTHINGALGoRITMF0RSMALLESTENCL0SINGBALLPRoBLEMSBASED0NLIMITEDMEMoRYBFGSMETH0DYEFengLIUSanyangLIUHongweiZHOUShuisheng(DepartmentofMathematics，XidianUniversity，xi’an710071)AbstractConsidertheproblemofcom

3、putingthesmallestenclosingballofasetcomposedofmballsinndimensionspace．First．theproblemistransformedintoanunconstrainedconvexoptimizationprobleminvolvingthemaximumfunctionmax(0，1，thenthesmoothingtechniqueandthelimitedmemoryBFGSmethodareusedtosolveSEBprobleminhi

4、ghdimensions，andalsotheconvergenceofthealgo—rithmisproved．Numericalresultsindicatetheefectivenessofthealgorithm．KeywordsSEBproblems，minimaxproblems，nonsmoothoptimization，smoothapproximation，limitedmemoryBFGSmethod．国家自然科学基金(61179040，61072144)资助课题收稿日期：2012—03—06

5、，收到修改稿日期：2012—06—26618系统科学与数学33卷1引言72维空间R中一个以Ci为中心，以n之0为半径的球Bi是指闭集合Bi={X∈R”：一clj)．在中给定m个球的集合B={B1，B2，⋯，B}，最小闭包球(theSmallestEnclosingBal1)问题就是找一个半径最小的球能够包含B中的m个球．这个问题很容易就可以改写为下列的非光滑凸优化问题，即极大极小问题min，()^()，(1)其中()=lIx—Cill+ri，i=1，2，⋯，m．注意到函数f(x)是严格凸的，所以问题(1)的解是存在

6、并且唯一的．SEB问题在定位分析，军事运筹学，以及模式识别等方面都有广泛应用，而这个问题本身在计算几何中也是一个很有意义的问题[1-5】．现在已经有很多算法来用于求解问题(1)，特别地，当半径n=0时，问题(1)就变为有限个点的最小闭包球问题．当点的维数n比较小(n30)时，文[3，6-9]中的计算几何方法无论在理论上，还是在实验中都可以得到很好的结果．但这些方法应用于高维空间中的问题效率就很低了，例如支撑向量机分类问题[10-12]需要在高维空间中进行计算．文献f9]中，G~rter和SchSherr用二次规划方

7、法求解问题(1)，但它的高精度要求限制它只能处理维数n300的问题．注意到SEB问题的特殊结构，Zhou[13]等人提出了利用熵函数来光滑逼近极大值函数(z)=max(0，z)，从而将问题(1)转化为光滑的无约束优化问题近似求解，它可以解决高维空间中的最小闭包球问题，其方法主要是基于内点法的思想．Kumar等人_14]利用二次锥规划和核集的思想给出了一个多项式时间的(1+￡)逼近算法来解决高维空间中的最小闭包球问题，但其实验结果也只能达到佗=1400的情况．在此基础上，Fischer等人[15]提出了一个组合算法来

8、解决包含点的最小闭包球问题，此算法能有效解决维数n从2000到10000的问题，这实质上类似于线性规划单纯形法的转轴算法．本文利用精确罚函数方法将问题(1)转化为等价的含有函数max(0，z)的非光滑无约束优化问题，然后构造一个新的光滑函数对函数max(0，)进行光滑逼近，同时给出了一个收敛的有限内存BFGS算法．此算法能解决维数佗和个数m都很大时的SEB问