Least-squares problem over the standard simplex

Question

$$\begin{array}{ll} \text{minimize} & \Vert \mathbf{x-Da}\Vert_2^2\\ \text{subject to} & \sum \mathbf{a}_i=1\\ & \mathbf{a}_i \geq 0\end{array}$$

How to convert this problem into an equivalent quadratic program so that I can use Matlab's quadprog function to solve this?

Answer 1

Hint: $||\mathbf{x-Da}\Vert_2^2$ is equivalent to

$(\mathbf{x-Da})^T\cdot (\mathbf{x-Da})=(\mathbf{x^T-a^TD^T})\cdot (\mathbf{x-Da})$

$=\mathbf{x^Tx-x^TDa-D^Ta^Tx+a^TD^TDa}$

Answer 2

You can write the objective as follows,

$$ \|\mathbf{x-Da}\|_2^2 = (\mathbf{x-Da})^T(\mathbf{x-Da}) = \mathbf{a^TD^TDa-2x^TDa}+\|\mathbf{x}\|^2 $$

You can neglect $\|\mathbf{x}\|^2$ since its a constant. The remaining is a quadratic function of the form $\mathbf{\frac{1}{2}a^TQa+c^Ta}.$ Similarly express the linear constraints in the form of $\mathbf{Pa}\leq \mathbf{q}$ and you have a QP.