How do I solve a linear inequality system ($X\beta+b<0$)?

Given a low-dimension linear regression problem $$\mathbf{y}=\mathbf{X}\beta + \epsilon$$, we can easily estimate $$\beta$$ with $$(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^Ty$$.

However, the problem seems much hard if we are interested in solving the $$\beta$$ that follows: $$\mathbf{y}>\mathbf{X}\beta$$, where $$>$$ denotes element-wise comparison.

I tried to formalize this as a constrained optimization problem, such as $$\arg\min_{\beta}||\beta||, \quad \text{subject to} \quad \mathbf{y}>\mathbf{X}\beta$$ then the solvers will only give me one solution $$\beta$$ that minimizes the norm (well, that's what I asked for anyway).

How should I formalize this problem if I want to find all (or at least multiple) solutions?

(I feel like this kind of question could have been asked previously, but I didn't find them, so I apologize ahead if this is a duplicate question)

• If you mean the $L_2$ norm, this is a quadratic programming problem. If the $L_1$ norm, can be formulated as a linear programming problem. Where do your problem come from? – kjetil b halvorsen Jul 10 at 17:26
• This is the problem of finding the lower part of the convex hull of the points $(X,y).$ It is solved most efficiently using methods of computational geometry. AFAIK, it holds no direct statistical interest in part because the implied loss function is not terribly useful and in part because the solution rapidly gets complicated as the dimensions grow. Even in one dimension there may be as many as $n-1$ distinct solutions plus two more families of solutions for $n$ data points! – whuber Jul 10 at 20:13
• @whuber Thanks. I understand that there are many solutions for the cases when we have control of the signs of the data, but I find it quite hard to determine whether there are solutions in general (and I hope to find them). For example, even with one variable and 2 samples, 2x > 1 and -3x > 2 will lead to no real solution. – Haohan Wang Jul 11 at 4:41
• You seem to be assuming there are more parameters $\beta$ than observations: is this the case? – whuber Jul 11 at 12:41
• @whuber I'm only hoping to solve a low-dimensional case now. I guess low-dimension case is easier to start with. – Haohan Wang Jul 11 at 14:57