Quadratic program with equality and non-negativity constraints

Question

How to solve the following quadratic program with equality and non-negativity constraints?

$$\begin{array}{ll} \text{minimize} & \| \mathbf{B} - \mathbf{P}\mathbf{A} \|_F^2\\ \text{subject to} & {\mathbf{P}}^T\mathbb{1} = \mathbb{1}\\ & \mathbf{P} \geq 0\end{array}$$

where $A$ and $B$ are given and $\mathbb{1}$ is a vector containing only $1$'s, which makes matrix $P$ a transition matrix. Will there be a closed-form solution? If not, how to solve it? Thanks so much.

Answer 1

We have the following convex quadratic program (QP) in $\mathrm P \in \mathbb R^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm P \mathrm A - \mathrm B \|_{\text{F}}^2\\ \text{subject to} & 1_n^\top \mathrm P = 1_n^\top\\ & \mathrm P \geq \mathrm O_n\end{array}$$

Vectorizing, $\mathrm x := \mbox{vec} (\mathrm P)$, we can rewrite the QP above in a more standard form

$$\begin{array}{ll} \text{minimize} & \| (\mathrm A^\top \otimes \mathrm I_n) \,\mathrm x - \mbox{vec}(\mathrm B) \|_2^2\\ \text{subject to} & (\mathrm I_n \otimes 1_n^\top) \,\mathrm x = 1_n\\ & \mathrm x \geq \mathrm 0_{n^2}\end{array}$$

which can be solved numerically using a QP solver.