美文网首页
(凸集)表示定理

(凸集)表示定理

作者: 流星落黑光 | 来源:发表于2018-10-09 20:46 被阅读0次

表示定理

S = \{x|Ax=b,x\ge 0\}为非空多面集,则有:
(1)极点集非空,且存在有限个极点x^{(1)},...,x^{(k)}
(2)极方向集合为空集的充要条件是S有界,若S无界,则存在有限个极方向d^{(1)},...,d^{(l)}
(3)x\in S的充要条件是:
*1:x = \sum_{j=1}^{k}\lambda_j x^{(j)} + \sum_{j=1}^{l}\mu_j d^{(j)}
*2: \sum_{j=1}{k}\lambda_j = 1
*3: \lambda_j \ge 0 , j = 1,...k
*4: \mu_j \ge 0 , j = 1,...l

证明略。

解释:

*1:
对一个有限多面体的表面,并不需要极方向(极方向只存在与无限情况!),显然任意一个表面上的点都在某个平面上,可由这个平面的端点(即有限个极点)表示。
对一个无限多面体表面,若一个点在一个无限大的面上,这个无限大的面也可由有限条线段(也可能是0条)和有限条射线(如果直线看成两条射线)围起来,而线段可以有线段的端点表示,因此任意点可由所在平面上的线段端点(极点)和射线(极方向)表示。

*2、3:
各个极点对应的系数非负且系数和为1。
一个简单的例子:x+y+z=1可表示一个三维空间的平面,范围是0\le x,y,z \le 1
那么可去三个极点(1,0,0),(0,1,0),(0,0,1),显然平面内的点都可以表示为三个极点坐标的线性表示,且系数非负、系数和为1。其中系数非负限制了点的范围,或者说平面的边界(即0\le x,y,z \le 1)。系数和为1限制了点在平面上(x+y+z=1),如果小于1则在平面下方,大于1在平面上方。对n维平面也是类似的道理。
更本质的证明:对于一条线段,显然线段内任意一点可表示成端点的组合,且有系数非负且和为1的性质;推广到二维平面,比如一个三角形ABC,任意一点D可与C连线并交线段AB与E。那么E可由AB表示,D可由CE表示,系数分别保持非负且和为1,再整理,可得D由A、B、C表示且系数非负且和为1.得证

*4:
极方向的系数非负。
对有限情况显然极方向系数为0。对无限平面,可分成有限部分和无限部分:将几个端点连起来围成的有限凸多边形为有限部分,其余为无限部分。那么任意一个无限部分的点可表示成有限部分的某点加上某长度的极方向,也就是极方向系数非负。

其他情况:

  1. 曲面的比如球体,球面上的点都是极点,也就是无穷个极点。但是也因为如此,曲面部分的任意点本身就是极点,可由自己表示,也符合(3);平面部分可使用表示定理。
  2. 要表示非空多面集内部的点,只需把*2去掉。
  3. 极方向可能有无限个吗?事实上,对于n维空间,n个方向就可以表示任意点;若需要无穷个方向,要到无穷维的情况了吧,在此不讨论无穷维情况。

相关文章

  • (凸集)表示定理

    表示定理 设为非空多面集,则有:(1)极点集非空,且存在有限个极点(2)极方向集合为空集的充要条件是S有界,若S无...

  • 《统计学习方法》-习题2.3

    题目: 证明以下定理:样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集构成的凸壳互不相交。 解答:...

  • 7,8 凸集的交,保凸运算

    若为凸集,则为凸集仿射函数是仿射的,当若为凸,仿射,则为凸,缩放与位移式保持凸性的。例:两个凸集的和是凸的例:线性...

  • 关于凸优化

    凸集 凸集的定义为: 如果集合C中任意2个元素连线上的点也在集合C中,则C为凸集。 如下图: 常见的凸集:n维实数...

  • 深度学习笔记

    什么是凸集、凸函数、凸学习问题? 凸集:若对集合C中任意两点u和v,连接他们的线段仍在集合C中,那么集合C是凸集。...

  • 凸集

    凸集 一.仿射集合与凸集 1.仿射集合(affine set) 过两个点的直线方程:,且为n维空间的两个点。可以更...

  • 凸集

    1.凸集定义 定义1:若集合是凸集,那么对于集合内的任意两点之间的线段上的点仍然在集合内。 定义2:称为凸组合(区...

  • 凸优化笔记2-主要内容

    笔记主要内容 凸集、凸函数、凸优化 凸优化理论 若干算法

  • COAC:Introduction

    凸集和凸函数的定义: 凸集: 数学定义:集合X 属于R^n(即其中的元素x有n维,每维都在R实数空间)如果X是凸集...

  • 凸优化(二)——凸集

    〇、说明 凸优化主要学习《凸优化》(Stephen Boyd等著,王书宁等译)[1]这本书。学习过程中,对其内容的...

网友评论

      本文标题:(凸集)表示定理

      本文链接:https://www.haomeiwen.com/subject/fnbyaftx.html