理论部分凸集的分离定义 1 设 nRDD?
21,
为两非空凸集,
nRa?
若存在
,1 xaRxHD Tn
,2 xaRxHD Tn
非零向量 和实数,? 使得:
则称超平面 xaRxH Tn分离了集合
1D 和,2D
注,严格分离.
定理 1 设 nRD? 是非空闭凸集,nRy? 但
,Dy? 则:
(1) 存在唯一的点,Dx? 使得集合 D 到点
y 的距离最小,即,,,in f Dxyxyx
(2) Dx? 是点 y 到集合 D 的最短距离点的充要条件为,,0 Dxyxxx T
注,闭凸集外一点与闭凸集的极小距离,
即投影定理。
定理 2 设 nRD? 为非空闭凸集,,nRy?
,Dy? 则存在非零向量 nRa? 和实数,?
使得:,,Dxyaxa TT
即存在超平面 xaRxH Tn严格分离点
y 与凸集,D
注,点与闭凸集的分离定理。
引理 1 设 nmRA 为 nm? 矩阵,,nRb?
则下述两组方程中有且仅有一组有解:
,0,0 xbAx T
,0, ybyA T
其中,,mn RyRx
注,以上是在最优化理论研究中起重要作用的 Farkas引理。
定义 2 设 nRD? 为非空集合,且点 nRx?
属于集合 D 的边界,即,Dx 若存在非零向量,nRa? 使成立:
0 xxaRxHD Tnx
或者0 xxaRxHD Tn
x
则称超平面0 xxaRxH Tn
x
是集合 D 在其边界点 x 的支撑超平面。
定理 3 设 nRD? 为非空凸集,,Dx 则存在非零向量,nRa? 使成立
,,Dxxaxa TT
即凸集 nRD? 在其边界点处存在支撑超平面,
其中 D 表示集合 D 的闭包。
注,非空凸集在其任一个边界点处都存在支撑超平面。
推论 1 设 nRD? 是非空凸集,,Dx? 则存在非零向量 nRa? 使成立
.Dxxaxa TT
定理 4 设 21,DD 是 nR 的两个非空凸集,且
,21DD? 则存在超平面分离 1D 和,2D
即存在非零向量 nRa? 使得
.,,21 DyDxyaxa TT
注,以上是两凸集分离定理。
定理 5 设 nmRA 为 nm? 阶矩阵,则或者存在
nRx? 使,0?Ax 则或者存在 nRy? 使
0,0,0 yyyA T
且两者不能同时成立。
注,以上是非线性最优化理论中具有重要作用的 Gordan择一定理。