I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger than $K$ and not all constraints have to be satisfied. The question is the following:
Find the parameters $\alpha_1,...,\alpha_K$ such that out of $N$ constraints maximum number of them ($M\leq N$) are satisfied.
Is this problem NP-Hard? What is the most effective way of solving such problems for large $N$ and $K$?
This can be shown to be NP-hard by reduction from 0-1 ILP feasibility. Take any 0-1 integer linear programming feasibility problem
$Ax=b$
$x \in \left\{ 0, 1 \right\}^{n}$
Where $A$ has $m$ rows and $n$ columns.
Relax the integrality constraint and add $2n$ additional constraints
$x_{i}=0, i=1, 2, \ldots, n$
$x_{i}=1, i=1, 2, \ldots, n$
Now, the 0-1 ILP is feasible if and only if you can satisfy $m+n$ constraints in the real system of equations.