Minimise $\sum_i \begin{Vmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{Vmatrix}$

Question

Consider column vectors $\boldsymbol{z}_i$, $\quad i=1,\dots,n$.
Each $\boldsymbol{z}_i$ has $j$ elements and can be expressed as $\boldsymbol{z}_i = \begin{bmatrix} \boldsymbol{x}_i \\ \boldsymbol{y}_i \end{bmatrix}$ where by $\boldsymbol{x}_i$ and $\boldsymbol{y}_i$ are the first $k$ and last $j-k$ elements respectively.

Given $\boldsymbol{y}_1,\boldsymbol{y}_2,\dots,\boldsymbol{y}_n$, find $\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_n$ such that $\sum_i \| \boldsymbol{z}_i \| $ is minimised and $\sum_i \boldsymbol{x}_i = \boldsymbol{c}$ for some $k$-element column vector $\boldsymbol{c}$.

In words: Minimise the sum of lengths of a set of vectors {$\boldsymbol{z}_i$}. Each vector $\boldsymbol{z}_i$, has some fixed elements $\boldsymbol{y}_i$ and some variable elements $\boldsymbol{x}_i$. Each of the variable elements has a fixed sum across the vectors expressed as $\sum_i \boldsymbol{x}_i = \boldsymbol{c}$. This could also be written $\sum_i x_{i,m} = c_m$ for each element $m$.

The solution is $\boldsymbol{x}_i = \boldsymbol{c} \frac{\| \boldsymbol{y}_i \|}{ \overline{\|\boldsymbol{y}\|} } \quad $ where $\overline{\|\boldsymbol{y}\|}=\sum_i{\|\boldsymbol{y}_i\|}$.

In words: The minimum total length is achieved by apportioning the variable components among the vectors in the ratio of the lengths of the fixed components.

The problem can be solved with Lagrange multipliers.

Question: Is there a simpler solution? Can it be solved with matrix algebra alone? It feels similar to the least-squares regression matrix formula.

Answer 1

Converted from my comments. The first observation is that you can assume the $y_i$ to be nonnegative scalars: indeed, you can replace $y_i$ with $\|y_i\|$ without changing the problem.

Then, the thesis follows from the triangle inequality. Indeed, $$ \begin{aligned} \|z_1\| + \|z_2\| + \dots + \|z_n\| &\geq \|z_1 + z_2 + \dots + z_n\| \\ & = \left\|\begin{bmatrix}c \\ \overline{y}\end{bmatrix}\right\| \\&= \left\|\begin{bmatrix}c\frac{y_1}{\overline{y}} \\ y_1\end{bmatrix} + \dots + \begin{bmatrix}c\frac{y_n}{\overline{y}} \\ y_n\end{bmatrix} \right\| \\&= \left\|\begin{bmatrix}c\frac{y_1}{\overline{y}} \\ y_1\end{bmatrix}\right\| + \dots + \left\|\begin{bmatrix}c\frac{y_n}{\overline{y}} \\ y_n\end{bmatrix} \right\|. \end{aligned} $$ with $\overline{y} = y_1 + y_2 + \dots + y_n$. The last equality holds because all the vectors in the last expression are nonnegative scalar multiples of $\begin{bmatrix}c\frac{1}{\overline{y}} \\ 1\end{bmatrix}$.

(If $\overline{y}=0$, then you can take any partition of $1$ in place of the quantiieis $\frac{y_i}{\overline{y}}$ and the proof works in the same way.)

The geometric idea behind this proof is the following: let $k=j-k=1$ for simplicity, so that we are on the plane. You wish to travel from the point $(0,0)$ to $(c,\overline{y})$, and you are allowed to move along a polygonal line that bends only in points with ordinates $y_1, y_1+y_2,\dots, y_1+y_2+\dots+y_{n-1}$. Then, clearly, the shortest path is a straight line, making no bends.