《最优化方法》课程教学资源（PPT课件）凸集的分离（2/2）（刘二永）

理论部分 凸集的分离

理论部分 凸集的分离

定义1设D,D,cR"为两非空凸集,若存在 非零向量a∈R"和实数B,使得 D1cH+={∈Rax≥B D CH R"ax≤B 则称超平面H={∈x=分离了集合 D和D2 注:严格分离

定义1 设 n D1 ,D2  R 为两非空凸集， n a R 若存在  , 1  =    + D H x R a x n T  , 2  =    − D H x R a x n T 非零向量 和实数  , 使得： 则称超平面 H = x R a x =  n T 分离了集合 D1 和 . D2 注：严格分离．

定理1设DcR是非空闭凸集,y∈R但 y∈D,则 (1)存在唯的点x∈D,使得集合D到点 y的距离最小,即报-川=inf{x-川,x∈D (2)x∈D是点y到集合D的最短距离点的 充要条件为:(x-x)(x-y)≥0v∈D 注:闭凸集外一点与闭凸集的极小距离 即投影定理

定理1 设 n D  R 是非空闭凸集， n yR 但 y D, 则： （１）存在唯一的点 x  D, 使得集合 D 到点 y 的距离最小，即： x − y = inf  x − y , xD. （２） x D 是点 y 到集合 D 的最短距离点的 充要条件为： (x x) (x y) 0 x D. T − −    注：闭凸集外一点与闭凸集的极小距离， 即投影定理

定理2设DcR为非空闭凸集n∈Rn y≠D,则存在非零向量a∈R和实数尸 使得:ax≤B<ay,Mx∈D 即存在超平面H={∈Rx=严格分离点 y与凸集D 注:点与闭凸集的分离定理

定理2 设 n D  R 为非空闭凸集， , n y R yD , 则存在非零向量 n a R 和实数  , 使得： a x a y , x D, T T      即存在超平面 H = x R a x =  n T 严格分离点 y 与凸集 D . 注：点与闭凸集的分离定理

引理1设A∈R"为mn矩阵b∈R", 则下述两组方程中有且仅有一组有解 Ax≤0,bx>0, Ay=b,y≥0, 其中x∈R",y∈R 注:以上是在最优化理论研究中起重要作用 的 Farkas引理

引理1 设 m n A R   为 mn 矩阵， , n b R 则下述两组方程中有且仅有一组有解： Ax  0 ,b x  0 , T A y = b , y  0 , T 其中 , . n m xR yR 注：以上是在最优化理论研究中起重要作用 的Farkas引理