5
$\begingroup$

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.

Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Jun 29, 2015 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, 2015 at 18:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .