# minimization problem: sum of Rayleigh quotients

I would like to find $x$ which minimizes the following equation:

$\frac{x^HAx}{x^HBx} + \frac{x^HCx}{x^HDx}$ where A, B, C, D are positive-definite. $x$ is not a very large vector (<1000 elements in size.)

The problem is easily solvable as a generalized eigenvalue problem when A or C=0, but I am not sure what the best approach is for the general case.

Thanks!

-
I think your problem is a bit ill-defined. If you have a solution to the problem with $\lambda = 0$, simply reuse the same solution but make $x$ much much smaller. –  Geoffrey Irving Feb 9 '13 at 4:06
Oops, you are completely correct! The first term is scale invariant while the second one can indeed be minimized by scaling down x. I will reword my question to fix the scale issue. Thanks! –  Costis Feb 9 '13 at 4:48

-
Thanks the for the paper. It indeed looks like they are solving a similar problem. However, they are maximizing the quantity rather than minimizing. I am not sure if there is a straightforward adaptation of the method to the minimization problem. –  Costis Feb 27 '13 at 23:48
Wouldn't you just negate the matrices? –  Geoffrey Irving Feb 28 '13 at 17:12
Oh, I misread. It seems like just W needs to be pos-def which is the matrix in the denominator. So negating should likely work. Thanks! –  Costis Feb 28 '13 at 22:42

Geoffrey already posted a solution that is adapted to your particular problem. As a general suggestion, here's another approach. Let me define the following function: $$J_\alpha(x) = \alpha \frac{x^HAx}{x^HBx} + (1-\alpha) \frac{x^HCx}{x^HDx}.$$ Then we can define $x_\alpha^\ast$ as the maximizer of $J_\alpha$: $$x_\alpha^\ast = \max_x J_\alpha(x).$$ The $x$ you are looking for in your original formulation is $x^\ast_{1/2}$. Now, $x^\ast_0$ and $x^\ast_1$ are easy to compute by just finding the eigenvector to the maximal eigenvalues of the individual generalized eigenproblems. Consequently, there are two approaches one could use:

• Use a path-following method where you start at $x^\ast_0$ and you find $x^\ast_{\alpha+\delta\alpha}$ by solving the nonlinear optimization problem with $x^\ast_\alpha$ as the starting point for each of these problems. If you choose $\delta\alpha$ appropriately, this shouldn't take you more than 1 or 2 Newton steps. You simply follow the path to $\alpha=1/2$.

• If the matrices $A,C$ and $B,D$ are somehow related, it may be that the maximal eigenvectors $x^\ast_0, x^\ast_1$ to the respective eigenproblems are not too different. In that case, starting the nonlinear iteration from $\frac 12(x^\ast_0 + x^\ast_1)$ may yield a Newton iteration that converges reasonably quickly to $x^\ast_{1/2}$.

-
Thanks, Prof. Bangerth. I am looking to minimize $J_a(x)$, not maximize. I assume that the ideas you presented should carry over in the same way, though? –  Costis Feb 27 '13 at 23:49
Yes, sorry. The solutions of the individual problems are then the eigenvectors associated with the minimal eigenvalues. –  Wolfgang Bangerth Feb 28 '13 at 19:10
Having skimmed the paper in GeoffreyIrving's answer in response to a later similar question, I've come to the conclusion that this procedure will probably yield a sequence of suboptimal local minima due to the nonconvexity of the problem (the paper linked by Geoffrey Irving demonstrates the nonconvexity). –  Geoff Oxberry Oct 24 '14 at 18:13