Solving Coupled Eigenvalue equations

I wish to solve the following set of coupled eigenvalue equations. How should I do it?

For real matrices $A$,$B$,$D$ and vectors $x \in R^m$, $y \in R^n$ $$A x + B y = \lambda x$$ $$B^T x + D y = \mu y$$ where, $A$ and $D$ are symmetric.

Background:

I am trying to solve the following optimization problem:

$$\min x^T A x + y^T D y + x^T By$$ $$\textrm{such that } \, x^T x = 1 , y^T y = 1$$ This leads to the above eigenvalue problem. $\lambda$ and $\mu$ are the Langrangian parameters for the constraints.

EDIT: I need to actually find numerical solutions for these equations given $A$, $B$, $D$

-
From the optimization, I just realized I want to maximize $\lambda + \mu$ –  Harsh Jun 25 '11 at 12:04

If you write $I^m$ for an $m \times m$ identity matrix, you can make a big matrix equation out of it $$\left(\begin {array}{c c}A-\lambda I^m & B\\B^T & D-\mu I^n \end {array}\right)\left(\begin {array}{c}x \\ y \end {array}\right)=0$$ which is a classic eigenvalue problem. Chapter 11 of Numerical Recipes (free for the obsolete versions) or any numerical analysis text can help you.

-
Thanks, will look it up –  Harsh Jun 24 '11 at 7:05
Can you please explain? AFAIU, This is not the classic Eigenvalue Problem because there are 2 parameters $\lambda$ and $\mu$. Numerical Recipes does not give methods to solve such problems –  Harsh Jun 25 '11 at 12:06
This was my first thought, too. But he wants to normalize the $x$ and $y$ parts to unit vectors independently from each other, and I don't see how to factor that in here. –  Jyrki Lahtonen Jun 26 '11 at 20:32

This is not a complete solution... but maybe this will help. Write $u = \begin{pmatrix}x\\y\end{pmatrix}$. Then the objective can be written as $u^TQu$ where $Q = \begin{pmatrix}A & B/2\\B^T/2 & D\end{pmatrix}$. The constraints can be written as $u^TM_1u = 1$ and $u^TM_2u = 1$.

Now, for $\alpha\in(0,1)$, let $M = \alpha M_1 + (1-\alpha)M_2$. Form a constraint as $u^TMu = 1$. It is clear that the minimization with this constraint alone will give a lower bound on the required minimum value. This minimization can be done easily. Let $R = \sqrt{M}$, as $M$ is p.d., and $v = Ru$. Then, the constraint is simply $v^Tv = 1$ and the objective can also be written as $v^TQ'v$, where $Q' = R^{-1}QR^{-1}$. The solution to this is the minimum eigenvalue of $Q'$, which can be obtained by Ritz iterations etc.

Hence the supremum of these lower bounds give a lower bound for for the given minimization problem. The interesting thing to prove is that the supremum of these lower bounds for various $\alpha\in(0,1)$ is the required minimum. This can be shown easily when $B=0$, but I haven't been able to prove it in the general case.

-

Perhaps adding the two equations in order to reeduce it to one equation with eqienvalue (lambda + mu) and Eqienvector x+y is the trick. Then find the inverse using a calculator or standard methods. But there is probably a trick involving the fact that the matrices satisfies the properties they do.

-
This does not work –  Harsh Jun 24 '11 at 5:48

Append x and y

form z belonging to R (m+n) by appending y to x

So, now, you will get

m * (m+n) matrix on the left hand side through 1st equation and n*(m+n) matrix on the left hand side through 2nd equation.

your variable is of size m+n.

hence, append the two equations...

now, you get a square matrix on the LHS of size m+n *m+n -- solve

-
This is an eigenvalue problem. lambda and mu are not known before hand, so this will not work –  Harsh Jun 24 '11 at 7:05