Biased eigenvalue problem

Question

I came across the following "biased eigenvalue problem" when I have tried to solve a quadratic constrained optimization problem.

$$Ax = \lambda (x+v), $$

where $A \in\mathbb{S}^{n}$ (the set of $n\times n$ positive semidefinite matrices), and $v \in \mathbb{R}^{n}$ a given unit vector.

My thoughts

By substituting $y =x+v$ into the problem, we have $$A(y-v) = \lambda y \implies Ay = \lambda y + u,$$ where $u =Av$. Here, $\lambda$ is only multiplied by the vector $y$, but still it is a biased problem.

How to find the eigenpairs $(x,\lambda)$ or $(y,\lambda)$? Is there a closed form or an algorithm to solve this problem?

I just need some hints or link for papers. Thanks in advance!

Answer 1

The problem can be written

$$(A-\lambda I)x=\lambda u.$$

In general, $A-\lambda I$ is invertible (unless $\lambda$ is an Eigenvalue of $A$) and the solution

$$x=\lambda (A-\lambda I)^{-1}u$$ holds.

The "trajectory" of the solution is a rational expression in $\lambda$, nothing simple.

With a random $3\times3$ example:

Answer 2

I have encountered a similar problem of solving a quotient-of-quadratic constrained optimization problem : $$\begin{array}{l} \max \frac{x^TAx}{x^TBx} \\ \text{s.t. } a^Tx=b\end{array}$$

which, without the constraint, is a standard problem that can be solved by generalized eigenvalue algorithms.

This problem has the Lagrangian $$\mathcal L(w, \lambda) = \frac{2Ax(x^TBx)-2Bx(x^TAx)}{(x^TBx)^2}-\lambda (a^Tx-b)$$

whose critical point equation is $$2Ax(x^TBx)-2Bx(x^TAx)=\lambda(x^TBx)^2 a$$

i.e. $$2Ax-2Bx\gamma =\lambda \beta a$$

The problem isn't exactly the same but I think it can give some clues for you to solve your problem.

Turns out that the objective function $\frac{x^TAx}{x^TBx}$ is invariant under scailing, thus we can simply solve the unconstrained problem and "scale" the argmax to fit the linear constraint $a^Tx=b$. Interestingly, it is exactly scailing that creates the baroque denominator presented in the original answer.