# Check if there exists a vector that satisfies a set of inequalities but violates another set of inequalities

Problem

Given rectangular matrices $$A$$, $$B$$ and vectors $$\vec{a}$$, $$\vec{b}$$, how to check if there exists an $$\vec{x}$$ that satisfies the following conditions?

1. $$\vec{x} \succcurlyeq \vec{0}$$ is true.
2. $$A\vec{x} \succcurlyeq \vec{a}$$ is true.
3. $$B\vec{x} \succcurlyeq \vec{b}$$ is false.

For vectors $$\vec{u}$$ and $$\vec{v}$$, $$\vec{u} \succcurlyeq \vec{v}$$ means:

• The vectors have the same number of elements.
• For all i, the ith elements of the vectors satisfy $$u_i > v_i$$.

I can't use $$B\vec{x} \preccurlyeq \vec{b}$$ because $$\vec{x}$$ only have to violate at least 1 inequalities among all inequalities represented by $$B\vec{x} \succcurlyeq \vec{b}$$.

Each problem has about 100 variables and 150 inequalities. I want to solve at least 10,000 problems per minute on a laptop. All of the problems share a large number of inequalities.

Ideas

Define two problems:

• $$P_{A}$$ means $$\vec{x} \succcurlyeq \vec{0}$$ and $$A\vec{x} \succcurlyeq \vec{a}$$ are true.
• $$P_{B}$$ means $$\vec{x} \succcurlyeq \vec{0}$$ and $$B\vec{x} \succcurlyeq \vec{b}$$ are true.

If I remember correctly, I think:

• Vectors that satisfies $$P_{A}$$ are the convex combinations of the vertex set $$V_{A}$$.
• The vectors in $$V_A$$ form a matrix $$M_{A}$$.
• The convex combinations form a convex set $$S_{A}$$.
• Vectors that satisfies $$P_{B}$$ are the convex combinations of the vertex set $$V_{B}$$.
• The vectors in $$V_B$$ form a matrix $$M_{B}$$.
• The convex combinations form a convex set $$S_{B}$$.
• Intersection of two convex sets is convex.
• Difference of two convex sets is not necessarily convex.

Idea 2

• The problem is equivalent to showing if $$S_{A}$$ is not a subset of $$S_{B}$$.
• I think the problem is also equivalent to showing if there exists a vertex $$\vec{\alpha} \in V_A$$ such that $$\vec{\alpha}$$ is not a convex combination of $$V_B$$. That means $$M_{B}\vec{u} = \vec{\alpha}$$ either has no solution or $$\vec{u}\cdot\vec{1} \ne 1$$.

I don't know how to find the vertexes. And there are potentially so many vertexes.

Idea 3

• Start from an old problem without such a $$\vec{x}$$
• By comparing the new $$P_{B}$$ and old $$P_{B}$$, we can identify the new cuts.
• Invert the comparison in the new cuts. ($$\ge$$ to $$\le$$).
• Check if each new inverted cut is compatible with the new $$P_{A}$$.
• For each inverted new cut, add the inverted new cut to the new $$P_A$$. If simplex algorithm says the combined problem is feasible, the new inverted cut is compatible with the new $$P_A$$.
• The new problem has such a $$\vec{x}$$ if and only if we find a new inverted cut that is incompatible with the new $$P_{A}$$.

That would be at most 60 runs of simplex per problem. The method caches the inequalities instead of the vertices.

I don't need the solution and only need to know if the new inverted cut is compatible with the existing cuts. Is there a faster way to get this?

I am assuming your notation means $$u_i \ge v_i$$ rather than $$u_i > v_i$$. Strict inequalities are somewhat problematic here.

First comment: Regardless of how you end up modeling this, I would be very surprised if you could solve 10,000 instances per minute on a laptop, even if consecutive instances have considerable commonality.

Second comment: For statement 3 to be false, there must be an index $$i$$ such that $$B^{(i)} x < b_i$$ (where $$B^{(i)}$$ denotes the $$i$$-th row of $$B$$. In practice, strict inequalities likely cannot be handled (especially if you end up solving an optimization problem), so you will almost certainly have to introduce a tolerance $$\epsilon > 0$$ and change statement 3 to $$B^{(i)}x \le b_i - \epsilon$$ for some $$i$$.

Third comment: Unless you know that the feasible regions of $$P_A$$ and $$P_B$$ are bounded, the correct statement is that a point in either one is the sum of a convex combination of vertices and nonnegative combination of rays (extreme directions).

Fourth comment: Identifying all vertices (and rays) of a polyhedron can be computationally expensive ... plus, for condition 3, you would need to show that the chosen $$x$$ cannot be expressed in terms of vertices and rays, which would be tricky.

Last comment: You can model this as a mixed integer linear program (though I'd be even more certain that 10K solutions per minute would be off the table). Introduce a binary variable $$y_i$$ with the same dimension as the number of rows in $$B$$. The feasible region for your problem is defined by $$x\ge 0$$ $$Ax\ge a$$ $$B^{(i)}x \le b_i -\epsilon + M_i y_i \quad \forall i$$and $$\sum_i y_i \ge 1.$$ $$M_i$$ is a "large enough" positive constant for each $$i$$. The objective function can be pretty much anything.

• Thanks a lot. $P_{A}$ and $P_{B}$ are always bounded. Nov 24 '21 at 19:52