Two unconstrained optimization approaches for the Euclidean \(\kappa \)-centrum location problem (Q2383649): Difference between revisions

Given a positive integer \(k\), \(1\leq k\leq m\), the single facility Euclidean \(k\)-center problem in \(\mathbb R^n\) consists in locating a new facility so as to minimize the sum of the \(k\) largest weighted Euclidean distances to the existing \(m\) facilities. If \(a_i\in\mathbb R^n\) represents the position of the \(i\)-th existing facility, then \[ f_i(x)=\omega_i((x_1-a_{i1})^2+\cdots+ (x_n-a_{in})^2)^{1/2} \] is the weighted Euclidean distance between a new facility and the \(i\)-th existing facility \((\omega_i>0\) is the associated weight). Two efficient algorithms for solving this problem are proposed. The first one is based on the neural networks smooth approximation of the objective function and on reducing the problem to an unconstrained smooth convex minimization problem. The second one in based on the Fischer-Burmeister merit function. The Karush-Kuhn-Tucker system is transformed into an equivalent unconstraint smooth minimization problem. This problem is then solved using an appropriate minimization method. Both methods are reported to be extremely efficient, the first algorithm is able to solve problems for \(n\) up to 10000. Numerical experiments in the concluding part of the paper demonstrate the efficiency of the proposed algorithms.