The weighted Euclidean one-center problem in $${\mathbb {R}}^n$$
针对Rn中带权点集，提出寻找最小半径欧几里得球的原始和对偶算法，每步沿射线或二维圆弧搜索，可求解高维大规模问题。
Abstract Given a finite set of distinct points in $${\mathbb {R}}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> and a positive weight for each point, primal and dual algorithms are developed for finding the Euclidean ball of minimum radius so that the weighted Euclidean distance between the center of the ball and each point is less than or equal to the radius of the ball. Each algorithm is based on a directional search method in which the search path at each iteration is either a ray or a two-dimensional circular arc in $${\mathbb {R}}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> . At each iteration, a search path is constructed by intersecting bisectors of pairs of points, where the bisectors are either hyperplanes or n -dimensional spheres. Each search path preserves complementary slackness and primal (dual) feasibility for the primal (dual) algorithm. The step size along each search path is determined explicitly. Test problems up to 1000 dimensions and 10,000 points were solved to optimality by both primal and dual algorithms. Computational results also show that these algorithms outperform several open-source SOCP codes.