Skip to main content
MathOverflow

Return to Question

Bumped by Community user
Post Reopened by R.P., Federico Poloni, Carlo Beenakker, Mark Wildon, Todd Trimble
added 4 characters in body; edited title
Source Link
Lincoln Hannah
Lincoln Hannah
  • 21
  • 4

Minimise $\sum_i \Bigl\|\begin\begin{bmatrixVmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{bmatrixVmatrix} \Bigr\|$$

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 $$\boldsymbol{x}_i = \boldsymbol{c} \frac{\| \boldsymbol{y}_i \|}{ \overline{\|\boldsymbol{y}\|} } \quad $ where $\|\overline{ \boldsymbol{y}}\|=\sum_i{\|\boldsymbol{y}_i\|}$$\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.

Minimise $\sum_i \Bigl\|\begin{bmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{bmatrix} \Bigr\|$

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.

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

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.

changed single bars to double bars, lowercased c, retagged, other smaller edits.
Source Link
Federico Poloni
Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120

Minimise $\sum_i \begin\Bigl\|\begin{vmatrixbmatrix} \boldsymbol\boldsymbol{x}_i \\ \boldsymbol{y}_i \end_i\end{vmatrixbmatrix}$ \Bigr\|$

Consider a set of column vectors {$\boldsymbol{z}_i$}, $\quad i=1,...n$$\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.

FindGiven $\boldsymbol{x}_i$ for$\boldsymbol{y}_1,\boldsymbol{y}_2,\dots,\boldsymbol{y}_n$, find $i = 1,..n $$\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_n$ such that $\sum_i \begin{vmatrix} \boldsymbol{z}_i \end{vmatrix} $$\sum_i \| \boldsymbol{z}_i \| $ is minimised and $\sum_i \boldsymbol{x}_i = \boldsymbol{C}$$\sum_i \boldsymbol{x}_i = \boldsymbol{c}$ for some $k$ element-element column vector $\boldsymbol{C}$$\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}$$\sum_i \boldsymbol{x}_i = \boldsymbol{c}$. This could also be written $\sum_i x_{i,m} = C_m$$\sum_i x_{i,m} = c_m$ for each element $m$.

The solution is $\boldsymbol{x}_i = \boldsymbol{C} \frac{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}} } \quad $$\boldsymbol{x}_i = \boldsymbol{c} \frac{\| \boldsymbol{y}_i \|}{ \| \overline{\boldsymbol{y}} \| } \quad $ where $\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}}=\sum_i{\begin{vmatrix}\boldsymbol{y}_i\end{vmatrix}}$$\|\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.

CanThe problem can be solved with La-Grange multiplierLagrange 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.

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

Consider a set of column vectors {$\boldsymbol{z}_i$}, $\quad i=1,...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.

Find $\boldsymbol{x}_i$ for $i = 1,..n $ such that $\sum_i \begin{vmatrix} \boldsymbol{z}_i \end{vmatrix} $ 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{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}} } \quad $ where $\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}}=\sum_i{\begin{vmatrix}\boldsymbol{y}_i\end{vmatrix}}$

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.

Can be solved with La-Grange multiplier.

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

Minimise $\sum_i \Bigl\|\begin{bmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{bmatrix} \Bigr\|$

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.

added 1014 characters in body
Source Link
Lincoln Hannah
Lincoln Hannah
  • 21
  • 4

Minimise $\sum_i \begin{vmatrix} \boldsymbol{x}_i \\ \boldsymbol{y}_i \end{vmatrix} $ overConsider a set of column vectors {$\boldsymbol{x}_i$$\boldsymbol{z}_i$}, such that $\quad i=1,...n$
$\sum_i \boldsymbol{x}_i = \boldsymbol{C}, \quad i=1..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.

Find $\boldsymbol{x}_i$ for $i = 1,..n $ such that $\sum_i \begin{vmatrix} \boldsymbol{z}_i \end{vmatrix} $ is minimised and $\boldsymbol{y}_i$ are$\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$}. TheEach 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{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\sum_i \begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}$$\boldsymbol{x}_i = \boldsymbol{C} \frac{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}} } \quad $ where $\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}}=\sum_i{\begin{vmatrix}\boldsymbol{y}_i\end{vmatrix}}$

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.

Can be solved with La-Grange multiplier. But is

Question: Is there a simpler solution?

Can Can it be solved with matrix algebra alone? It feels similar to the least-squares regression matrix formula.

Minimise $\sum_i \begin{vmatrix} \boldsymbol{x}_i \\ \boldsymbol{y}_i \end{vmatrix} $ over {$\boldsymbol{x}_i$}, such that $\sum_i \boldsymbol{x}_i = \boldsymbol{C}, \quad i=1..n$

$\boldsymbol{x}_i$ and $\boldsymbol{y}_i$ are column vectors. The solution is $\boldsymbol{x}_i = \boldsymbol{C} \frac{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\sum_i \begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}$

Can be solved with La-Grange multiplier. But is there a simpler solution?

Can it be solved with matrix algebra alone? It feels similar to the least-squares regression matrix formula.

Consider a set of column vectors {$\boldsymbol{z}_i$}, $\quad i=1,...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.

Find $\boldsymbol{x}_i$ for $i = 1,..n $ such that $\sum_i \begin{vmatrix} \boldsymbol{z}_i \end{vmatrix} $ 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{\begin{vmatrix} \boldsymbol{y}_i \end{vmatrix}}{\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}} } \quad $ where $\overline{ \begin{vmatrix} \boldsymbol{y} \end{vmatrix}}=\sum_i{\begin{vmatrix}\boldsymbol{y}_i\end{vmatrix}}$

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.

Can be solved with La-Grange multiplier.

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

Post Closed as "Needs details or clarity" by Mark Wildon, David Roberts♦, LeechLattice, R.P., Federico Poloni
Source Link
Lincoln Hannah
Lincoln Hannah
  • 21
  • 4