7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Well, let $x$ be a minimizer of $\langle(A+\mu B)x,x\rangle$ if $\langle Bx,x\rangle=0$, you are done. If not, you can change $\mu$ a little bit to move the minimum up (assuming you do not hit multiple eigenvalues, in which case you have to search for a vector satisfying the constraint in the full eigenspace). I have no idea how efficient that can be made (the trickery is to adjust $\mu$ neither too slow, nor too fast and the whole thing is just searching for the maximum of an expensive to compute function, so you'd better think of what you can say about that min as a function of $\mu$ first) $\endgroup$
    – fedja
    Nov 13, 2017 at 1:18
  • $\begingroup$ And, yeah, symmetrize $B$ first; there is no need to keep it asymmetric. $\endgroup$
    – fedja
    Nov 13, 2017 at 1:25
  • $\begingroup$ It is concave, actually, so you can use the standard bisection techniques and find the maximum fairly quickly. $\endgroup$
    – fedja
    Nov 13, 2017 at 2:29
  • $\begingroup$ @fedja Thank you. That's a general way. I understand it better now - in terms of physical picture alas. $\endgroup$
    – Yang
    Nov 14, 2017 at 2:56
  • $\begingroup$ Your problem is a non-convex QCQP. If you don't need to code up the solution yourself, you could just use a general QCQP solver $\endgroup$
    – Pushpendre
    Nov 14, 2017 at 3:54

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Why "$x^TBx$ is rarely zero for full-rank matrices"? For instance, the block matrix $\begin{bmatrix}0 & I\\I & 0\end{bmatrix}$ has two dim/2-dimensional subspaces of vectors such that $x^TBx=0$. $\endgroup$ Nov 12, 2017 at 10:04
  • $\begingroup$ @FedericoPoloni I said "rarely" not never. $\endgroup$
    – Igor Rivin
    Nov 12, 2017 at 14:51
  • $\begingroup$ Thank you for the comments. In viewing of your comments, I removed the "full rank" condition to accept a broader class of solutions. One obviously can use the vectors in the null space of $B$ to minimize $A$. If $B$ is not symmetric, are there any additional solutions beyond the null-space? I appreciate your answer. $\endgroup$
    – Yang
    Nov 12, 2017 at 21:36
  • $\begingroup$ I don't understand your second sentence: $x^tBx=0$ does not imply that $x\in N(B)$ (for example take $B=\textrm{diag}(1,-1)$). $\endgroup$ Nov 12, 2017 at 21:44
  • $\begingroup$ @ChristianRemling Re your first comment, I was tired :( Re the second, I am specifically looking at the OP's lagrange multiplier equation. $\endgroup$
    – Igor Rivin
    Nov 12, 2017 at 21:48
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, I meant "positive definite". I'll try your suggested optimizer. $\endgroup$
    – Yang
    Nov 12, 2017 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.