# minimization with orthogonality constraint

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.

-
can you put in a few steps to explain "However, you can simplify the problem by transforming A and B to diagonal form (spectral factorization), and transforming X accordingly. This preserves the orthogonality constraint, and simplifies the objective function to $\sum_{i,k}a_ib_kX_{ik}^2$? –  qlinck Nov 18 '12 at 17:51
done in the main answer. –  Arnold Neumaier Nov 18 '12 at 18:11
Thanks for the wonderful answer –  qlinck Nov 18 '12 at 18:23
Can you explain the approach "parameterize Z as a product of reflections or rotations, and pose the problem of finding the optimal parameters as an unconstrained optimization problem" in few steps?? I may need to look at an example to understand/learn about it at my level of maturity.. –  qlinck Nov 18 '12 at 19:25
done in the main answer. –  Arnold Neumaier Nov 18 '12 at 19:47