Given matrices $A$ ($n \times k$) and $C$ ($m \times $k), and vectors $b$ and $d$, I want to know if there is a value of $x$ that solves the two constraints below:
\begin{array}{c} A x = b \\ C x \geq d \end{array}
In case it helps, I already have a previous solution of $x$ that solves the first equation (the equality $Ax=b$), and I want to know if a solution that also solves $Cx \geq d$ exists.
Both matrices are potentially huge (e.g. 100,000 rows and/or 1,000 columns). There are no extra assumptions, so they might e.g. be ill-conditioned.
I suspect this might be solved with the simplex method (but I haven't had any luck with this yet), or perhaps with a twist to Farkas' lemma, but I haven't had any luck yet.
I also found some related questions, but either they were incorrectly worded (and thus incorrectly answered), or had incorrect/useless responses. For instance,
- Checking the existence of a solution for a set of linear equality and ineaulity equations
- Linear least squares with inequality constraints (here, the linked paper, by Golub & Saunders, does not actually use inequality constraints but equality constraints).