Friday, 7 December 2012

linear algebra - Containment of one convex hull in another



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 A1x0 and A2x0 and the common equality x=a where A1, A2 are real valued matrices, a is a real positive constant and xRn. 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:A1x0,x=a} is nonempty.
For each row R of A2, you want every solution of A1x0, x=a to satisfy Rx0, i.e. the optimal value of the linear programming
problem P:



minimize Rx subject to A1x0, x=a




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



maximize az
subject to AT1y+z1=R, y0 (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 y0 and z0 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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...