Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
For positive semi-definite symmetric matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:
that $X$ is orthogonal.
All the matrices have real entries and $A,B$ are square while $X$ is rectangular. Thanks.
This is what I have:
Define $B=F^{T}F$. Define $Y=FX$. You get the above problem as \begin{align} \min_{Y}~ \text{trace}(AY^{T}Y) \end{align}
But now I want $X^*$ that minimizes the original problem. This is what is confusing me!
I guess that $A$ and $B$ are also assumed symmetric.
Your second optimization problem is not equivalent to the first, for two reasons:
(1) You forgot the constraint $YY^T=FF^T$, which corresponds to the old orthogonality constraints.
(2) $F$ may be singular, in which case you cannot reconstruct $X$ from $Y$.
As a result, your transformation gained nothing. Indeed, there doesn't seem to be a closed form solution.
However, you can simplify the problem by transforming $A$ and $B$ to diagonal form (spectral factorization), and transforming $X$ accordingly: Factor $A=QaQ^T$, $B=UbU^T$ with $a,b$ diagonal, $Q,U$ square orthogonal, and define $Z=U^TXQ$. Then $Z$ is orthogonal, $tr~AX^TbX=tr~ aZ^TbZ$, and $X$ can be recovered as $X=UZQ^T$. Thus this preserves the orthogonality constraint, and simplifies the objective function to $\sum_{i,k} a_ib_k Z_{ik}^2$.
Now you have two options:
(i) Pose the problem as a constrained optimization problem to a standfard constrained optimization problem solver such as IPOPT.
(ii) Parameterize $Z$ as a product of reflections or rotations. (This is the Householder or givens version of the QR factorization, applied to an orthogonal matrix $Z$. Use the reflection vectors respective rotation angles as new variables.) Then pose the problem of finding the optimal parameters as an unconstrained optimization problem.
Note that (i) is significantly simpler to prepare, as for high solution quality, one should provide the solver with explicit first derivative information.
