How to derive the closed-form solution for this optimization problem?

640 Views Asked by At

$$\begin{array}{ll} \text{maximize} & \mbox{tr} (A^T B A)\\ \text{subject to} & A^T A = I\end{array}$$

where the maximization is over $A$.

I know that the solution is eigenvectors of $B$, but I don't know how to arrive at it. In particular, constructing the Lagrangian is not straightforward because the constraint is a matrix equation while the objective function is scalar.

1

There are 1 best solutions below

2
On BEST ANSWER

Say instead of A, we solve for columns of A one by one.

max $u^TBu$

such that $u^Tu=1$

Construct the lagrangian, then differentiate to get:

$dL/du$=2Bu-2 $\lambda u$

Equate to zero, solve, you end up with Eigen decomposition problem of B.

Now pick the Eigen vector that corresponds to the largest Eigen value. If you want more solutions (more colums to A, pick the second and the third Eigen vectors that corresponds to second and third largest Eigen value and so on)