Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

2012-11-03T16:17:13Z

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.

Answer by S. Sra for Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

2012-11-15T20:29:02Z

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

Simultaneous maximization of two Generalized Rayleigh Ritz Ratios - MathOverflow

Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

Answer by S. Sra for Simultaneous maximization of two Generalized Rayleigh Ritz Ratios