Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider hermitian positive semi-definite matrices $A_1$ and $A_2$. Consider also positive definite matrices $B_1$ and $B_2$. I want to maximize the minimum of the two Generalized Rayleigh Ritz ratios $\frac{x^{H}A_1x}{x^{H}B_1x}$ and $\frac{x^{H}A_2x}{x^{H}B_2x}$. To state it formally, the problem is

\begin{align} \max_{x} \min\left(\frac{x^{H}A_1x}{x^{H}B_1x},\frac{x^{H}A_2x}{x^{H}B_2x}\right) \end{align}

I would be very much happy if we can find a closed form solution for it. I would also appreciate if some one can suggest a iterative algorithm to solve it. I am not interested in converting it to a convex optimization problem even if it is possible. (But, if convertible to a convex is fruitful, then I would like to see it).

EDIT------

My attempt on the problem

Introduce a extra variable $t$ and rewrite the problem as

\begin{align} \max_{x,t}~t , \end{align} \begin{align}sucht~that~ \frac{x^{H}A_1x}{x^{H}B_1x} \geq t, \frac{x^{H}A_2x}{x^{H}B_2x} \geq t \end{align} Since $B_1$ and $B_2$ are positive definite, one can re-write this equations as

\begin{align} \max_{x,t}~t , \end{align} \begin{align}sucht~that~ x^{H}(A_1-t B_1)x \geq 0 \end{align} \begin{align} x^{H}(A_2-t B_2)x \geq 0 \end{align}

May some one here can come up with a algorithm for this problem.

share|improve this question
    
I guess it relates to the condition number of the underlying matrices. See if this paper is helpful sinnamon.math.uwo.ca/pdf/convexity.pdf –  Betrand Nov 3 '12 at 20:22
    
Thanks for the help, the paper you mentioned concerns with product of quadratic forms rather than the ratio. –  dineshdileep Nov 4 '12 at 13:56
    
@ Karim Baghery: this problem has been solved in Multiuser channel in cooperative communications, It is solved using of bisection search. In IEEE link of mentioned paper you can see the algorithm of solution and more details about that. if it was not clear I can explain more, My Email is Baghey.karim@yahoo.com Best, –  user37774 Jul 26 '13 at 16:21
add comment

2 Answers

up vote 2 down vote accepted

Here is a crude idea that might work (haven't thought too carefully about it).

Let $a=\lambda_{\min}(B_1^{-1}A_1)$ and $b=\lambda_{\min}(B_2^{-1}A_2)$. Then, for there to be a feasible solution to the 2nd formulation, the variable $t$ must lie in the interval $[0,t_{\max}]$, where $t_{\max} := \min(a,b)$.

This suggests that maybe we can do a binary-search for the optimal value of $t$.

  1. Start with $t = t_{\max}/2$
  2. With this value of $t$, either there is a feasible $x$ that satisfies both inequalities, or there isn't. If there isn't, we shrink $t$, else we expand it; that is, if there is no feasible $x$, we search in $[0,t]$, otherwise we search in $[t, t_{\max}]$ and repeat this step.

(Notice that we obtain an optimal $x$ as a by-product).

share|improve this answer
    
@Suvrit thanks for the reply. Seems good. In fact, I came to this point. But the problem was checking the feasibility. Thus dropped the idea. Any help on that? –  dineshdileep Nov 16 '12 at 12:27
    
I really like your question, so when I get some time, will try to think more about it! While typing up the answer I had also doubts as to how easy feasibility might be---anyhow...let us see! –  Suvrit Nov 16 '12 at 17:40
    
@Suvrit Actually I am not sure with that variable substitution, say $y_{1}=B_{1}^{1/2}x$ and $y_{2}=B_{2}^{1/2}x$. Then the optimization becomes in terms of $y_1$ and $y_2$ with an additional equality constraint. –  dineshdileep Nov 17 '12 at 11:37
    
@Dinesh: I had also thought that this two variable thing makes it tricky. But the above argument is more along the lines: the set of values that ratio1 can take is an interval, all possible values that second ratio also takes is also an interval; thus we should be able to do the max-min --- any catch in this line of thought? –  Suvrit Nov 17 '12 at 18:00
    
@Suvrit Did you mean about a kind of bisection search, i.e. we fix $t$ at every step, then you check if a feasible $x$ exists or not?. That is, for every $t$, it is equivalent to consider the cases $x^{H}T_1 x\geq 0$ and $x^{H}T_2 x\geq 0$, where $T_i=A_i-t*B_i$. This is also equivalent to solve the original problem with $B_1=I$ and $B_2=I$. Do you think it is connected to the generalized eigen value problem. –  dineshdileep Nov 19 '12 at 3:10
add comment

Problem solved in (7) in

Jianshu Zhang; Roemer, F.; Haardt, M.; Khabbazibasmenj, A.; Vorobyov, S.A., "Sum rate maximization for multi-pair two-way relaying with single-antenna amplify and forward relays," Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on , vol., no., pp.2477,2480, 25-30 March 2012 doi: 10.1109/ICASSP.2012.6288418

share|improve this answer
add comment

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.