Programa cuadrático con restricciones de igualdad y no negatividad

Question

¿Cómo resolver el siguiente programa cuadrático con restricciones de igualdad y no negatividad?

$$\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}$$

donde $A$ y $B$ se dan y $\mathbb{1}$ es un vector que sólo contiene $1$ lo que hace que la matriz $P$ una matriz de transición. ¿Habrá una solución de forma cerrada? Si no es así, ¿cómo resolverla? Muchas gracias.

Answer 1

Tenemos lo siguiente convexo programa cuadrático (QP) en $\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}$$

Vectorización, $\mathrm x := \mbox{vec} (\mathrm P)$ podemos reescribir la QP anterior en una forma más estándar

$$\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}$$

que puede resolverse numéricamente utilizando un solucionador QP.