凸优化（一）绪论与凸集

也可以前往 我的博客 查看原文

参考：

1. Stanford《convex optimization》
2. 中科大 凌青 凸优化

优化问题

优化问题：从一系列可行解集合中，寻找出最优的元素

优化问题的形式：

 minimize  f 0 ( x )  subject to  f i ( x ) ≤ b i \begin{array}{ll} \text{ minimize } & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leq b_i \end{array}  minimize  subject to ​f0​(x)fi​(x)≤bi​​

f 0 f_0 f0​是目标函数（ R n → R R^n \to R Rn→R）

优化问题在现实生活中各个领域都非常常见，深度学习中也是要使Loss最小，也是优化问题。

优化问题的分类

线性优化/非线性优化

（有时候也叫规划，和优化是一个意思）

目标函数由多个线性函数组合成，就是线性优化问题，否则就是非线性优化问题。

线性优化问题，最优解不是在顶点就是在整条边上

凸优化/非凸优化

凸优化：

 minimize  f 0 ( x )  subject to  f i ( x ) ≤ 0 , i = 1 , … , m a i T x = b i , i = 1 , … , p \begin{array}{ll} \text{ minimize } & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leq 0, \quad i=1, \ldots, m \\ & a_{i}^{T} x=b_{i}, \quad i=1, \ldots, p \end{array}  minimize  subject to ​f0​(x)fi​(x)≤0,i=1,…,maiT​x=bi​,i=1,…,p​

优化问题里面，比较好求解的是凸优化问题，非凸优化问题难解决

光滑/非光滑

目标函数每个点都可微就是光滑的，否则是非光滑的

连续/离散

按照可行域连续或者离散分类

单目标/多目标

对多个目标进行优化

这门课只研究单目标连续光滑的凸优化问题

判断是否为凸问题的一个关键，就是看约束集合、目标函数是否是凸集。所以凸集是凸优化问题最基本的一个概念。

仿射集 Affine set

集合中任取两个点，形成的直线，如果整条线上的点也都在集合中，那么称该集合为仿射集
要求任意两点连成的直线在集合中，也就是说

x 1 , x 2 ∈ C , θ ∈ R → θ x 1 + ( 1 − θ ) x 2 ∈ C x_1, x_2 \in C, \theta\in R \to \theta x_1 + (1- \theta)x_2 \in C x1​,x2​∈C,θ∈R→θx1​+(1−θ)x2​∈C

仿射组合：不仅限两个点，而是多个点：
x 1 , . . . x k ∈ C , θ 1 + . . . θ k = 1 → θ 1 x 1 + . . . θ k x k ∈ C x_1,...x_k \in C , \theta_1 + ... \theta_k = 1 \to \theta_1 x_1 + ... \theta_k x_k \in C x1​,...xk​∈C,θ1​+...θk​=1→θ1​x1​+...θk​xk​∈C

利用
( θ 1 + θ 2 ) ( θ 1 θ 1 + θ 2 x 1 + θ 2 θ 1 + θ 2 x 2 ) + ( 1 − θ 1 − θ 2 ) x 3 ∈ C (\theta_1 + \theta_2)(\frac{\theta_1}{\theta_1 + \theta_2}x_1 + \frac{\theta_2}{\theta_1 + \theta_2}x_2) + (1-\theta_1 - \theta_2)x_3 \in C (θ1​+θ2​)(θ1​+θ2​θ1​​x1​+θ1​+θ2​θ2​​x2​)+(1−θ1​−θ2​)x3​∈C即可证明

任意线性方程组 A x = b Ax = b Ax=b的解集都是仿射集，任意仿射集都可以写成线性方程组的解集

假设该线性方程组有两个解 x 1 , x 2 x_1, x_2 x1​,x2​，则直线上的任意一点 θ x 1 + ( 1 − θ ) x 2 \theta x_1+(1-\theta)x_2 θx1​+(1−θ)x2​代入得 A ( θ x 1 + ( 1 − θ ) x 2 ) = b A(\theta x_1+(1-\theta)x_2) = b A(θx1​+(1−θ)x2​)=b，说明也是该线性方程组的解

仿射包：从非仿射集合中构造一个最小的仿射集

比如两个点的集合不是仿射集，构造一个经过它们的直线，就是仿射集了，这条直线就是仿射包。三个不同直线的点，它们的最小的仿射包就是经过它们的二维平面。如果本身就是仿射集，那么仿射包就是它自己。

凸集 convex set

凸集相比于仿射集条件放松，要求任意两点连成的线段在集合中。凸集的定义为：

x 1 , x 2 ∈ C , θ ∈ [ 0 , 1 ] → θ x 1 + ( 1 − θ 2 ) x 2 ∈ C x_1, x_2 \in C, \theta\in[0,1] \to \theta x_1 + (1- \theta_2)x_2 \in C x1​,x2​∈C,θ∈[0,1]→θx1​+(1−θ2​)x2​∈C

仿射集必然是凸集，可以认为是一种特殊的凸集，凸集包含的更广。

凸组合：不仅限两个点，而是多个点：
x 1 , . . . x k ∈ C , θ 1 + . . . θ k = 1 , θ i ∈ [ 0 , 1 ] → θ 1 x 1 + . . . θ k x k ∈ C x_1,...x_k \in C , \theta_1 + ... \theta_k = 1, \theta_i\in[0,1] \to \theta_1 x_1 + ... \theta_k x_k \in C x1​,...xk​∈C,θ1​+...θk​=1,θi​∈[0,1]→θ1​x1​+...θk​xk​∈C

凸包：包含集合S的最小凸集

下图2.2，只有左边的凸多边形是凸集。不过如果右图只少了角点，是凸集，少了边上或者内部的点就不是凸集了。

下图2.3是凸包，包括一组离散点的凸包，以及非凸形状的凸包。

典型凸集

凸锥 Convex cone

锥： ∀ x ∈ C , θ ≥ 0 , θ x ∈ C \forall x \in C, \theta \geq 0, \theta x \in C ∀x∈C,θ≥0,θx∈C（锥尖需要在原点）

凸锥： x 1 , x 2 ∈ C , θ 1 x 1 + θ 2 x 2 ∈ C , θ 1 > 0 , θ 2 > 0 x_1, x_2 \in C, \theta_1 x_1 + \theta_2 x_2 \in C, \theta_1 > 0, \theta_2 > 0 x1​,x2​∈C,θ1​x1​+θ2​x2​∈C,θ1​>0,θ2​>0

图形理解，任取两点 x 1 , x 2 x_1, x_2 x1​,x2​，如果 x 1 , x 2 , o x_1,x_2,o x1​,x2​,o不在一条直线上，那么在 x 1 o x 2 ⌢ \overset{\frown}{x_1 o x_2} x1​ox2​⌢​的扇形区域内的所有的点都在凸锥集上

过原点的直线和原点发出的射线是凸锥

凸锥组合： x 1 , . . . x k ∈ C , θ 1 x 1 + . . . θ k x k ∈ C , θ 1 > 0 , . . . θ k > 0 x_1,... x_k \in C, \theta_1 x_1 + ... \theta_k x_k \in C, \theta_1 > 0, ... \theta_k > 0 x1​,...xk​∈C,θ1​x1​+...θk​xk​∈C,θ1​>0,...θk​>0

凸锥包：和前面一样，如下图所示

对比一下前面几种组合：
仿射组合： θ 1 + . . . + θ k = 1 \theta_1 + ... + \theta_k = 1 θ1​+...+θk​=1
凸组合： θ 1 + . . . + θ k = 1 , θ 1 , . . . , θ k > 0 \theta_1 + ... + \theta_k = 1, \theta_1, ... , \theta_k > 0 θ1​+...+θk​=1,θ1​,...,θk​>0
凸锥组合： θ 1 , . . . , θ k ≥ 0 \theta_1, ... , \theta_k \geq 0 θ1​,...,θk​≥0

超平面 Hyperplane

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

是仿射集，也是凸集，不一定凸锥（除非过原点）

半空间 Halfspace

{ x ∣ a T x ≤ b } \{ x|a^T x \leq b \} {x∣aTx≤b}

半空间是凸集，不是仿射集，不一定凸锥（除非过原点）

下图分别为超平面和半空间：

证明：
假设 x 1 , x 2 x_1, x_2 x1​,x2​在空间上：
a T x 1 ≤ b a^T x_1 \leq b aTx1​≤b
a T x 2 ≤ b a^T x_2 \leq b aTx2​≤b
对于 x 1 , x 2 x_1,x_2 x1​,x2​上的任意一点 θ x 1 + ( 1 − θ ) x 2 \theta x_1 + (1-\theta) x_2 θx1​+(1−θ)x2​有：
a T ( θ x 1 + ( 1 − θ ) x 2 ) = θ ( a T x 1 − b ) + ( 1 − θ ) ( a T x 2 − b ) + b ≤ b a^T(\theta x_1 + (1-\theta) x_2) = \theta (a^T x_1 -b) + (1-\theta) (a^T x_2 - b) +b \leq b aT(θx1​+(1−θ)x2​)=θ(aTx1​−b)+(1−θ)(aTx2​−b)+b≤b，也在集合中，所以半空间是凸集

法线的反方向

空间球 Euclidean Ball

欧几里得球，就是一个空间球

B ( x c , r ) = { x ∣ ∥ x − x c ∥ 2 ≤ r } = { x ∣ ( x − x c ) T ( x − x c ) ≤ r 2 } B\left(x_{c}, r\right)=\left\{x \mid\left\|x-x_{c}\right\|_{2} \leq r\right\}=\left\{x \mid\left(x-x_{c}\right)^{T}\left(x-x_{c}\right) \leq r^{2}\right\} B(xc​,r)={x∣∥x−xc​∥2​≤r}={x∣(x−xc​)T(x−xc​)≤r2}

证明：
假设 x 1 , x 2 x_1, x_2 x1​,x2​在空间上：
∣ ∣ x 1 − x c ∣ ∣ 2 ≤ r || x_1 - x_c ||_2 \leq r ∣∣x1​−xc​∣∣2​≤r
∣ ∣ x 2 − x c ∣ ∣ 2 ≤ r || x_2 - x_c ||_2 \leq r ∣∣x2​−xc​∣∣2​≤r
对于 x 1 , x 2 x_1,x_2 x1​,x2​上的任意一点$\theta x_1 + (1-\theta) x_2 ， （ 其 中 ，（其中 ，（其中\theta \in [0,1]$），有：
∣ ∣ θ x 1 + ( 1 − θ ) x 2 − x c ∣ ∣ r = ∣ ∣ θ ( x 1 − x c ) + ( 1 − θ ) ( x 2 − x c ) ∣ ∣ ≤ θ ∣ ∣ x 1 − x c ∣ ∣ 2 + ( 1 − θ ) ∣ ∣ x 2 − x c ∣ ∣ 2 ≤ r || \theta x_1 + (1-\theta) x_2 - x_c ||_r = || \theta (x_1 - x_c) + (1-\theta)(x_2 - x_c)||\newline \leq \theta ||x_1 - x_c||_2 + (1-\theta) ||x_2 - x_c||_2 \leq r ∣∣θx1​+(1−θ)x2​−xc​∣∣r​=∣∣θ(x1​−xc​)+(1−θ)(x2​−xc​)∣∣≤θ∣∣x1​−xc​∣∣2​+(1−θ)∣∣x2​−xc​∣∣2​≤r
这里用到了范数的三角不等式

范数性质
假设 x x x的范数是 f ( x ) f(x) f(x)， f ( x ) ≥ 0 f(x)\geq 0 f(x)≥0，满足下面三条性质：
if  f ( x ) = 0 → x = 0 \text{if}\ f(x)=0 \to x=0 if f(x)=0→x=0
k f ( x ) = ∣ k ∣ f ( x ) kf(x) = |k|f(x) kf(x)=∣k∣f(x)
f ( x + y ) ≤ f ( x ) + f ( y ) f(x+y) \leq f(x) + f(y) f(x+y)≤f(x)+f(y)（三角不等式）

椭球 Ellipsoids

E = { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } \mathcal{E}=\left\{x \mid\left(x-x_{c}\right)^{T} P^{-1}\left(x-x_{c}\right) \leq 1\right\} E={x∣(x−xc​)TP−1(x−xc​)≤1}

矩阵P是一个n*n的对称正定矩阵

（特征值，奇异值）

多面体 Polyhedra

多面体：有限个线性等式和不等式的解集
多面体是有限个半空间和超平面的交集

P = { x ∣ a j T x ≤ b j , j = 1 , … , m , c j T x = d j , j = 1 , … , p } \mathcal{P}=\left\{x \mid a_{j}^{T} x \leq b_{j}, j=1, \ldots, m, c_{j}^{T} x=d_{j}, j=1, \ldots, p\right\} P={x∣ajT​x≤bj​,j=1,…,m,cjT​x=dj​,j=1,…,p}

范数球 Norm Ball & 范数锥 Norm Cone

范数：满足以下条件的函数 ∣ ∣ ⋅ ∣ ∣ ||\cdot|| ∣∣⋅∣∣
1、 ∣ ∣ x ∣ ∣ ≥ 0 ||x||\geq 0 ∣∣x∣∣≥0， ∣ ∣ x ∣ ∣ = 0 ||x||=0 ∣∣x∣∣=0当且仅当 x = 0 x=0 x=0
2、 ∣ ∣ t x ∣ ∣ = t ∣ ∣ x ∣ ∣ ||tx|| = t||x|| ∣∣tx∣∣=t∣∣x∣∣，对于任何 t ∈ R t\in R t∈R成立
3、 ∣ ∣ x + y ∣ ∣ ≤ ∣ ∣ x ∣ ∣ + ∣ ∣ y ∣ ∣ ||x+y|| \leq ||x|| + ||y|| ∣∣x+y∣∣≤∣∣x∣∣+∣∣y∣∣

C = { ( x , t ) ∣ ∥ x ∥ ≤ t } ⊆ R n + 1 C=\{(x, t) \mid\|x\| \leq t\} \subseteq \mathbf{R}^{n+1} C={(x,t)∣∥x∥≤t}⊆Rn+1

其他的例子

n*n的对称矩阵组成的集合，是凸锥，也是凸集

n*n的半正定矩阵组成的集合，是凸集

n*n的正定矩阵组成的集合不是凸集（取值只能>=0，不属于正定了）

线性矩阵不等式的解集也是凸集

保凸运算

如果要证明是凸集可以用定义法，不过复杂情况会很难证明。
另一种方法是证明集合是多个凸集的保凸运算的简单组合，保凸运算包括以下几个：

交集 Intersection

C 1 C_1 C1​, C 2 C_2 C2​是凸集，其交集 C = C 1 ∩ C 2 C = C_1 \cap C_2 C=C1​∩C2​也一定是凸集。

拓展到n个也是。

仿射函数 Affine

f f f是仿射变换： R n → R m \mathbf{R}^{n} \rightarrow \mathbf{R}^{m} Rn→Rm

如果有 S ∈ R n S \in R^n S∈Rn是凸集，那么 f ( S ) = { f ( x ) ∣ x ∈ S } f(S)=\{f(x) \mid x \in S\} f(S)={f(x)∣x∈S}也是凸集，用定义证明即可。
逆函数 f − 1 ( S ) = { x ∣ f ( x ) ∈ S } f^{-1}(S)=\{x \mid f(x) \in S\} f−1(S)={x∣f(x)∈S}也是凸集。

透视函数 Perspective functions

透视函数 P : R n + 1 → R n P: \mathbf{R}^{n+1} \rightarrow \mathbf{R}^{n} P:Rn+1→Rn，相当于通过变换（所有元素除以最后一个元素）将最后一个维度的元素变为1，然后去掉这个维度的一种变换。降低一个维度。

P ( X , t ) = X / t , d o m P = ( X , t ) , t > 0 P(\mathbf{X}, t) = \mathbf{X}/t, dom P = {(\mathbf{X}, t), t > 0} P(X,t)=X/t,domP=(X,t),t>0
这里t是一个标量，X是矩阵，相当于P是dom(X)+1维度的，去掉最后一个维度t，X里的每一个元素除以t。

类比于针孔相机，3维的点 ( x 1 , x 2 , x 3 ) (x_1, x_2, x_3) (x1​,x2​,x3​)会通过孔映射到二维的平面 − ( x 1 / x 3 , x 2 / x 3 , 1 ) -(x_1/x_3, x_2/x_3, 1) −(x1​/x3​,x2​/x3​,1)上，就是一个透视函数的过程。

任意凸集的反透视映射也是凸集

线性分段函数 Linear-fractional

一个Linear-fractional function是由perspective function和一个affine function组成的

g ( x ) = [ A c T ] x + [ b d ] g(x)=\left[\begin{array}{c}A \\ c^{T}\end{array}\right] x+\left[\begin{array}{l}b \\ d\end{array}\right] g(x)=[AcT​]x+[bd​]

超平面分离定理与支撑超平面

超平面分离定理

如果 C C C和 D D D是两个不相交的凸集，那么必然存在一个超平面 { x ∣ a T x = b } \{x|a^Tx = b\} {x∣aTx=b}能够分离 C C C和 D D D，这超平面被称为分割超平面

支撑超平面

集合C边界上的点 x 0 x_0 x0​的支撑超平面： { x ∣ a T x = a T x 0 } \{x | a^Tx = a^T x_0\} {x∣aTx=aTx0​}

其中 a ≠ 0 a \neq 0 a​=0，对于所有的 x ∈ C x \in C x∈C满足 a T x ≤ a T x 0 a^Tx \leq a^T x_0 aTx≤aTx0​

如果 C C C是凸的，那么C边界上的每一个点都存在一个支撑超平面。