## Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

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.

-
 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 at 20:22 Thanks for the help, the paper you mentioned concerns with product of quadratic forms rather than the ratio. – dineshdileep Nov 4 at 13:56

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

-
 @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 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! – S. Sra Nov 16 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 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? – S. Sra Nov 17 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 at 3:10