求解加权最小闭包球问题的列生成算法

Column Generation Algorithm for Solving Weighted Minimum Enclosing Ball Problem

先建立求解加权最小闭包球(WMEB)问题的序列最小最优化(SMO)算法的线性收敛性,再结合列生成算法的思想,即每次迭代将与当前球心加权距离最远的点加到核心集中,并调用SMO算法,提出一种求解WMEB问题的列生成算法.数值实验结果表明,该算法能有效提高求解大规模数据集上WMEB问题的计算效率.

Firstly,the linear convergence of sequential minimal optimization(SMO)algorithm for solving the weighted minimum enclosing ball(WMEB)problem was established.Secondly,by incorporating the idea of column generation algorithm into the SMO algorithm,we proposed a column generation algorithmfor solving the WMEB problem.The algorithm added the furthest point of weighted distance from the current ball center to the core set at each iteration.The results of numerical experiments show that the proposed algorithm can effectively improve the computational efficiency of solving the WMEB problem on large-scale data sets.