1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.