期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

求解MEB问题的一种SMO-型方法 被引量：9

An SMO-type method for solving the MEB problem
下载PDF
导出
摘要 目的求解n维空间中m个点的最小闭包球(MEB)问题。方法基于序列最小优化(SMO)的方法,提出了一种近似算法,求解MEB问题的一个(1+ε)-近似。结果建立了此算法的计算复杂度为O(mn/ε),并且算法最终得到一个独立于m,n的大小为O(1/ε)的核心集。结论数值结果表明对于求解高精度的大规模问题,算法是很有效的。 Aim To solve the minimum enclosing ball（MEB） problem of m points in n dimensions.Methods Based on the approach of sequential minimal optimization（SMO）,an approximation algorithm for the MEB problem is proposed,in order to get a（1＋ε）-approximation to the MEB problem.Results This algorithm computes a（1＋ε）-approximation to MEB in O（mn/ε） arithmetic operations and achieves a core set of size O（1/ε）,which is independent of both m and n.Conclusion The numerical results demonstrate the efficiency of the method for solving large-scale problem with a high degree of accuracy.
作者 丛伟杰 刘红卫
机构地区 西安电子科技大学理学院
出处 《西北大学学报（自然科学版）》 CAS CSCD 北大核心 2010年第6期965-969,共5页 Journal of Northwest University（Natural Science Edition）
基金 国家自然科学基金资助项目(61072144) 中央高校基本科研业务费基金资助项目(JY10000970004)
关键词 最小闭包球 序列最小优化 近似算法 计算复杂度 核心集 minimum enclosing balls sequential minimal optimization approximation algorithms computational complexity core sets
分类号 O242.2 [理学—计算数学] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献9

  • 1CHAPELLE O,VAPNIK V,BOUSQUET O,et al.Choosing multiple parameters for support vector machines[J].Machine Learning,2002,46 (1):131-159.
  • 2TSANG I W,KWOK J T,CHEUNG P M.Core Vector machines:Fast SVM training on very large date sets[J].Journal of Machine Learning Research,2005,6 (4):363-392.
  • 3BEN-HUR A,HORN D,SIEGLMANN H T,et al.Support vector clustering[J].Journal of Machine Learning Research,2001,2 (12):125-137.
  • 4KUMAR P,MITCHELL J S B,YILDIRIM E A.Approximate minimum enclosing balls in high dimensions using core-sets[J].The ACM Journal of Experimental Algorithmics,2003,8 (1):1-29.
  • 5YILDIRIM E A.Two algorithms for the minimum enclosing ball problem[J].SIAM Journal on Optimization,2008,19:1368-1391.
  • 6PAN S H,LI X S.An efficient algorithm for the smallest enclosing ball problem in high dimensions[J].Applied Mathematics and Computation,2006,172 (1):49-61.
  • 7田苗,刘红卫,叶峰.求解半定规划问题的一种光滑化方法[J].西北大学学报（自然科学版）,2009,39(1):33-38. 被引量：1
  • 8CHEN P H,FAN R E,LIN C J.A study on SMO-type decomposition methods for support vector machines[J].IEEE Transactions on Neural Networks,2006,17 (4):893-908.
  • 9TODD M J,YILDIRIM E A.On Khachiyan's algorithm for the computation of minimum volume enclosing ellipsoids[J].Discrete Applied Mathematics,2007,155 (13):1731-1744.

二级参考文献5

  • 1CHEN X, TSENG P. Non-interior continuation methods for solving semidefinite complementarity problems [ J ]. Math Program A,2003,95:431-474.
  • 2KANZOW C, NAGEL C. Semidefinite programs : New search directions, smoothing-type methods, and numerical results [ J ]. SIAM Journal on Optimization, 2003,13 : 1-23.
  • 3TOH K C, TUTUNCU R H, TODD M J. SDPT3-a Matlab software package for semidefinite programming, version 2. 1 [J]. Optimization Methods and Software, 1999, 11: 545 -581.
  • 4VANDENBERGHE L, BOYD S. Semidefinite programming [J]. SIAM Review, 1996,38( 1 ) :49-95.
  • 5BORCHERS B. SDPLIB1.2, a library of semidefinite programming test problems [ J ]. Optimization Methods and Software, 1999,11 - 12:6834590.

同被引文献71

引证文献9

二级引证文献20

西北大学学报（自然科学版）
2010年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部