信息检索与数据挖掘 2019/4/22 8 Distance between polyhedra The (Euclidean)distance between the polyhedra Pi ={x Aix 61}and P2 x A2x b2}in R"is defined as dist(P1,P2)=inf{lx1-x2ll2|x1∈P1,x2∈P2}. If the polyhedra intersect,the distance is zero. To find the distance between Pi and P2,we can solve the QP minimize x1-23 subject to A1x1≤b1,A2x2≤b2, with variables 1,2 ER".This problem is infeasible if and only if one of the polyhedra is empty.The optimal value is zero if and only if the polyhedra intersect, in which case the optimal xI and z2 are equal (and is a point in the intersection PiP2).Otherwise the optimal z1 and z2 are the points in Pi and P2,respectively, that are closest to each other.(We will study geometric problems involving distance in more detail in chapter 8.) Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems信息检索与数据挖掘 2019/4/22 8 Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems