Eigenvalue problem with two quadratic constraints

Question

I would like to solve the following problem:

$$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \mathbf{x}^T\mathbf{B}\mathbf{x} = 0\\ & \mathbf{x}^T \mathbf{x} = 1\end{array}$$

where $\bf x$ is a vector, $\bf A, \bf B$ are square matrices, and $\bf A$ is symmetric.

---

Here is my thinking:

Use the Lagrange multiplier method, \begin{equation} \mathcal L (\bf x, \lambda, \mu) = \mathbf{x}^T \mathbf{A} \mathbf{x} - \lambda \mathbf{x}^T\mathbf{x} - \mu \mathbf{x}^T \mathbf{B} \mathbf{x}. \end{equation} Take the derivative with respect to $\bf x$, we get: \begin{equation} \bf{A x = \lambda x + \mu Bx} \end{equation} This is not exactly an eigenvalue problem or a generalized one. What's next?

I can apply the constraints and get $\lambda = \bf x^TAx$, $\mu = \bf x^TB^TAx/(x^TB^TBx)$. But I am looking for a method that can turn the problem to a linear problem, e.g. generalized eigenvalue problem, so that I can apply the standard numerical linear algorithms. In principle, if I can solve $\det (A-\lambda I - \mu B) = 0$, I can eliminate, say, $\mu$. But this is not feasible, numerically. A perturbative solution with $|\mu|\ll 1$ is acceptable.

Question: Are there any methods, ideally using standard numerical linear algorithm, to solve this problem?

---

These problems are similar but not the same:

Linearly constrained eigenvalue problem

Thank you in advance.

Edit: In viewing of the comments, I removed the "full rank" condition and does not requires $\bf A$ to be "positively defined". Hopefully, the problem may have a solution?

The background of the problem is as follows: $\bf A$ is a Hamiltonian. $\bf x$ is its eigenvector with lowest energy. $\bf x^T Bx = 0$ represents a constraint imposed by a symmetry. In practice, $\bf A$ is truncated, and $\bf x^T B x \ne 0$.

Now, I am trying to reformulate the problem to guarantee the symmetry constraint $\bf x^T B x = 0$. As a result, $\bf x$ may not be an eigenvector of $\bf A$, which is the price to pay. My hope is that as the symmetry violation is small enough, the problem may still have an efficient solution. Hope this helps.

Answer 1

Generically, your system will have no solution, since $\mathbf{x}^t B \mathbf{x}$ is rarely zero for full-rank matrices. In the special case where $B$ is a degenerate symmetric matrix, then $x$ is in the null-space of $B,$ but then your Lagrange multiplier equation seems to indicate that $x$ has to also be an eigenvector of $A,$ which, again, seems highly rare.

Answer 2

Because no one has offered a solution meeting your ideal of using a standard numerical linear algorithm, I will offer an approach using the global numerical nonlinear optimizer BARON.

Here is a solution using BARON as the solver under YALMIP under MATLAB. I will use the B provided by @Federico Poloni in his comment above. I'm not sure what symmetric and positively defined is supposed to mean, so I chose a random A which is symmetric positive definite with all elements positive, which ought to comply with whatever it means.

n = 4;
B = [zeros(n/2) eye(n/2);eye(n/2) zeros(n/2)];
A = rand(n); A = A*A'; % random instantiation of A
x = sdpvar(n,1); % declare x an an optimization vector
Constraints = [x'*B*x == 0,x'*x == 1] % the non-convex constraints
Objective = x'*A*x % objective function to be minimnized
% minimize the Objective, subject to the Constraints, using BARON
optimize(Constraints,Objective,sdpsettings('solver','baron')) 

For

A =
   1.716800970124081   0.998289669825227   1.266317282130762   0.970191833948101
   0.998289669825227   1.486118602130391   1.165572239200317   0.702280553602394
   1.266317282130762   1.165572239200317   1.679161019401491   0.884294705407438
   0.970191833948101   0.702280553602394   0.884294705407438   0.729460526019744

The result is

   optimal x = [-0.397502000000000 -0.061859500000000 -0.140779000000000  0.904625000000000]'

   optimal objective value = 0.116730782147915

The constraints are satisfied to within a tolerance of less than 1e-6, but a tighter tolerance could be used.

True, this will not scale in a friendly way as n increases.