凸优化理论(一)深入理解仿射集,凸集,锥等定义及相关证明 |
您所在的位置:网站首页 › 一个平面经过一条直线是什么意思 › 凸优化理论(一)深入理解仿射集,凸集,锥等定义及相关证明 |
文章目录
1:仿射集相关定义与证明2:相关子空间与性质证明3:线性方程组的解集与化零空间4:任意集合构建最小仿射集-仿射包5:凸集相关:凸包-凸组合6:锥 Cone与凸锥 Convex Cone7:概念比较
重点是理解组合的概念,对于集合包括仿射集,凸集,凸锥集的定义都类似,也就是相应 k k k个点的的组合仍然在这个集合里。而对于包的定义也类似,就是从一个不是仿射集/凸集/凸锥集的集合构造出一个这样的集合。 1:仿射集相关定义与证明直线 \color{red}\textbf{直线} 直线 给定空间的两个点 x 1 , x 2 ∈ R n x_1,x_2\in R^n x1,x2∈Rn,,我们可以确定一条过这两个点的直线 y = θ x 1 + ( 1 − θ ) x 2 = x 2 + θ ( x 1 − x 2 ) y=\theta x_1+(1-\theta)x_2=x_2+\theta(x1-x2) y=θx1+(1−θ)x2=x2+θ(x1−x2) 也就是我们从 x 2 x_2 x2出发,沿着 x 1 − x 2 x_1-x_2 x1−x2的方向任意的变化 θ \theta θ值,这样就可以画出来整个一条直线。 线段 \color{red}\textbf{线段} 线段 对于线段而言, 我们需要加上约束 θ ∈ [ 0 , 1 ] \theta\in[0,1] θ∈[0,1]。 仿射集 \color{red}\textbf{仿射集} 仿射集 一个集合 c c c是仿射集,那么在集合中选择任意两点 x 1 , x 2 ∈ c x_1,x_2\in c x1,x2∈c,那么连接 x 1 , x 2 x_1,x_2 x1,x2的直线也在集合内。 显然一个直线是一个仿射集,一个线段不是仿射集,整个的二维空间是一个仿射集,但是在二维空间内选择一有限的区域不是一个仿射集。 仿射集的定义依赖于任意两点这个概念,那么如果我们将两个点扩充到三个点,四个点,无穷个点,然后对概念进行扩充, 仿射组合 \color{red}\textbf{仿射组合} 仿射组合 设 x 1 , x 2 , . . . , x k ∈ c , θ 1 , θ 2 , . . . , θ k , ∑ i = 1 k θ i = 1 \color{blue}x_1,x_2,...,x_k\in c,\theta_1,\theta_2,...,\theta_k,\sum_{i=1}^k\theta_i=1 x1,x2,...,xk∈c,θ1,θ2,...,θk,∑i=1kθi=1,那么我们有一个仿射组合: θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk 那么我们将定义扩展,如果一个集合是仿射集,那么我们从中选取任意 k k k个点,他们的仿射组合总是在集合 c c c内。(考虑 k = 2 k=2 k=2那么该定义就退化为了直线的定义)。 仿射组合的简单证明 \color{red}\textbf{仿射组合的简单证明} 仿射组合的简单证明 我们将两个点的情况拓广至三个点的情况,来证明仿射集在放射组合上的拓展是有效的 假设我们有三个点 x 1 , x 2 , x 3 ∈ c , θ 1 + θ 2 + θ 3 = 1 x_1,x_2,x_3\in c,\theta_1+\theta_2+\theta_3=1 x1,x2,x3∈c,θ1+θ2+θ3=1,那么对于任意两个点(姑且选择前两个点,我们有) θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ∈ c \frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2\in c θ1+θ2θ1x1+θ1+θ2θ2x2∈c 此时此两个点的线性组合可以看作一个点,然后我们将第三个点加入,可以得到: ( θ 1 + θ 2 ) ( θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ) + ( 1 − θ 1 − θ 2 ) x 3 ∈ c (\theta_1+\theta_2)(\frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2)+(1-\theta_1-\theta_2)x_3 \in c (θ1+θ2)(θ1+θ2θ1x1+θ1+θ2θ2x2)+(1−θ1−θ2)x3∈c 得证。 2:相关子空间与性质证明对于上面的定义,我们很容易产生一个问题, 如 果 有 两 个 点 x 1 , x 2 ∈ c , c 是 仿 射 集 , 如 果 我 们 选 择 两 个 不 相 关 的 数 α , β ∈ R , 那 么 α x 1 + β x 2 是 否 也 属 于 c 呢 ? \color{blue}\mathbf{如果有两个点x_1,x_2\in c,c是仿射集,如果我们选择两个不相关的数\alpha,\beta\in R,那么\alpha x_1+\beta x_2是否也属于c呢?} 如果有两个点x1,x2∈c,c是仿射集,如果我们选择两个不相关的数α,β∈R,那么αx1+βx2是否也属于c呢? 好像不一定,那么我们有没有更一般的仿射集,使得上面这种线性组合也能够保证他们的结果属于仿射集内部? 答案是肯定的,比如下图中过原点的直线,由于
x
1
,
x
2
x_1,x_2
x1,x2是向量,因此过原点的直线无论经过怎样的组合都还是在这条直线上,那么我们需要寻找这一类集合具有什么样的普遍规律。 相 关 子 空 间 : V = c − x 0 = { x − x 0 ∣ x ∈ c } ∀ x 0 ∈ c \color{red}\mathbf{相关子空间:V=c-x_0=\{x-x_0|x\in c\} \forall x_0\in c} 相关子空间:V=c−x0={x−x0∣x∈c}∀x0∈c 任意给定一个仿射集 c c c, c c c不一定具有上述的任意两点的任意组合还在集合内的性质,我们将 c c c中的任意一个元素 x x x,把所有的 x − x 0 x-x_0 x−x0拿出来构成一个新的集合, x 0 x_0 x0是我们从 c c c中任意拿出的一个点(也就是对 c c c中的任意一个点,相对 x 0 x_0 x0做一次空间的平移),那么我们称 V V V为与 c c c相关的子空间。注意这里的 c c c必须是一个仿射集,否则不能称 V V V为一个子空间。这个 V V V满足以下两个性质: V V V是一个仿射集 如 果 有 两 个 点 x 1 , x 2 ∈ c , c 是 仿 射 集 , 如 果 我 们 选 择 两 个 不 相 关 的 数 α , β ∈ R , 那 么 α x 1 + β x 2 是 否 属 于 V 呢 如果有两个点x_1,x_2\in c,c是仿射集,如果我们选择两个不相关的数\alpha,\beta\in R,那么\alpha x_1+\beta x_2是否属于V呢 如果有两个点x1,x2∈c,c是仿射集,如果我们选择两个不相关的数α,β∈R,那么αx1+βx2是否属于V呢 相关子空间性质证明 \color{red}\textbf{相关子空间性质证明} 相关子空间性质证明 假设我们有两个点 ∀ v 1 , v 2 ∈ V , ∀ α , β ∈ R \color{blue}\forall v_1,v_2\in V, \forall\alpha,\beta\in R ∀v1,v2∈V,∀α,β∈R,我们要证明 α x 1 + β x 2 ∈ V \alpha x_1+\beta x_2\in V αx1+βx2∈V也就是要证明 α x 1 + β x 2 + x 0 ∈ c \alpha x_1+\beta x_2+x_0\in c αx1+βx2+x0∈c(这一步是因为相关子空间的定义哈),那么我们把他拆成三部分 α ( v 1 + x 0 ) + β ( v 2 + x 0 ) + ( 1 − α − β ) x 0 \alpha(v_1+x_0)+\beta(v_2+x_0)+(1-\alpha-\beta)x_0 α(v1+x0)+β(v2+x0)+(1−α−β)x0 因为 c c c是仿射集,所以 v 1 + x 0 v_1+x_0 v1+x0和 v 2 + x 0 v_2+x_0 v2+x0和 x 0 x_0 x0都是属于仿射集 c c c的,所以上面这个式子是 c c c中的一个仿射组合!所以上式也属于 c c c,证毕。其他性质 \color{red}\textbf{其他性质} 其他性质 对相关子集和, x 0 x_0 x0任意选择都是可以的。所谓的空间,一定是经过原点的,只有经过原点才能称之为空间或者子空间。而在集合 c c c中一定有一个 x 0 x_0 x0点,我们减去 x 0 x_0 x0就一定会经过原点。 3:线性方程组的解集与化零空间定理证明 \color{red}\textbf{定理证明} 定理证明 c = { x ∣ A x = b } A ∈ R m ∗ n , b ∈ R m , x ∈ R n c=\{x|Ax=b\}\;A\in R^{m*n},b\in R^m,x\in R^n c={x∣Ax=b}A∈Rm∗n,b∈Rm,x∈Rn 这是一个一般的线性方程组,那么我们需要证明 c c c是一个仿射集。对 ∀ x 1 , x 2 ∈ c \forall x_1,x_2\in c ∀x1,x2∈c,我们有 A x 1 = b , A x 2 = b Ax_1=b,Ax_2=b Ax1=b,Ax2=b。那么是否有 θ x 1 + ( 1 − θ ) x 2 ∈ c \theta x_1+(1-\theta)x_2\in c θx1+(1−θ)x2∈c?答案是肯定的。因为 A ( θ x 1 + ( 1 − θ ) x 2 ) = θ A x 1 + ( 1 − θ ) A x 2 = b A(\theta x_1+(1-\theta)x_2)=\theta Ax_1+(1-\theta) Ax_2=b A(θx1+(1−θ)x2)=θAx1+(1−θ)Ax2=b。证毕。那么推而广之,我们可以证明任何一个仿射集都可以写成一个线性方程组的解集。 解集的相关子空间:化零空间 \color{red}\textbf{解集的相关子空间:化零空间} 解集的相关子空间:化零空间 那么相应的,这样一个仿射集也应该有相关子空间,那么他的相关子空间,也就是下式是什么? V = { x − x 0 ∣ x ∈ c } ∀ x 0 ∈ c V=\{x-x_0|x\in c\}\;\forall x_0\in c V={x−x0∣x∈c}∀x0∈c 我们将上式化简,可以得到 V = { x − x 0 ∣ A x = b } A x 0 = b V=\{x-x_0|Ax=b\}\;Ax_0=b V={x−x0∣Ax=b}Ax0=b,再来一步化简得到 V = { x − x 0 ∣ A ( x − x 0 ) = 0 } V=\{x-x_0|A(x-x_0)=0\}\; V={x−x0∣A(x−x0)=0},然后我们将 x − x 0 x-x_0 x−x0替换为 y y y,那么我们将其写为 V = { y ∣ A y = 0 } V=\{y|Ay=0\}\; V={y∣Ay=0},那么我们得到了 A A A的化零空间,也就是对于任意的子空间 V V V中的点我们给用 A A A相乘都能得到0。 那么我们实际上做了什么工作呢?比较 V = { y ∣ A y = 0 } V=\{y|Ay=0\}\; V={y∣Ay=0}和 c = { x ∣ A x = b } c=\{x|Ax=b\}\; c={x∣Ax=b},我们实际上是在高维空间中做了一次平移,让 c c c平移到至少一个点在原点上的空间。 4:任意集合构建最小仿射集-仿射包如果给定一个集合,他可能是一个仿射集也可能不是,那么我们是否能在 c c c上构造出一个仿射集,而且保证这个仿射集是最小的! 我们需要先引入一个新的定义,c的仿射包: a f f c = { θ 1 x 1 + . . . + θ k x k ∣ ∀ x i , x i ∈ c ; ∀ θ 1 + . . . + θ k = 1 } \color{red}\mathbf{aff c=\{ \theta_1 x_1+...+\theta_kx_k|\forall x_i,x_i\in c; \forall \theta_1+...+\theta_k=1\}} affc={θ1x1+...+θkxk∣∀xi,xi∈c;∀θ1+...+θk=1} 仿射包仍然是一个集合。我们可以将其简单的理解为如下形式: 对两个点 x 1 , x 2 x_1,x_2 x1,x2构成的集合他显然不是一个仿射集,那么根据他的仿射包的定义,我们取 x 1 , x 2 x_1,x_2 x1,x2的任意组合 θ 1 x 1 + θ 2 x 2 \theta_1x_1+\theta_2x_2 θ1x1+θ2x2就形成了什么东西?一条直线,这也就是我们最开始提到的最简单的仿射集。如果我们再添加一个点 x 3 x_3 x3,那么他们仨个经过任意组合所形成的仿射包就是整个平面,也就是说这个仿射包一定是一个仿射集。如果 c c c本身就是一个仿射集,那么他的仿射包就是他自己。我们需要比较以下凸集和仿射集二者的定义: 一个集合 c c c是凸集,当任意两点之间的线段仍然在 c c c内。一个集合 c c c是凸集,当任意两点之间的直线仍然在 c c c内。二者的差距就在线段和直线上,这也就是为什么凸优化的书籍从直线,线段的表示讲起的原因。那么参照仿射集,凸集定义如下: c i s c o n v e x < = > θ x 1 + ( 1 − θ ) x 2 ∈ c ; ∀ x 1 , x 2 ∈ c , ∀ θ ∈ [ 0 , 1 ] , c\;is\;convex\theta x_1+(1-\theta) x_2\in c;\forall x_1,x_2\in c,\color{blue}{\forall\theta\in[0,1]}, cisconvexθx1+(1−θ)x2∈c;∀x1,x2∈c,∀θ∈[0,1], 其中 ∀ θ ∈ [ 0 , 1 ] \forall\theta\in[0,1] ∀θ∈[0,1]就是作为线段的限制。显然仿射集是凸集,因为直线都在集合内了,线段显然也在集合内。 对于仿射集我们定义了仿射组合,那么对于凸集,我们同样有类似的凸组合。 凸组合 \color{red}\textbf{凸组合} 凸组合 同样我们先回顾一下仿射组合的定义: 设 x 1 , x 2 , . . . , x k ∈ c , θ 1 , θ 2 , . . . , θ k , ∑ i = 1 k θ i = 1 x_1,x_2,...,x_k\in c,\theta_1,\theta_2,...,\theta_k,\sum_{i=1}^k\theta_i=1 x1,x2,...,xk∈c,θ1,θ2,...,θk,∑i=1kθi=1,那么我们有一个仿射组合: θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk,那么对于凸组合呢?我们无非在 θ \theta θ上做一些限制。 x 1 , x 2 , . . . , x k x_1,x_2,...,x_k x1,x2,...,xk的凸组合 θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk具有如下限制: x 1 , x 2 , . . . , x k ∈ c , ∑ i = 1 k θ i = 1 , ∀ θ i ∈ [ 0 , 1 ] x_1,x_2,...,x_k\in c,\sum_{i=1}^k\theta_i=1,\color{blue}\forall \theta_i\in[0,1] x1,x2,...,xk∈c,∑i=1kθi=1,∀θi∈[0,1],也就是加上了对线段的约束,仅此而已。 凸集概念扩充 \color{red}\textbf{凸集概念扩充} 凸集概念扩充 又来了,再一次的,我们不满足于两个点的现状,必须将凸集扩充到多个点的情况,这和使用仿射组合扩充仿射集是非常类似的。 如果一个集合是凸集,那么我们从中选取任意 k k k个点,他们的凸组合总是在集合 c c c内。(考虑 k = 2 k=2 k=2那么该定义就退化为了线段的定义)。 考虑仿射集有仿射包,凸集拥有着凸包的概念 凸包 \color{red}\textbf{凸包} 凸包 对任意一个集合 c ∈ R n c\in R^n c∈Rn, c c c的凸包定义为: C o n v c = { θ 1 x 1 + . . . + θ k x k ∣ ∀ x i , x i ∈ c ; ∑ i = 1 k θ i = 1 ; ∀ θ i ∈ [ 0 , 1 ] } \color{red}\mathbf{Conv\; c=\{ \theta_1 x_1+...+\theta_kx_k|\forall x_i,x_i\in c; \sum_{i=1}^k\theta_i=1;\color{blue}\forall\theta_i\in[0,1]\}} Convc={θ1x1+...+θkxk∣∀xi,xi∈c;i=1∑kθi=1;∀θi∈[0,1]} 同样的,给仿射包加上线段的限制就变成了凸包的定义 图形展示 \color{red}\textbf{图形展示} 图形展示 最经典的三个图: 值得注意的是,对肾形图案而言,他的凸包就是将空白部分补上。 如果去掉正方形的四个端点,他依然是一个凸集,也就是说此时他的凸包是他自己,端点不影响他的凸性。如果去掉正方形的中间两点而不是端点,那么他的凸包是整个正方形。 上述都是连续集合,对于离散集合的凸包我们如何构造呢?其实现在已经有很多求凸包的算法 了: c i s C o n e ⟺ ∀ x ∈ c , θ > 0 , w e h a v e θ x ∈ c \color{red}c\;is\;Cone\Longleftrightarrow \forall x\in c,\theta>0,we\;have\;\theta x\in c cisCone⟺∀x∈c,θ>0,wehaveθx∈c c i s C o n v e x C o n e ⟺ ∀ x 1 , x 2 ∈ c , θ 1 , θ 2 > 0 , w e h a v e θ 1 x 1 + θ 2 x 2 ∈ c \color{red}c\;is\;Convex \;Cone\Longleftrightarrow \forall x_1,x_2\in c,\theta_1,\theta_2>0,we\;have\;\theta_1x_1+\theta_2x_2\in c cisConvexCone⟺∀x1,x2∈c,θ1,θ2>0,wehaveθ1x1+θ2x2∈c 关于这个凸锥的概念,我们可以发现他和相关子空间的定义很像,在相关子空间的部分,我们希望对任意的 α , β ∈ R , 有 α x 1 + β x 2 ∈ c \alpha,\beta\in R,有\alpha x_1+\beta x_2\in c α,β∈R,有αx1+βx2∈c,而在这里有了新的约束 θ 1 , θ 2 > 0 \theta_1,\theta_2>0 θ1,θ2>0,这个约束有什么含义呢?换句话说,他和相关子空间的差别在哪里。 首先,对于过原点的三条射线(以原点为起点),他们所构成的集合是一个锥(也就是说我们有几条射线,我们把他们起点放在一起,同时保证他的连接点放在原点上就能构成一个锥)。相反这个Y字形的线不过原点,他上面的点并不满足凸锥的定义。那么我们不妨来要无穷多个射线,他会构成什么样的形状呢?即右图,它不仅是一个锥,而且是一个凸集,于是构成了凸锥。到这里我冒昧的总结一下如果说仿射集是基于直线来定义,凸集是基于线段来定义,那么锥就是基于射线的定义与前面类似,我们依然可以定义凸锥组合,凸锥包等概念 凸锥组合 \color{red}\textbf{凸锥组合} 凸锥组合 同样我们先回顾一下仿射组合的定义: 设 x 1 , x 2 , . . . , x k ∈ c , θ 1 , θ 2 , . . . , θ k , ∑ i = 1 k θ i = 1 x_1,x_2,...,x_k\in c,\theta_1,\theta_2,...,\theta_k,\sum_{i=1}^k\theta_i=1 x1,x2,...,xk∈c,θ1,θ2,...,θk,∑i=1kθi=1,那么我们有一个仿射组合: θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk,那么对于凸锥组合呢?我们无非在 θ \theta θ上做一些限制。 x 1 , x 2 , . . . , x k x_1,x_2,...,x_k x1,x2,...,xk的凸锥组合 θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk具有如下限制: x 1 , x 2 , . . . , x k ∈ c , ∀ θ i > 0 x_1,x_2,...,x_k\in c,\color{blue}\forall \theta_i>0 x1,x2,...,xk∈c,∀θi>0,也就是加上了对射线的约束,仅此而已。 凸锥包 \color{red}\textbf{凸锥包} 凸锥包 对任意一个集合 c ∈ R n c\in R^n c∈Rn, c c c的凸锥包定义为: C o n v c = { θ 1 x 1 + . . . + θ k x k ∣ ∀ x i , x i ∈ c ; ∀ θ i > 0 } \color{red}\mathbf{Conv\; c=\{ \theta_1 x_1+...+\theta_kx_k|\forall x_i,x_i\in c; \color{blue}\forall\theta_i>0\}} Convc={θ1x1+...+θkxk∣∀xi,xi∈c;∀θi>0} 同样的,给仿射包加上射线的限制就变成了凸锥包的定义
图形展示
\color{red}\textbf{图形展示}
图形展示 注意第一象限的两个点的凸锥是一条射线,而不是直线,做个比较,两个点的仿射集是两点所在直线,凸集是两点所成线段,而锥是过原点的射线集合。 各种组合 \color{red}\textbf{各种组合} 各种组合 仿射组合: x 1 , x 2 , . . . , x k ∈ c , ∑ i = 1 k θ i = 1 x_1,x_2,...,x_k\in c,\color{blue}\sum_{i=1}^k\theta_i=1 x1,x2,...,xk∈c,∑i=1kθi=1凸组合: x 1 , x 2 , . . . , x k ∈ c , ∑ i = 1 k θ i = 1 , ∀ θ i ∈ [ 0 , 1 ] x_1,x_2,...,x_k\in c,\color{blue}\sum_{i=1}^k\theta_i=1,\forall \theta_i\in[0,1] x1,x2,...,xk∈c,∑i=1kθi=1,∀θi∈[0,1]凸锥组合: x 1 , x 2 , . . . , x k ∈ c , ∀ θ i > 0 x_1,x_2,...,x_k\in c,\color{blue}\forall \theta_i>0 x1,x2,...,xk∈c,∀θi>0三种组合的差别就在限制条件上,对于直线而言,我们需要限制 ∑ i = 1 k θ i = 1 \sum_{i=1}^k\theta_i=1 ∑i=1kθi=1,对于线段而言,我们需要 ∑ i = 1 k θ i = 1 , ∀ θ i ∈ [ 0 , 1 ] \sum_{i=1}^k\theta_i=1,\forall \theta_i\in[0,1] ∑i=1kθi=1,∀θi∈[0,1],而对于射线而言,我们只需要 ∀ θ i > 0 \forall \theta_i>0 ∀θi>0。各种集合 \color{red}\textbf{各种集合} 各种集合 任意的仿射集一定是凸的,因为如果任意的仿射组合在集合内的话,任意的凸组合显然也在集合内。也就是说,仿射集是凸集的一个特例(一个无限大的凸集)凸锥也一定是凸的。因为只要凸锥组合的条件满足,凸组合的性质一定是满足的。只有一个点/没有点的场景 \color{red}\textbf{只有一个点/没有点的场景} 只有一个点/没有点的场景 注意到我们在考虑上述问题时,默认是有两个以上点的,那么单个点能否成为凸集 c = { x } c=\{x\} c={x} 我们永远有, θ 1 x + θ 2 x = x \theta_1x+\theta_2x=x θ1x+θ2x=x,所以他是一个仿射集,也是一个凸集。凸锥稍有不同,如果这个点是原点,那么他一定是凸锥,否则他一定不是凸锥。 那么一个空集呢?他既是凸集,也是仿射集,也是凸锥。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |