Suppose there is a set of $n$ linear constraints $\{a_i^Tx+b_i\le 0\}_{i=1}^n$ with $a_i\in\mathbb{R}^d$, $b_i\in\mathbb{R}$, $x\in\mathbb{R}^d$. How can I find $x^*$ that maximizes $\vert \{i\in [n]\mid a_i^Tx^*+b_i\le 0\}\vert$? Is this problem solvable or can be approximated within polynomial time?
Some reference materials would also be nice. Thanks!
The maximum cardinality feasible subsystem problem is NP-hard: Chakravarti N., Some Results Concerning Post-Infeasibility Analysis, European Journal of Operational Research, Vol. 73 (1994), pp. 139- 143.
You might also search for the equivalent minimum cardinality IIS set cover problem.
You can solve the problem via mixed integer linear programming as follows. Let binary decision variable indicate whether constraint $i$ is satisfied. The problem is to maximize $\sum_i z_i$ subject to linear (big-M) constraints $$a_i^T x+b_i\le M_i(1-z_i) \quad \text{for all $i$}.$$ Here, $M_i$ is a (small) constant upper bound on the LHS when $z_i=0$.