1
$\begingroup$

I have the following cost function.

$J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$

Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars.

How can I find W?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

First of all, note that $$J = \mathop{\textrm{Trace}}(W^TQW), \qquad Q \triangleq \sum_{i=1}^N a X_i - b Y_i$$ Furthermore, if we break $W$ into columns, and stack them on top of each other to produce a long vector $\bar{w}$, $$W \triangleq \begin{bmatrix} w_1 & w_2 & \dots & w_N \end{bmatrix}$$ then we can express $J$ as $$J = \sum_{i=1}^N (W^TQW)_{ii} = \sum_{i=1}^N w_i^T Q w_i = \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_N \end{bmatrix}^T \begin{bmatrix} Q \\ & Q \\ & & \ddots \\ & & & Q \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_N \end{bmatrix}$$ So if we call the long "stacked" vector $\bar{w}$, and the block diagonal matrix $\bar{Q}$, then $J=\bar{w}^T\bar{Q}\bar{w}$, a simple quadratic form. Sure, it's got a lot of structure, but it can still be represented in a standard quadratic programming context.

If $Q$ is positive semidefinite, the so will $\bar{Q}$ be, and this cost function can be minimized in a standard quadratic programming or convex programming framework. If you're seeking to minimize the unconstrained cost, it's $J=0$ and $W=0$. It can also be written in this case as $\|Q^{1/2}W\|_F^2$, where $Q^{1/2}$ is a matrix square root of $Q$.

If $Q$ is not positive semidefinite, then attempts to minimize it are non-convex. Constrained problems will be intractable except in very limited special cases. The unconstrained minimum will be unbounded below; that is, it will be possible to obtain any negative value of $J$ with appropriate choice of $W$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .