凸优化理论学习一|最优化及凸集的基本概念

---

一、优化问题

（一）数学优化

从本质上讲，人工智能的目标就是最优化——在复杂环境中与多体交互中做出最优决策。几乎所有的人工智能问题都会归结为一个优化问题。

• 优化目标：minimize $f_0(x)$
• 约束条件：
  • 非等式约束：$f_i(x)\le 0，i=1,...,m$
  • 等式约束：$g_i(x)=0，i=1,...,m$

将最优化问题用于求解最佳决策时，$x$代表决策，约束用于限制决策或对结果施加条件
将最优化问题用于求解最优模型时，$x$ 表示模型中的参数，约束对模型参数提出要求（例如，非负性）

最优化问题一般情况下不能得到完全的解决，但是可以尝试近似地解决它，而且通常无伤大雅。这个问题的例外情况是：凸优化问题。

一般非凸问题的传统技术通常会涉及到一定的妥协：

• 局部优化方法（非线性规划）
  • 在其附近的可行点中找到一个使 $f_0$ 最小的点
  • 可以处理大问题，例如神经网络训练
  • 需要初始猜测，并且通常需要算法参数微调
  • 不提供有关找到的点有多次优的信息
• 全局优化方法
  • 找到（全局）解决方案
  • 最坏情况的复杂性随着问题的规模呈指数级增长
  • 通常基于解决凸子问题

（二）凸优化

凸优化问题是特殊形式的优化问题，包括线性规划 (LP)、二次规划 (QP) 等，我们通常能够可靠、高效地解决这些问题。

• 优化目标：minimize $f_0(x)$
• 约束条件：
  • 非等式约束：$f_i(x)\le 0，i=1,...,m$
  • 等式约束：$Ax=b$

凸优化问题与最优化问题的对比：

• 凸优化问题的等式约束是线性的
• $f_0,...,f_m$是凸的：$\theta \in [0,1],f_i(\theta x+(1-\theta )y)\le \theta f_i(x)+(1-\theta )f_i(y)$

二、凸集

（一）一些标准凸集

仿射集包含通过集合中任意两个不同点的线（通过$x_1$、$x_2$两点的线：$x=\theta x_1+(1-\theta )x_2,\theta \in R$）

• 函数形式为f=Ax+b，则称函数是仿射的，即线性函数加常数的形式。
• 比如线性方程组的解 { x ∣ A x = b } \{x |Ax = b\} {x∣Ax=b}，并且每个仿射集都可以表示为线性方程组的解集
  

凸集包含集合中任意两点之间的线段（$x_1$和$x_2$两点间的线段：$x=\theta x_1+(1-\theta )x_2,0\le \theta \le 1$）

• 凸集满足对于$x_1,x_2\in C,0\le \theta \le 1$,有$\theta x_1+(1-\theta )x_2\in C$；
• 以下为一个凸集和两个非凸集的示意：
  

为什么$x=\theta x_1+(1-\theta )x_2$可以表示任意两点连接线段的所有点？将上式展开得：
$$x=\theta x_1+(1-\theta )x_2=\theta x_1+x_2-\theta x_2=\theta (x_1-x_2)+x_2$$

凸包： S 中所有点的凸组合的集合（$x_1,...,x_k$的凸组合：$x={\theta }_1{x}_1+{\theta }_2{x}_2+...+{\theta }_k{x}_k$，其中${\theta }_1+...+{\theta }_k=1,{\theta }_i\ge 0$）

凸锥体： 包含集合中点的所有圆锥组合的集合（$x_1$和$x_2$的圆锥组合：$x={\theta }_1{x}_1+{\theta }_2{x}_2$，且${\theta }_1\ge 0,{\theta }_2\ge 0$）

超平面： 形式为 { x ∣ a T x = b } \{x | a^T x = b\} {x∣aTx=b}的集合，其中 $a\ne 0$，半空间： 形式为 { x ∣ a T x ≤ b } \{x | a^T x \leq b\} {x∣aTx≤b}的集合，其中 $a\ne 0$。（a是法向量，超平面是仿射和凸的；半空间是凸的）

欧几里得球： B ( x c , r ) = { x ∣ ∣ ∣ x − x c ∣ ∣ 2 ≤ r } = { x c + r u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } B(x_c,r)=\{x|\ ||x-x_c||_2\leq r\} = \{x_c+ru|\ ||u||_2\leq1\} B(xc​,r)={x∣ ∣∣x−xc​∣∣2​≤r}={xc​+ru∣ ∣∣u∣∣2​≤1}

椭球： { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } = { x c + r u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } = { x c + A u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } \{x|\ (x-x_c)^T P^{-1}(x-x_c)\leq 1\} = \{x_c+ru|\ ||u||_2\leq1\} = \{x_c+Au|\ ||u||_2\leq1\} {x∣ (x−xc​)TP−1(x−xc​)≤1}={xc​+ru∣ ∣∣u∣∣2​≤1}={xc​+Au∣ ∣∣u∣∣2​≤1}，其中$P\in S_{++}^n$，也就是说P 对称正定，A平方且非奇异。

中心为 $x_c$，半径为 $r$ 的标准球： { x ∣ ∣ ∣ x − x c ∣ ∣ ≤ r } \{x|\ ||x − x_c|| ≤ r\} {x∣ ∣∣x−xc​∣∣≤r}

标准锥： $\{(x,t)|||x||\le t\}$

欧几里得范数锥： $\{(x,t)|||x|{|}_2\le t\}$

多面体 是有限多个线性不等式和等式的解集，也是有限数量的半空间和超平面的交集。 { x ∣ A x ≤ b , C x = d } \{x| Ax\leq b,Cx=d\} {x∣Ax≤b,Cx=d}

（二）保留凸性的运算

证明集合 C 凸性的方法：

• 基于定义：如果$x_1,x_2\in C,0\le \theta \le 1$，则有$\theta x_1+(1-\theta )x_2\in C$；
• 使用凸函数；
• 表明 C 是通过保留凸性的操作从简单凸集（超平面、半空间、范数球……）获得的；

交运算：（任意数量的）凸集的交集是凸的。

仿射映射：凸集的仿射映射也是凸的。（函数形式为f=Ax+b，则称函数是仿射的，即线性函数加常数的形式。）

（仿射变换就认为是一个矩阵变换，足球可以映射成一个橄榄球，依然是凸集。）

由仿射变换推出凸集的和也是凸集：

透视函数：凸集在透视下的像和逆像都是凸的（透视函数实际上就是对向量进行伸缩规范化）

线性分数函数是仿射映射函数和透视变换的复合函数，依然还是保凸运算，凸集在线性分数函数下的像和逆像都是凸的。从联合概率到条件概率的变换是一个线性分数函数。

（三）正常锥和广义不等式

正常锥的定义：如果凸锥体$K\subseteq R_n$满足如下条件，则称锥$K\subseteq R_n$为正常锥。

• K是凸的
• K是闭的
• K是实的，即K有非空的内部
• K是尖的，即K不包含任何直线

广义不等式满足类似普通不等式的性质，如传递性，反对称性等等。 广义不等式和普通不等式最大的区别是不是任意两点都是可比的。即$x\le y$ 和$y\le x$对于普通不等式二者必居其一。而对于广义不等式这不一定成立。所以最小，最大这些概念对于广义不等式变得很复杂。

（四）分离和支撑超平面

分离超平面：利用超平面将两个不相交的凸集分离开来，即得到超平面分离定理。

支撑超平面：如果C是凸的，那么在C的每个边界点都存在一个支持超平面。
支撑超平面不完全逆定理：如果一个集合是闭的，具有非空内部并且其边界上每个点均存在支撑超平面，那么它是凸的。

参考：
凸优化之保凸运算
广义不等式
【最优化理论与算法】数学预备知识、凸集和凸函数