欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

UA SIE545 优化理论基础1 凸分析3 凸集与凸包

发布时间：2025/4/14 编程问答 39 豆豆
生活随笔 收集整理的这篇文章主要介绍了 UA SIE545 优化理论基础1 凸分析3 凸集与凸包 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

UA SIE545 优化理论基础1 凸分析3 凸集与凸包

  • 基本概念与性质
    • 凸集
    • 凸组合
    • 凸包

基本概念与性质

凸集

考虑数域FFF上的线性空间VVV。

定义一 凸集(convex set)。S⊂VS \subset VS⊂V为凸集，如果∀x1,x2∈S\forall x_1,x_2 \in S∀x1​,x2​∈S, ∀λ∈[0,1]\forall \lambda \in [0,1]∀λ∈[0,1], λx1+(1−λ)x2∈S\lambda x_1+(1-\lambda)x_2 \in Sλx1​+(1−λ)x2​∈S。

定理一 任意个凸集的交是凸集。
证明
考虑指标集III以及一列凸集Si,i∈IS_{i},i \in ISi​,i∈I，
S=⋂i∈ISiS = \bigcap_{i \in I}S_iS=i∈I⋂​Si​

∀x1,x2∈S\forall x_1,x_2 \in S∀x1​,x2​∈S, x1,x2∈Si,∀i∈Ix_1,x_2 \in S_i,\forall i \in Ix1​,x2​∈Si​,∀i∈I, 给定i∈Ii \in Ii∈I，SiS_iSi​是凸集，∀λ∈[0,1]\forall \lambda \in [0,1]∀λ∈[0,1]，λx1+(1−λ)x2∈Si\lambda x_1 +(1-\lambda)x_2 \in S_iλx1​+(1−λ)x2​∈Si​，因此
λx1+(1−λ)x2∈S\lambda x_1 +(1-\lambda)x_2 \in Sλx1​+(1−λ)x2​∈S

例1 欧式空间中的常见凸集：

  • 线性流形；
  • 开半空间(open half space)；
    H={x∈V:(x,b)>β}H =\{x \in V:(x,b)>\beta\}H={x∈V:(x,b)>β}
  • 闭半空间(closed half space)；
    H={x∈V:(x,b)≥β}H =\{x \in V:(x,b)\ge\beta\}H={x∈V:(x,b)≥β}
  • 多面体集合(polyhedral set)：任意个半空间的交，通常可以用矩阵AAA表示为 H={x∈V:Ax≥β}H =\{x \in V:Ax\ge\beta\}H={x∈V:Ax≥β}

    • 例二 关于凸集封闭的集合运算

  • S1⊕S2={x1+x2:x1∈S1,x2∈S2}S_1 \oplus S_2=\{x_1+x_2:x_1 \in S_1,x_2 \in S_2\}S1​⊕S2​={x1​+x2​:x1​∈S1​,x2​∈S2​}
  • S1⊖S2={x1−x2:x1∈S1,x2∈S2}S_1 \ominus S_2=\{x_1-x_2:x_1 \in S_1,x_2 \in S_2\}S1​⊖S2​={x1​−x2​:x1​∈S1​,x2​∈S2​}

    • 凸组合

    定义二 凸组合(convex combination)。考虑∀x1,⋯,xm∈V,∀λ1,⋯,λm≥0\forall x_1,\cdots,x_m \in V,\forall \lambda_1,\cdots,\lambda_m \ge 0∀x1​,⋯,xm​∈V,∀λ1​,⋯,λm​≥0, λ1+⋯+λm=1\lambda_1+\cdots+\lambda_m=1λ1​+⋯+λm​=1，称x=λ1x1+⋯+λmxmx=\lambda_1x_1+\cdots+\lambda_mx_mx=λ1​x1​+⋯+λm​xm​

    为一个凸组合。凸组合与上一讲定义的仿射组合非常相似，它们的本质都是一些特殊的线性组合，但凸组合对线性组合系数的要求比仿射组合更严格。

    定理二 S⊂VS \subset VS⊂V是凸集的充要条件为SSS包含SSS中任何向量的所有凸组合。

    凸包

    定义三 S⊂VS \subset VS⊂V，称凸包(convex hull) convSconvSconvS是包含MMM的最小凸集。
    convS={∑i=1mλixi:xi∈S,λi∈F,∑i=1mλi=1,λi≥0,m∈N}=⋂{Mconvex:M⊃S}convS=\{\sum_{i=1}^m \lambda_ix_i:x_i \in S,\lambda_i \in F,\sum_{i=1}^m \lambda_i=1,\lambda_i \ge 0,m \in \mathbb{N}\} \\ = \bigcap \{M\ convex:M \supset S\}convS={i=1∑m​λi​xi​:xi​∈S,λi​∈F,i=1∑m​λi​=1,λi​≥0,m∈N}=⋂{M convex:M⊃S}
    定理二续 定理二的条件可以叙述为S=conv(S)S = conv(S)S=conv(S)。

    定义四 VVV中一个有限点集为{y0,⋯,ym}\{y_0,\cdots,y_m\}{y0​,⋯,ym​}，称它的凸包为凸多面体(polytope)；如果y0,⋯,ymy_0,\cdots,y_my0​,⋯,ym​仿射无关(affinely independent)，就称它的凸包conv{y0,⋯,ym}conv\{y_0,\cdots,y_m\}conv{y0​,⋯,ym​}为单纯形(simplex)。

    总结

    以上是生活随笔为你收集整理的UA SIE545 优化理论基础1 凸分析3 凸集与凸包的全部内容，希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。