代码编织梦想

引言

这是中科大最优化理论的笔记,中科大凌青老师的凸优化课程,详尽易懂,基础扎实。不论是初学者还是从业多年的人,都值得系统地好好学一遍。

本文介绍什么是凸集、凸包与凸锥包。

仿射集

我们先来看最简单的凸集——仿射集(Affine sets)。在此之间我们先看直线的定义。

直线与线段

给定两个点 x 1 , x 2 ∈ R n x_1,x_2 \in R^n x1,x2Rn,且 x 1 ≠ x 2 x_1 \neq x_2 x1=x2,如何表示一个直线方程?

我们可以定义一个变量 θ ∈ R \theta \in R θR,那么可以这样表达
y = θ x 1 + ( 1 − θ ) x 2 (1) y = \theta x_1 + (1-\theta)x_2 \tag 1 y=θx1+(1θ)x2(1)
为什么这样可以表示直线呢?我们先来看它的另一种表述
y = x 2 + θ ( x 1 − x 2 ) (2) y = x_2 + \theta(x_1 - x_2) \tag 2 y=x2+θ(x1x2)(2)
只是变换了一下形式,这样子就更好理解。表示从点 x 2 x_2 x2出发,沿着 x 1 − x 2 x_1 - x_2 x1x2方向变化 θ \theta θ从而形成整条直线。

回忆了一下以前学的直线公式什么 y = a x + b y=ax +b y=ax+b都不好理解。直到我们引入向量的概念。

IMG_4566EB4FFCE0-1

在二维平面中,假设有 x 1 , x 2 x_1,x_2 x1,x2两点,接着我们用向量来描述这两点:

IMG_04AAED50A2D0-1

接着看式 ( 2 ) (2) (2) x 1 − x 2 x_1 -x_2 x1x2部分,从向量的角度来看,它表示从 x 2 x_2 x2的终点指向 x 1 x_1 x1的终点,即:

IMG_BDE83B890E91-1

这样我们得到了向量 x 1 − x 2 x_1 -x_2 x1x2,那么$y = x_2 + \theta(x_1 - x_2) 表 示 从 点 表示从点 x_2 出 发 , 沿 着 向 量 出发,沿着向量 沿x_1 -x_2 的 方 向 , 走 的方向,走 |\theta(x_1 - x_2)| 的 距 离 后 产 生 的 点 。 : w a r n i n g : 若 的距离后产生的点。:warning:若 :warning:\theta 固 定 则 产 生 的 只 是 一 个 点 ; 固定则产生的只是一个点; \theta 变 化 则 产 生 多 个 点 ; 若 变化则产生多个点;若 \theta 取 实 数 ( 取实数( (R ) , 则 产 生 的 点 组 成 无 限 长 的 直 线 。 这 里 ),则产生的点组成无限长的直线。这里 )线\theta$可以理解为机器学习中的步长。

如果 θ = 1 \theta=1 θ=1,那么得到的点 y y y就等于 x 1 x_1 x1;如果 θ = 2 \theta=2 θ=2,那么得到的点为 2 ( x 1 − x 2 ) + x 2 = 2 x 1 − x 2 = x 1 + ( x 1 − x 2 ) 2(x_1-x_2) + x_2=2x_1-x_2=x_1 +(x_1 -x_2) 2(x1x2)+x2=2x1x2=x1+(x1x2),可以看成是从点 x 1 x_1 x1出发,沿着 x 1 − x 2 x_1-x_2 x1x2的方向走了 ∣ x 1 − x 2 |x_1-x_2 x1x2的距离,得到的图形如下:

IMG_C534E5A3B009-1

这样,若 θ \theta θ不同,得到的点就不同。若 θ \theta θ为负值,就是往相反的方向移动。

θ ∈ R \theta \in R θR时, y y y就为经过 x 1 , x 2 x_1,x_2 x1,x2两点的直线。这样我们就理解了为什么公式 ( 2 ) (2) (2)表示经过 x 1 , x 2 x_1,x_2 x1x2两点的直线。

复习一下高中的知识。

img

向量的加法口诀:首尾相连,首连尾,方向指向末向量( b ⃗ \vec{b} b )。

向量的减法口诀:首首相连,尾连尾,方向指向被减向量( a ⃗ \vec{a} a )。

下面我们就来看下什么是线段。

同样给两个点 x 1 , x 2 x_1,x_2 x1,x2,如何表示 x 1 x_1 x1 x 2 x_2 x2之间的线段呢?同样可以写成下面的形式:
y = θ x 1 + ( 1 − θ ) x 2 (3) y = \theta x_1 + (1-\theta)x_2 \tag 3 y=θx1+(1θ)x2(3)
此时要限定 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ[0,1]

θ = 0 \theta=0 θ=0 y = x 2 y=x_2 y=x2;当 θ = 1 \theta=1 θ=1 y = x 1 y=x_1 y=x1。否则 y y y就在 x 1 , x 2 x_1,x_2 x1,x2的连线之间。

image-20221116075333972

总之,若 θ ∈ R \theta \in R θR时,公式 ( 3 ) (3) (3)表示经过 x 1 , x 2 x_1,x_2 x1,x2的无限延伸的直线;若 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ[0,1]时,则被限定为 x 1 , x 2 x_1,x_2 x1,x2之间的线段,如上图所示。

有了上面的概念,我们来看下仿射集的定义。

仿射集合

仿射集: 一个集合 C C C是仿射集,若 ∀    x 1 , x 2 ∈ C \forall \,\, x1,x_2 \in C x1,x2C,则连接 x 1 x_1 x1 x 2 x_2 x2的直线也在集合内。
θ x 1 + ( 1 − θ ) x 2 ∈ C , θ ∈ R (4) \theta x_1 + (1-\theta)x_2 \in C ,\quad \theta \in R\tag 4 θx1+(1θ)x2C,θR(4)
即任意从 C C C中取两个点,连接它们的直线也在集合内。

有了这个知识,那么直线是仿射集吗?根据定义,从直线内任取两点(不重合),形成的就是该直线本身,所以直线是仿射集

线段是仿射集吗?显然不是。线段是封闭的,任取两点变成连接该两点的直线,超出了线段的范围。

那整个二维空间 R 2 R^2 R2(想象一个无限扩展的二维平面)是仿射集吗?根据定义,连接二维空间内任意两点的直线一定在二维空间内,所以** R 2 R^2 R2是仿射集**。

IMG_97993F6BF490-1

若如上图所示,限定为该二维空间内的一个填充内部的正方形,由于它是有限的,在其中任取两点连接的直线会超出它的边界,显然也不是仿射集。

上面的定义限定为任取两点,那能否扩展为多个点呢。

x 1 , ⋯   , x k ∈ C x_1,\cdots,x_k \in C x1,,xkC, θ 1 , ⋯   , θ k ∈ R \theta_1,\cdots,\theta_k \in R θ1,,θkR,且 θ 1 + ⋯ + θ k = 1 \theta_1 + \cdots + \theta_k =1 θ1++θk=1

称具有 θ 1 x 1 + ⋯ + θ k x k \theta_1 x_1 + \cdots + \theta_k x_k θ1x1++θkxk的形式为仿射组合

θ 1 x 1 + ⋯ + θ k x k \theta_1 x_1 + \cdots + \theta_k x_k θ1x1++θkxk一定是一个点,它是多个向量相加。

image-20221116082612844

比如上图向量 u ⃗ + v ⃗ + w ⃗ + x ⃗ \vec u+\vec v+\vec w+\vec x u +v +w +x 得到的点是黑色向量的终点。

所以若一个集合是仿射集,从中任取两个点,它的仿射组合 θ 1 x 1 + ⋯ + θ k x k \theta_1 x_1 + \cdots + \theta_k x_k θ1x1++θkxk一定在集合内。

看起来有点复杂,如果退化为两个点,即 k = 2 k=2 k=2,就变成了连接该两点的直线也在集合内,该集合一定为仿射集合。

下面我们来证明下第二个定义与第一个定义是等价的,有了第一个定义后,我们想推出来第二个定义的集合也是仿射集。

简单起见,我们先来看三个点的情况。

有仿射集 C C C x 1 , x 2 , x 3 ∈ c x_1,x_2,x_3 \in c x1,x2,x3c θ 1 , θ 2 , θ 3 ∈ c \theta_1,\theta_2,\theta_3 \in c θ1,θ2,θ3c,且 θ 1 + θ 2 + θ 3 = 1 \theta_1 + \theta_2 + \theta_3 =1 θ1+θ2+θ3=1

我们先构造另外一个点:
θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ∈ C (5) \frac{\theta_1}{\theta_1+\theta_2}x_1 + \frac{\theta_2}{\theta_1+\theta_2}x_2 \in C \tag 5 θ1+θ2θ1x1+θ1+θ2θ2x2C(5)
因为根据仿射集的第一个定义, x 1 , x 2 x_1,x_2 x1,x2前面的系数相加为 1 1 1,形成的新点一定属于 c c c。我们继续组合:
( θ 1 + θ 2 ) ( θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ) + ( 1 − θ 1 − θ 2 ) x 3 ∈ C (6) (\theta_1+\theta_2) \left (\frac{\theta_1}{\theta_1+\theta_2}x_1 + \frac{\theta_2}{\theta_1+\theta_2}x_2 \right) +(1-\theta_1-\theta_2)x_3 \in C \tag 6 (θ1+θ2)(θ1+θ2θ1x1+θ1+θ2θ2x2)+(1θ1θ2)x3C(6)
( 4 ) (4) (4)构建的新点与 x 3 x_3 x3该两点前面的系数之和为 1 1 1,所以形成的点也一定属于 c c c

我们对式 ( 5 ) (5) (5)进行变形:
θ 1 x 1 + θ 2 x 2 + θ 3 x 3 ∈ C (7) \theta_1 x_1 + \theta_2x_2 + \theta_3x_3 \in C \tag 7 θ1x1+θ2x2+θ3x3C(7)
θ 1 + θ 2 \theta_1+\theta_2 θ1+θ2乘到 ( 5 ) (5) (5)式第一项中,并由 1 − θ 1 − θ 2 = θ 3 1-\theta_1-\theta_2=\theta_3 1θ1θ2=θ3得到了上式。

这样我们就证明了仿射集的第二个定义与第一个定义是等价的。

仿射集的性质

我们知道,若 x 1 , x 2 ∈ C x_1,x_2 \in C x1,x2C C C C是仿射集, θ x 1 + ( 1 − θ ) x 2 ∈ C \theta x_1 + (1-\theta)x_2 \in C θx1+(1θ)x2C

那下面这个点
α x 1 + β x 2 ∈ C , α , β ∈ R (8) \alpha x_1 +\beta x_2 \in C,\quad \alpha,\beta \in R \tag 8 αx1+βx2C,α,βR(8)
是否成立呢?我们知道当 α + β = 1 \alpha+\beta=1 α+β=1时,一定成立。

那是否有比较特殊的仿射集,对于这种更一般的形式也成立呢?

IMG_92AED4971613-1

如上图,我们有两点 x 1 , x 2 x_1,x_2 x1,x2,如果 α = 1 , β = 1 \alpha=1,\beta=1 α=1,β=1,那么得到的点 x 3 x_3 x3肯定在直线外面。

但如果我们改成与这条直线平行,且经过原点的直线。

IMG_7C4D686862C3-1

如上图绿线所示,相当于这两个向量共线,那么得到的这两向量相加得到的点一定在直线内。

所以经过原点的直线满足这个性质。

更一般地,若 C C C是一个仿射集且 x c ∈ C x_c \in C xcC,则集合
V = C − x 0 = { x − x 0 ∣ x ∈ C } ∀ x 0 ∈ C (9) V= C- x_0 = \{x-x_0 |x \in C \} \quad \forall x_0 \in C\tag 9 V=Cx0={xx0xC}x0C(9)
C C C是任意仿射集,不一定要满足式 ( 8 ) (8) (8),我们来构造一个新的集合 V = C − x 0 V=C-x_0 V=Cx0,即让集合 C C C内任意一点都减去 C C C内任意选定的点,得到的新集合。实际上让仿射集 C C C相对 x 0 x_0 x0进行了平移。

C − x 0 C-x_0 Cx0到底是什么意思呢?

IMG_F7F3D9624075-1

我们画一条不经过原点的直线来表示 C C C,并任意在 C C C内取五个点,包括 x 0 x_0 x0

我们知道 C − x 0 C-x_0 Cx0就是 C C C内所有的点都减去 x 0 x_0 x0。我们这里计算 x 0 , x 1 , x 2 , x 3 , x 4 x_0,x_1,x_2,x_3,x_4 x0,x1,x2,x3,x4减去 x 0 x_0 x0的结果,先来看 x 0 − x 0 = 0 x_0-x_0=0 x0x0=0,变成了原点。那么其他的点减去 x 0 x_0 x0是怎样的呢?比如 x 2 − x 0 x_2 -x_0 x2x0

IMG_6ED9ED75DEC2-1

x − x 0 x-x_0 xx0可以看成是 x + ( − x 0 ) x+(-x_0) x+(x0),那么 − x 0 -x_0 x0就是上图由 x 0 x_0 x0出发指向原点的那个向量。根据三角形法则,首尾相连,指向末向量。我们分别将 − x 0 -x_0 x0的首与其他向量的尾相连得到对应新点的位置:

IMG_E2D549B9E9C8-1

这样我们得到了五个新点,如果我们取 C C C内所有的点,是不是就形成了一条直线,并且是经过原点的。

IMG_4C997C1F6058-1

如上图所示,我们得到了经过原点的直线 V V V(抱歉,没画好)。是不是就是让 C C C相对 x 0 x_0 x0进行了平移,移到了经过原点的位置。这里任取 C C C内一点进行相对移动都是一样的。

我们称 V V V为与 C C C相关的子空间。

这里注意 C C C一定要是仿射集,得到的 V V V才能是子空间,子空间一定是经过原点的,子空间关于加法和数乘是封闭的。

V V V也是一个仿射集,并且从 V V V中任取两点 x 1 , x 2 x_1,x_2 x1,x2都满足
α x 1 + β x 2 ∈ V , α , β ∈ R (8) \alpha x_1 +\beta x_2 \in V,\quad \alpha,\beta \in R \tag 8 αx1+βx2V,α,βR(8)
我们刚才通过几何画图来证明了这一点,下面我们通过定义来证明。

∀    v 1 , v 2 ∈ V \forall \,\, v_1,v_2 \in V v1,v2V ∀    α , β ∈ R ⇒ α v 1 + β v 2 ∈ V \forall \,\, \alpha,\beta \in R \Rightarrow \alpha v_1 + \beta v_2 \in V α,βRαv1+βv2V

即证明 α v 1 + β v 2 + x 0 ∈ C \alpha v_1 + \beta v_2 + x_0 \in C αv1+βv2+x0C
α v 1 + β v 2 + x 0 = α ( v 1 + x 0 ) + β ( v 2 + x 0 ) + ( 1 − α − β ) x 0 ∈ C \begin{aligned} & \alpha v_1 + \beta v_2 + x_0 \\ &= \alpha(v_1+x_0) + \beta(v_2 + x_0) + (1-\alpha -\beta)x_0 \in C \end{aligned} αv1+βv2+x0=α(v1+x0)+β(v2+x0)+(1αβ)x0C
证毕。 由仿射集第二个定义, v 1 + x 0 ∈ C , v 2 + x 0 ∈ C , x 0 ∈ C v_1+x_0 \in C,v_2+x_0 \in C,x_0 \in C v1+x0C,v2+x0C,x0C,这三个点都属于 C C C,且前面的系数相加为 1 1 1,因此得到组合的新点也是属于 C C C

经过这样一个变换( C − x 0 C-x_0 Cx0),我们可以由性质一般(要满足 θ 1 + ⋯ + θ k = 1 \theta_1+\cdots+\theta_k=1 θ1++θk=1)的仿射集变成一个性质更好的仿射集 V V V

例 线性方程组的解集是仿射集

线性方程组的解 C = { x ∣ A x = b } C=\{x|Ax=b\} C={xAx=b},其中 A ∈ R m × n , b ∈ R m , x ∈ R n A \in R^{m \times n}, b \in R^m ,x \in R^n ARm×n,bRm,xRn

x 1 , x 2 ∈ C x_1,x_2 \in C x1,x2C,满足 A x 1 = b , A x 2 = b Ax_1=b,Ax_2=b Ax1=b,Ax2=b,则对于任意 θ ∈ R \theta \in R θR,有
A ( θ x 1 + ( 1 − θ ) x 2 ) = θ A x 1 + ( 1 − θ ) A x 2 = θ b + ( 1 − θ ) b = b (9) \begin{aligned} A(\theta x_1 + (1-\theta)x_2) &= \theta Ax_1 + (1-\theta)Ax_2 \\ &= \theta b + (1-\theta)b \\ &= b \end{aligned} \tag 9 A(θx1+(1θ)x2)=θAx1+(1θ)Ax2=θb+(1θ)b=b(9)
即我们证明了 A ( θ x 1 + ( 1 − θ ) x 2 ) = b A(\theta x_1 + (1-\theta)x_2)=b A(θx1+(1θ)x2)=b,即 θ x 1 + ( 1 − θ ) x 2 ∈ C \theta x_1 + (1-\theta)x_2 \in C θx1+(1θ)x2C

表明任意的仿射组合 θ x 1 + ( 1 − θ ) x 2 \theta x_1 + (1-\theta)x_2 θx1+(1θ)x2也在 C C C中,反之任意仿射集合可以表示为一个线性方程组的解集。

我们知道任何一个仿射集都可以构造出与它相关的子空间的,那么上例中这样一个仿射集与它相关的子空间是怎样的呢?

我们按照子空间的定义

我们看集合 V = { x − x 0 ∣ x ∈ C } V =\{x -x_0|x \in C\} V={xx0xC}是什么
V = { x − x 0 ∣ x ∈ C } = { x − x 0 ∣ A x = b } , A x 0 = b = { x − x 0 ∣ A ( x − x 0 ) = 0 } = { y ∣ A y = 0 } (10) \begin{aligned} V &=\{x-x_0|x \in C\} \\ &= \{x-x_0|Ax=b\},Ax_0=b \\ &= \{x-x_0|A(x-x_0)=0\}\\ &= \{y|Ay=0\} \end{aligned} \tag {10} V={xx0xC}={xx0Ax=b},Ax0=b={xx0A(xx0)=0}={yAy=0}(10)
我们最后一步把 x − x 0 x-x_0 xx0用新的变量 y y y表示,得到满足 A y = 0 Ay=0 Ay=0 y y y的集合。

这个集合是与仿射集 C = { x ∣ A x = b } C=\{x|Ax=b\} C={xAx=b}相关的子空间,也是 A A A的零空间。

仿射包

如果任意给定一个集合 C C C,可能不是仿射集,有没有办法在 C C C上面构造出来一个尽可能小的仿射集。

由集合 C C C中任取 k k k个点的所有仿射组合组成的集合为 C C C仿射包(aff C)
aff C = { θ 1 x 1 + ⋯ + θ k x k ∣ x 1 , ⋯   , x k ∈ C ,    θ 1 + ⋯ θ k = 1 } (11) \text{aff C}=\{ \theta_1x_1+\cdots + \theta_kx_k|x_1,\cdots,x_k \in C,\,\, \theta_1+\cdots \theta_k=1 \} \tag{11} aff C={θ1x1++θkxkx1,,xkC,θ1+θk=1}(11)
我们从一个最简单的例子来理解这个定义。

IMG_7ED26F90F6F4-1

我们看二维空间上的一个集合,它只包含如上两点 x 1 , x 2 x_1,x_2 x1,x2。显然它不是仿射集。

那它的仿射包是什么?

对集合中这两个点做仿射组合,我们就得到了连接这两个点的直线。

IMG_F6738CCEDB11-1

显然,得到的集合(直线)就是从集合( x 1 , x 2 x_1,x_2 x1,x2)中所构造出来的仿射包。

IMG_3E5D5031A222-1

如果再添加一个点 x 3 x_3 x3,考虑由 x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3所构成的集合,那它的仿射包是什么?

包含这三个点的任何组合实际上构成了平面。所以包含这三个点的最小仿射集就是二维平面。

如果 C C C本身就是仿射集,那么它的仿射包就是其本身。

凸集

集合 C C C凸集(Convex Set),当任意两点之间的线段仍然在 C C C内。

即对于任意 x 1 , x 2 ∈ C x_1,x_2 \in C x1,x2C和满足 0 ≤ θ ≤ 1 0\leq \theta \leq 1 0θ1 θ \theta θ都有
θ x 1 + ( 1 − θ ) x 2 ∈ C (12) \theta x_1 + (1-\theta)x_2 \in C \tag{12} θx1+(1θ)x2C(12)
这就是为什么在前面先介绍了直线和线段的定义。

从这个定义中我们可以发现仿射集一定是凸集。因为如果连接两点的直线已经在集合内了,那么连接两点的线段一定在集合内。

之前我们有仿射组合,相应的就会有凸组合。

我们称点 θ 1 x 1 + ⋯ + θ k x k \theta_1x_1 + \cdots+\theta_kx_k θ1x1++θkxk x 1 , ⋯   , x k x_1,\cdots,x_k x1,,xk的一个凸组合,其中 θ 1 + ⋯ + θ k = 1 \theta_1+\cdots+\theta_k=1 θ1++θk=1,且 θ 1 , ⋯   , θ k ∈ [ 0 , 1 ] \theta_1,\cdots,\theta_k \in [0,1] θ1,,θk[0,1]

公式 ( 12 ) (12) (12)是凸集的第一个定义,与仿射集类似,我们也可以扩充一下。

集合 C C C为凸集等价于集合中任意元素的凸组合也在 C C C内。

凸包

我们称集合 C C C(可能不是凸集)中所有点的凸组合的集合为其凸包(conv C)
conv C = { θ 1 x 1 + ⋯ + θ k x k ∣ x i ∈ C ,    θ i ≥ 0 ,    i = 1 , ⋯   , k ,    θ 1 + ⋯ + θ k = 1 } \text{conv C} =\{ \theta_1x_1 + \cdots+\theta_kx_k|x_i \in C,\,\, \theta_i \geq 0,\,\,i=1,\cdots,k,\,\, \theta_1+\cdots+\theta_k=1 \} conv C={θ1x1++θkxkxiC,θi0,i=1,,k,θ1++θk=1}
凸包总是凸的,它是包含 C C C的最小的凸集。

我们来画几个凸来看下什么是凸集,什么是凸包。

IMG_A22D2C5F1813-1

一个仅包含边的六边形是否为凸集?显然不是。因为很有肯能选择到两个点形成的线段不在集合内。

IMG_9F1363C6FA4D-1

那由六边形所圈出来的区域(包含边)所构成的集合是凸集吗?此时它就是凸集,因为任意连接集合内两个点的线段也在集合内。

IMG_4DF2AD94BD71-1

显然,上图这样的集合也不是凸集,哪怕中间是填充的。

这些集合或者是凸集,或者不是凸集,我们都可以在它们的基础上构建出最小的凸集——凸包。

IMG_A22D2C5F1813-1

填充上图六边形所圈出来的范围就是它的凸包。如下图所示:

IMG_9F1363C6FA4D-1

那下面这个集合呢?

IMG_4DF2AD94BD71-1

它的凸包是什么?首先我们要填充它圈出来的区域,同时要用最小的代价补平它凹陷的区域:

IMG_AC38F8B79521-1

通过黑线填充了它的区域,通过蓝线补平了它凹陷的部分就得到了它构成的凸包。

上面看到的都是由连续的点所构成的集合,下面来看下离散点所构成的集合怎么构建凸包。

IMG_41B08E1A07CD-1

上面这是一个由离散点构成的集合,它的凸包不难想象就是连接边缘点所圈出来的区域:

IMG_77DA00952E1B-1

如果集合 C C C是**锥(Conv)**等价于对于任意 x ∈ C x \in C xC θ ≥ 0 \theta \geq 0 θ0都有 θ x ∈ C \theta x \in C θxC

C C C是**凸锥(Convex cone)**等价于对于任意 x 1 , x 2 ∈ C x_1,x_2 \in C x1,x2C θ 1 , θ 2 ≥ 0 \theta_1,\theta_2 \geq 0 θ1,θ20都有 θ 1 x 1 + θ 2 x 2 ∈ C \theta_1x_1 + \theta_2x_2 \in C θ1x1+θ2x2C

我们画几个图来理解。

IMG_2132B19692C1-1

上图在二维空间中经过原点的三条射线,它们所构成的集合是否为锥?是的,是一个锥。这和我们想象的锥不太一样,我们能想象的锥是一个冰激凌的形状,但它确实满足锥的定义。

IMG_54D061A9FF87-1

那么上图中Y形集合是否为锥呢?不是的,因为它们交叉点不在原点上,没法满足 θ x ∈ C \theta x \in C θxC的性质。

IMG_748EDCD071E2-1

上图这样一个像冰激凌的形状所构成的集合是否为锥?是的,它实际上是由若干组连在一起的射线所构成的。且它们的起点都是原点。

同时它也是一个凸锥,因为我们在该集合中任取两点所形成的新点(平行四边形法则)一定在集合内。

凸锥包

具有 θ 1 x 1 + ⋯ + θ k x k ,    θ 1 , ⋯   , θ k ≥ 0 \theta_1 x_1 +\cdots + \theta_k x_k,\,\, \theta_1,\cdots,\theta_k \geq 0 θ1x1++θkxk,θ1,,θk0形式的点称为 x 1 , ⋯   , x k x_1,\cdots,x_k x1,,xk凸锥组合.

集合 C C C凸锥包 C C C中元素的所有凸锥组合的集合,即
{ θ 1 x 1 + ⋯ + θ k x k ∣ x i ∈ C ,    θ i ≥ 0 ,    i = 1 , ⋯   , k } \{\theta_1x_1+\cdots+\theta_k x_k|x_i \in C, \,\, \theta_i\geq 0,\,\, i=1,\cdots,k \} {θ1x1++θkxkxiC,θi0,i=1,,k}
它是包含 C C C的最小凸锥。

image-20221117230628712

比如上图中的散点图构成的集合,它的凸锥包就是经过原点(上图 0 0 0位置)包含这些点的最小“冰激凌”。如上图所示。

image-20221117230853435

上图这样一个不规整形状的集合所形成的凸锥包。

IMG_B5DF0289A5CC-1

上图由这两个点所构成的集合,已知这两个点的连线经过原点,那么该集合的凸锥包是怎样的。

IMG_D724C71C87A1-1

由原点出发,连接这两点的射线就是它的凸锥包。

总结

我们比较下仿射组合、凸组合、凸锥组合的定义。

对于任意 x 1 , ⋯   , x k ∈ C x_1,\cdots,x_k \in C x1,,xkC,点 θ 1 x 1 + ⋯ + θ k x k \theta_1 x_1 + \cdots+\theta_k x_k θ1x1++θkxk的组合为

仿射组合

∀ θ 1 , ⋯   , θ k , θ 1 + ⋯ + θ k = 1 \forall \theta_1,\cdots,\theta_k,\quad \theta_1+\cdots+\theta_k=1 θ1,,θk,θ1++θk=1

凸组合

∀ θ 1 , ⋯   , θ k , θ 1 + ⋯ + θ k = 1 ,    θ 1 , ⋯   , θ k ∈ [ 0 , 1 ] \forall \theta_1,\cdots,\theta_k,\quad \theta_1+\cdots+\theta_k=1,\,\, \theta_1,\cdots,\theta_k \in [0,1] θ1,,θk,θ1++θk=1,θ1,,θk[0,1]

凸锥组合

∀ θ 1 , ⋯   , θ k , θ 1 , ⋯   , θ k ≥ 0 \forall \theta_1,\cdots,\theta_k,\quad \theta_1,\cdots,\theta_k \geq 0 θ1,,θk,θ1,,θk0

接着比较下仿射集、凸集合凸锥的关系。

我们知道任意仿射集一定是凸的,因为仿射组合在集合内,凸组合一定在集合内。

另外凸锥也一定是凸的,因为只要满足了凸锥组合的定义,也一定能满足(包含)凸组合的定义。

我们之前引入这些定义的时候,都考虑了至少两个不同的点。那如果只有一个点的集合 C = { x } C=\{x\} C={x}是仿射集、凸集、凸锥吗?

我们扩充以下上面的定义,即允许这两个点重合在一个点上。

那么它的仿射组合 θ 1 x + θ 2 x = x \theta_1x + \theta_2 x = x θ1x+θ2x=x,那么新构成的这个点也在 C C C内,所以一个点构成的集合仍然是一个仿射集。那么它一定也是一个凸集。

那任意的一个点它是凸锥吗?

显然,只有这个点在原点上它才是凸锥。

那如果一个集合是空集,它是仿射集吗?空集一定是仿射集,因为连接空集的直线是不存在的,不存在存在于空集之中,所以它是仿射集。凸组合和凸锥组合也都不存在,所以空集同时是仿射集、凸集、凸锥。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yjw123456/article/details/128010906

凸优化学习笔记(1)——凸集-爱代码爱编程

笔记是根据《Convex Optimization》写的,序号对应章。 2 凸集 2.1 凸集(convex sets)   如果在集合 C C中的任意两点满足: θx1+(1−θ)x2∈Cθx_1+

抄书——最优化理论与方法(6)——凸集的分离和支撑_田神的博客-爱代码爱编程

以下内容主要抄自抄袁亚湘的《最优化理论与方法》的 1.3.3 凸集的分离和支撑 凸集的分离和支撑是研究最优性条件的重要工具。我们首先讨论闭凸集外一点与闭凸集的极小距离。 定理 1.3.17 设

凸优化——凸集与凸函数-爱代码爱编程

一、数学规划   从一个可行解的集合中,寻找出最优的元素,称为数学规划,又名优化。可以写为

最优化技术——线性规划-爱代码爱编程

最优化技术——线性规划 线性规划基本概念 线性规划问题就是在一组线性约束条件下,求解目标函数最优解的问题 标准形式 线性规划问题的标准形式: 目标函数求最大值所有约束条件均由等式表示每个约束条件右端常数常为非负值所有决策变量为非负值改造方法 所有的情况与改造方法 目标函数求最小值则应该改为求最大值: 方法——添加负号:

最优化问题——线性规划(一)-爱代码爱编程

最优化问题——线性规划(一) 1、 “凸”概念 在介绍线性规划之前,我们先来回顾一下在线性代数中的“凸”的概念,这些概念在我们以后的求解过程中,会提供很多的帮助。 1.1 基本概念 凸组合: 点 x

最优化问题——线性规划(二)-爱代码爱编程

最优化问题——线性规划(二) 在之前的文章最优化问题——线性规划(一)中,我们简单的介绍了线性规划问题的引入,基本形式和图解法求解。接下来,我们开始讲述线性规划问题的一般求解过程。 1、线性规划中的一些基本概念 满足所有的约束条件的解称为可行解,所有的可行解组成的集合称为可行域。 这里,我们对线性规划的标准型进行一些变换,为了更好的理解上面的

最优化理论基础与方法学习笔记——凸集与凸函数以及手写定理证明-爱代码爱编程

文章目录 凸集的定义凸集的几何意义有关凸集的定理定理1.4.2内点、边界点和闭包的定义定义1.4.3 超平面的定义定理1.4.3 投影定理定理1.4.4 点与凸集的分离定理定理1.4.5 支撑超平面定理定义1.4.4 凸函数的定义定义1.4.5 水平集定理1.4.6 凸函数的水平集还是凸集定理1.4.7 函数是凸函数的充要条件定理1.4.8 凸

最优化——线性规划总结1(线性规划标准型,规范型,顶点)-爱代码爱编程

文章目录 线性规划的形式标准型规范型线性规划的求解思路前提条件主要思路怎么搞一些概念线性规划标准形式的基本定理 线性规划的形式 标准型 规范型 线性规划的求解思路 前提条件 线性规划:凸优化(凸集上的凸函数的优化) 线性规划的可行集是凸集,优化函数是凸函数(仿射函数嘛) 总有顶点是最优解,所有顶点组成的集合总是有限集,所以

最优化学习笔记——第三章-爱代码爱编程

第三章——非线性规划的数学模型 这里写目录标题 第三章——非线性规划的数学模型前言一、 数学模型二、 直观理解三、无约束问题的最优性条件四、 凸的无约束问题的最优性条件五、基本思路最优化方法通常采用迭代方法(iterative)求解最优化方法的基本结构,给定初始点x^(0)下降方向:计算的终止条件(Termination criterion)与收

凸优化理论基础2——凸集和锥_凸包是最小的凸集为什么-爱代码爱编程

  🍊作者简介:秃头小苏,致力于用最通俗的语言描述问题 🍊往期回顾:凸优化理论基础1–仿射集 🍊近期目标:拥有5000粉丝 🍊支持小苏:点赞👍🏼、收藏⭐、留言📩 文章目录 凸优化理论基础2

凸优化理论基础3——凸集和凸锥重要例子_半空间凸集证明-爱代码爱编程

  🍊作者简介:秃头小苏,致力于用最通俗的语言描述问题 🍊往期回顾:凸优化理论基础1–仿射集    凸优化理论基础2——凸集和锥 🍊近期目标:拥有5000粉丝 🍊支持小苏:点赞👍🏼、收藏⭐、留言📩

最优化理论——(二)凸性1 凸集_数据集凸性 是什么-爱代码爱编程

文章目录 1.凸集1.1凸集的概念及性质1.1.1点的几种组合1.1.2凸集的定义1.1.3常见的凸集1.1.4凸集的性质1.1.5锥和凸锥 1.2凸集的分离定理1.2.1定义及定理1.2.3凸集分离定