Rewrite matrix equation as a quadratic programming problem

Question

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form:

minimize $(1/2)x^TAx + q^Tx$ under the constraint $Mx = b$.

This is how far I got: $Tr(X^TAX)=\sum_{i=1}^nX_{i\cdot}AX_{i\cdot}^{T} =VDV^T$ where D is a block diagonal matrix with A's on the diagonal repeated $p$ times and $V$ is $vec(X)$, that is has columns of $V$ stacked on to it as a vector.

Can you verify if this is correct? Also does $V$ have rows stacked into it or columns stacked into it? What would $M,b,q,x$ be in the quadratic program formulation?

Answer 1

You are right. Usually $\operatorname{vec}$ stacks columns.

Since $A$ appears twice, I will use $Q$ for the Hessian of the quadratic:

• $x = \operatorname{vec}(X)$,
• $Q = I \otimes A$, where $I$ is the identity and $\otimes$ the Kronecker product,
• $q = 0$,
• $M = \operatorname{vec}(C)$,
• $b = \phi$.

Answer 2

You can directly solve your problem. Using Lagrange's conditions, we obtain the following linear system $BX+\lambda C=0,Tr(C^TX)=\phi$, where $B=A+A^T$ and $\lambda\in \mathbb{R}$ is unknown.

If $B$ is invertible and $Tr(C^TB^{-1}C)\not=0$, then $X=-\lambda B^{-1} C$ and consequently $\lambda=-\phi/Tr(C^TB^{-1}C)$. Finally $X=\dfrac{\phi}{Tr(C^TB^{-1}C)}B^{-1}C$. If $B$ is not invertible, then use its pseudo inverse.

EDIT. $f(X)=X^TAX=\dfrac{1}{2}Tr(X^TBX)$. If $B\geq 0$, then $f$ admits a minimum, otherwise the minimum does not necessarily exist. Moreover, if $B$ is not invertible, then $f(X_0)=0$ for $X_0\in \ker(B)$ and $Tr(X_0^TC)=\phi$; in this case, the minimum is $0$. Finally we may assume that $B>0$. Under this hypothesis, the condition $Tr(C^TB^{-1}C)\not= 0$ is equivalent to $C\not=0$.

The value of the minimum is $\dfrac{\phi^2}{2Tr(C^TB^{-1}C)}$ when $B$ is invertible and $0$ otherwise.