文章目录
前言
x
1
,
x
2
∈
R
n
,
θ
∈
R
\mathrm{x}_1,\mathrm{x}_2\in R^n,\quad\theta\in R
x1,x2∈Rn,θ∈R
则过点
x
1
,
x
2
\mathrm{x}_1,\mathrm{x}_2
x1,x2的直线可表示为
y
=
θ
x
1
+
(
1
−
θ
)
x
2
=
x
2
+
θ
(
x
1
−
x
2
)
\mathrm{y}=\theta \mathrm{x}_1+(1-\theta)\mathrm{x}_2=\mathrm{x}_2+\theta(\mathrm{x}_1-\mathrm{x}_2)
y=θx1+(1−θ)x2=x2+θ(x1−x2)1；
点
x
1
,
x
2
\mathrm{x}_1,\mathrm{x}_2
x1,x2之间的线段可表示为
y
=
θ
x
1
+
(
1
−
θ
)
x
2
,
θ
∈
[
0
,
1
]
\mathrm{y}=\theta \mathrm{x}_1+(1-\theta)\mathrm{x}_2,\;\theta\in[0,1]
y=θx1+(1−θ)x2,θ∈[0,1]。
仿射集、凸集、凸锥
| 集 | 组合 | 包 | |
|---|---|---|---|
| 仿射 | ∀ x 1 , . . . , x k ∈ C , θ 1 + . . . + θ k = 1 ， 有 θ 1 x 1 + . . . + θ k x k ∈ C \forall x_1,...,x_k\in C,\theta_1+...+\theta_k=1，有\\\theta_1x_1+...+\theta_kx_k\in C ∀x1,...,xk∈C,θ1+...+θk=1，有θ1x1+...+θkxk∈C | θ 1 x 1 + . . . + θ k x k \theta_1x_1+...+\theta_kx_k θ1x1+...+θkxk | { θ 1 x 1 + . . . + θ k x k ∣ x 1 , . . . , x k ∈ C , θ 1 + . . . + θ k = 1 } \{\theta_1x_1+...+\theta_kx_k\vert x_1,...,x_k\in C,\\\theta_1+...+\theta_k=1\} {θ1x1+...+θkxk∣x1,...,xk∈C,θ1+...+θk=1} |
| 凸 | ∀ x 1 , . . . , x k ∈ C , θ 1 + . . . + θ k = 1 , θ 1 , . . . , θ k ≥ 0 ， 有 θ 1 x 1 + . . . + θ k x k ∈ C \forall x_1,...,x_k\in C,\theta_1+...+\theta_k=1,\theta_1,...,\theta_k\ge0，有\\\theta_1x_1+...+\theta_kx_k\in C ∀x1,...,xk∈C,θ1+...+θk=1,θ1,...,θk≥0，有θ1x1+...+θkxk∈C | θ 1 x 1 + . . . + θ k x k \theta_1x_1+...+\theta_kx_k θ1x1+...+θkxk | { θ 1 x 1 + . . . + θ k x k ∣ x 1 , . . . , x k ∈ C , x 1 + . . . + x k = 1 , θ 1 , . . . , θ k ≥ 0 } \{\theta_1x_1+...+\theta_kx_k\vert x_1,...,x_k\in C,\\x_1+...+x_k=1,\theta_1,...,\theta_k\ge0\} {θ1x1+...+θkxk∣x1,...,xk∈C,x1+...+xk=1,θ1,...,θk≥0} |
| 凸锥 | ∀ x 1 , . . . , x k ∈ C , θ 1 , . . . , θ k ≥ 0 ， 有 θ 1 x 1 + . . . + θ k x k ∈ C \forall x_1,...,x_k\in C,\theta_1,...,\theta_k\ge0，有\\\theta_1x_ 1+...+\theta_kx_k\in C ∀x1,...,xk∈C,θ1,...,θk≥0，有θ1x1+...+θkxk∈C | θ 1 x 1 + . . . + θ k x k \theta_1x_1+...+\theta_kx_k θ1x1+...+θkxk | { θ 1 x 1 + . . . + θ k x k ∣ x 1 , . . . , x k ∈ C , θ 1 , . . . , θ k ≥ 0 } \{\theta_1x_1+...+\theta_kx_k\vert x_1,...,x_k\in C,\\\theta_1,...,\theta_k\ge0\} {θ1x1+...+θkxk∣x1,...,xk∈C,θ1,...,θk≥0} |
仿射集
定义
仿射集：集合c是仿射集
⟺
\Longleftrightarrow
⟺ 若
∀
x
1
,
x
2
∈
c
\forall\;\mathrm{x}_1,\mathrm{x}_2\in c
∀x1,x2∈c，则连接
x
1
\mathrm{x}_1
x1与
x
2
\mathrm{x}_2
x2的直线也在集合c内。
例如：
- R 2 R^2 R2是一个仿射集；
- R 2 R^2 R2内的一条直线是一个仿射集；
- 但
R
2
R^2
R2内的一条线段 不是 一个仿射集。
数学定义：c是一个仿射集
⟺
\Longleftrightarrow
⟺ 若
∀
x
1
,
.
.
.
,
x
k
∈
c
，
θ
1
,
.
.
.
,
θ
k
∈
R
，
θ
1
+
.
.
.
+
θ
k
=
1
\forall\;\mathrm{x}_1,...,\mathrm{x}_k\in c，\theta_1,...,\theta_k\in R，\theta_1+...+\theta_k=1
∀x1,...,xk∈c，θ1,...,θk∈R，θ1+...+θk=1，则
θ
1
x
1
+
.
.
.
+
θ
k
x
k
∈
c
\theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k\in c
θ1x1+...+θkxk∈c 2
注：
- 当k=2时，就是上面的定义。
- θ 1 x 1 + . . . + θ k x k \theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k θ1x1+...+θkxk 被称为 仿射组合。
如何从k=2推广到k=3
已知：对于 ∀ x 1 , x 2 ∈ c \forall \mathrm{x}_1,\mathrm{x}_2\in c ∀x1,x2∈c，连接 x 1 , x 2 \mathrm{x}_1,\mathrm{x}_2 x1,x2的直线在c中
欲证：对于 ∀ x 1 , x 2 , x 3 ∈ c , θ 1 , θ 2 , θ 3 ∈ R , θ 1 + θ 2 + θ 3 = 1 \forall \mathrm{x}_1,\mathrm{x}_2,\mathrm{x}_3\in c,\theta_1,\theta_2,\theta_3\in R,\theta_1+\theta_2+\theta_3=1 ∀x1,x2,x3∈c,θ1,θ2,θ3∈R,θ1+θ2+θ3=1，有 θ 1 x 1 + θ 2 x 2 + θ 3 x 3 ∈ c \theta_1\mathrm{x}_1+\theta_2\mathrm{x}_2+\theta_3\mathrm{x}_3\in c θ1x1+θ2x2+θ3x3∈c
证明：
∵ θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ∈ c \because \dfrac{\theta_1}{\theta_1+\theta_2}\mathrm{x}_1+\dfrac{\theta_2}{\theta_1+\theta_2}\mathrm{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 \therefore (\theta_1+\theta_2)( \dfrac{\theta_1}{\theta_1+\theta_2}\mathrm{x}_1+\dfrac{\theta_2}{\theta_1+\theta_2}\mathrm{x}_2)+(1-\theta_1-\theta_2)\mathrm{x}_3\in c ∴(θ1+θ2)(θ1+θ2θ1x1+θ1+θ2θ2x2)+(1−θ1−θ2)x3∈c
∴ θ 1 x 1 + θ 2 x 2 + ( 1 − θ 1 − θ 2 ) x 3 ∈ c \therefore \theta_1\mathrm{x}_1+\theta_2\mathrm{x}_2+(1-\theta_1-\theta_2)\mathrm{x}_3\in c ∴θ1x1+θ2x2+(1−θ1−θ2)x3∈c
即证，且由此可以推论到k=n。
性质
- 对于 ∀ x 1 , x 2 ∈ c , α , β ∈ R \forall \mathrm{x}_1,\mathrm{x}_2\in c,\alpha,\beta\in R ∀x1,x2∈c,α,β∈R，则 α x 1 + β x 2 \alpha\mathrm{x}_1+\beta\mathrm{x}_2 αx1+βx2 不一定 ∈ c \in c ∈c
仿射集的相关子空间
与仿射集c相关的子空间3 V V V： V = c − x 0 = { x − x 0 ∣ x ∈ c } , ∀ x 0 ∈ c V=c-\mathrm{x}_0=\{\mathrm{x}-\mathrm{x}_0|\mathrm{x}\in c\},\forall\mathrm{x}_0\in c V=c−x0={x−x0∣x∈c},∀x0∈c
性质
- 对于 ∀ v 1 , v 2 ∈ V , α , β ∈ R \forall \mathrm{v}_1,\mathrm{v}_2\in V,\alpha,\beta\in R ∀v1,v2∈V,α,β∈R，有 α v 1 + β v 2 ∈ V \alpha \mathrm{v}_1+\beta \mathrm{v}_2\in V αv1+βv2∈V
证明：
⟸ α v 1 + β v 2 + x 0 ∈ c \Longleftarrow \alpha \mathrm{v}_1+\beta \mathrm{v}_2+\mathrm{x}_0\in c ⟸αv1+βv2+x0∈c
⟸ α ( v 1 + x 0 ) + β ( v 2 + x 0 ) + ( 1 − α − β ) x 0 ∈ c \Longleftarrow \alpha(\mathrm{v}_1+\mathrm{x}_0)+\beta(\mathrm{v}_2+\mathrm{x}_0)+(1-\alpha-\beta)\mathrm{x}_0\in c ⟸α(v1+x0)+β(v2+x0)+(1−α−β)x0∈c
- 线性方程组的解集是仿射集。
c = { x ∣ A x = b } , A ∈ R m × n , b ∈ R m , x ∈ R n c=\{\mathrm{x}|A\mathrm{x}=\mathrm{b}\},A\in R^{m\times n},\mathrm{b}\in R^m,\mathrm{x}\in R^n c={x∣Ax=b},A∈Rm×n,b∈Rm,x∈Rn
证明：
由已知， ∀ x 1 , x 2 ∈ c , A x 1 = b , A x 2 = b \forall \mathrm{x}_1,\mathrm{x}_2\in c,A\mathrm{x}_1=\mathrm{b},A\mathrm{x}_2=\mathrm{b} ∀x1,x2∈c,Ax1=b,Ax2=b
则对于 θ ∈ R \theta\in R θ∈R，有 A ( θ x 1 + ( 1 − θ ) x 2 ) = θ A x 1 + ( 1 − θ ) A x 2 = b A(\theta\mathrm{x}_1+(1-\theta)\mathrm{x}_2)=\theta A\mathrm{x}_1+(1-\theta)A\mathrm{x}_2=\mathrm{b} A(θx1+(1−θ)x2)=θAx1+(1−θ)Ax2=b
∴ θ x 1 + ( 1 − θ ) x 2 ∈ c \therefore \theta\mathrm{x}_1+(1-\theta)\mathrm{x}_2\in c ∴θx1+(1−θ)x2∈c
即 集合c 是仿射集。
对于仿射集的相关子空间
v = { x − x 0 ∣ x ∈ c } , ∀ x 0 ∈ c = { x − x 0 ∣ A x = b } , A x 0 = b = { x − x 0 ∣ A ( x − x 0 ) = 0 } = { y ∣ A y = 0 } \begin{aligned}\mathrm{v}&=\{\mathrm{x}-\mathrm{x}_0|\mathrm{x}\in c\},\forall \mathrm{x}_0\in c\\ &=\{\mathrm{x}-\mathrm{x}_0|A\mathrm{x}=\mathrm{b}\},A\mathrm{x}_0=\mathrm{b}\\&=\{\mathrm{x}-\mathrm{x}_0|A(\mathrm{x}-\mathrm{x}_0)=0\}\\&=\{\mathrm{y}|A\mathrm{y}=0\}\end{aligned} v={x−x0∣x∈c},∀x0∈c={x−x0∣Ax=b},Ax0=b={x−x0∣A(x−x0)=0}={y∣Ay=0}
∴ v \therefore \mathrm{v} ∴v是A的零空间4
结论：将仿射集c 平移到原点，就得到了与它相关的子空间。
- 仿射集 一定是 某个线性方程组的解集。
仿射包
任意集合c，构造尽可能小的仿射集
定义
a f f c = { θ 1 x 1 + . . . + θ k x k ∣ ∀ x 1 , . . . , x k ∈ c ， θ 1 , . . . , θ k ∈ R ， θ 1 + . . . + θ k = 1 } aff\;c=\{\theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k|\forall \mathrm{x}_1,...,\mathrm{x}_k\in c，\theta_1,...,\theta_k\in R，\theta_1+...+\theta_k=1\} affc={θ1x1+...+θkxk∣∀x1,...,xk∈c，θ1,...,θk∈R，θ1+...+θk=1}
即包含该集合的最小仿射集。
性质
- 对于空间中任意两点 的仿射包 是经过这两点的直线；
- 对于空间中 三个不在一条直线上的点 的仿射包，是经过这三个点的二维平面；
- 任意一个仿射集 的仿射包 是它本身。
凸集
定义
凸集： 集合c是凸集 ⟺ \Longleftrightarrow ⟺ c上任意两点间的线段 仍在c内。
数学定义： 集合c是凸集
⟺
\Longleftrightarrow
⟺
∀
x
1
,
.
.
.
,
x
k
∈
c
，
θ
1
,
.
.
.
,
θ
k
∈
[
0
,
1
]
，
θ
1
+
.
.
.
+
θ
k
=
1
\forall\mathrm{x}_1,...,\mathrm{x}_k\in c，\theta_1,...,\theta_k\in[0,1]，\theta_1+...+\theta_k=1
∀x1,...,xk∈c，θ1,...,θk∈[0,1]，θ1+...+θk=1，则
θ
1
x
1
+
.
.
.
+
θ
k
x
k
∈
c
\theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k\in c
θ1x1+...+θkxk∈c。
注：
θ
1
x
1
+
.
.
.
+
θ
k
x
k
\theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k
θ1x1+...+θkxk被称为凸组合。
性质
- c为凸集 ⟺ \Longleftrightarrow ⟺ 任意元素的凸组合 ∈ c \in c ∈c
凸包
定义
c o n v c = { θ 1 x 1 + . . . + θ k x k ∣ ∀ x 1 , . . . , x k ∈ c ， θ 1 , . . . , θ k ∈ [ 0 , 1 ] ， θ 1 + . . . + θ k = 1 } conv\;c=\{\theta_1\mathrm{x}_1+...+\theta_k\mathrm{x}_k|\forall \mathrm{x}_1,...,\mathrm{x}_k\in c， \theta_1,...,\theta_k\in[0,1]，\theta_1+...+\theta_k=1\} convc={θ1x1+...+θkxk∣∀x1,...,xk∈c，θ1,...,θk∈[0,1]，θ1+...+θk=1}
即包含该集合的最小凸集。
凸锥
锥
C是锥
⟹
∀
x
∈
C
,
θ
≥
0
\Longrightarrow \forall x\in C, \theta\ge0
⟹∀x∈C,θ≥0 有
θ
x
∈
C
\theta x\in C
θx∈C
凸锥的定义
C是凸锥 ⟹ ∀ x 1 , x 2 ∈ C , θ 1 , θ 2 ≥ 0 \Longrightarrow \forall x_1,x_2\in C, \theta_1, \theta_2\ge0 ⟹∀x1,x2∈C,θ1,θ2≥0 有 θ 1 x 1 + θ 2 x 2 ∈ C \theta_1x_1+\theta_2x_2\in C θ1x1+θ2x2∈C
凸锥组合
θ 1 x 1 + θ 2 x 2 + . . . + θ k x k \theta_1x_1+\theta_2x_2+...+\theta_kx_k θ1x1+θ2x2+...+θkxk，其中 θ 1 , θ 2 , . . . , θ k ≥ 0 \theta_1, \theta_2,...,\theta_k\ge0 θ1,θ2,...,θk≥0
凸锥包
{ θ 1 x 1 + θ 2 x 2 + . . . + θ k x k ∣ ∀ x 1 , x 2 , . . . , x k ∈ c , θ 1 , θ 2 , . . . , θ k ≥ 0 } \{\theta_1x_1+\theta_2x_2+...+\theta_kx_k|\forall x_1,x_2,...,x_k\in c, \theta_1, \theta_2,...,\theta_k\ge0\} {θ1x1+θ2x2+...+θkxk∣∀x1,x2,...,xk∈c,θ1,θ2,...,θk≥0}
即包含该集合的最小凸锥。
几种重要的凸集
- R n R^n Rn空间：也是仿射集、凸锥
- R n R^n Rn空间的子空间5：也是仿射集、凸锥
- 任意直线：是仿射集，过原点的才是凸锥
- 任意线段：当是一个点时，是仿射集、凸锥
- { x 0 + θ v ∣ θ ≥ 0 } , x 0 ∈ R n , θ ∈ R , v ∈ R n \{x_0+\theta v\vert\theta\ge0\}, x_0\in R^n, \theta\in R, v\in R^n {x0+θv∣θ≥0},x0∈Rn,θ∈R,v∈Rn：当 v = 0 v=0 v=0时 是仿射集6；当 x 0 = 0 x_0=0 x0=0时 是凸锥
- 超平面与半空间：超平面是仿射集，过原点的是凸锥；半空间不是仿射集，过原点的是凸锥
- 超平面： { x ∣ a T x = b } , x , a ∈ R n , b ∈ R , a ≠ 0 \{x\vert a^Tx=b\}, x,a\in R^n, b\in R, a\ne0 {x∣aTx=b},x,a∈Rn,b∈R,a=0
-
半空间：
{
x
∣
a
T
x
>
b
}
,
x
,
a
∈
R
n
,
b
∈
R
,
a
≠
0
\{x\vert a^Tx>b\}, x,a\in R^n, b\in R, a\ne0
{x∣aTx>b},x,a∈Rn,b∈R,a=0 或者
{
x
∣
a
T
x
<
b
}
,
x
,
a
∈
R
n
,
b
∈
R
,
a
≠
0
\{x\vert a^Tx<b\}, x,a\in R^n, b\in R, a\ne0
{x∣aTx<b},x,a∈Rn,b∈R,a=0
- 球和椭球：当 x c = 0 , r = 0 x_c=0,r=0 xc=0,r=0时，才是仿射集、凸集
- 球： B ( x c , r ) = { x ∣ ∥ x − x c ∥ 2 ≤ r } B(x_c, r)=\{x|\lVert x-x_c\rVert_2\le r\} B(xc,r)={x∣∥x−xc∥2≤r}，显然 x c x_c xc 表示球心， r r r 表示半径
已知： ∀ x 1 , x 2 ∈ B , ∥ x 1 − x c ∥ 2 ≤ r , ∥ x 2 − x c ∥ 2 ≤ r \forall x_1,x_2\in B,\lVert x_1-x_c\rVert_2\le r,\lVert x_2-x_c\rVert_2\le r ∀x1,x2∈B,∥x1−xc∥2≤r,∥x2−xc∥2≤r
证明：
∀ θ ∈ [ 0 , 1 ] , \forall\theta\in[0,1], ∀θ∈[0,1],
∥ θ x 1 + ( 1 − θ ) x 2 − x c ∥ 2 = ∥ θ ( x 1 − x c ) + ( 1 − θ ) ( x 2 − x c ) ∥ 2 ≤ θ ∥ x 1 − x c ∥ 2 + ( 1 − θ ) ∥ x 2 − x c ∥ 2 ≤ r \begin{aligned}\lVert\theta x_1+(1-\theta)x_2-x_c\rVert_2&=\lVert\theta(x_1-x_c)+(1-\theta)(x_2-x_c)\rVert_2\\&\le\theta\lVert x_1-x_c\rVert_2+(1-\theta)\lVert x_2-x_c\rVert_2\\&\le r\end{aligned} ∥θx1+(1−θ)x2−xc∥2=∥θ(x1−xc)+(1−θ)(x2−xc)∥2≤θ∥x1−xc∥2+(1−θ)∥x2−xc∥2≤r
即证7
-
椭球：
ε
(
x
c
,
P
)
=
{
x
∣
(
x
−
x
c
)
T
P
−
1
(
x
−
x
c
)
≤
1
}
,
x
c
∈
R
n
,
P
∈
S
+
+
n
\varepsilon(x_c,P)=\{x|(x-x_c)^TP^{-1}(x-x_c)\le1\}, x_c\in R^n, P\in S^n_{++}
ε(xc,P)={x∣(x−xc)TP−1(x−xc)≤1},xc∈Rn,P∈S++n8，
P
P
P的奇异值对应椭球的半轴长
- 例如：
ε
=
{
x
∣
x
T
(
4
0
0
1
)
−
1
x
≤
1
}
=
{
(
x
1
,
x
2
)
∣
1
4
x
1
2
+
x
2
2
≤
1
}
\begin{aligned}\varepsilon&=\{x|x^T\begin{pmatrix}4&0\\0&1\end{pmatrix}^{-1}x\le1\}\\&=\{(x_1,x_2)|\frac14x_1^2+x_2^2\le1\}\end{aligned}
ε={x∣xT(4001)−1x≤1}={(x1,x2)∣41x12+x22≤1}
- 例如：
ε
=
{
x
∣
x
T
(
4
0
0
1
)
−
1
x
≤
1
}
=
{
(
x
1
,
x
2
)
∣
1
4
x
1
2
+
x
2
2
≤
1
}
\begin{aligned}\varepsilon&=\{x|x^T\begin{pmatrix}4&0\\0&1\end{pmatrix}^{-1}x\le1\}\\&=\{(x_1,x_2)|\frac14x_1^2+x_2^2\le1\}\end{aligned}
ε={x∣xT(4001)−1x≤1}={(x1,x2)∣41x12+x22≤1}
-
沿着 x 1 − x 2 \mathrm{x}_1-\mathrm{x}_2 x1−x2方向调整参数 θ \theta θ，再加上 x 2 \mathrm{x}_2 x2即可得到直线上一点。 ↩︎
-
类似于线性组合。 ↩︎
-
只有经过原点，才能叫做空间。 ↩︎
-
满足运算封闭性（过原点） ↩︎
-
点既是凸集又是仿射集，原点是凸锥 ↩︎
-
利用三角不等式 ∥ a + b ∥ ≤ ∥ a ∥ + ∥ b ∥ \lVert a+b\rVert\le\lVert a\rVert+\lVert b\rVert ∥a+b∥≤∥a∥+∥b∥ ↩︎
-
n表示矩阵P是n*n的，S表示P是对称矩阵，++表示P是正定的，例如 P = r 2 I n P=r^2I_n P=r2In ↩︎