1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by $\boldsymbol{A}_i$ and $\boldsymbol{x}1$? Your notation is not clear. $\endgroup$ – MrYouMath May 10 '18 at 13:35
  • $\begingroup$ @MrYouMath, I modify it. $x1$ means that sum of all element in $x$. $\endgroup$ – jason May 10 '18 at 13:38
  • $\begingroup$ The sum of all the elements of $\boldsymbol{x}$ or the sum of the absolute values of all the elements of $\boldsymbol{x}$? $\endgroup$ – MrYouMath May 10 '18 at 13:40
  • $\begingroup$ @MrYouMath since all element of $x$ is nonnegative. so they are the same. Thanks $\endgroup$ – jason May 10 '18 at 13:43
  • 1
    $\begingroup$ @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. $\endgroup$ – measure_theory May 10 '18 at 15:20
4
$\begingroup$

$||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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.