3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – jason Jul 14 '17 at 14:34
  • 1
    $\begingroup$ @jason Write a new question and link to this question. $\endgroup$ – Rodrigo de Azevedo Jul 14 '17 at 16:58
  • $\begingroup$ Sure. The new question is here. math.stackexchange.com/questions/2358683/… $\endgroup$ – jason Jul 14 '17 at 23:41

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.