# How to optimize $\sum_{i=1}^{T}\|A_ix - b_i\|^2$ subject t0 $\sum_i x = 1$ and $x \geq 0$

How to solve the follow optimization problem?

$$\begin{array}{ll} \text{minimize} &\displaystyle\sum_{i=1}^{T} \| \mathbf{A}_i\mathbf{x} - \mathbf{b}_i \|^2\\ \text{subject to} & \mathbb{1}^\top {\mathbf{x}} = 1\\ & \mathbf{x} \geq 0\end{array}$$

where $\mathbf{x} \in \mathbb R^{n}$ is a vector and $\mathbf{b}_i \in \mathbb R^{m}$ are a sequence of vectors and $\mathbf{A}_i \in \mathbb R^{m \times n}$ is a sequence of matrices. $T$ is the number of equation. The constraints mean that all element of vector $\mathbf{x}$ are non-negative and that the sum of its elements is equal to $1$.

A simple reduction is solve in How to optimize $\|Ax - b\|^2$ subject t0 $x1 = 1$, $x\geq 0$

This time, my goal is to jointly optimize those $T$ equation.

My second question is the following. How to show constraint $\mathbf{x}$ is in compact convex set?

• What do you mean by $\boldsymbol{A}_i$ and $\boldsymbol{x}1$? Your notation is not clear. – MrYouMath May 10 '18 at 13:35
• @MrYouMath, I modify it. $x1$ means that sum of all element in $x$. – jason May 10 '18 at 13:38
• The sum of all the elements of $\boldsymbol{x}$ or the sum of the absolute values of all the elements of $\boldsymbol{x}$? – MrYouMath May 10 '18 at 13:40
• @MrYouMath since all element of $x$ is nonnegative. so they are the same. Thanks – jason May 10 '18 at 13:43
• @MrYouMath It just came off overly rude. There's a difference between providing constructive comments that help the OP get their question answered and trying to make them feel stupid. Seems to me like he put a good amount of effort into thinking about the question before posting, which is much more than we can say for a lot of other posts. – measure_theory May 10 '18 at 15:20

$||z||_2^2 + ||w||_2^2$ is equal to $\left|\left|\begin{matrix}z\\w\end{matrix}\right|\right|_2^2$ so you already have the answer as all you have to do is to stack your expressions (i.e. create a large $A$ and $b$ matrix from the given ones)

I assume $\| \cdot \|$ is the $\ell_2$-norm. Let $$A = \begin{bmatrix} A_1 \\ A_2 \\ \vdots \\A_T \end{bmatrix}, \qquad b = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_T \end{bmatrix}.$$ Then $$\sum_{i=1}^T \| A_i x - b_i \|^2 = \| Ax - b \|^2.$$ So you can use the solution in the question you linked to.