Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric and positive definite and that we have several symmetric matrices $B_i\in\mathbb{R}^{n\times n}$ that are low-rank and indefinite. I need an algorithm for solving the following optimization problem: $$ \begin{align*} \min_{x\in\mathbb{R}^n}\ & x^\top Ax\\ \textrm{s.t.}\ & \|x\|_2^2=1\\ & x^\top B_i x=0\ \forall i\in\{1,\ldots,k\}. \end{align*} $$ Any suggestions?

I am hoping it is somehow equivalent to an eigenvalue problem. Assorted observations:

  • If the second constraint is removed, the output is the minimal eigenvector of $A$.
  • The Lagrange multiplier expression is $Ax=\lambda x + \sum_i \mu_iB_ix$. So, if we somehow know the dual variables $\{\mu_i\}_{i=1}^k$, then $x$ is an eigenvector of $A-\sum_i\mu_i B_i$ with minimal eigenvalue $\lambda$. So, we could think of $x$ as a very nonlinear function $x(\mu_1,\ldots,\mu_k)$.
  • If one of the $B_i$'s is positive definite, then this problem is not satisfiable (implies $x=0$). But for my specific problem I can prove the feasible region is nonempty.
  • This can be approached using semidefinite relaxation, but this would be very slow for large $n$.
  • $\begingroup$ How big is $n$? $k$? the rank of each $B_{i}$? I'm assuming the $B_{i}$ matrices are symmetric. Do you have low rank factorizations of these matrices so that e.g. $B_{i}=F_{i}D_{i}F_{i}^{T}$? $\endgroup$ – Brian Borchers Oct 29 '15 at 22:38
  • 1
    $\begingroup$ $n$ and $k$ are both large, but the $B_i$'s are (very!) low rank and sparse (for me each $B_i$ has only a $5\times5$ block on the diagonal). So, I can factor all the $B_i$'s as you mention. Does this help if $D_i$ has both positive and negative numbers on its diagonal? I'm not sure how to solve this even if $k=1$. Any ideas? $\endgroup$ – Justin Solomon Oct 29 '15 at 23:26
  • $\begingroup$ It's a nonconvex problem so there's little reason to expect an easy solution. You could use eigenvalue optimization techniques on the dual (as you've mentioned in your comments) to get lower bounds or you could try to use an SDP relaxation (and having low rank B_{i} matrices with factorizations would help this), but that's all that I've got for you. $\endgroup$ – Brian Borchers Oct 30 '15 at 1:36
  • $\begingroup$ You might consider homotopy continuation methods ala Bertini, but chances are that your problems are too large for that. $\endgroup$ – Brian Borchers Oct 30 '15 at 1:40
  • 1
    $\begingroup$ The problem you have posed is NP-hard, since the binary integer constraint $x \in \{-1, +1\}$ can be posed in the form of $\|x\|=1, x^T B x = 0$, and that binary integer programming is NP-complete. Hence if you can efficiently solve this problem (e.g. using an eigendecomposition in $O(n^p)$ time, as your question had suggested), you would prove P=NP. $\endgroup$ – Richard Zhang Nov 3 '15 at 19:22

Your Answer

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

Browse other questions tagged or ask your own question.