本文主要是介绍凸优化3:几种重要凸集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、几种简单的凸集
| 仿射集 | 凸集 |
|---|---|
| R n R^n Rn空间、 R n R^n Rn空间子空间、直线 | 任意线段、${x_0+\theta v |
2、超平面与半空间
超平面（Hyperplane）: { x ∣ a T x = b } \{x|a^T x=b\} {x∣aTx=b} x , a ∈ R n , b ∈ R , a ≠ 0 x,a \in R^n,b \in R, a \neq 0 x,a∈Rn,b∈R,a=0
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eLDUUwgC-1642769035169)(D:\StudyFiles\ConvexOptimization\note\3.几种重要凸集\3-1.png)]](https://img-blog.csdnimg.cn/13f7e9d693564410922c3cf369eb6255.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQW5ob25nemhhbg==,size_13,color_FFFFFF,t_70,g_se,x_16)
半空间(Halfspace): { x ∣ a T x ≤ b } \{x|a^T x \leq b\} {x∣aTx≤b} x , a ∈ R n , b ∈ R , a ≠ 0 x,a \in R^n,b \in R, a \neq 0 x,a∈Rn,b∈R,a=0
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-j0ZHOlbD-1642769035170)(D:\StudyFiles\ConvexOptimization\note\3.几种重要凸集\3-2.png)]](https://img-blog.csdnimg.cn/a21d41bb3d30463c88ec3733da6f127a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQW5ob25nemhhbg==,size_17,color_FFFFFF,t_70,g_se,x_16)
2、球和椭球
球
球 ： 我 们 所 提 的 球 指 欧 几 里 得 球 ( E u c l i d e a n b a l l ) B ( x c , r ) = { x ∣ ∣ ∣ x − x c ∣ ∣ 2 ≤ r } = { x ∣ ( x − x c ) T ( x − x c ) ≤ r } 球：我们所提的球指欧几里得球(Euclidean \space ball) \\ B(x_c,r)=\{x \mid ||x-x_c||_2 \leq r\} \\ =\{x \mid \sqrt{{(x-x_c)}^T(x-x_c)} \leq r\} \\ 球：我们所提的球指欧几里得球(Euclidean ball)B(xc,r)={x∣∣∣x−xc∣∣2≤r}={x∣(x−xc)T(x−xc)≤r}
椭球(ellipsoids)
ε ( x c , p ) = { x ∣ ( x − x c ) T p − 1 ( x − x c ) ≤ 1 } x , x c ∈ R n , P ∈ S + + n P 的 奇 异 值 对 应 椭 球 的 半 周 长 ， S + + n 为 n × n 的 对 称 正 定 矩 阵 \varepsilon(x_c,p)=\{x \mid (x-x_c)^Tp^{-1}(x-x_c) \leq 1\} \\ x,x_c \in R^n, P \in S^n_{++}\\ P的奇异值对应椭球的半周长，S^n_{++}为 n \times n的对称正定矩阵 ε(xc,p)={x∣(x−xc)Tp−1(x−xc)≤1}x,xc∈Rn,P∈S++nP的奇异值对应椭球的半周长，S++n为n×n的对称正定矩阵
3、多面体和单纯形
多面体（Polyhedron）
P = { x ∣ a j T x ≤ b j , j = 1 , . . . , m c j T x = d j , j = 1 , . . . , r } P=\{x \mid a^T_jx \leq b_j,j=1,...,m\\ \space\space\space\space\ c^T_jx=d_j,j=1,...,r\} P={x∣ajTx≤bj,j=1,...,m cjTx=dj,j=1,...,r}
**单纯形（Simplex）**定义较为复杂
R n 空 间 中 选 择 v 0 , . . . , v k 共 k + 1 个 点 ， v 1 − v 0 , . . . , v k − v 0 线 性 无 关 ， 则 与 上 述 点 相 关 的 单 纯 形 为 ： C = c o n v { v 0 , . . . , v k } = { θ 0 v 0 + . . . + θ k v k , θ ≥ 0 , 1 T θ = 1 } , θ ∈ R n R^n空间中选择v_0,...,v_k共k+1个点，\\ v_1-v_0,...,v_k-v_0线性无关，\\ 则与上述点相关的单纯形为：\\ C=conv\{v_0,...,v_k\}=\{\theta_0 v_0+...+\theta_k v_k, \theta \geq 0, 1^T \theta=1\},\theta \in R^n Rn空间中选择v0,...,vk共k+1个点，v1−v0,...,vk−v0线性无关，则与上述点相关的单纯形为：C=conv{v0,...,vk}={θ0v0+...+θkvk,θ≥0,1Tθ=1},θ∈Rn
证明：一个单纯形是一种多面体
x ∈ C ∈ R n , C 为 s i m p l e x ⇔ x = θ 0 v 0 + . . . + θ k v k , 1 T θ = 1 , θ ≥ 0 , v 1 − v 0 , . . . , v k − v 0 线 性 无 关 x\in C \in R^n, C为simplex \\ \Leftrightarrow x=\theta_0 v_0+...+\theta_k v_k,1^T \theta=1,\theta \geq 0,\\v_1-v_0,...,v_k-v_0线性无关\\ x∈C∈Rn,C为simplex⇔x=θ0v0+...+θkvk,1Tθ=1,θ≥0,v1−v0,...,vk−v0线性无关
定 义 ： y = [ θ 1 , . . . , θ k ] T , y i ≥ 0 , 1 T y ≤ 1 B = [ v 1 − v 0 , . . . , v k − v 0 ] T ∈ R n × k x ∈ C ⇔ x = θ 0 v 0 + . . . + θ k v k = v 0 + θ 1 ( v 1 − v 0 ) + . . . + θ k ( v k − v 0 ) = v 0 + B y 定义：y=[\theta_1,...,\theta_k]^T,y_i \geq 0, 1^T y \leq 1 \\ B=[v_1-v_0,...,v_k-v_0]^T \in R^{n \times k} \\ x \in C \Leftrightarrow x=\theta_0 v_0+...+\theta_k v_k \\ = v_0+\theta_1(v_1-v_0)+...+\theta_k(v_k-v_0) \\ = v_0 + By 定义：y=[θ1,...,θk]T,yi≥0,1Ty≤1B=[v1−v0,...,vk−v0]T∈Rn×kx∈C⇔x=θ0v0+...+θkvk=v0+θ1(v1−v0)+...+θk(vk−v0)=v0+By
引入如下结论：
B = [ v 1 − v 0 , . . . , v k − v 0 ] 线 性 无 关 , 故 r a n k ( B ) = k ≤ n 对 于 非 奇 异 矩 阵 B ， 一 定 存 在 一 个 矩 阵 A = [ I k 0 ] ∈ [ R k × k 0 ( n − k ) × k ] 使 得 A B = [ A 1 A 2 ] B = [ I k 0 ] B=[v_1-v_0,...,v_k-v_0]线性无关,故rank(B) = k \leq n \\ 对于非奇异矩阵B，一定存在一个矩阵\\ A=\left[ \begin{matrix} I_k \\ 0 \end{matrix} \right] \in \left[ \begin{matrix} R^{k \times k} \\ 0^{(n-k) \times k} \end{matrix} \right]\\ 使得 AB=\left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]B=\left[ \begin{matrix} I_k \\ 0 \end{matrix} \right] \\ B=[v1−v0,...,vk−v0]线性无关,故rank(B)=k≤n对于非奇异矩阵B，一定存在一个矩阵A=[Ik0]∈[Rk×k0(n−k)×k]使得AB=[A1A2]B=[Ik0]
则对于前面得到的等式我们可以做如下变换：
x = v 0 + B y ⇒ A x = A v 0 + A B y ⇔ [ A 1 A 2 ] x = [ A 1 A 2 ] v 0 + [ A 1 B A 2 B ] y ⇔ { A 1 x = A 1 v 0 + y A 2 x = A 2 v 0 ⇔ { A 1 x ≥ A 1 v 0 1 T A 1 x ≤ 1 + 1 T A 1 v 0 A 2 x = A 2 v 0 ⇒ 由 不 等 式 和 等 式 构 成 ， 是 多 面 体 x=v_0+By \\ \Rightarrow Ax=Av_0+ABy\\ \Leftrightarrow \left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]x=\left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]v_0+\left[ \begin{matrix} A_1B \\ A_2B \end{matrix} \right]y\\ \Leftrightarrow \left\{ \begin{matrix} A_1x=A_1v_0+y\\ A_2x=A_2v_0 \end{matrix} \right.\\ \Leftrightarrow \left\{ \begin{matrix} A_1x \geq A_1v_0\\ 1^TA_1x \leq 1+1^TA_1v_0\\ A_2x=A_2v_0 \end{matrix} \right. \\ \Rightarrow 由不等式和等式构成，是多面体\\ x=v0+By⇒Ax=Av0+ABy⇔[A1A2]x=[A1A2]v0+[A1BA2B]y⇔{A1x=A1v0+yA2x=A2v0⇔⎩⎨⎧A1x≥A1v01TA1x≤1+1TA1v0A2x=A2v0⇒由不等式和等式构成，是多面体
4、一些对称矩阵
对称矩阵集合 S n = { x ∈ R n × n ∣ x = x T } S^n=\{x \in R^{n \times n} \mid x=x^T\} Sn={x∈Rn×n∣x=xT}
对称半正定矩阵集合 S + n = { x ∈ R n × n ∣ x = x T , x ⪰ 0 } S^n_+=\{x \in R^{n \times n} \mid x=x^T,x \succeq 0\} S+n={x∈Rn×n∣x=xT,x⪰0}
对称正定矩阵集合 S + + n = { x ∈ R n × n ∣ x = x T , x ≻ 0 } S^n_{++}=\{x \in R^{n \times n} \mid x=x^T, x \succ 0\} S++n={x∈Rn×n∣x=xT,x≻0}
证明： S + n S^n_+ S+n是 C o n v e x C o n e Convex \space Cone Convex Cone，即：
∀ θ 1 , θ 2 ≥ 0 , ∀ A , B ∈ S + n , 证 明 θ 1 A + θ 2 B ∈ S + n \forall \space\space \theta_1,\theta_2 \geq 0, \forall \space\space A,B \in S^n_+,证明 \space \theta_1A+\theta_2B \in S^n_+ \\ ∀ θ1,θ2≥0,∀ A,B∈S+n,证明 θ1A+θ2B∈S+n
证：
∀ x ∈ R n , x ≠ 0 , x T A x ≥ 0 , x T B x ≥ 0 x T ( θ 1 A + θ 2 B ) x = θ 1 x T A x + θ 2 x T B x ≥ 0 ⇒ 正 定 得 证 ( θ 1 A + θ 2 B ) T = ( θ 1 A T + θ 2 B T ) = ( θ 1 A + θ 2 B ) ⇒ 对 称 得 证 故 ： θ 1 A + θ 2 B ∈ S + n \forall \space\space x \in R^n,x \neq 0, x^TAx \geq 0,x^TBx \geq 0 \\ x^T(\theta_1A+\theta_2B)x =\theta_1x^TAx+\theta_2x^TBx \geq 0 \Rightarrow 正定得证\\ (\theta_1A+\theta_2B)^T=(\theta_1A^T+\theta_2B^T)=(\theta_1A+\theta_2B)\Rightarrow 对称得证 \\ 故：\theta_1A+\theta_2B \in S^n_+ ∀ x∈Rn,x=0,xTAx≥0,xTBx≥0xT(θ1A+θ2B)x=θ1xTAx+θ2xTBx≥0⇒正定得证(θ1A+θ2B)T=(θ1AT+θ2BT)=(θ1A+θ2B)⇒对称得证故：θ1A+θ2B∈S+n
S + + n S^n_{++} S++n不是 C o n v e x C o n e Convex \space Cone Convex Cone,是凸集
∀ x ∈ R n , x ≠ 0 , x T A x ≥ 0 , x T B x ≥ 0 x T ( θ 1 A + θ 2 B ) x = θ 1 x T A x + θ 2 x T B x ≯ 0 因 为 θ 1 , θ 2 = 0 时 θ 1 x T A x + θ 2 x T B x = 0 ， 不 符 合 凸 锥 定 义 \forall \space\space x \in R^n,x \neq 0, x^TAx \geq 0,x^TBx \geq 0 \\ x^T(\theta_1A+\theta_2B)x =\theta_1x^TAx+\theta_2x^TBx \ngtr 0 \\ 因为\theta_1,\theta_2=0时\space \theta_1x^TAx+\theta_2x^TBx = 0，不符合凸锥定义 ∀ x∈Rn,x=0,xTAx≥0,xTBx≥0xT(θ1A+θ2B)x=θ1xTAx+θ2xTBx≯0因为θ1,θ2=0时 θ1xTAx+θ2xTBx=0，不符合凸锥定义
这篇关于凸优化3:几种重要凸集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
