最优化理论与方法02-凸集

02-凸集

向量范数

范数（Norm） 是一种用于衡量向量或矩阵大小的数学函数。简单来说，范数可以理解为表示“距离”或“长度”的概念，用于评估向量或矩阵的大小或规模。

定义：

令记号\Vert \cdot \Vert: \mathbb{R}^n\rightarrow\mathbb{R}^+是一种非负函数，满足：

• 正定性：\Vert v\Vert\geq0
• 齐次性：\Vert \alpha v\Vert =|\alpha|\Vert v\Vert
• 三角不等式：\Vert v+w\Vert \leq \Vert v\Vert +\Vert w\Vert

最常用的向量范数即是我们熟知的\ell_p范数，且p\geq 1

\Vert v\Vert_p=\Bigg(\sum_{i=1}^{n}|v_i|^p\Bigg)^{\frac{1}{p}};

柯西不等式：|a^Tb|\leq \Vert a\Vert_2 \Vert b\Vert_2，等号成立是a和b线性相关。

矩阵范数

矩阵范数由向量范数推广得到的，

• \Vert A\Vert_1=\sum_{i,j}|A_{ij}|
• \Vert A\Vert_F=\sqrt{\sum_{i,j}A_{ij}^2}=\sqrt{\mathbf{Tr}(AA^T)}

“谱”其实是关于矩阵的特征值，矩阵的二范数不是所有元素平方（F-范数）

\Vert A\Vert_{p=2}=\max_{\Vert x\Vert_2=1}\Vert Ax\Vert_2=\sqrt{\lambda_\max(A^TA)}

1-范数是竖着的，所以是列和的最大值

\infty范数是横着的，所以是行和的最大值

• 核范数定义：

\Vert A\Vert _*=\sum_{i=1}^{r}\sigma_i

​ 也就是所有非零奇异值的和，r=\mathbf{rank}(A)

• 矩阵A，B的内积定义为：

\langle A, B \rangle = \text{Tr} (A B^\top) = \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} b_{ij}

• 柯西不等式，设A,B\in \mathbb{R}^{m\times n}

|\langle A, B\rangle |\leq \Vert A\Vert_F\Vert B\Vert_F

​ 等号成立当且仅当A和B线性相关

凸集的定义

在\mathbb{R}^n空间中，经过不同的两点x_1,x_2可以确定一条直线，方程为：

y=\theta x_1+(1-\theta)x_2,\theta\in\mathbb{R}

特别的，当\theta\in[0,1]的时候是线段，如下：

• 仿射集

  若过集合\mathcal{S}中的任意两点的直线都在\mathcal{S}内，则称\mathcal{S}为仿射集即：

  x_1,x_2\in\mathcal{S}\Rightarrow \theta x_1+(1-\theta)x_2\in\mathcal{S},\forall \theta \in \mathbb{R}

线性方程组Ax=b的解集\mathcal{X}是仿射集

因为\forall x_1,x_2\in\mathcal{X}(x_1\neq x_2)均满足\theta Ax_1+(1-\theta)Ax_2=b

• 凸集

  如果连接集合\mathcal{S}的任意两点的线段都在\mathcal{S}内，则称S为凸集，即

  x_1,x_2\in\mathcal{S}\Rightarrow \theta x_1+(1-\theta)x_2\in\mathcal{S},\forall \theta\in[0,1]

仿射集当然都是凸集

• 凸集的性质：

  定理（若\mathcal{S},\mathcal{T}都是凸集）：

  • k\mathcal{S}=\{ks\mid k\in\mathbb{R},s\in \mathcal{S}\}也是凸集
  • \mathcal{S+T}=\{s+t\mid s\in\mathcal{S},t\in \mathcal{T}\}也是凸集
  • \mathcal{S}\cap\mathcal{T}也是凸集
  • 凸集的内部和闭包都是凸集

• 凸组合

  形如：

  x=\theta_1 x_1+\theta_2x_2+\cdots +\theta_kx_k,\\\theta_1+\cdots+\theta_k=1,{\color{red}\theta_i\geq 0},i=1,\cdots,k.
  \\ \text{的点称为}x_1,\cdots,x_k\text{的凸组合}

凸组合知识在凸集中选择特定点进行线性组合得到的点，因此它是凸集的子集。

点集的凸包等价于该点集的所有凸组合。

• 凸包：集合\mathcal{S}的所有点的凸组合构成的点集为\mathcal{S}的凸包，记为\mathbf{conv}\mathcal{S}

• \mathbf{conv}\mathcal{S}是包含\mathcal{S}的最小凸集

• 仿射包

  仿射包和凸集定义很小，\theta的范围有所不同

  • 仿射组合的定义

  形如：

  x=\theta_1 x_1+\theta_2x_2+\cdots +\theta_kx_k,\\\theta_1+\cdots+\theta_k=1,{\color{red}\theta_i\in\mathbb{R}},i=1,\cdots,k.
  \\ \text{的点称为}x_1,\cdots,x_k\text{的仿射组合}

• 仿射包

  集合\mathcal{S}的所有点的仿射组合构成的点集为\mathcal{S}的仿射包，记为\mathbf{affine}S

  \mathbf{affine}S是包含\mathcal{S}的最小仿射集

仿射包直接将原集合拓展为了其所在的全平面

• 锥组合

  • 锥：对于集合\mathcal{S}中的任意点x和任意\theta\geq0都有\theta x\in \mathcal{S}

  相比于凸组合和仿射组合，锥组合不要求系数和为1，锥组合一般都是开放的

  • 锥组合 形如：

  x=\theta_1x_1+\cdots\theta_kx_k,\theta_i\geq0(i=1,\cdots,k).\\
  \text{的点称为}x_1,\cdots,x_k\text{的锥组合}

• 凸锥：若集合\mathcal{S}中的任意点的锥组合都在\mathcal{S}中，则称\mathcal{S}为凸锥

• 非凸锥的例子：坐标轴第一和第三象限的并集，y=|x|

  

上图显示了二维平面包含两点x_1,x_2的凸锥，可见两点若不共线，则形成的凸锥为一个半径无穷的圆的扇形部分。

重要的凸集举例

• 超平面：任取非零向量a\in\mathbb{R}^n，形如\{a\mid a^Tx=b\}的集合称为超平面
• 半空间：任取非零向量a\in\mathbb{R}^n，形如\{a\mid a^Tx\leq b\}的集合称为半空间

超平面是仿射集和凸集, 半空间是凸集但不是仿射集.

• 多面体：满足线性等式和不等式组的点的集合称为多面体，即

\{x\mid Ax\leq b,Cx=d\}

其中A\in \mathbb{R}^{m\times n},C\in\mathbb{R}^{p\times n}，x\leq y表示向量逐元素小于。

多面体是有限个半空间和超平面的交，所以也是凸集

• 范数球

  设空间中到某一定点x_c（称为中心）的距离小于等于定制r（称为半径）的点的集合为（范数）球，即：

  \mathrm{B}(x_c,r)=\{x\mid \Vert x-x_c\Vert\leq r\}=\{x_c+ru\mid \Vert u\Vert \leq 1\}

一般而言2-范数球

• 椭球

  形如：

  \{x\mid (x-x_c)^TP^{-1}(x-x_c)\leq 1\}=\{x_c+Au\mid \Vert u\Vert_2\leq 1\}

的集合为椭球，x_c为椭球中心，p对称正定，且A非奇异，可以认为是球仿射变换而来（A）

• 范数锥

  形如：

  \{(x,t)\mid \Vert x\Vert \leq t\}

当t=0的时候，是最下面的点；当t=1的时候，是最上面的圆

• 特殊矩阵集合和（半）正定锥

  （待完善）

• 半正定锥的例子：

  （二阶主子式忘记了）

保凸的运算

仿射变换的保凸性

Ax=b的解集是仿射集，任何一个仿射集可以由Ax=b来表示

仿射变换的保凸性： 设f:\mathbb{R}^n\rightarrow \mathbb{R}^m是仿射变换，即f(x)=Ax+b，A\in \mathbb{R}^{m\times n},b\in\mathbb{R}^m，那么有：

• 凸集在f下的像是凸集：\mathcal{S}\subseteq\mathbb{R}^n\text{是凸集}\Rightarrow f(\mathcal{S})=\{f(x)\mid x\in\mathcal{S}\text{是凸集}\}
• 凸集在f下的原像是凸集:\mathcal{C}\subseteq\mathbb{R}^m\text{是凸集}\Rightarrow f^{-1}(\mathcal{C})=\{f(x)\mid x\in\mathcal{C}\text{是凸集}\}

证明第一个：

\forall y_1,y_2\in f(\mathcal{S}),\exists x_1,x_2\in\mathcal{S}\\
Ax_1+b=y_1\\
Ax_2+b=y_2\\
\begin{align}
\forall \lambda\in[0,1],\quad & \quad\ \lambda y_1+(1-\lambda)y_2\in f(\mathcal{S})\\
&=\lambda(Ax_1+b)+(1-\lambda)(Ax_2+b)\\
&=A(\lambda x_1+(1-\lambda)x_2)+b\\
&\text{其中}A(\lambda x_1+(1-\lambda)x_2\in\mathcal{S}
\end{align}

例 线性矩阵不等式的解集

\{x\mid x_1A_1+\cdots +x_mA_m\preceq B\}(A_i,i=1,\cdots,m,B\in\mathcal{S}^p)

是凸集，这由仿射变换可以直接得到

老师方法：

\begin{align}
f(x)&=B-(x_1A_1+\cdots+x_mA_m)\\
&=B-A(x)
\end{align}

x_1,x_2,\cdots,x_m不是向量是数，B是个常量，(x_1A_1+\cdots+x_mA_m)是线性变换

要证明\{x\mid B-A(x)\in\mathcal{S}_+^n\}是凸集，B-A(x)是仿射变换，\mathcal{S}_+^n是凸集

注意：

• A\preceq B表示0\preceq B-A是半正定（\preceq的LaTeX为\preceq）
• A\prec B表示0\prec B-A是正定（\prec的LaTeX为\prec）
• 线性变换：

A(x_1+x_2)=A(x_1)+A(x_2)

A(kx)=kA(x)

• 仿射变换：

线性变换+常数

（GPT椭圆和圆的关系）

例 双曲锥

\{x\mid x^TPx\leq (c^Tx)^2,c^Tx\geq 0,P\in \mathcal{S}_+^n\}

是凸集

证明：双曲锥可以转化为二阶锥

二次锥：(\{(x,t)\mid \Vert x\Vert_2\leq t,t\geq 0\})

对x和t都进行仿射变换

(Ax+b,c^Tx+d)\Rightarrow \Vert Ax+b\Vert_2\leq c^Tx+d,c^Tx+d\geq 0
\\x^TPx=x^TA^TAx=\Vert Ax\Vert_2^2\leq c^Tx

\{x\mid \Vert Ax\Vert_2\leq c^Tx,c^Tx\geq 0,A^TA=P\}

而二阶锥可由二次锥\{(x,t)\}\mid\Vert x\Vert)2\leq t,t\geq 0经过仿射变换得到，所以均为凸集。

• 透视变换P:\mathbb{R}^{n+1}\rightarrow \mathbb{R}^n

P(x,t)=x/t,\quad \text{dom} P=\{(x,t)\mid t>0\}

透视变换下凸集的像和原像是凸集

• 分式线性变换f:\mathbb{R}^n\rightarrow \mathbb{R}^m

f(x)=\dfrac{Ax+b}{c^T+d}, \quad \mathbf{dom} f=\{x\mid c^T+d\gt 0\}

分式线性变换下的凸集的像和原像是凸集，分子分母都是仿射变换

分离超平面定理

超平面是空间中一类特殊的凸集(仿射集), 可以证明\mathbb{R}^n空间中的超平面 恰好是n − 1维的. 我们可以用超平面分离不相交的凸集.

分离超平面定理：如果\mathcal{C}和\mathcal{D}是不相交的凸集，则存在非零向量a和常数b，使得

a^Tx\leq b,\forall x\in\mathcal{C},

且

a^Tx\geq b,\forall x\in\mathcal{D}

即超平面\{\mid a^Tx=b\}分离了\mathcal{C}和\mathcal{D}

支撑超平面：

针对单个凸集来说的

给定集合\mathcal{C}以及边界上的点x_0，如果a\neq 0满足a^T\leq a^tx_0,\forall x\in\mathcal{C}，那么称集合

\{x\mid a^Tx=a^Tx_0\}

为\mathcal{C}在边界点x_0的的支撑超平面

支撑超平面定理：若\mathcal{C}是凸集，则\mathcal{C}的任意边界点都存在支撑超平面：