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
    0 references
    0 references
    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
    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

    Identifiers