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.


  • $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Feb 9 '13 at 4:06
  • $\begingroup$ 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! $\endgroup$ – Costis Feb 9 '13 at 4:48

This paper may be useful:

Lei-Hong Zhang. "On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere".

  • $\begingroup$ 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. $\endgroup$ – Costis Feb 27 '13 at 23:48
  • $\begingroup$ Wouldn't you just negate the matrices? $\endgroup$ – Geoffrey Irving Feb 28 '13 at 17:12
  • $\begingroup$ 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! $\endgroup$ – 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}$.

  • $\begingroup$ 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? $\endgroup$ – Costis Feb 27 '13 at 23:49
  • $\begingroup$ Yes, sorry. The solutions of the individual problems are then the eigenvectors associated with the minimal eigenvalues. $\endgroup$ – Wolfgang Bangerth Feb 28 '13 at 19:10
  • $\begingroup$ 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). $\endgroup$ – Geoff Oxberry Oct 24 '14 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.