The linearized version of an algorithm for the mixed norms problem (Q912569)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The linearized version of an algorithm for the mixed norms problem |
scientific article |
Statements
The linearized version of an algorithm for the mixed norms problem (English)
0 references
1989
0 references
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.
0 references
mixed norms optimization problem
0 references
Weber's problem
0 references
Fermat-Weber's problem
0 references
Steiner-Weber's problem
0 references
generalized Fermat's problem
0 references
inner linearization technique
0 references
optimal planning process
0 references