I started with a (positive-definite) quadratic programming problem subject only to a single equality constraint. i.e.

$$ f(x)=x^{T}Qx+c^{T}x $$ $$ s.t. x_1+x_2+x_3+...+x_n=y $$

I now have to find the optimal solution subject to varying $m<n$ of the parameters with all other variables fixed to be zero. I'm well aware that I can now reduce the dimensionality of the problem to a $Q$-matrix of order $m$ and that's not the issue.

The issue is choosing the 'optimal' set of $m$ parameters that best minimize the objective function. Essentially, I have to find the optimal optimization from the $^nC_m$ possible choices of free variables to play with.

I don't really know how to classify this problem let alone solve it. Assume $m$ is typically 7 and $n$ is typically 100 so about 16 billion problems via brute force :S

Any idea how to tackle this? Help, thoughts much obliged.


You have a cardinality constrained QP, known to be hard (intractable in the general case). You can formulate it as a mixed-integer QP and solve it globally, or apply some heuristic and hope for the best. Searching for the topic will lead you to a wealth of references and material.

| cite | improve this answer | |

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.