I am trying to solve the following binary quadratic program.

$$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma $$

where $H$ is not a positive semidefinite matrix (and hence the minimization problem is not convex) and $\Gamma$ is a fixed natural number less than $n$. I suppose that one might consider this problem a loosely cardinality-constrained quadratic program.

I have been somewhat unsuccessful in trying to find a literature on this kind of optimization problem. I was wondering if anyone here might be able to refer me to some good resources on non-convex binary quadratic optimization with a linear constraint as above.



The indefiniteness of H is a non-issue when you only have binary variables, as you always can add the zero-term $\lambda \Delta^T\Delta - \lambda \sum \Delta_i$. If you pick $\lambda$ large enough (larger than $-\lambda_{min}(H)$ where $\lambda_{\min}$ denotes smallest eigenvalue), the objective is convex.

  • $\begingroup$ Hi Johan. Thanks for the clarification. After some more looking around, I found the following resource: sciencedirect.com/science/article/pii/S0166218X97000395?np=y# Is it true that even though you can make the objective convex (as you say) the problem remains NP-Hard as indicated by this paper? $\endgroup$ – user1936768 Jun 29 '15 at 14:48
  • $\begingroup$ unfortunately yes. even if the objective is linear, it would be np hard. as you could code everything using binary encoding. however there are problem tailored approximation and heuristics. $\endgroup$ – user251257 Jun 29 '15 at 18:15

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.