精华内容
下载资源
问答
  • 凸集

    千次阅读 2019-08-29 17:48:29
    本文参考自清华大学研究生...一:凸集 定义:设S为n维欧式空间中中的一个集合,若对S中任意两点,联结它们的线段仍属于S,称这样的集合S是一个凸集。 用代数的形式表达为:对S中任意两点,及每个实数,都有 称...

    本文参考自清华大学研究生公共课教材——数学系列《最优化理论与算法》(第二版)

    一:凸集

    定义:设S为n维欧式空间中\mathbb{R}^{n}中的一个集合,若对S中任意两点,联结它们的线段仍属于S,称这样的集合S是一个凸集。

    用代数的形式表达为:对S中任意两点x^{(1)}x^{(2)}及每个实数\lambda \in [0,1],都有

                                                                       \lambda x^{(1)}+(1-\lambda )x^{(2)}\in S

    称S为凸集

                                                          \lambda x^{(1)}+(1-\lambda )x^{(2)}称为x^{(1)}x^{(2)}的凸组合。

     

    下面验证几个集合是否为凸集:

    例一:验证集合H=\left \{ x|p^{T}x=a \right \}为凸集,其中,p为n维列向量,a为实数

    对于任意两点x^{(1)}x^{(2)}\in H,及每个实数\lambda \in [0,1]都有

                                                                                 \lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}

                                                                                \because p^{T}x^{(1)}=p^{T}x^{(2)}=a

                                                                                \therefore \lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}=\lambda a+(1-\lambda)a=a

    所以\lambda x^{(1)}+(1-\lambda )x^{(2)}\in H

    H称为\mathbb{R}^{n}中的一个超平面,所以超平面为凸集。

     

    例二:验证集合H^{-}=\left \{ x|p^{T}x\leqslant a \right \}为凸集

    对于任意两点x^{(1)},x^{(2)}\in H^{-},及每个实数\lambda \in [0,1]都有

                                                                              p^{T}\left [ \lambda x^{(1)}+(1-\lambda)x^{(2)} \right ]\leqslant a

    上式左=\lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}

                                                                             \because p^{T}x^{(1)}\leqslant a     p^{T}x^{(2)}\leqslant a

                                                                             \lambda+(1-\lambda)=1

                                                                             \therefore \lambda p^{T}x^{(1)}+(1-\lambda)p^{T}x^{(2)}\leqslant a

    所以\lambda x^{(1)}+(1-\lambda)x^{(2)}\in H^{-}

    所以H^{-}为凸集,集合H^{-}=\left \{ x|p^{T}x\leqslant a \right \}称为半空间,所以半空间为凸集

     

    例三:验证集合L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}为凸集,其中d是给定的非零向量,x^{(0)}是定点

    对于任意两点x^{(1)},x^{(2)}\in L及每一个数\lambda \in [0,1],必有x^{(1)}=x^{(0)}+\lambda_{1}dx^{(2)}=x^{(0)}+\lambda_{2}d\lambda_{1},\lambda_{2}是非负数

                                                       \lambda x^{(1)}+(1-\lambda)x^{(2)}=\lambda(x^{(0)}+\lambda_{1}d)+(1-\lambda)(x^{(0)}+\lambda_{2}d)

                                                                                         =x^{(0)}+\left [ \lambda \lambda_{1}+(1-\lambda)\lambda_{2} \right ]d

    由于\lambda \lambda_{1}+(1-\lambda)\lambda_{2}\geqslant 0,所以\lambda x^{(1)}+(1-\lambda)x^{(2)}\in L,所以L为凸集

    集合L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}成为射线,所以射线为凸集,x^{(0)}为射线的预点

     

    二:极点

    若假设S为非空凸集,x=\lambda x^{(1)}+(1-\lambda)x^{(2)}(\lambda \in (0,1)),x^{(1)},x^{(2)} \in S,必推得x=x^{(1)}=x^{(2)},则称x为凸集S的极点

    这个论断对于紧凸集是正确的,但是对于无界集并不成立,此时引入极方向的概念

     

    三:极方向

    设S为\mathbb{R}^{n}中的闭凸集,d为非零向量,如果对S中的每一个x,都有射线

                                                                                      \left \{ x+\lambda d|\lambda\geqslant 0 \right \}\subset S

    则称向量d为S的方向。

    d^{(1)}d^{(2)}是S的两个方向,若对任意正数\lambda,有d^{(1)}\neq \lambda d^{(2)},则称d^{(1)}d^{(2)}为两个不同的方向。

    若S的方向d不能表示为该集合中两个不同方向的正的线性组合,则称d为S的极方向。

     

    四:凸集分离定理

    对于两个集合S1,S2,存在一个超平面H,使S1在H的一边,S2在H的另一边。

    设超平面的方程为P^{T}x=a,那么对于H某一边的点x,有p^{T}x\geqslant a,而对另一边的点x,必有p^{T}x\leqslant a

    称超平面分离集合S_{1}S_{2}

    展开全文
  • 本片文档主要介绍了凸集的一些保凸代数运算,像加法,标量乘法,直和,线性变换,逆线性变换和逆加法等。
  • 本文主要介绍了凸包,凸组合,凸锥的概念以及相关运算
  • 对文献[1]中有关无界凸性的三个性质给出了新的证明。
  • LazySets.jl:带有凸集的微积分的Julia包
  • 本文证明了投影算子的一个新的单调性质,并简要讨论了与其它单调性质的关系。
  • 【第1章】凸集——几种重要的凸集

    千次阅读 2020-04-11 21:35:35
    凸集——几种重要的凸集2.几种重要的凸集2.1 超平面与半空间2.2 球和椭球2.3 多面体(关注单纯形)2.4 半正定锥2.6参考 Date: 2020/04/11 Editor:任于帅(Jesse) Contact: renyushuai804@qq.com 2.几种重要的凸集...


    Date: 2020/04/11
    Editor:萧潇子(Jesse)
    Contact: 1223167600@qq.com


    2.几种重要的凸集

    本节讲述一些重要凸集的概念,首先介绍一些简单的例子,我们不妨先来看一些特例:

    • C = { x } C=\{x \} C={x} 单点
    • 点是仿射集,凸集,原点是凸锥
    • 空集是仿射集,凸集,凸锥

    下面再来看几种重要的凸集:

    • R n R^n Rn 仿射集、凸集、凸锥
    • R n R^n Rn空间的子空间 仿射集、凸集、凸锥
    • 任意直线 仿射集、凸集、凸锥(过原点)
    • 任意线段 仿射集(点)、凸集、凸锥(原点)
    • { x 0 + θ v ∣ θ ≥ 0 } \{x_0+\theta v|\theta\ge0\} {x0+θvθ0} x 0 ∈ R n x_0\in R^n x0Rn θ ∈ R \theta \in R θR - v ∈ R n v\in R^n vRn 射线 仿射集(v=0缩减为一个点) 、凸集、凸锥(过原点)

    2.1 超平面与半空间

    超平面
    定义: { x ∣ a T x = b } \{x|a^Tx=b\} {xaTx=b} x , a ∈ R n x,a\in R^n x,aRn, b ∈ R b\in R bR, a ≠ 0 a\neq0 a=0
    性质: 仿射集、凸集、凸锥(过原点)

    半空间
    定义: a T x ≤ b , a T x ≥ b a^Tx\le b,\quad a^Tx\ge b aTxb,aTxb
    性质: 凸集、凸锥(过原点b=0)

    从上述对超平面和半空间集合表达式定义形式很难直观的感受定义与性质,下面我们通过在二维平面中的例子来理解一下超平面与半空间的几何意义,如下图所示:

    • 红色直线(不过原点)称之为一个二维平面上的超平面,具有直线集合所有的性质,属于仿射集、凸集;
    • 蓝色直线(过原点)为红色直线的特例,除了是仿射集/凸集之外,还是个凸锥;
    • 红色直线把二维平面分成了1和2两个空间,这两个空间称为半空间,并且满足凸集的定义,因此是半空间是凸集;
    • 与超平面一样,当超平面过原点时,半空间也满足凸锥的定义,此时半空间也是个凸锥;

    在这里插入图片描述

    2.2 球和椭球

    同样以二维平面上的圆和椭圆去理解比较容易理解,这里就不做赘述,只给出简单定义:

    定义:
    B ( x c , r ) = { x   ∣ ∥ x − x c ∥ 2   ≤ r } = { x   ∣ ( x − x c ) T ( x − x c ) ≤ r } B(x_c,r)=\{x\:|\parallel x-x_c \parallel _2 \:\le r\}=\{x\:|\sqrt{(x-x_c)^T(x-x_c)}\le r\} B(xc,r)={xxxc2r}={x(xxc)T(xxc) r}
    性质: 凸集 仿射集(r=0) 凸锥(r=0 & 原点)
    椭球:
    定义: (对称正定矩阵几何)
    ξ ( x c , P ) = { x   ∣ ( x − x c T ) P − 1 ( x − x c )   ≤ 1 }   x c ∈ R n   P ∈ S + + n \xi(x_c,P)=\{x\:| (x-x_c^T)P^{-1}(x-x_c) \:\le 1\} \: x_c\in R^n \: P\in S_{++}^{n} ξ(xc,P)={x(xxcT)P1(xxc)1}xcRnPS++n
    性质: 凸集

    假设: P = r 2 I n P=r^2I_n P=r2In, r ≠ 0 r\neq0 r=0 奇异值大于0

    A矩阵 A T A A^TA ATA 特征值: e i g ( A T A ) ≥ 0 eig(A^TA) \ge0 eig(ATA)0 奇异值: e i g ( A T A ) \sqrt{eig(A^TA)} eig(ATA)

    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} \xi &=\{x\:| x^T\begin{pmatrix} 4 & 0\\ 0 & 1 \end{pmatrix}^{-1}x \:\le 1\}\\ &=\{(x_1,x_2)|\frac{1}{4}x_1^2+x_2^2 \le 1\} \end{aligned} ξ={xxT(4001)1x1}={(x1,x2)41x12+x221}

    2.3 多面体(关注单纯形)

    多面体:可以简单的理解为超平面与半空间的交集,数学表达式如下:
    P = { x   ∣ a j T x ≤ b j i = 1 ⋯ m c j T x = d j i = 1 ⋯ m } P=\Bigg\{x\:\mid \begin{aligned} a_j^Tx \le b_j\qquad i=1\cdots m\\ c_j^Tx = d_j \qquad i=1\cdots m\\ \end{aligned}\Bigg\} P={xajTxbji=1mcjTx=dji=1m}
    其中有界多面体为凸集 ,如下图中集合P(阴影部分:由五条直线与其分割形成的相应半空间的交集)所示:

    在这里插入图片描述

    单纯形定义:

    R n R^n Rn空间中选择 v 0 ⋯ v k v_0\cdots v_k v0vk k + 1 k+1 k+1个点, v 1 − v 0 , ⋯   , v k − v 0 v_1-v_0,\cdots,v_k-v_0 v1v0,,vkv0线性无关,则与上述点相关的单纯形为:

    C = C o n v { v 0 ⋯ v k } = { θ 0 v 0 + θ 1 v 1 + θ 2 v 2 + ⋯ + θ k v k   ∣   θ 0 ⋯ θ k ≥ 0 ,   θ 0 + ⋯ + θ k = 1 } C=Conv\{v_0\cdots v_k\}=\{\theta_0v_0+\theta_1v_1 + \theta_2v_2 + \cdots + \theta_kv_k \:|\: \theta_0 \cdots \theta_k \ge 0,\:\theta_0 +\cdots +\theta_k = 1 \} C=Conv{v0vk}={θ0v0+θ1v1+θ2v2++θkvkθ0θk0,θ0++θk=1}

    例子:

    • R R R 一维空间, 两个点单纯形为两点连接线段,
    • R 2 R^2 R2 二维空间, 两个点单纯形为两点连接线段, 三个点为两个向量围成的三角形, 四个点无法满足线性无关的三个向量
    • R 3 R^3 R3 三维空间,四个点单纯形为一个四面体

    证明:单纯形是多面体的一种

    x ∈ C ∈ R n x\in C \in R^n xCRn C C C为单纯形 x x x ⇔ \Leftrightarrow θ 0 v 0 + θ 1 v 1 + θ 2 v 2 + ⋯ + θ k v k \theta_0v_0 + \theta_1v_1 + \theta_2v_2 + \cdots + \theta_kv_k θ0v0+θ1v1+θ2v2++θkvk

    θ 0 ⋯ θ k ≥ 0 ,   θ 0 + ⋯ + θ k = 1 \theta_0 \cdots \theta_k \ge 0,\:\theta_0 +\cdots +\theta_k = 1 θ0θk0,θ0++θk=1. v 1 − v 0 , ⋯   , v k − v 0 v_1-v_0,\cdots,v_k-v_0 v1v0,,vkv0线性无关

    首先定义下面两个向量:

    [ θ 1 ⋯ θ k ] T = y [\theta_1 \cdots \theta_k]^T=y [θ1θk]T=y, y ≥ 0 y\ge0 y0, 1 T y ≤ 1 1^Ty\le1 1Ty1,

    [ v 1 − v 0 , ⋯   , v k − v 0 ] = B ∈ R n × k [v_1-v_0, \cdots, v_k-v_0]=B\in R^{n\times k} [v1v0,,vkv0]=BRn×k

    因此:

    X ∈ C ⇔ X = θ 0 v 0 + θ 1 v 1 + θ 2 v 2 + ⋯ + θ k v k = v 0 + θ 1 ( v 1 − v 0 ) + ⋯ + θ k ( v k − v 0 ) = v 0 + B y \begin{aligned} X \in C \Leftrightarrow X &=\theta_0v_0 + \theta_1v_1 + \theta_2v_2 + \cdots + \theta_kv_k\\ &= v_0 + \theta_1(v_1-v_0)+ \cdots + \theta_k(v_k-v_0) \\ &= v_0 +By\\ \end{aligned} XCX=θ0v0+θ1v1+θ2v2++θkvk=v0+θ1(v1v0)++θk(vkv0)=v0+By

    B包含k个线性无关的向量,因此: r a n k ( B ) = k ( k ≤ n ) rank(B)=k \quad (k \le n) rank(B)=k(kn)

    B是列满秩矩阵,可以转换成: [ I k 0 ] \begin{bmatrix} I_k \\[0.3em] 0\end{bmatrix} [Ik0]

    存在一个非奇异矩阵 A = [ A 1 A 2 ] ∈ R n × n A=\begin{bmatrix}A_1 \\[0.3em] A_2\end{bmatrix} \in R^{n \times n} A=[A1A2]Rn×n使得 A B = [ A 1 A 2 ] B = [ I k 0 ] AB=\begin{bmatrix}A_1 \\[0.3em] A_2\end{bmatrix}B =\begin{bmatrix} I_k \\[0.3em] 0\end{bmatrix} AB=[A1A2]B=[Ik0]

    X = v 0 + B y X=v_0+By X=v0+By 左右两边同乘以 A A A 的:

    A X = A v 0 + A B y AX =Av_0+ABy AX=Av0+ABy ⇔ \Leftrightarrow [ A 1 A 2 ] X = [ A 1 A 2 ] v 0 + [ A 1 B A 2 B ] y \begin{bmatrix}A_1 \\[0.3em] A_2\end{bmatrix}X=\begin{bmatrix}A_1 \\[0.3em] A_2\end{bmatrix}v_0+\begin{bmatrix}A_1B \\[0.3em] A_2B \end{bmatrix}y [A1A2]X=[A1A2]v0+[A1BA2B]y ⇔ \Leftrightarrow { A 1 X = A 1 v 0 + y A 2 X = A 2 v 0 \begin{cases} A_1X=A_1v_0+y \\ A_2X=A_2v_0 \\ \end{cases} {A1X=A1v0+yA2X=A2v0

    ⇔ \Leftrightarrow { 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 \begin{cases} A_1X &\ge A_1v_0 \\ 1^TA_1X &\le 1+ 1^TA_1v_0 \\ A_2X &=A_2v_0 \\ \end{cases} A1X1TA1XA2XA1v01+1TA1v0=A2v0

    两个线性不等式和一个线性等式=多面体

    2.4 半正定锥

    对称矩阵集合 S n = { X ∈ R n × n ∣ X = X T } S^n=\{X\in R^{n\times n}|X=X^T\} Sn={XRn×nX=XT} 凸集 凸锥

    对称半正定矩阵集合 S + n = { X ∈ R n × n ∣ X = X T ,   X ⪰ 0 } S_{+}^n=\{X\in R^{n\times n}|X=X^T,\: X \succeq 0\} S+n={XRn×nX=XT,X0} 其中 X ⪰ 0 X \succeq 0 X0表示特征值大于等于0 凸集 凸锥

    对称正定矩阵集合 S + + n = { X ∈ R n × n ∣ X = X T ,   X ≻ 0 } S_{++}^n=\{X\in R^{n\times n}|X=X^T,\: X \succ 0\} S++n={XRn×nX=XT,X0} 其中 X ≻ 0 X \succ 0 X0表示 X X X是正定矩阵 凸集 非凸锥

    证明 S + n S_{+}^n S+n 是凸集、凸锥

    ∀ θ 1 ,   θ 2   ≥ 0 \forall \theta_1, \: \theta_2 \: \ge 0 θ1,θ20 ∀   A ,   B ∈ S + n \forall \: A, \: B \in S_{+}^n A,BS+n 证明 θ 1 A + θ 2 B ∈ S + n \theta_1A+\theta_2B \in S_+^n θ1A+θ2BS+n 即证明 θ 1 A + θ 2 B \theta_1A+\theta_2B θ1A+θ2B 对称半正定

    如果 A , B A, B A,B是半正定矩阵,则对于 ∀ X ∈ R n \forall X\in R^n XRn, X T A X ≥ 0 X T B X ≥ 0 \begin{aligned} X^TAX &\ge 0 \\ X^TBX &\ge 0 \\ \end{aligned} XTAXXTBX00

    由上可知证明半正定即证明 X T ( θ 1 A + θ 2 B ) X ≥ 0 = X T θ 1 A X + X T θ 2 B X ≥ 0 X^T(\theta_1A+\theta_2B)X \ge 0=X^T \theta_1AX+X^T \theta_2BX \ge 0 XT(θ1A+θ2B)X0=XTθ1AX+XTθ2BX0

    因此得证

    考虑简单情况:

    n = 1 n=1 n=1 时, S + n = R + S_+^n=R_+ S+n=R+ S + + n = R + + S_{++}^n=R_{++} S++n=R++ S n = R S^n=R Sn=R 可知对称正定矩阵 S + + n S_{++}^n S++n不包含原点,因此非凸锥


    S + n S_+^n S+n n = 2 n=2 n=2 S + n = { [ x y y z ] ∣ x ≥ 0 ,   z ≥ 0 ,   x z ≥ y 2 } S_+^n=\Bigg\{\begin{bmatrix} x&y \\[0.3em] y&z\end{bmatrix} | x \ge 0,\:z\ge0,\: xz\ge y^2 \Bigg\} S+n={[xyyz]x0,z0,xzy2} 二维矩阵空间与xyz 三维空间可以对应起来, 如下图所示:

    交集

    S 1 , S 2 S_1,S_2 S1,S2为凸集,则 S 1 ⋂ S 2 S_1 \bigcap S_2 S1S2为凸

    S a S_a Sa为凸集, ∀ a ∈ A \forall a\in A aA ⋂ a ∈ A S a \mathop{\bigcap} \limits_{a\in A} S_a aASa为凸集

    在这里插入图片描述

    2.5参考

    1、Stephen Boyd 、Lieven Vandenberghe——《Convex Optimization》)
    2、中科大凌青凸优化 (https://www.bilibili.com/video/BV1Jt411p7jE?)

    展开全文
  • 02 凸集

    千次阅读 2020-01-25 23:53:33
    02.凸集 目录 2.1.仿射集合和凸集 2.2.重要的例子 2.3.保凸运算 2.4.广义不等式 2.5.分离与支撑超平面 2.6.对偶锥与广义不等式 2.1.仿射集合和凸集 2.1.2 仿射集合 2.1.1直线与线段的定义、几何含义 Def 1 仿射...

    02 凸集

    在这里插入图片描述

    目录
    2.1.仿射集合和凸集
    2.2.重要的例子
    2.3.保凸运算

    2.5.分离与支撑超平面

    2.4.正常锥与广义不等式
    2.6.对偶锥与广义不等式

    2.1 仿射集合和凸集

    2.1.2 仿射集合

    2.1.1直线与线段的定义、几何含义
    Def 1 仿射集合的定义

    (一)仿射组合&仿射包

    Def 2 仿射组合&仿射包的定义

    引理1:一个仿射集包含其中任意两点的仿射组合[定义]→一个仿射集包含其中任意多点的仿射组合

    定理1:仿射包 aff( C)是包含C的最小的仿射集合,也就是说,S是满足C⊆S的仿射集合,则aff( C)⊆S

    (二)仿射集的刻画

    定理2(仿射集是子空间的平移):(1)如果C是一个仿射集合并且x0∈C,则集合V=C-x0是一个子空间,即关于加法和乘法是封闭的;
    (2)任意仿射集合C都可以表示为C=V+x0,∀x0∈C,其中x0的选取与V无关。

    推论2(仿射集等价于线性方程组的解集):任意仿射集等价于一个线性方程组的解集。

    (三)2.1.3 仿射维数与相对内部

    Def 3 仿射维数的定义:集合C的仿射维数是其仿射包的维数,即其平行子空间的维数。
    ps. 平面上单位圆环的仿射维数为2,而大多数维数定义下为1。

    Def 4 相对内部&相对边界的定义:仿射包的内部
    ps. 相对内部和内部的区别:仿射维数与空间维数的关系

    2.1.4 凸集

    Def 5 凸集的定义
    Def 6 凸组合&凸包的定义

    引理3:一个凸集包含其中任意两点的凸组合[定义]→一个凸集包含其中任意多点的凸组合

    定理3:凸包conv( C)是包含C的最小的凸集,也就是说,B是满足C⊆B的凸集,则aff( C)⊆B

    凸组合概念的扩展[无穷级数、积分、概率分布]

    2.2 重要的例子

    (一)凸锥

    2.1.5 锥

    Def 7 锥、凸锥的定义,几何含义&等价定义
    Def 8 锥组合&锥包的定义

    引理4:一个凸锥包含其中任意两点的锥组合[定义]→一个凸锥包含其中任意多点的锥组合

    定理4:锥包是包含C的最小的凸锥,也就是说,B是满足C⊆B的凸锥,则cone( C)⊆B

    2.2.3 范数锥

    Def 9 范数锥的定义
    示例:二阶锥(二次锥/Lorentz锥/冰淇淋锥):由Euclid范数定义的范数锥

    2.2.5 半正定锥

    Def 10 对称矩阵、对称半正定矩阵、对称正定矩阵的定义

    定理5*:对称半正定矩阵是凸锥

    定理6*:对称正定矩阵是对称半正定矩阵的内部

    示例:二阶对称半正定矩阵的元素

    (二)球体

    2.2.3 范数球

    Def 11 范数球的定义

    2.2.2 Euclid球和椭球

    Def 12 Euclid球的定义:由Euclid范数定义的范数球
    ps. Euclid球两种形式的表述

    定理7:Euclid球是凸集(只用到范数的齐次性和三角不等式)

    Def 13 椭球的定义[两种表述]

    (三)多面体

    2.2.1 超平面与半空间

    Def 14 超平面的定义&几何含义
    Def 15 半空间的定义&几何含义、半开空间

    2.2.4 多面体

    Def 16 多面体的定义&矩阵表示
    Def 17 多胞体的定义:有界的多面体
    示例:非负象限(多面体锥)

    重要的例子:单纯形

    Def 18 仿射独立的定义

    定理8:仿射独立与线性独立的关系

    Def 19 单纯形的定义:有限个仿射独立的点生成的凸包
    示例:1.一维、二维、三维单纯性;2.单位单纯性;3.概率单纯性

    定理9(单纯性的多面体描述):将单纯形转换为多面体形式

    多面体的凸包描述

    定理10(凸包形式与多面体形式的转换):(1)凸包是多面体,但无法简单地用多面体形式表示;(2*)凸包扩展式与多面体形式可以相互转换

    示例:Rn中无穷范数下单位球的凸包和多面体形式

    2.3 保凸运算

    2.3.1 交集

    定理11*:交集运算(有限&无穷)是保凸的

    示例:多面体是半平面和超平面的交集
    示例1:半正定锥是无穷个半空间的交集
    示例2:无穷个平板的交集

    定理12*:(1)半空间的交集是凸集(如上示例);(2)每一个闭凸集是半空间的交集,即一个闭集是包含它的所有半空间的交集;(3)每个仿射集都是有限个超平面的交集

    2.3.2 仿射变换

    Def 20:仿射变换的定义

    定理13*:仿射变换/逆变换是保凸的

    运算示例
    1.凸集的伸缩和平移是凸的;
    2.凸集向它的某几个坐标的投影是凸的;
    3.两个凸集的是凸的;
    4*.两个凸集的部分和是凸的:交集和两个凸集的和是其特殊情况;
    5.直积运算是保凸的:两个凸集和的逆运算;

    凸集示例
    1.多面体;
    2.线性矩阵不等式的解:半正定锥的原像;
    3.双面锥:二阶锥的原像;
    4.椭球:单位Euclid球的像;

    2.3.3 线性分式及透视函数

    (一)透视函数

    Def 21:透视函数的定义、小孔成像解释

    定理14:凸集在透视函数下的像/原像是凸集

    (二)线性分式函数[投射函数]

    Def 22:线性分式函数的定义:仿射函数复合透视函数
    :线性分式函数的投射解释、几何解释、投射/逆投射变换

    定理15:线性分式函数的像/原像是保凸的

    示例:条件概率是线性分式变换
    ps. 二维空间中集合在线性分式函数下像与原像的图形比较

    2.5 分离与支撑超平面

    2.5.1 超平面分离定理

    (一)超平面分离定理

    引理16(钝角原理的推论)*:当集合C和D为闭集,且至少有一个有界,则存在 c ∈ C c \in C cC d ∈ D d \in D dD 达到两个集合间的最小距离,即 dist(C,D)。

    定理16(超平面分离定理):假设C和D是两个不相交的凸集,那么存在 a ≠ 0 a \neq 0 a=0 和 b使得对于所有 x ∈ D x \in D xD a T x ≥ b a^Tx\geq b aTxb

    示例:仿射集与凸集的分离:分离函数满足的条件

    (二)超平面严格分离定理

    定理17(超平面严格分离定理)*:(1)两个凸集都是闭集不一定能严格分离;(2)在某些特殊情况下,可以构造严格分离。

    示例

    定理18(点与闭凸集的严格分离):令C为闭凸集,而 x 0 ∉ C x_0 \notin C x0/C,那么存在将x_0与C 严格分离的超平面。

    推论18:一个闭凸集是包含它的所有半空间的交集

    (三)超平面分离定理的逆定理

    定理18(超平面分离定理的逆定理):(1)两个凸集C和D存在分离超平面,但这两个集合不一定不相交(超平面分离定理的逆定理不成立);(2)给凸集C和D添加额外的条件,才有逆定理成立,从而构成等价定理。

    示例:

    定理19:两个集合C和D是凸集,如果其中至少一个是开集,那么当且仅当存在分离超平面时,它们不相交。

    超平面分离定理的应用:示例

    定理20(严格线性不等式的择一定理):严格线性不等式Ax<b(2.17)与 λ ≠ 0 , λ ≥ 0 , A T λ = 0 , λ T b ≤ 0 λ \neq 0,λ\geq0,A^Tλ=0,λ^Tb\leq0 λ=0λ0ATλ=0λTb0(2.18)构成一对一择一选择,即对于任意A和b,两者中仅有一组有解。

    2.5.2 支撑超平面

    Def 23 支撑超平面的定义、几何含义

    定理21(支撑超平面定理):对于任意非空的凸集C和任意 x 0 ∈ b d C x_0 \in bdC x0bdC,在 x 0 x_0 x0处存在C的支撑超平面。 Pf:C的内部是空集;C的内部非空

    定理22(支撑超平面定理的逆定理)*:如果一个集合是闭集,具有非空内部,并且其边界上每个点均存在支撑超平面,那么它是凸的。

    2.4.正常锥与广义不等式

    2.4.1正常锥&广义不等式

    Def 24 正常锥的定义:尖的非空内部闭凸锥
    Def 25 广义不等式的定义:由正常锥定义 R n R^n Rn上的偏序关系、严格偏序关系
    示例
    1.K是非负象限(分量不等式);
    2.K是半正定锥(矩阵不等式);
    3.K是[0,1]上的非负多项式锥;

    定理23(广义不等式的性质) :(1)广义不等式的性质;(2)严格广义不等式的性质。(与普通的不等式有类似的性质)

    2.4.2.最小与极小元

    定理24 一般的广义不等式(不是普通的不等式)不是线性序的,即任意两点不一定具有大小的可比性。因此,最大元和极小元在概念上不同。

    Def 26 最小元的定义:对于每个 y ∈ S y \in S yS,均有 x ≤ K y x\leq_Ky xKy,称x是S的最小元。(所有点都比他大)

    定理24*:如果一个集合有最小元(最大元),那么它们是唯一的。

    Def 27 极小元的定义:如果 y ∈ S , y ≤ K x y \in S,y\leq_Kx ySyKx 可以推出y=x,称x是S的极小元。(任何小于等于x的点是其本身)

    定理25*:一个集合可以有多个极小元(极大元)。

    ps.极小元和最小元的含义、图示
    示例:
    对称矩阵集合中的最小元和极小元:1.正定矩阵与椭圆的关系;2.包含特定点的最小和极小椭圆。

    2.6.对偶锥(极锥)与广义不等式

    2.6.1.对偶锥(极锥)

    Def 26 对偶锥的定义:K*={ y ∣ x T y ≥ 0 , 任 意 x ∈ K {y|x^Ty\geq0,任意x \in K} yxTy0,xK},其中K是锥。

    定理26 对偶锥K*是凸锥,即使K不是凸锥。

    ps.对偶锥的几何含义
    示例
    1.子空间的对偶锥是其正交补;
    2.非负象限的对偶锥是其本身(自对偶);
    3.半正定锥的对偶锥是其本身;
    4.范数锥的对偶

    定理27(对偶锥的性质)
    (1)K是闭凸锥;
    (2) K 1 ⊆ K 2 , 则 K 2 ∗ ⊆ K 2 ∗ K_1\subseteq K_2,则K^*_2\subseteq K^*_2 K1K2K2K2
    (3)如果K有非空内部,那么K
    是尖的;
    (4)如果K的闭包是尖的,那么K*有非空内部;
    (5)K**是K的凸包的闭包,如果K是闭凸的,则K **=K 。

    推论27:如果K是一个正常锥,那么它的对偶K*也是对偶锥(性质(1)(3)(4)),进一步,K**=K(性质(5))。

    2.6.2.广义不等式的对偶

    Def 27 广义不等式的对偶定义:正常锥的对偶锥得到的广义不等式(推论27:正常锥K的对偶锥K*是正常锥,且K**=K)

    定理28(广义不等式及其对偶的关系)
    (1) x ≤ K y x\leq_Ky xKy当且仅当对于任意 λ ≥ K 0 有 λ T x ≤ λ T y λ \geq_K 0有λ^Tx\leqλ^Ty λK0λTxλTy;
    (2) x < K y x<_Ky x<Ky当且仅当对于任意 λ > K 0 和 λ ≠ 0 λ >_K 0和λ \neq 0 λ>K0λ=0 λ T x ≤ λ T y λ^Tx\leqλ^Ty λTxλTy;
    (3) 以上两式中K*和K可以互换(由于K**=K)。

    示例:对比 “定理20:K是半正定锥”

    定理29(线性严格广义不等式的择一定理):严格线性不等式 A x < K b ( 2.17 ) Ax<_Kb(2.17) Ax<Kb2.17 λ ≠ 0 , λ ≥ K ∗ 0 , A T λ = 0 , λ T b ≤ 0 λ \neq 0,λ\geq_K*0,A^Tλ=0,λ^Tb\leq0 λ=0λK0ATλ=0λTb0(2.18)构成一对一择一选择,即对于任意A和b,两者中仅有一组有解。

    2.6.3.对偶不等式定义的最小元和极小元

    定理30(最小元的对偶性质) :(1)x是S上关于广义不等式 ≤ K \leq_K K的最小元的充要条件是对于所有 λ > K ∗ 0 λ>_K*0 λ>K0,x是在 z ∈ S z \in S zS上极小化 λ T z λ^Tz λTz的唯一最优解。
    (2)几何含义:对于任意 λ > K ∗ 0 λ>_K*0 λ>K0,超平面{ z ∣ λ T ( z − x ) = 0 z|λ^T(z-x)=0 zλT(zx)=0}是在x处对S的一个严格支撑超平面。

    定理31(极小元的对偶性质):(1)如果存在 λ > K ∗ 0 λ>_K*0 λ>K0并且x是在 z ∈ S z \in S zS上极小化 λ T z λ^Tz λTz,那么x是极小的;
    (2)逆命题不一定成立:S的极小元x可以对于任意λ都不是 z ∈ S z \in S zS上极小化 λ T z λ^Tz λTz的解;
    (3)添加凸性条件,逆定理成立:如果集合S是凸集,对于任意极小元x,存在非0的 λ ≥ K ∗ 0 λ\geq_K*0 λK0 使得x在在 z ∈ S z \in S zS上极小化 λ T z λ^Tz λTz
    (4)注意:性质(1)中的λ不能是 λ ≥ K ∗ 0 λ\geq_K*0 λK0,性质(3)中的λ不能是 λ > K ∗ 0 λ>_K*0 λ>K0(反例)

    示例:Pareto最优制造前沿

    展开全文
  • 组合最优化——凸集&凸函数

    千次阅读 2019-12-03 10:57:02
    1、凸集: 对于一个数集合D,对于其中的任何两个数x和y,构成一个点,以及我们所选的任何实数a,0,都有 a*x+(1-a)*y∈D 则证明集合D是一个凸集 **性质1:**有限个(或者无限个)凸集的交集为凸集 **性质2:**假设D...

    1、凸集:

    对于一个数集合D,对于其中的任何两个数x和y,构成一个点,以及我们所选的任何实数a,0<a<1,都有

    a*x+(1-a)*y∈D
    

    则证明集合D是一个凸集
    **性质1:**有限个(或者无限个)凸集的交集为凸集
    **性质2:**假设D是凸集,β是一个实数,则下面的集合是凸集

    β*D={y|y=β*x, x∈D}
    

    **性质3:**两个凸集的和集是凸集

    D1+D2={y|y=x+z,x∈D1,z∈D2}
    

    **推论1:**凸集的线性组合是凸集
    **推论2:**凸集中任意有限个点的凸组合仍然在该凸集中

    2、极点

    对于一个凸集D中的x,如果D中不存在两个相异的数y,z及某一个实数a,0<a<1,使得

    x=α*y+(1-α)*z
    

    则x为D的极点
    **性质1:**若D={x ∈Rn| ||x||≤a}(a>0),则||x||=a上的点均为极点

    证明:设||x||=a,若存在y,z ∈D及α∈(0,1),使
    得x=αy+(1-α)z.则 
    a2=||x||2=(αy+(1-α)z,αy+(1-α)z) 
    ≤α2||y||2+(1-α)2||z||2+2α (1-α)||y||||z||≤a2
    不等式取等号,必须||y||=||z||=a,且( y,z ) =||y||||z||,
    容易证明y=z=x,根据定义可知,x为极点.
    

    3、凸函数

    设函数f(x)定义在凸集D上,如果对应任意的x,y∈D,及任意的a∈[0,1]都有

    f (α x+(1-α)y) ≤ α f(x)+(1-α) f (y)
    

    则f(x)为凸集D上的凸函数
    同理,有严格凸函数的定义
    设函数f (x)定义在凸集D上,若对任意的x,y∈D,x≠y,及任意的α ∈(0,1)都有

    f (α x+(1-α)y) < α f(x)+(1-α) f (y)
    

    则称函数f (x)为凸集D上的严格凸函数
    最常见的严格凸函数是二次函数y=x^2
    **举例:**设f (x)=(x–1)^2,试证明f(x)在(–∞,+∞)上是严格凸函数.

    证明:设x,y∈ R,且x≠y, α∈(0,1)都有
     f (αx+(1-α)y)-(α f (x) +(1-α)f (y))
    =(αx+(1-α)y-1)2-α (x-1)2-(1-α) (y-1)2
    = –α (1-α)(x-y)2<0
    因此f(x)(–∞,+∞)上是严格凸函数.
    

    下面是判断凸函数的代码,采用的是随机数方法:

    import random as rn
    def hanshu(x):
        return float((x-1)*(x-1))
    
    if __name__=="__main__":
        a=float(input('请输入范围左端点横坐标'))
        b=float(input('请输入范围右端点横坐标'))
        c=float(input('请输入范围左端点纵坐标'))
        d=float(input('请输入范围右端点纵坐标'))
        flag=1
        for i in range(100):
            x=rn.uniform(a,b)
            y=rn.uniform(c,d)
            z=rn.uniform(0,1)
            if(hanshu(z*x+(1-z)*y)<(z*hanshu(x)+(1-z)*hanshu(y))):
                flag=1
            else:
                flag=0
                break
        if(flag==1):
            print('是凸函数')
        else:
            print('不是凸函数')
    

    这个代码是生成随机数进行100次测试,得到一个结果,如果更改循环的次数,准确率会更高
    **凸函数几何性质:**对一元函数f (x),在几何上α f (x1)+(1-α)f (x2)(0≤α≤1)表示连接(x1,f(x1)),(x2,f (x2))的线段, f(αx1+(1-α)x2)表示在点αx1+(1-α)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.
    个人感觉,这里的凸函数实际上就是我们初中时所学的“下凹函数”,当然,对于凸函数与凹函数,在学术界好像也没有特别严密的定义,每个学校都不一样,看自己啦~~
    **性质1:**设f(x)是凸集D Rn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数
    **性质2:**设f1(x), f2(x)是凸集D上的凸函数,实数λ,µ≥0,则λf1(x)+µ f2(x)也是D上的凸函数
    **性质3:**设f(x)是凸集D Rn上的凸函数,β为实数,则水平集S(f,β)={x|x∈D,f(x)≤β }是凸集。
    凸函数的判断:
    当然可以采用定义来判断,但这里似乎给出了更简单的判断方法:
    设f(x)定义在凸集D Rn上,x,y∈D. 令Φ (t)=f (tx+(1-t)y), t ∈ [0,1],则

    1f(x)是凸集D上的凸函数的充要条件是对任
    意的x ∈ D,一元函数Φ (t)[0,1]上的凸函数.
    2f(x)是凸集D上的严格凸函数的充要条件是
    对任意的x,y ∈ D(x≠y),一元函数Φ (t)[0,1]
    上的严格凸函数
    

    该定理的几何意义是:凸函数上任意两点之间的部分是一段向下凸的弧线.
    下面是这个判断方法的代码实现:

    import random as rn
    def hanshu(x):
        return float((x-1)*(x-1))
    
    def hanshuq(x,y,t):
        return float(hanshu(t*x+(1-t)*y))
    
    if __name__=="__main__":
        a=float(input('请输入范围左端点横坐标'))
        b=float(input('请输入范围右端点横坐标'))
        c=float(input('请输入范围左端点纵坐标'))
        d=float(input('请输入范围右端点纵坐标'))
        flag=1
        for i in range(100):
            x=rn.uniform(a,b)
            y=rn.uniform(c,d)
            x0=rn.uniform(0,1)
            y0=rn.uniform(0,1)
            z=rn.uniform(0,1)
            if(hanshuq(x,y,z*x0+(1-z)*y0)<(z*hanshuq(x,y,x0)+(1-z)*hanshuq(x,y,y0))):
                flag=1
            else:
                flag=0
                break
        if(flag==1):
            print('是凸函数')
        else:
            print('不是凸函数')
    

    不知道为什么,感觉更复杂了呢~
    一阶条件:
    1、设在凸集D Rn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y ∈ D,都有

    f(y)f(x)+ f(x)T(y-x)
    

    2、设在凸集D Rn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y ∈ D, x≠y,都有

    f(y)>f(x)+ f(x)T(y-x)
    

    二阶条件:

    设在开凸集D Rn上f(x)可微,1f(x)是D内的凸函数的充要条件为,在D内任
    一点x处, f(x)的Hesse矩阵G(x)半正定,其中
    

    在这里插入图片描述

    2、若在D内G(x)正定,f(x)在D内是严格凸函数.
    

    4、凸规划

    设D为凸集,则f(x)为D上的凸函数,则称规划问题
    min f(x)
    s.t. x ∈ D
    为凸规划问题.
    **定理1:**凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.
    **定理2:**若f(x)是D Rn上的严格凸函数,且凸规划问题
    min f(x)
    s.t. x ∈ D
    的整体极小点存在,则整体极小点唯一

    展开全文
  • 关于凸集的基础概念。
  • 凸集(Convex sets)

    2021-09-23 18:08:56
    凸集(Convex sets)1 仿射集(affine sets)和凸集(convex sets)1.1 直线(lines)和线段(line segments)1.2 仿射集 1 仿射集(affine sets)和凸集(convex sets) 1.1 直线(lines)和线段(line segments) ...
  • [最优化]凸集的定义与常见凸集

    万次阅读 2018-08-31 18:40:27
    凸集的定义与常见凸集 通常认为,如果某个实际问题可以表述为凸优化问题,那么事实上已经解决了这个问题,然而凸优化问题的识别还比较困难,本文将先介绍凸集的定义与常见凸集。 仿射集 如果集合 C⊆RnC⊆RnC\...
  • 凸集基本概念仿射集Affine Set凸集Convex Set凸组合Convex Combination凸包Convex Pull凸锥Convex cone超平面多面体保凸运算不等关系|支撑面对偶总结 基本概念 仿射集Affine Set 定义:集合内任意两个不同的点,都...
  • 仿射集合与凸集

    2021-09-12 13:29:06
    凸集convex set 对于任意 x 1 , x 2 ∈ C x_1,x_2\in C x1​,x2​∈C和满足 0 ≤ θ ≤ 1 0\leq\theta\leq 1 0≤θ≤1都有 θ x 1 + ( 1 − θ ) x 2 ∈ C \theta x_1+(1-\theta)x_2\in C θx1​+(1−θ)x2​∈C 则...
  • 关于凸集的证明

    2021-10-04 16:41:01
    关于凸集的证明 例题: 设C={x∈Rn∣xTAx+bTx+c≤0}C=\{x \in R^n|x^TAx+b^Tx+c \leq 0\}C={x∈Rn∣xTAx+bTx+c≤0},其中AAA为nnn阶对称矩阵,b∈Rnb \in R^nb∈Rn,c∈Rc \in Rc∈R,证明:当AAA正定时,CCC为凸集...
  • 仿射集&凸集

    千次阅读 2020-08-10 16:12:52
    本文要学习的主要内容是凸优化中的仿射集、凸集和凸锥的概念。 例一:给定两个点,如何描述一条直线? 给定两点x1≠x2∈Rn,θ∈R{x_1} \ne {x_2} \in R{^n},\theta \in Rx1​​=x2​∈Rn,θ∈R,这条直线可以描述...
  • 凸集、凸函数与凸规划

    千次阅读 2018-11-03 11:28:11
    凸集、凸函数、凸规划、一阶判别公式、二阶判别公式
  • 椭圆是一个凸集的证明

    千次阅读 2020-12-27 20:54:08
    椭圆是一个凸集的证明常见的凸集椭圆是凸集的证明从 norm 的角度去看 ellipsoid 常见的凸集 我们在 Affine set 和 convex set 的定义 一文中讲解了凸集(convex set)的概念。我们先来回顾一下凸集的定义: 如果连接...
  • 凸集和凸优化

    2019-11-07 00:27:49
    凸集和凸优化一、 凸集1. 凸集与仿射集的关系2. 凸集相关概念二、凸函数1. 定义2. 性质3. 凸函数举例4. 海森矩阵与泰勒展开式4.1 定理4.2 二元泰勒展开4.2 多元泰勒展开三、凸优化1. 凸优化问题的基本形式2. 借助...
  • 凸集几何

    2020-12-10 08:46:38
    凸集几何
  • Affine set: 线性方程组的所有解 • Halfspace: 不等式的所有解: 凸集的定理 ✅两个凸集的交集也是凸集(intersection of convex set is convex) 画图即可理解 凸函数定义 ✅函数的定义域 domf 为凸集,对于定义域...
  • 【第1章】凸集——保凸运算

    千次阅读 2020-05-05 11:37:05
    凸集——保凸运算3.保凸运算3.1交集3.2仿射函数3.3透视函数3.4 线性分数函数(转换后凸性质不变) Date: 2020/05/05 Editor:萧潇子(Jesse) Contact: 1223167600@qq.com 3.保凸运算 本节给出一些典型的保凸运算...
  • 凸优化学习(二)——凸集

    万次阅读 2019-03-16 16:48:36
    注意,本文内容来自于吴恩达老师cs229课堂笔记的...2. 凸集 我们从凸集的概念开始研究凸优化问题。 定义2.1 我们定义一个集合是凸的,当且仅当任意x,y∈Cx,y\in Cx,y∈C 且 θ∈R,0≤θ≤1\theta\in R, 0\le\theta...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,653
精华内容 1,861
关键字:

凸集