Containment of one convex hull in another

270 Views Asked by At

This question is related my previous question (Comparing two probability distributions) which are both related to my current research.

Suppose we have two bounded convex hulls in $\mathbb{R}^n$ defined by the two sets of linear inequalities $A_1x \geq 0$ and $A_2x \geq 0$ and the common equality $\sum x=a$ where $A_1$, $A_2$ are real valued matrices, $a$ is a real positive constant and $x \in \mathbb{R}^n$. What conditions must be satisfied by $A_1$, $A_2$ for the first convex hull to be contained in the second convex hull?

Thank you.

1

There are 1 best solutions below

2
On BEST ANSWER

Let's assume $\{x: A_1 x \ge 0, \sum x = a\}$ is nonempty. For each row $R$ of $A_2$, you want every solution of $A_1 x \ge 0$, $\sum x = a$ to satisfy $R \cdot x \ge 0$, i.e. the optimal value of the linear programming problem P:

minimize $R \cdot x$ subject to $A_1 x \ge 0$, $\sum x = a$

is at least $0$. The dual of this linear programming problem is D:

maximize $a z$ subject to $ A_1^T y + z {\bf 1} = R$, $y \ge 0$ (where $\bf 1$ is the vector of all $1$'s)

By duality, P has a solution with objective value $ < 0$ if and only if D has no solution with objective value $\ge 0$. Your condition is equivalent to: there exist $y \ge 0$ and $z\ge 0$ such that $R = A_1^T y + z \bf 1$, i.e. each row of $A_2$ is a linear combination with nonnegative coefficients of $\bf 1$ and the rows of $A_1$.