Welcome to MathOverflow

Question

4

1

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.

edited Nov 19 at 5:32

asked Nov 3 at 16:17

dineshdileep
281●5

	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

S. Sra · Accepted Answer · 2012-11-19 00:22:18Z UTC

2

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

Start with $t = t_{\max}/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).

edited Nov 19 at 0:22

answered Nov 15 at 20:29

S. Sra
10.1k●1●16●44

	@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

Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.