1
$\begingroup$

Edit: The norm constraint in the optimization problem in the below question was not there earlier. I apologize to the answerer user1551 who had to put his time and effort for my mistake.

Let $A$ and $B$ be two given hermitian positive semi-definite matrices, then what is the solution for \begin{align} \max_{||x||_2=1}\frac{x^HAx}{x^HBx+1}. \end{align} I am looking for closed form solutions. If the denominator didn't have that $1$, this is standard generalized rayleigh quotient and would be unbounded.

NOTES

I know how to solve it numerically. The trick is to re-write it as \begin{align} \max_{x,t}~&t\\ \text{s.t.}~~&x^H(A-tB)x>=t \end{align} Then find the largest $t$ such that there exists a $x$ which satisfies $x^H(A-tB)x>0$. A Bi-section search on $t$ will do the job.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The original problem is equivalent to the following problem: $$\max_{x^H x =1}\frac{x^H A x}{x^H(B+I)x}$$ This is a standard Rayleigh Quotient problem, where the solution can be easily written as $$x^* = (B+I)^{-1/2} eigenvector( (B+I)^{-1/2} A (B+I)^{-1/2} )$$

$\endgroup$
3
  • $\begingroup$ Thank you Distance for your answer and the reference. Could you also explain how did you find the answer $ x^* = (B+I)^{-1/2} eigenvector( (B+I)^{-1/2} A (B+I)^{-1/2} ) $ ? For example did you use Lagrange multipliers? $\endgroup$
    – nastak
    Commented Oct 8, 2017 at 11:36
  • $\begingroup$ it is true that in principle that $$x^* = eigvector((B+I)^{-1}A))$$. However, usually the matrix $(B+I)^{-1}A$ is not hermitian matrix, which makes more complicated to solve such a problem. For reference: en.wikipedia.org/wiki/… $\endgroup$
    – Distance
    Commented Oct 8, 2017 at 13:14
  • $\begingroup$ @nastak This is a standard method. Let $y = (B+I)^{1/2}x$. Then the original problem becomes $$max_y \frac{y^H (B+I)^{-1/2} A (B+I)^{-1/2} } { y^H y } $$. So, $y^* = eigenvector( (B+I)^{-1/2} A (B+I)^{-1/2} )$. And $x^* = (B+I)^{-1/2}y^* = (B+I)^{-1/2} eigenvector(...)$. $\endgroup$
    – Distance
    Commented Oct 8, 2017 at 14:17

You must log in to answer this question.

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