The linearized version of an algorithm for the mixed norms problem (Q912569)

One considers the mixed norms optimization problem (also called Weber's problem with the Euclidean and the rectangular norm, Fermat-Weber's problem, Steiner- Weber's problem or generalized Fermat's problem): \[ \text{minimize } \sum^{m}_{r-1} \left[ w,_ r \| x-a_ r \|_1 + w_ r \| x-a_ r \|_2 \right] \text{ subject to } Ax\leq b, \] where \(w_ r\), \(w'_ r\) (\(r=1,\ldots,m\)) are known sequences of nonnegative scalars; \(a_ r\) (\(r=1,\ldots,m\)) is the known set of noncollinear points in \(R^ n\); \(A\) is a given matrix of dimension \(s \times n\); \(b\) is an \(s\times1\) vector; \(\| \cdot \|_1\), \(\| \cdot\|_2\) are the rectangular and the Euclidean norm, respectively. Using some transformations of the mixed norms optimization problem and the duality theory, the authors show that the solution of the optimization problem \[ \text{minimize }\hat b^ T_ y \text{ subject to }\hat A^ T y + \sum sp{m}_{r=1} I_ r t_ r \geq -W^ 1, \quad y \geq 0, \quad t_ r \in K_ r, \quad r=1,\ldots,m, \] determines also the solution of the mixed norms optimization problem. Here \[ \hat b = (b - Aa_1, b-Aa_2, \ldots, b-Aa_ m)_{ms\times1}, \] \[ \hat A = \left[ \begin{matrix} A & 0 \\ 0 & A \end{matrix} \right]_{ms\times k}, \] \[ I_1 = \left[ \begin{matrix} W_1^2 & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 \\ \vdots & \vdots && \vdots \\ 0 & 0 & \ldots & 0 \end{matrix} \right], \ldots, I_ m = \left[ \begin{matrix} 0 & \ldots & 0 & 0 \\ \vdots && \vdots & \vdots \\ 0 & \ldots & 0 & 0 \\ 0 & \ldots & 0 & W_ m^2 \end{matrix} \right], \] \(W^2_ r = \text{diag} \left[ (w_ r)^2, \ldots, (w_ r)^2 \right] \in R^{n\times n},\) \(r=1, \ldots, m,\) \(W^1 = (w^1_1\text{\textbf{1}}, \ldots, w^1_ m\text{\textbf{1}}) \in R^ k\), and \(K_ r\) is the unit ball in \(R^ k\). Since each point \(t_ r \in K_ r\) can be expressed as a linear convex combination of points \(t_{rj}\) belonging to the boundary of \(K_ r\), problem (P) can be solved using Geoffrion's inner linearization technique. An application in the optimal planning process of excavated material for a given set of excavators in an opencast lignite mine is proposed.