Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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".

share|improve this answer
    
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}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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