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$
  • $\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 '17 at 1:18
  • $\begingroup$ And, yeah, symmetrize $B$ first; there is no need to keep it asymmetric. $\endgroup$ – fedja Nov 13 '17 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 '17 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 '17 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 '17 at 3:54
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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Federico Poloni Nov 12 '17 at 10:04
  • $\begingroup$ @FedericoPoloni I said "rarely" not never. $\endgroup$ – Igor Rivin Nov 12 '17 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 '17 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$ – Christian Remling Nov 12 '17 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 '17 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I meant "positive definite". I'll try your suggested optimizer. $\endgroup$ – Yang Nov 12 '17 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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