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 Rn defined by the two sets of linear inequalities A1x≥0 and A2x≥0 and the common equality ∑x=a where A1, A2 are real valued matrices, a is a real positive constant and x∈Rn. What conditions must be satisfied by A1, A2 for the first convex hull to be contained in the second convex hull?
Thank you.
Answer
Let's assume {x:A1x≥0,∑x=a} is nonempty.
For each row R of A2, you want every solution of A1x≥0, ∑x=a to satisfy R⋅x≥0, i.e. the optimal value of the linear programming
problem P:
minimize R⋅x subject to A1x≥0, ∑x=a
is at least 0. The dual of this linear programming problem is D:
maximize az
subject to AT1y+z1=R, y≥0 (where 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 ≥0. Your condition is equivalent
to: there exist y≥0 and z≥0 such that R=AT1y+z1,
i.e. each row of A2 is a linear combination with nonnegative coefficients
of 1 and the rows of A1.
No comments:
Post a Comment