5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Betrand
    Commented Nov 3, 2012 at 20:22
  • $\begingroup$ Thanks for the help, the paper you mentioned concerns with product of quadratic forms rather than the ratio. $\endgroup$
    – dineshdileep
    Commented Nov 4, 2012 at 13:56
  • $\begingroup$ @ 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 [email protected] Best, $\endgroup$
    – user37774
    Commented Jul 26, 2013 at 16:21

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ @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? $\endgroup$
    – dineshdileep
    Commented Nov 16, 2012 at 12:27
  • $\begingroup$ 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! $\endgroup$
    – Suvrit
    Commented Nov 16, 2012 at 17:40
  • $\begingroup$ @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. $\endgroup$
    – dineshdileep
    Commented Nov 17, 2012 at 11:37
  • $\begingroup$ @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? $\endgroup$
    – Suvrit
    Commented Nov 17, 2012 at 18:00
  • $\begingroup$ @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. $\endgroup$
    – dineshdileep
    Commented Nov 19, 2012 at 3:10
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .