# Quadratic program with equality and non-negativity constraints

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.

• This problem is not convex. $P^TP-I=0$ is not affine. – Ture Jul 13 '17 at 18:28
• Thanks, that make sense – jason Jul 13 '17 at 20:45
• There is no closed form solution. In fact, even a standard "nonnegative least squares" problem has no closed form solution. – littleO Jul 14 '17 at 1:45

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.

• Thanks, I have following question, says now $J(P,A)$ is involving two variables $P$ and $A$. and the objective is not joint convex with both $P$ and $A$. we can solve it by multiplicative update rules. fixed $P$ update $A$, then fix $A$ update $P$. when $P$ is fixed, $J(A)$ is easy to solve; when $A$ is fixed, use your QP solver. My question is that: will this technique finally converge. I mean the $J$ will non-increase. Thanks – jason Jul 14 '17 at 14:34
• @jason Write a new question and link to this question. – Rodrigo de Azevedo Jul 14 '17 at 16:58
• Sure. The new question is here. math.stackexchange.com/questions/2358683/… – jason Jul 14 '17 at 23:41