《最优化方法》课程教学资源（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引理

定义2设DcR"为非空集合,且点x∈R 属于集合D的边界,即x∈aD.若存在非零 向量a∈R",使成立: DcH=k∈R"l(x-x)20 或者DH1=k∈Ra(x-x)≤0} 则称超平面H2={∈Ra(x-x)=0 是集合D在其边界点x的支撑超平面

定义2 设 n D  R 为非空集合，且点 n x  R 属于集合 D 的边界，即 x D. 若存在非零 向量 , n aR 使成立：  =   ( − )  0 + D H x R a x x n T x 或者  =   ( − )  0 − D H x R a x x n T x 则称超平面 H = x R a (x − x) = 0 n T x 是集合 D 在其边界点 x 的支撑超平面

定理3设DcR为非空凸集,∈aD,则存在 非零向量a∈R",使成立 ax<a1x,x∈D 即凸集D∈R在其边界点处存在支撑超平面 其中D表示集合D的闭包。 注:非空凸集在其任一个边界点处都存在 支撑超平面

定理3 设 n D  R 为非空凸集， x D, 则存在 非零向量 , n aR 使成立 a x a x , x D , T T    即凸集 n DR 在其边界点处存在支撑超平面， 其中 D 表示集合 D 的闭包。 注：非空凸集在其任一个边界点处都存在 支撑超平面

推论1设DcR是非空凸集,x函D,则存在 非零向量a∈R"使成立 x<axVx∈D 定理4设D,D2是R"的两个非空凸集,且 D∩D2=②,则存在超平面分离D和D2, 即存在非零向量a∈R使得 ax≤ay,x∈D1,y∈D2 注:以上是两凸集分离定理

推论1 设 n D  R 是非空凸集， x D, 则存在 非零向量 n a R 使成立 a x a x x D . T T    定理4 设 1 2 D ,D 是 n R 的两个非空凸集，且 , D1  D2 =  则存在超平面分离 D1 和 , D2 即存在非零向量 n aR 使得 , , . 1 D2 a x a y x D y T T     注： 以上是两凸集分离定理

定理5设A∈Rwm为m×n阶矩阵,则或者存在 x∈R使Ax<0,则或者存在y∈R"使 Ay=0,y≥0,y≠0 且两者不能同时成立。 注:以上是非线性最优化理论中具有重要 作用的 Gordan择一定理

定理5 设 m n A R   为 mn 阶矩阵，则或者存在 n x R 使 Ax  0, 则或者存在 n yR 使 A y = 0 , y  0 , y  0 T 且两者不能同时成立。 注：以上是非线性最优化理论中具有重要 作用的Gordan择一定理