凸优化2：凸集

发布时间：2024-11-25 10:58

利用修容产品改善脸型，凸显优点 #生活技巧# #创意技巧# #化妆打扮建议#

文章目录什么是凸集直线和线段直线线段仿射集仿射组合子空间仿射包仿射维度凸集凸组合凸包凸锥锥组合锥包凸集的一些例子超平面半空间Euclid球椭球范数球范数锥

什么是凸集

直线和线段

直线

R n R^n Rn空间两个点 x 1 ≠ x 2 x_1\neq x_2 x1=x2,穿越两点的直线：

y = θ x 1 + ( 1 − θ ) x 2 y=\theta x_1 + (1-\theta) x_2 y=θx1+(1−θ)x2

另一种形式：

y = x 2 + θ ( x 1 − x 2 ) y= x_2 + \theta (x_1 - x_2) y=x2+θ(x1−x2)

可以理解为，以 x 2 x_2 x2为参考点，沿着从 x 2 x_2 x2指向 x 1 x_1 x1的向量 v ⃗ = ( x 1 − x 2 ) \vec v=(x_1 - x_2) v

=(x1−x2)，移动 θ \theta θ倍长度后到达的点 y y y。当 θ = 1 \theta = 1 θ=1时，到达点 x 1 x_1 x1，即 y = x 1 y=x_1 y=x1。

线段

如果限定参数 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，则构成 x 1 , x 2 x_1, x_2 x1,x2两点间线段。

仿射集

对于两个点：

如果通过集合 C ⊆ R n C\sube R^n C⊆Rn中任意两个不同点的直线仍在集合 C C C中，则称集合 C C C是仿射的。

或者说， ∀ x 1 , x 2 ∈ C , θ ∈ R \forall x_1, x_2 \in C, \theta \in R ∀x1,x2∈C,θ∈R ，有 y = θ x 1 + ( 1 − θ ) x 2 ∈ C y=\theta x_1 + (1-\theta) x_2 \in C y=θx1+(1−θ)x2∈C，则集合 C C C是仿射集。

扩展到多个点：

对于 C C C中的 k k k个点 ∀ x 1 , ⋯ , x k ∈ C \forall x_1, \cdots, x_k \in C ∀x1,⋯,xk∈C, 以及 R R R中的系数 ∑ i = 0 k θ i = 1 \sum_{i=0}^{k}\theta_i=1 ∑i=0kθi=1，如果有 y = ∑ i = 0 k θ i x i ∈ C y=\sum_{i=0}^{k} \theta_i x_i \in C y=∑i=0kθixi∈C，则集合 C C C是仿射的。

仿射组合

y = ∑ i = 0 k θ i x i y=\sum_{i=0}^{k} \theta_i x_i y=∑i=0kθixi称为点 x 1 , ⋯ , x k x_1, \cdots, x_k x1,⋯,xk的仿射组合，其中 ∑ i = 0 k θ = 1 \sum_{i=0}^k\theta=1 ∑i=0kθ=1。

子空间

仿射集合 C C C中包含 0 \boldsymbol{0} 0元素 ⟺ \iff ⟺ 集合 C C C关于加法和数乘封闭 ⟺ \iff ⟺ 集合 C C C是一个子空间

仿射包

集合 C C C中的点的所有仿射组合，组成 C C C的仿射包。即包含 C C C的最小仿射组合。
a f f C = { ∑ i = 1 k θ i x i ∣ x i ∈ C , ∑ i = 0 k θ = 1 } \bold{aff}C = \Big\lbrace \sum_{i=1}^{k} \theta_i x_i | x_i \in C, \sum_{i=0}^k\theta=1 \Big\rbrace affC={i=1∑kθixi∣xi∈C,i=0∑kθ=1}

仿射维度

定义集合 C C C的仿射维度为其仿射包的维度。此处需要区别于自由度。

例如，定义集合 C C C为 R 2 R^2 R2上的单位圆 C = { x ∈ R 2 ∣ x 1 2 + x 2 2 = 1 } C=\{x\in R^2 | x_1^2 +x_2^2 = 1 \} C={x∈R2∣x12+x22=1}，其仿射包为整个 R 2 R^2 R2空间，所以仿射维度为2。但其自由度为1。

凸集

如果集合 C C C中任意两点间的线段仍在 C C C中，则 C C C为凸集。

凸组合

∑ i = 0 k θ i x i \sum_{i=0}^k \theta_i x_i ∑i=0kθixi为点 x 1 , ⋯ , x k x_1, \cdots, x_k x1,⋯,xk的一个凸组合，其中 ∑ i = 0 k θ i = 1 , θ i ≥ 0 \sum_{i=0}^k \theta _i = 1, \theta _i \ge 0 ∑i=0kθi=1,θi≥0;

集合是凸集 ⟺ \iff ⟺ 包含其所有元素的所有凸组合；

对比仿射集：

仿射集：通过集合 C ⊆ R n C\sube R^n C⊆Rn中任意两个不同点的直线仍在集合 C C C中；仿射集也是凸集，但凸组合的前提条件更加严格，即要求 θ i ≥ 0 \theta _i \ge 0 θi≥0。仿射集 ⊆ \sube ⊆凸集，仿射集 ⇒ \Rightarrow ⇒凸集，仿射集 ⇍ \nLeftarrow ⇍凸集；凸包

集合 C C C（不一定凸）中所有点的凸组合的集合，为其凸包。

c o n v C = { ∑ i = 0 k θ i x i ∣ x i ∈ C , θ i ≥ 0 , ∑ i = 0 k θ i = 1 } \bold{conv}C = \Big\lbrace \sum_{i=0}^k \theta_i x_i |x_i \in C, \theta _i \ge 0, \sum_{i=0}^k \theta _i = 1 \Big\rbrace convC={i=0∑kθixi∣xi∈C,θi≥0,i=0∑kθi=1}

凸包总是凸的，是包含 C C C的最小凸集。

可以理解为，集合 C C C的凸包为其最小的凸包络面及内部区域。

凸锥

如果对于任意 x ∈ C , θ ≥ 0 x\in C, \theta \ge 0 x∈C,θ≥0, 都有 θ x ∈ C \theta x \in C θx∈C, 则称集合 C C C是锥或非负齐次。
同时，如果 C C C也是凸的，则称 C C C为凸锥。

例如， R 2 R^2 R2上集合 C C C的凸锥为包含 C C C的最小扇形。

锥组合

∑ i = 0 k θ i x i \sum_{i=0}^k \theta_i x_i ∑i=0kθixi为 x 1 , ⋯ , x k x_1,\cdots, x_k x1,⋯,xk 的锥组合（或非负线性组合)，其中 θ i ≥ 0 \theta _i \ge 0 θi≥0;

集合是凸锥 ⟺ \iff ⟺ 包含其所有元素的所有锥组合；

锥包

是 C C C中所有元素的所有锥组合的集合；也是包含 C C C的最小凸锥；

{ ∑ i = 0 k θ i x i ∣ x i ∈ C , θ i ≥ 0 } \Big\lbrace \sum_{i=0}^k \theta_i x_i |x_i \in C, \theta _i \ge 0\Big\rbrace {i=0∑kθixi∣xi∈C,θi≥0}

对比凸包

锥包不要求 ∑ i = 0 k θ i = 1 \sum_{i=0}^k \theta _i = 1 ∑i=0kθi=1。

凸集的一些例子

超平面

{ x ∣ a T x = b } \{ x | a^T x = b\} {x∣aTx=b}

另一种形式，对于超平面一点 x 0 x_0 x0:
{ x ∣ a T ( x − x 0 ) = 0 } \{ x | a^T (x-x_0) = 0\} {x∣aT(x−x0)=0}

超平面是凸的，而且是仿射的。

半空间

闭的半空间：
{ x ∣ a T x ≤ b } \{ x | a^T x \le b\} {x∣aTx≤b}

另一种形式，对于分界面上一点 x 0 x_0 x0:
{ x ∣ a T ( x − x 0 ) ≤ 0 } \{ x | a^T (x-x_0) \le 0\} {x∣aT(x−x0)≤0}
半空间是凸的，但不是仿射的。

Euclid球

球心 x c x_c xc, 半径 r r r:

B ( x c , r ) = { x ∣ ∥ x − x c ∥ 2 ≤ r } = { x ∣ ( x − x c ) T ( x − x c ) ≤ r 2 } B(xc,r)={x|‖ B(xc,r)={x∣∣∥x−xc∥2≤r}={x∣∣(x−xc)T(x−xc)≤r2}

另一种表达形式：

B ( x c , r ) = { x c + r u ∣ ∥ u ∥ 2 ≤ 1 } B(x_c, r) = \{ x_c + ru \big| \| u \| _2 \le 1 \} B(xc,r)={xc+ru∣∣∥u∥2≤1}

椭球

E = { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ r 2 } \mathcal{E} =\{ x \big| (x-x_c)^TP^{-1}(x-x_c) \le r^2 \} E={x∣∣(x−xc)TP−1(x−xc)≤r2}
其中， P P P对称正定，即特征值 λ i ≥ 0 \lambda_i\ge 0 λi≥0。椭球 E \mathcal{E} E半长轴: λ i \sqrt{\lambda_i} λi

另一种表达形式：

B ( x c , r ) = { x c + A u ∣ ∥ u ∥ 2 ≤ 1 } B(x_c, r) = \{ x_c + Au \big| \| u \| _2 \le 1 \} B(xc,r)={xc+Au∣∣∥u∥2≤1}

A A A是非奇异方阵（普通情况）； A A A奇异时，椭球退化。例如 R 3 R_3 R3中的椭球退化为圆柱。范数球

Euclid球中使用的2范数，替换为其他范数。则对于球心 x c x_c xc, 半径 r r r，范数球:

B ( x c , r ) = { x ∣ ∥ x − x c ∥ ≤ r } = { x c + r u ∣ ∥ u ∥ ≤ 1 } B(xc,r)={x∣∣∥x−xc∥≤r}={xc+ru∣∣∥u∥≤1}

范数锥

对于 x ∈ R n x \in R^n x∈Rn，范数锥：

C = { ( x , t ) ∣ ∥ x ∥ ≤ t } ∈ R n + 1 C = \{(x,t) \big| \|x\| \le t\} \in R^{n+1} C={(x,t)∣∣∥x∥≤t}∈Rn+1

网址：凸优化2：凸集 https://www.yuejiaxmz.com/news/view/256914

上一篇：空间利用与功能分区优化

下一篇：优化新居空间利用效果–光波网

凸优化2：凸集

什么是凸集

直线和线段

仿射集

凸集

凸集的一些例子

相关内容

随便看看

最新动态分享

热点动态分享

专题

推荐动态分享