Simultaneous maximization of two Generalized Rayleigh Ritz Ratios - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T04:51:01Z http://mathoverflow.net/feeds/question/111389 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111389/simultaneous-maximization-of-two-generalized-rayleigh-ritz-ratios Simultaneous maximization of two Generalized Rayleigh Ritz Ratios dineshdileep 2012-11-03T16:17:13Z 2012-11-19T05:32:37Z <p>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 </p> <p>\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}</p> <p>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). </p> <p>EDIT------ </p> <p>My attempt on the problem </p> <p>Introduce a extra variable $t$ and rewrite the problem as </p> <p>\begin{align} \max_{x,t}~t ,<br> \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 </p> <p>\begin{align} \max_{x,t}~t ,<br> \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<br> \end{align}</p> <p>May some one here can come up with a algorithm for this problem. </p> http://mathoverflow.net/questions/111389/simultaneous-maximization-of-two-generalized-rayleigh-ritz-ratios/112516#112516 Answer by S. Sra for Simultaneous maximization of two Generalized Rayleigh Ritz Ratios S. Sra 2012-11-15T20:29:02Z 2012-11-19T00:22:18Z <p>Here is a crude idea that might work (haven't thought too carefully about it).</p> <p>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)$. </p> <p>This suggests that maybe we can do a <em>binary-search</em> for the optimal value of $t$.</p> <ol> <li>Start with $t = t_{\max}/2$</li> <li>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.</li> </ol> <p>(Notice that we obtain an optimal $x$ as a by-product).</p>