凸优化 - 快速指南
凸优化 - 简介
本课程对于想要解决各种工程和科学应用中出现的非线性优化问题的学生很有用。本课程从线性规划的基本理论开始，介绍凸集和函数的概念以及相关术语，以解释解决非线性规划问题所需的各种定理。本课程将介绍用于解决此类问题的各种算法。这类问题出现在各种应用中，包括机器学习、电气工程中的优化问题等。它要求学生具备高中数学概念和微积分的先验知识。
在本课程中，学生将学习解决诸如 $min f\left ( x \right )$ 等受某些约束的优化问题。
如果函数 $f\left ( x \right )$ 是线性函数并且约束是线性的，那么这些问题很容易解决。那么它被称为线性规划问题（LPP）。但如果约束是非线性的，那么上述问题就很难解决。除非我们可以在图表中绘制函数，否则尝试分析优化可以是一种方法，但如果函数超出三个维度，我们就无法绘制函数。因此出现了非线性规划或凸规划技术来解决此类问题。在这些教程中，我们将重点学习此类技术，最后介绍一些解决此类问题的算法。首先，我们将引入凸集的概念，它是凸规划问题的基础。然后随着凸函数的介绍，我们将介绍解决这些问题的一些重要定理以及基于这些定理的一些算法。
术语
空间 $\mathbb{R}^n$ − 是一个实数的 n 维向量，定义如下 − $\mathbb{R}^n=\left \{ \left ( x_1,x_2,... ,x_n \right )^{\tau }:x_1,x_2,....,x_n \in \mathbb{R} \right \}$
空间 $\mathbb{R}^{mXn}$ - 它是阶数为 $mXn$ 的所有实值矩阵的集合。
凸优化 - 线性规划
方法
线性规划也称为线性优化，是一种用于解决数学问题的技术，其中关系本质上是线性的。线性规划的基本性质是在某些约束下最大化或最小化目标函数。目标函数是从问题的数学模型获得的线性函数。约束是施加在模型上的条件，也是线性的。
- 从给定的问题中找出目标函数。
- 找到约束条件。
- 在图上画出约束条件。
- 找到由所有约束条件相交形成的可行区域。
- 找到可行区域的顶点。
- 求这些顶点处的目标函数的值。
- 最大化或最小化目标函数（根据问题）的顶点就是答案。
例子
第 1 步- 最大化 $5x+3y$，但须遵守
$x+y\leq 2$,
$3x+y\leq 3$,
$x\geq 0 \:和 y\geq 0$
解决方案-
第一步是找到图上的可行区域。
从图中可以清楚地看出，可行区域的顶点是
$\left ( 0, 0 \right )\left ( 0, 2 \right )\left ( 1, 0 \right )\left ( \frac{1}{2}, \frac{3}{2} \right )$
令 $f\left ( x, y \right )=5x+3y$
将这些值放入目标函数中，我们得到 -
$f\左 ( 0, 0 \右 )$=0
$f\左 ( 0, 2 \右 )$=6
$f\左 ( 1, 0 \右 )$=5
$f\left ( \frac{1}{2}, \frac{3}{2} \right )$=7
因此，函数在 $\left ( \frac{1}{2}, \frac{3}{2} \right )$ 处最大化
步骤 2 - 一家手表公司生产数字手表和机械手表。长期预测表明，每天预计需求至少 100 块数字手表和 80 块机械手表。由于产能限制，每天只能生产200只数字表和170只机械表。为了履行运输合同，每天至少要运输 200 块手表。
如果每售出一块数字手表会导致 $\$2$ 损失，但每块机械手表会产生 $\$5$ 利润，那么每种类型每天应该生产多少块才能使净利润最大化？
解决方案-
设 $x$ 为生产的数字手表的数量
$y$ 是生产的机械表的数量
根据问题，每天至少要生产100只电子表，最多可以生产200只电子表。
$\右箭头 100 \leq \:x\leq 200$
同样，每天至少生产80枚机械表，最多可制造170枚。
$\右箭头 80 \leq \:y\leq 170$
因为每天至少要生产 200 只手表。
$\右箭头 x +y\leq 200$
由于每售出一个数字手表会导致 $\$2$ 损失，但每个机械手表都会产生 $\$5$ 利润，
总利润可计算为
$利润 =-2x + 5y$
我们必须最大化利润，因此，问题可以表述为 -
最大化 $-2x + 5y$ 取决于
$100 \:\leq x\:\leq 200$
$80 \:\leq y\:\leq 170$
$x+y\:\leq 200$
将上述方程绘制在图表中，我们得到，
可行区域的顶点是
$\左 ( 100, 170\右 )\左 ( 200, 170\右 )\左 ( 200, 180\右 )\左 ( 120, 80\右 ) 和 \左 ( 100, 100\右 )$
目标函数的最大值在 $\left ( 100, 170\right )$ 处获得。因此，为了使净利润最大化，需要生产 100 块电子表和 170 块机械表。
凸优化 - 范数
范数是为向量或变量提供严格正值的函数。
范数是一个函数 $f:\mathbb{R}^n\rightarrow \mathbb{R}$
规范的基本特征是 -
设 $X$ 为向量，使得 $X\in \mathbb{R}^n$
$\左\| x \右\|\geq 0$
$\左\| x \right \|= 0 \Leftrightarrow x= 0\forall x \in X$
$\left \|\alpha x \right \|=\left | \alpha \right |\left \| x \right \|\forall \:x \in X 和 \:\alpha \:是 \:a \:标量$
$\左\| x+y \right \|\leq \left \| x \右\|+\左\| y \右\| \forall x,y \in X$
$\左\| xy \右\|\geq \左\| \左\| x \右\|-\左\| y \右\| \右\|$
根据定义，范数计算如下 -
$\左\| x \right \|_1=\displaystyle\sum\limits_{i=1}^n\left | x_i \右|$
$\左\| x \right \|_2=\left ( \displaystyle\sum\limits_{i=1}^n\left | x_i \right |^2 \right )^{\frac{1}{2}}$
$\左\| x \right \|_p=\left ( \displaystyle\sum\limits_{i=1}^n\left | x_i \right |^p \right )^{\frac{1}{p}},1 \leq p \leq \infty$
范数是连续函数。
证明
根据定义，如果 $x_n\rightarrow x$ 位于 $X\Rightarrow f\left ( x_n \right )\rightarrow f\left ( x \right ) $ 中，则 $f\left ( x \right )$ 是常函数。
令 $f\left ( x \right )=\left \| x \右\|$
因此，$\left | f\left ( x_n \right )-f\left ( x \right ) \right |=\left | \左\| x_n \右\| -\左\| x \right \|\right |\leq \left | \左 | x_n-x \右 | \:\右|$
由于 $x_n \rightarrow x$ 因此，$\left \| x_n-x \右\|\右箭头0$
因此 $\left | f\left ( x_n \right )-f\left ( x \right ) \right |\leq 0\Rightarrow \left | f\left ( x_n \right )-f\left ( x \right ) \right |=0\Rightarrow f\left ( x_n \right )\rightarrow f\left ( x \right )$
因此，范数是一个连续函数。
凸优化 - 内积
内积是一个为一对向量提供标量的函数。
内积 − $f:\mathbb{R}^n \times \mathbb{R}^n\rightarrow \kappa$ 其中 $\kappa$ 是标量。
内积的基本特征如下 -
令$X \in \mathbb{R}^n$
$\left \langle x,x \right \rangle\geq 0, \forall x \in X$
$\left \langle x,x \right \rangle=0\Leftrightarrow x=0, \forall x \in X$
$\left \langle \alpha x,y \right \rangle=\alpha \left \langle x,y \right \rangle,\forall \alpha \in \kappa \: 和\: \forall x,y \in X $
$\left \langle x+y,z \right \rangle =\left \langle x,z \right \rangle +\left \langle y,z \right \rangle, \forall x,y,z \in X$
$\left \langle \overline{y,x} \right \rangle=\left ( x,y \right ), \forall x, y \in X$
注意-
范数与内积的关系：$\left \| x \right \|=\sqrt{\left ( x,x \right )}$
$\forall x,y \in \mathbb{R}^n,\left \langle x,y \right \rangle=x_1y_1+x_2y_2+...+x_ny_n$
例子
1. 求 $x=\left ( 1,2,1 \right )\: 和 \: y=\left ( 3,-1,3 \right )$ 的内积
解决方案
$\左\langle x,y \右\rangle =x_1y_1+x_2y_2+x_3y_3$
$\left \langle x,y \right \rangle=\left ( 1\times3 \right )+\left ( 2\times-1 \right )+\left ( 1\times3 \right )$
$\left \langle x,y \right \rangle=3+\left ( -2 \right )+3$
$\左\langle x,y \右\rangle=4$
2. 如果 $x=\left ( 4,9,1 \right ),y=\left ( -3,5,1 \right )$ 且 $z=\left ( 2,4,1 \right )$，求$\左(x+y,z\右)$
解决方案
我们知道，$\left \langle x+y,z \right \rangle=\left \langle x,z \right \rangle+\left \langle y,z \right \rangle$
$\left \langle x+y,z \right \rangle=\left ( x_1z_1+x_2z_2+x_3z_3 \right )+\left ( y_1z_1+y_2z_2+y_3z_3 \right )$
$\left \langle x+y,z \right \rangle=\left \{ \left ( 4\times 2 \right )+\left ( 9\times 4 \right )+\left ( 1\times1 \right ) \右\}+$
$\left \{ \left ( -3\times2 \right )+\left ( 5\times4 \right )+\left ( 1\times 1\right ) \right \}$
$\left \langle x+y,z \right \rangle=\left ( 8+36+1 \right )+\left ( -6+20+1 \right )$
$\左\langle x+y,z \右\rangle=45+15$
$\左\langle x+y,z \右\rangle=60$
凸优化 - 最小值和最大值
局部最小值或最小化
$\bar{x}\in \:S$ 被称为函数 $f$ 的局部最小值，如果 $f\left ( \bar{x} \right )\leq f\left ( x \right ),\ forall x \in N_\varepsilon \left ( \bar{x} \right )$ 其中 $N_\varepsilon \left ( \bar{x} \right )$ 表示 $\bar{x}$ 的邻域，即 $ N_\varepsilon \left ( \bar{x} \right )$ 表示 $\left \| x-\bar{x} \right \|< \varepsilon$
局部最大值或最大化器
$\bar{x}\in \:S$ 被称为函数 $f$ 的局部最大值，如果 $f\left ( \bar{x} \right )\geq f\left ( x \right ), \ forall x \in N_\varepsilon \left ( \bar{x} \right )$ 其中 $N_\varepsilon \left ( \bar{x} \right )$ 表示 $\bar{x}$ 的邻域，即 $ N_\varepsilon \left ( \bar{x} \right )$ 表示 $\left \| x-\bar{x} \right \|< \varepsilon$
全局最小值
$\bar{x}\in \:S$ 被称为函数 $f$ 的全局最小值，如果 $f\left ( \bar{x} \right )\leq f\left ( x \right ), \对于所有 x \新元
全局最大值
$\bar{x}\in \:S$ 被称为函数 $f$ 的全局最大值，如果 $f\left ( \bar{x} \right )\geq f\left ( x \right ), \对于所有 x \新元
例子
步骤 1 - 找到 $f\left ( \bar{x} \right )=\left | 的局部最小值和最大值 x^2-4 \右|$
解决方案-
从上述函数的图中可以清楚地看出，局部最小值出现在 $x= \pm 2$ 处，局部最大值出现在 $x = 0$ 处
步骤 2 - 找到函数 $f\left (x \right )=\left | 的全局最小值 4x^3-3x^2+7 \右 |$
解决方案-
从上述函数的图表中可以清楚地看出，全局最小值出现在 $x=-1$ 处。
凸优化-凸集
设 $S\subseteq \mathbb{R}^n$ 如果连接集合 S 的任意两点的线段也属于 S，则称集合 S 是凸的，即，如果 $x_1,x_2 \in S$ ，则 $\lambda x_1+\left ( 1-\lambda \right )x_2 \in S$ ，其中 $\lambda \in\left ( 0,1 \right )$。
注意-
- 两个凸集的并集可能是也可能不是凸的。
- 两个凸集的交集始终是凸的。
证明
设$S_1$和$S_2$是两个凸集。
让 $S_3=S_1 \cap S_2$
让 $x_1,x_2 \in S_3$
由于 $S_3=S_1 \cap S_2$ 因此 $x_1,x_2 \in S_1$ 和 $x_1,x_2 \in S_2$
由于 $S_i$ 是凸集，$\forall$ $i \in 1,2,$
因此 $\lambda x_1+\left ( 1-\lambda \right )x_2 \in S_i$ 其中 $\lambda \in \left ( 0,1 \right )$
因此，$\lambda x_1+\left ( 1-\lambda \right )x_2 \in S_1\cap S_2$
$\Rightarrow \lambda x_1+\left ( 1-\lambda \right )x_2 \in S_3$
因此，$S_3$ 是凸集。
$\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$ 形式的加权平均值，其中 $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ 和 $\lambda_i\geq 0 ,\forall i \in \left [ 1,k \right ]$ 称为 $x_1,x_2,....x_k.$ 的圆锥组合
$\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$ 形式的加权平均值，其中 $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ 称为 $x_1 的仿射组合,x_2,....x_k.$
$\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$ 形式的加权平均值称为 $x_1,x_2,....x_k.$ 的线性组合
例子
步骤 1 - 证明集合 $S=\left \{ x \in \mathbb{R}^n:Cx\leq \alpha \right \}$ 是凸集。
解决方案
让 $x_1$ 和 $x_2 \in S$
$\Rightarrow Cx_1\leq \alpha$ 和 $\:and \:Cx_2\leq \alpha$
显示：$\:\:y=\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\in S \:\forall \:\lambda \in\left ( 0,1 \对）$
$Cy=C\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=\lambda Cx_1+\left ( 1-\lambda \right )Cx_2$
$\Rightarrow Cy\leq \lambda \alpha+\left ( 1-\lambda \right )\alpha$
$\右箭头 Cy\leq \alpha$
$\向右箭头 y\单位为 S$
因此，$S$ 是凸集。
步骤 2 - 证明集合 $S=\left \{ \left ( x_1,x_2 \right )\in \mathbb{R}^2:x_{1}^{2}\leq 8x_2 \right \}$ 是凸集。
解决方案
让 $x,y \in S$
设 $x=\left ( x_1,x_2 \right )$ 和 $y=\left ( y_1,y_2 \right )$
$\Rightarrow x_{1}^{2}\leq 8x_2$ 和 $y_{1}^{2}\leq 8y_2$
要显示 - $\lambda x+\left ( 1-\lambda \right )y\in S\Rightarrow \lambda \left ( x_1,x_2 \right )+\left (1-\lambda \right )\left ( y_1, y_2 \right ) \in S\Rightarrow \left [ \lambda x_1+\left ( 1- \lambda)y_2] \in S\right ) \right ]$
$现在，\left [\lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}=\lambda ^2x_{1}^{2}+\left ( 1-\lambda \right ) ^2y_{1}^{2}+2 \lambda\left ( 1-\lambda \right )x_1y_1$
但 $2x_1y_1\leq x_{1}^{2}+y_{1}^{2}$
所以，
$\left [ \lambda x_1 +\left ( 1-\lambda \right )y_1\right ]^{2}\leq \lambda ^2x_{1}^{2}+\left ( 1- \lambda \right ) ^2y_{1}^{2}+2 \lambda\left ( 1- \lambda \right )\left ( x_{1}^{2}+y_{1}^{2} \right )$
$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq \lambda x_{1}^{2}+\left ( 1- \lambda \right ) y_{1}^{2}$
$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq 8\lambda x_2+8\left ( 1- \lambda \right )y_2$
$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )y_1 \right ]^{2}\leq 8\left [\lambda x_2+\left ( 1- \lambda \right )y_2 \right ] $
$\Rightarrow \lambda x+\left ( 1- \lambda \right )y \in S$
步骤 3 - 证明集合 $S \in \mathbb{R}^n$ 是凸的，当且仅当对于每个整数 k，$S$ 的任何 k 个点的每个凸组合都在 $S$ 中。
解决方案
令 $S$ 为凸集。然后，展示；
$c_1x_1+c_2x_2+.....+c_kx_k \in S, \displaystyle\sum\limits_{1}^k c_i=1,c_i\geq 0, \forall i \in 1,2,....,k $
归纳证明
对于 $k=1,x_1 \in S，c_1=1 \Rightarrow c_1x_1 \in S$
对于 $k=2,x_1,x_2 \in S, c_1+c_2=1$ 并且由于 S 是凸集
$\右箭头 c_1x_1+c_2x_2 \in S.$
设S的m个点的凸组合在S中，即，
$c_1x_1+c_2x_2+...+c_mx_m \in S,\displaystyle\sum\limits_{1}^m c_i=1 ,c_i \geq 0, \forall i \in 1,2,...,m$
现在，令 $x_1,x_2...,x_m,x_{m+1} \in S$
设 $x=\mu_1x_1+\mu_2x_2+...+\mu_mx_m+\mu_{m+1}x_{m+1}$
令 $x=\left ( \mu_1+\mu_2+...+\mu_m \right )\frac{\mu_1x_1+\mu_2x_2+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}+\ mu_{m+1}x_{m+1}$
设 $y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}$
$\Rightarrow x=\left ( \mu_1+\mu_2+...+\mu_m \right )y+\mu_{m+1}x_{m+1}$
现在 $y \in S$ 因为系数之和为 1。
$\Rightarrow x \in S$ 因为 S 是凸集并且 $y,x_{m+1} \in S$
故用归纳法证明。
凸优化-仿射集
如果对于任何两个不同的点，通过这些点的线位于集合 $A$ 中，则集合 $A$ 被称为仿射集。
注意-
$S$ 是一个仿射集当且仅当它包含其点的每个仿射组合。
空集和单例集都是仿射集和凸集。
例如，线性方程的解是仿射集。
证明
令 S 为线性方程的解。
根据定义，$S=\left \{ x \in \mathbb{R}^n:Ax=b \right \}$
设 $x_1,x_2 \in S\Rightarrow Ax_1=b$ 和 $Ax_2=b$
证明：$A\left [ \theta x_1+\left ( 1-\theta \right )x_2 \right ]=b, \forall \theta \in\left ( 0,1 \right )$
$A\left [ \theta x_1+\left ( 1-\theta \right )x_2 \right ]=\theta Ax_1+\left ( 1-\theta \right )Ax_2=\theta b+\left ( 1-\theta \right )b=b$
因此S是仿射集。
定理
如果 $C$ 是仿射集且 $x_0 \in C$，则集合 $V= C-x_0=\left \{ x-x_0:x \in C \right \}$ 是 C 的子空间。
证明
令 $x_1,x_2 \in V$
显示：$\alpha x_1+\beta x_2 \in V$ 对于某些 $\alpha,\beta$
现在，根据 V 的定义，$x_1+x_0 \in C$ 和 $x_2+x_0 \in C$
现在， $\alpha x_1+\beta x_2+x_0=\alpha \left ( x_1+x_0 \right )+\beta \left ( x_2+x_0 \right )+\left ( 1-\alpha -\beta \right )x_0 $
但是 $\alpha \left ( x_1+x_0 \right )+\beta \left ( x_2+x_0 \right )+\left ( 1-\alpha -\beta \right )x_0 \in C$ 因为 C 是仿射集。
因此，$\alpha x_1+\beta x_2 \in V$
由此证明。
凸优化 - 赫尔
S 中点集的凸包是包含 S 内部或其边界上的所有点的最小凸区域的边界。
或者
设 $S\subseteq \mathbb{R}^n$ S 的凸包，记为 $Co\left ( S \right )$ ，是 S 的所有凸组合的集合，即 $x \in Co\left ( S \right )$ 当且仅当 $x \in \displaystyle\sum\limits_{i=1}^n \lambda_ix_i$，其中 $\displaystyle\sum\limits_{1}^n \lambda_i=1$ 且$\lambda_i \geq 0 \forall x_i \in S$
备注- 平面中 S 中的一组点的凸包定义了一个凸多边形，多边形边界上的 S 点定义了多边形的顶点。
定理$Co\left ( S \right )= \left \{ x:x=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i,x_i \in S, \displaystyle\sum\limits_{i=1 }^n \lambda_i=1,\lambda_i \geq 0 \right \}$ 证明凸包是凸集。
证明
设 $x_1,x_2 \in Co\left ( S \right )$，则 $x_1=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i$ 和 $x_2=\displaystyle\sum\limits_{i= 1}^n \lambda_\gamma x_i$ 其中 $\displaystyle\sum\limits_{i=1}^n \lambda_i=1、\lambda_i\geq 0$ 和 $\displaystyle\sum\limits_{i=1}^ n \gamma_i=1,\gamma_i\geq0$
对于 $\theta \in \left ( 0,1 \right ),\theta x_1+\left ( 1-\theta \right )x_2=\theta \displaystyle\sum\limits_{i=1}^n \lambda_ix_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n \gamma_ix_i$
$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n \lambda_i \theta x_i+\displaystyle\sum\limits_{i=1}^n \gamma_i\左 ( 1-\theta \right )x_i$
$\theta x_1+\left ( 1-\theta \right )x_2=\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \右]x_i$
考虑到系数，
$\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i\theta +\gamma_i\left ( 1-\theta \right ) \right ]=\theta \displaystyle\sum\limits_{i=1 }^n \lambda_i+\left ( 1-\theta \right )\displaystyle\sum\limits_{i=1}^n\gamma_i=\theta +\left ( 1-\theta \right )=1$
因此，$\theta x_1+\left ( 1-\theta \right )x_2 \in Co\left ( S \right )$
因此，凸包是凸集。
卡拉西奥多里定理
设 S 为 $\mathbb{R}^n$ 中的任意集合。如果 $x \in Co\left ( S \right )$，则 $x \in Co\left ( x_1,x_2,...., x_n,x_{n+1} \right )$。
证明
由于 $x \in Co\left ( S\right )$，则 $x$ 表示为 S 中有限个点的凸组合，即
$x=\displaystyle\sum\limits_{j=1}^k \lambda_jx_j,\displaystyle\sum\limits_{j=1}^k \lambda_j=1, \lambda_j \geq 0$ 和 $x_j \in S, \forall j \in \left ( 1,k \right )$
如果$k \leq n+1$，得到的结果显然是true。
如果 $k \geq n+1$，则 $\left ( x_2-x_1 \right )\left ( x_3-x_1 \right ),....., \left ( x_k-x_1 \right )$ 是线性相关的。
$\Rightarrow \exists \mu _j \in \mathbb{R}, 2\leq j\leq k$ (不全为零)使得 $\displaystyle\sum\limits_{j=2}^k \mu _j\left ( x_j-x_1 \right )=0$
定义$\mu_1=-\displaystyle\sum\limits_{j=2}^k \mu _j$，则$\displaystyle\sum\limits_{j=1}^k \mu_j x_j=0, \displaystyle\sum\限制_{j=1}^k \mu_j=0$
其中并非所有 $\mu_j's$ 都等于 0。由于 $\displaystyle\sum\limits_{j=1}^k \mu_j=0$，至少 $\mu_j > 0,1 \leq j \leq k$ 之一
然后，$x=\displaystyle\sum\limits_{1}^k \lambda_j x_j+0$
$x=\displaystyle\sum\limits_{1}^k \lambda_j x_j- \alpha \displaystyle\sum\limits_{1}^k \mu_j x_j$
$x=\displaystyle\sum\limits_{1}^k\left (\lambda_j- \alpha\mu_j \right )x_j $
选择 $\alpha$ 使得 $\alpha=min\left \{ \frac{\lambda_j}{\mu_j}, \mu_j\geq 0 \right \}=\frac{\lambda_j}{\mu _j},$对于某些 $i=1,2,...,k$
如果 $\mu_j\leq 0, \lambda_j-\alpha \mu_j\geq 0$
如果 $\mu_j> 0，则 \:\frac{\lambda _j}{\mu_j}\geq \frac{\lambda_i}{\mu _i}=\alpha \Rightarrow \lambda_j-\alpha \mu_j\geq 0， j=1,2,...k$
特别是，$\lambda_i-\alpha \mu_i=0$，根据 $\alpha$ 的定义
$x=\displaystyle\sum\limits_{j=1}^k \left ( \lambda_j- \alpha\mu_j\right )x_j$，其中
$\lambda_j- \alpha\mu_j\geq0$ 和 $\displaystyle\sum\limits_{j=1}^k\left ( \lambda_j- \alpha\mu_j\right )=1$ 和 $\lambda_i- \alpha\ mu_i=0$
因此，x可以表示为最多(k-1)个点的凸组合。
可以重复这个归约过程，直到 x 被表示为 (n+1) 个元素的凸组合。
凸优化 - 维尔斯特拉斯定理
设 S 为 $\mathbb{R}^n$ 中的非空闭有界集（也称为紧集），并设 $f:S\rightarrow \mathbb{R} $ 为 S 上的连续函数，则问题 min $\left \{ f\left ( x \right ):x \in S \right \}$ 达到最小值。
证明
由于 S 是非空且有界的，因此存在下界。
$\alpha =Inf\left \{ f\left ( x \right ):x \in S \right \}$
现在令 $S_j=\left \{ x \in S:\alpha \leq f\left ( x \right ) \leq \alpha +\delta ^j\right \} \forall j=1,2,... $ 和 $\delta \in \left ( 0,1 \right )$
根据 infimium 的定义，对于每个 $j$，$S_j$ 都是非空的。
选择一些$x_j \in S_j$ 得到序列$\left \{ x_j \right \}$ for $j=1,2,...$
由于S是有界的，所以序列也是有界的，并且存在一个收敛子序列$\left \{ y_j \right \}$，它收敛到$\hat{x}$。因此 $\hat{x}$ 是一个极限点，并且 S 是闭合的，因此，$\hat{x} \in S$。由于 f 是连续的，$f\left ( y_i \right )\rightarrow f\left ( \hat{x} \right )$。
由于 $\alpha \leq f\left ( y_i \right )\leq \alpha+\delta^k, \alpha=\displaystyle\lim_{k\rightarrow \infty}f\left ( y_i \right )=f\left ( \帽子{x} \右)$
因此，$\hat{x}$ 是最小化解。
评论
维尔斯特拉斯定理成立有两个重要的必要条件。这些如下 -
步骤 1 - 集合 S 应该是有界集合。
考虑函数 f\left ( x \right )=x$。
它是一个无界集合，并且在其域中的任何点都有最小值。
因此，为了获得最小值，S 应该有界。
步骤 2 - 集合 S 应该是闭合的。
考虑域 \left ( 0,1 \right ) 中的函数 $f\left ( x \right )=\frac{1}{x}$ 。
该函数在给定域中不是封闭的，并且其最小值也不存在。
因此，为了获得最小值，S 应该关闭。
凸优化 - 最近点定理
设S为$\mathbb{R}^n$中的非空闭凸集，并令$y\notin S$，则$\存在$S$中的一个点$\bar{x}\，其最小距离为y，即$\left \| y-\bar{x} \右\| \leq \左\| yx \右\| \forall x \in S.$
此外，$\bar{x}$ 是最小化点当且仅当 $\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq 0$ 或 $\left ( y-\hat{x}, x-\hat{x} \right )\leq 0$
证明
最近点的存在性
由于$S\ne \phi,\在S$中存在$一个点$\hat{x}\，使得S到y的最小距离小于或等于$\left \| y-\hat{x}\right\|$。
定义 $\hat{S}=S \cap \left \{ x:\left \| yx \右\|\leq \左\| y-\hat{x} \right \| \右\}$
由于 $ \hat{S}$ 是闭有界的，并且由于范数是连续函数，因此根据 Weierstrass 定理，在 S$ 中存在一个最小点 $\hat{x} \ 使得 $\left \| y-\hat{x} \right \|=Inf\left \{ \left \| yx \right \|,x \in S \right \}$
独特性
假设 $\bar{x} \in S$ 使得 $\left \| y-\hat{x} \right \|=\left \| y-\hat{x} \right \|= \alpha$
由于 S 是凸的，$\frac{\hat{x}+\bar{x}}{2} \in S$
但是，$\left\| y-\frac{\hat{x}-\bar{x}}{2} \right \|\leq \frac{1}{2}\left \| y-\hat{x} \right \|+\frac{1}{2}\left \| y-\bar{x} \right \|=\alpha$
它不可能是严格的不等式，因为 $\hat{x}$ 最接近 y。
因此，$\left\| y-\hat{x} \right \|=\mu \left \| y-\hat{x} \right \|$，对于某些 $\mu$
现在$\左\| \mu \right \|=1.$ 如果 $\mu=-1$，则 $\left ( y-\hat{x} \right )=-\left ( y-\hat{x} \right )\右箭头 y=\frac{\hat{x}+\bar{x}}{2} \in S$
但是$y \in S$。因此矛盾。因此 $\mu=1 \Rightarrow \hat{x}=\bar{x}$
因此，最小化点是唯一的。
对于证明的第二部分，假设 $\left ( y-\hat{x} \right )^{\tau }\left ( x-\bar{x} \right )\leq 0$ 对于所有 $x\单位：新元
现在，
$\左\| yx \右\|^{2}=\左\| y-\hat{x}+ \hat{x}-x\right \|^{2}=\left \| y-\hat{x} \right \|^{2}+\left \|\hat{x}-x \right \|^{2}+2\left (\hat{x}-x \right ) ^{\tau }\left ( y-\hat{x} \right )$
$\右箭头\左\| yx \右\|^{2}\geq \左\| y-\hat{x} \right \|^{2}$ 因为 $\left \| \hat{x}-x \right \|^{2}\geq 0$ 和 $\left ( \hat{x}- x\right )^{T}\left ( y-\hat{x} \right )\geq 0$
因此，$\hat{x}$ 是最小化点。
相反，假设 $\hat{x}$ 是最小化点。
$\右箭头\左\| yx \右\|^{2}\geq \左\| y-\hat{x} \right \|^2 \forall x \in S$
由于 S 是凸集。
$\Rightarrow \lambda x+\left ( 1-\lambda \right )\hat{x}=\hat{x}+\lambda\left ( x-\hat{x} \right ) \in S$ for $x \in S$ 和 $\lambda \in \left ( 0,1 \right )$
现在，$\left \| y-\hat{x}-\lambda\left ( x-\hat{x} \right ) \right \|^{2}\geq \left \| y-\hat{x} \right \|^2$
和
$\左\| y-\hat{x}-\lambda\left ( x-\hat{x} \right ) \right \|^{2}=\left \| y-\hat{x} \right \|^{2}+\lambda^2\left \| x-\hat{x} \right \|^{2}-2\lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )$
$\右箭头\左\| y-\hat{x} \right \|^{2}+\lambda^{2}\left \| x-\hat{x} \right \|-2 \lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\geq \left \ | y-\hat{x} \right \|^{2}$
$\Rightarrow 2 \lambda\left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq \lambda^2\left \| x-\hat{x} \right \|^2$
$\Rightarrow \left ( y-\hat{x} \right )^{T}\left ( x-\hat{x} \right )\leq 0$
故得证。
基本分离定理
设 S 为 $\mathbb{R}^n$ 和 $y \notin S$ 中的非空闭凸集。那么，存在一个非零向量 $p$ 和标量 $\beta$，使得对于每个 $x \in S$，$p^T y>\beta$ 和 $p^T x < \beta$
证明
由于 S 是非空闭凸集，并且 $y \notin S$ 因此根据最近点定理，存在唯一的最小化点 $\hat{x} \in S$ 使得
$\left ( x-\hat{x} \right )^T\left ( y-\hat{x} \right )\leq 0 \forall x \in S$
设 $p=\left ( y-\hat{x} \right )\neq 0$ 且 $\beta=\hat{x}^T\left ( y-\hat{x} \right )=p^T \帽子{x}$。
然后 $\left ( x-\hat{x} \right )^T\left ( y-\hat{x} \right )\leq 0$
$\Rightarrow \left ( y-\hat{x} \right )^T\left ( x-\hat{x} \right )\leq 0$
$\Rightarrow \left ( y-\hat{x} \right )^Tx\leq \left ( y-\hat{x} \right )^T \hat{x}=\hat{x}^T\left ( y-\hat{x} \right )$ 即 $p^Tx \leq \beta$
另外，$p^Ty-\beta=\left ( y-\hat{x} \right )^Ty-\hat{x}^T \left ( y-\hat{x} \right )$
$=\left ( y-\hat{x} \right )^T \left ( yx \right )=\left \| y-\hat{x} \right \|^{2}>0$
$\右箭头 p^Ty> \beta$
该定理导致分离超平面。基于上述定理的超平面可以定义如下 -
设 $S_1$ 和 $S_2$ 是 $\mathbb{R}$ 的非空子集，$H=\left \{ X:A^TX=b \right \}$ 是超平面。
如果 $A^TX \leq b \forall X \in S_1$ 和 $A_TX \geq b \forall X \in S_2$，则称超平面 H 分隔 $S_1$ 和 $S_2$
如果 $A^TX < b \forall X \in S_1$ 且 $A_TX > b \forall X \in S_2$，则超平面 H 被称为严格分离 $S_1$ 和 $S_2$
如果 $A^TX \leq b \forall X \in S_1$ 和 $A_TX \geq b+ \varepsilon \forall X \in S_2$，则超平面 H 被认为是强分离 $S_1$ 和 $S_2$，其中 $\varepsilon $ 是正标量。
凸优化 - 锥体
如果 $x \in C\Rightarrow \lambda x \in C \forall \lambda \geq 0$，$\mathbb{R}^n$ 中的非空集合 C 被称为顶点为 0 的圆锥体。
如果集合 C 既是凸锥又是凸锥，则它是凸锥。
例如，$y=\left | x \right |$ 不是凸锥，因为它不是凸的。
但是，$y \geq \left | x \right |$ 是凸锥体，因为它既是凸锥体又是锥体。
注意- 锥体 C 是凸的当且仅当对于任何 $x,y \in C, x+y \in C$。
证明
由于 C 是圆锥体，对于 $x,y \in C \Rightarrow \lambda x \in C$ 和 $\mu y \in C \:\forall \:\lambda, \mu \geq 0$
C 是凸的，如果 $\lambda x + \left ( 1-\lambda \right )y \in C \: \forall \:\lambda \in \left ( 0, 1 \right )$
由于 C 是圆锥体，因此 $\lambda x \in C$ 和 $\left ( 1-\lambda \right )y \in C \Leftrightarrow x,y \in C$
因此 C 是凸的，如果 $x+y \in C$
一般来说，如果 $x_1,x_2 \in C$，则 $\lambda_1x_1+\lambda_2x_2 \in C, \forall \lambda_1,\lambda_2 \geq 0$
例子
$\mathbb{R}^n$ 中无限向量集的圆锥组合是凸圆锥。
任何空集都是凸锥体。
任何线性函数都是凸锥体。
由于超平面是线性的，因此它也是凸锥体。
闭半空间也是凸锥体。
注- 两个凸锥体的交集是凸锥体，但它们的并集可能是也可能不是凸锥体。
凸优化 - 极锥
设 S 为 $\mathbb{R}^n$ 中的非空集合，则 $S^*$ 表示的 S 的极锥由 $S^*=\left \{p \in \mathbb{R }^n, p^Tx \leq 0 \: \forall x \in S \right \}$。
评论
即使 S 不凸，极锥也始终是凸的。
如果S是空集，则$S^*=\mathbb{R}^n$。
极性可以被视为正交性的概括。
设 $C\subseteq \mathbb{R}^n$ 则 C 的正交空间表示为 $C^\perp =\left \{ y \in \mathbb{R}^n:\left \langle x,y \right \rangle=0 \forall x \in C \right \}$。
引理
设 $S,S_1$ 和 $S_2$ 为 $\mathbb{R}^n$ 中的非空集，则以下陈述成立 -
$S^*$ 是一个封闭的凸锥体。
$S \subseteq S^{**}$ 其中 $S^{**}$ 是 $S^*$ 的极锥。
$S_1 \subseteq S_2 \Rightarrow S_{2}^{*} \subseteq S_{1}^{*}$。
证明
步骤 1 − $S^*=\left \{ p \in \mathbb{R}^n,p^Tx\leq 0 \: \forall \:x \in S \right \}$
设 $x_1,x_2 \in S^*\Rightarrow x_{1}^{T}x\leq 0 $ 和 $x_{2}^{T}x \leq 0,\forall x \in S$
对于 $\lambda \in \left ( 0, 1 \right ),\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]^Tx=\left [ \left ( \lambda x_1 \right )^T+ \left \{\left ( 1-\lambda \right )x_{2} \right \}^{T}\right ]x, \forall x \in S$
$=\left [ \lambda x_{1}^{T} +\left ( 1-\lambda \right )x_{2}^{T}\right ]x=\lambda x_{1}^{T}x+ \left ( 1-\lambda \right )x_{2}^{T}\leq 0$
因此 $\lambda x_1+\left ( 1-\lambda \right )x_{2} \in S^*$
因此$S^*$是凸集。
对于 $\lambda \geq 0,p^{T}x \leq 0, \forall \:x \in S$
因此，$\lambda p^T x \leq 0,$
$\Rightarrow \left ( \lambda p \right )^T x \leq 0$
$\Rightarrow \lambda p \in S^*$
因此，$S^*$ 是一个圆锥体。
显示$S^*$ 是闭合的，即显示如果$p_n \rightarrow p$ 为$n \rightarrow \infty$，则$p \in S^*$
$\forall x \in S, p_{n}^{T}xp^T x=\left ( p_n-p \right )^T x$
作为 $p_n \rightarrow p$ 作为 $n \rightarrow \infty \Rightarrow \left ( p_n \rightarrow p \right )\rightarrow 0$
因此$p_{n}^{T}x \rightarrow p^{T}x$。但 $p_{n}^{T}x \leq 0, \: \forall x \in S$
因此，$p^Tx \leq 0, \forall x \in S$
$\右箭头 p \in S^*$
因此，$S^*$ 被关闭。
步骤 2 − $S^{**}=\left \{ q \in \mathbb{R}^n:q^T p \leq 0, \forall p \in S^*\right \}$
设 $x \in S$，则 $ \forall p \in S^*, p^T x \leq 0 \Rightarrow x^Tp \leq 0 \Rightarrow x \in S^{**}$
因此，$S \subseteq S^{**}$
步骤 3 − $S_2^*=\left \{ p \in \mathbb{R}^n:p^Tx\leq 0, \forall x \in S_2 \right \}$
由于 $S_1 \subseteq S_2 \Rightarrow \forall x \in S_2 \Rightarrow \forall x \in S_1$
因此，如果 $\hat{p} \in S_2^*，$则 $\hat{p}^Tx \leq 0,\forall x \in S_2$
$\Rightarrow \hat{p}^Tx\leq 0, \forall x \in S_1$
$\Rightarrow \hat{p}^T \in S_1^*$
$\Rightarrow S_2^* \subseteq S_1^*$
定理
设C为非空闭凸锥，则$C=C^**$
证明
$C=C^{**}$ 通过前面的引理。
证明：$x \in C^{**} \subseteq C$
令$x \in C^{**}$ 并令$x \notin C$
然后根据基本分离定理，存在向量 $p \neq 0$ 和标量 $\alpha$ 使得 $p^Ty \leq \alpha, \forall y \in C$
因此，$p^Tx > \alpha$
但由于 $\left ( y=0 \right ) \in C$ 和 $p^Ty\leq \alpha, \forall y \in C \Rightarrow \alpha\geq 0$ 和 $p^Tx>0$
如果 $p \notin C^*$，则 C$ 中存在一些 $\bar{y} \，使得 $p^T \bar{y}>0$ 且 $p^T\left ( \lambda \bar {y} \right )$ 可以通过使 $\lambda$ 足够大而变得任意大。
这与 $p^Ty \leq \alpha, \forall y \in C$ 的事实相矛盾
因此，$p \in C^*$
由于 $x \in C^*=\left \{ q:q^Tp\leq 0, \forall p \in C^* \right \}$
因此，$x^Tp \leq 0 \Rightarrow p^Tx \leq 0$
但是 $p^Tx> \alpha$
这就是矛盾。
因此，$x \in C$
因此$C=C^{**}$。
凸优化 - 圆锥组合
$\alpha_1x_1+\alpha_2x_2+....+\alpha_nx_n$ 与 $\alpha_1, \alpha_2,...,\alpha_n\geq 0$ 形式的点称为 $x_1, x_2,..., x_n.$
如果 $x_i$ 在凸圆锥 C 中，则 $x_i$ 的每个圆锥组合也在 C 中。
如果集合 C 包含其元素的所有圆锥组合，则它是凸圆锥。
圆锥形船体
圆锥包被定义为给定集合 S 的所有圆锥组合的集合，并用 coni(S) 表示。
因此， $coni\left ( S \right )=\left \{ \displaystyle\sum\limits_{i=1}^k \lambda_ix_i:x_i \in S,\lambda_i\in \mathbb{R}, \lambda_i\ geq 0,i=1,2,...\右\}$
- 圆锥壳是凸集。
- 原点始终属于圆锥壳。
凸优化 - 多面体集
$\mathbb{R}^n$ 中的集合如果是有限数量的闭半空间的交集，则称为多面体，即
$S=\left \{ x \in \mathbb{R}^n:p_{i}^{T}x\leq \alpha_i, i=1,2,....,n \right \}$
例如，
$\left \{ x \in \mathbb{R}^n:AX=b \right \}$
$\left \{ x \in \mathbb{R}^n:AX\leq b \right \}$
$\left \{ x \in \mathbb{R}^n:AX\geq b \right \}$
多面锥体
$\mathbb{R}^n$ 中的集合如果是包含原点的有限个半空间的交集，则称为多面体锥体，即 $S=\left \{ x \in \mathbb{ R}^n:p_{i}^{T}x\leq 0, i=1, 2,... \right \}$
多面体
多面体是有界的多面体集合。
评论
- 多面体是有限点集的凸包。
- 多面体锥体由有限的向量集生成。
- 多面体集是闭集。
- 多面体集是凸集。
凸集的极值点
令 S 为 $\mathbb{R}^n$ 中的凸集。向量 $x \in S$ 被称为 S 的极值点，如果 $x= \lambda x_1+\left ( 1-\lambda \right )x_2$ 且 $x_1, x_2 \in S$ 和 $\lambda \ in\left ( 0, 1 \right )\Rightarrow x=x_1=x_2$。
例子
步骤 1 − $S=\left \{ \left ( x_1,x_2 \right ) \in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}\leq 1 \对\}$
极值点，$E=\left \{ \left ( x_1, x_2 \right )\in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}= 1 \right \}$
步骤 2 − $S=\left \{ \left ( x_1,x_2 \right )\in \mathbb{R}^2:x_1+x_2< 2, -x_1+2x_2\leq 2, x_1,x_2\geq 0 \对\}$
极值点，$E=\left \{ \left ( 0, 0 \right), \left ( 2, 0 \right), \left ( 0, 1 \right), \left ( \frac{2}{3 }, \frac{4}{3} \right) \right \}$
步骤 3 - S 是由点 $\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ), \left ( 1,3 \right ), \left ( - 2,4 \right ),\left ( 0,2 \right ) \right \}$
极值点，$E=\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ),\left ( 1,3 \right ),\left ( -2,4 \right ) \右\}$
评论
凸集S的任意点都可以表示为其极值点的凸组合。
仅适用于 $\mathbb{R}^n$ 中的闭集和有界集。
对于无界集合来说可能不成立。
k个极值点
凸集中的点称为k极值当且仅当它是S内k维凸集的内点，并且不是S内(k+1)维凸集的内点。基本上，对于凸集 S，k 个极值点构成 k 维开放面。
凸优化 - 方向
令 S 为 $\mathbb{R}^n$ 中的闭凸集。非零向量 $d \in \mathbb{R}^n$ 称为 S 的方向，如果对于每个 $x \in S,x+\lambda d \in S, \forall \lambda \geq 0.$
如果 $d \neq \alpha d_2$ for $ \alpha>0$，则 S 的两个方向 $d_1$ 和 $d_2$ 被称为不同的。
如果 $S$ 的方向 $d$ 不能写成两个不同方向的正线性组合，则称其为极端方向，即，如果 $d=\lambda _1d_1+\lambda _2d_2$ 对于 $\lambda _1, \ lambda _2>0$，则 $d_1= \alpha d_2$ 对于某些 $\alpha$。
任何其他方向都可以表示为极值方向的正组合。
对于凸集 $S$，使得 $x+\lambda d \in S$ 对于某些 $x \in S$ 和所有 $\lambda \geq0$ 的方向 d 称为 $S$ 的隐性。
设 E 为 $\mathbb{R}^n$ 中非空凸集 S 上的某个函数 $f:S \rightarrow$ 达到最大值的点的集合，则 $E$ 称为$S$。暴露面的方向称为暴露方向。
方向为极值方向的射线称为极值射线。
例子
考虑函数 $f\left ( x \right )=y=\left |x \right |$，其中 $x \in \mathbb{R}^n$。设 d 为 $\mathbb{R}^n$ 中的单位向量
那么，d 就是函数 f 的方向，因为对于任何 $\lambda \geq 0，x+\lambda d \in f\left ( x \right )$。
凸函数和凹函数
设 $f:S \rightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x \right )$ 被称为 S 上的凸集if $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right ), \forall \lambda \in \left ( 0,1 \right )$。
另一方面，设 $f:S\rightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则表示 $f\left ( x \right )$在 S 上凹 如果 $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\geq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right ), \forall \lambda \in \left ( 0, 1 \right )$。
设 $f:S \rightarrow \mathbb{R}$ 其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x\right )$ 被称为 S 上的严格凸集if $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right ), \forall \lambda \in \left ( 0, 1 \right )$。
令 $f:S \rightarrow \mathbb{R}$ 其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x\right )$ 被称为 S 上的严格凹集if $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )> \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right ), \forall \lambda \in \left ( 0, 1 \right )$。
例子
线性函数既是凸函数又是凹函数。
$f\left ( x \right )=\left | x \right |$ 是凸函数。
$f\left ( x \right )= \frac{1}{x}$ 是凸函数。
定理
设 $f_1,f_2,...,f_k:\mathbb{R}^n \rightarrow \mathbb{R}$ 为凸函数。考虑函数 $f\left ( x \right )=\displaystyle\sum\limits_{j=1}^k \alpha_jf_j\left ( x \right )$，其中 $\alpha_j>0,j=1, 2, 。 ..k,$ 那么 $f\left ( x \right )$ 是凸函数。
证明
由于 $f_1,f_2,...f_k$ 是凸函数
因此， $f_i\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f_i\left ( x_1 \right )+\left ( 1-\lambda \right )f_i\left ( x_2 \right ), \forall \lambda \in \left ( 0, 1 \right )$ 和 $i=1, 2,....,k$
考虑函数 $f\left ( x \right )$。
所以，
$ f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )$
$=\displaystyle\sum\limits_{j=1}^k \alpha_jf_j\left (\lambda x_1 +1-\lambda \right )x_2\leq \displaystyle\sum\limits_{j=1}^k\alpha_j\ lambda f_j\left ( x_1 \right )+\left ( 1-\lambda \right )f_j\left ( x_2 \right )$
$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \left ( \displaystyle\sum\limits_{j=1}^k \alpha _jf_j\left ( x_1 \right ) \right )+\left ( \displaystyle\sum\limits_{j=1}^k \alpha _jf_j\left ( x_2 \right ) \right )$
$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_2 \right )\leq \left ( 1-\lambda \right )f\左 ( x_2 \右 )$
因此，$f\left ( x\right )$ 是凸函数。
定理
设 $f\left ( x\right )$ 为凸集 $S\subset \mathbb{R}^n$ 上的凸函数，则 S 上 $f\left ( x\right )$ 的局部最小值为全局最小值。
证明
令 $\hat{x}$ 为 $f\left ( x \right )$ 的局部最小值，并且 $\hat{x}$ 不是全局最小值。
因此，$\hat{x} \在 S$ 中，使得 $f\left ( \bar{x} \right )< f\left ( \hat{x} \right )$
由于 $\hat{x}$ 是局部最小值，因此存在邻域 $N_\varepsilon \left ( \hat{x} \right )$ 使得 $f\left ( \hat{x} \right )\leq f \left ( x \right ), \forall x \in N_\varepsilon \left ( \hat{x} \right )\cap S$
但 $f\left ( x \right )$ 是 S 上的凸函数，因此对于 $\lambda \in \left ( 0, 1 \right )$
我们有 $\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$
$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \右 )f\左 (\hat{x} \右 )$
$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0 ,1 \右)$
但对于一些 $\lambda<1$ 但接近 1 的情况，我们有
$\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \in N_\varepsilon \left ( \hat{x} \right )\cap S$ 和 $f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left ( \bar{x} \right )$
这是一个矛盾。
因此，$\bar{x}$ 是全局最小值。
铭文
设 S 为 $\mathbb{R}^n$ 中的非空子集，并令 $f:S \rightarrow \mathbb{R}$ 则由 epi(f) 或 $E_f$ 表示的 f 的铭文是一个子集$\mathbb{R}^n+1$ 的定义为 $E_f=\left \{ \left ( x,\alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{ R}, f\left ( x \right )\leq \alpha \right \}$
低位描记器
设 S 为 $\mathbb{R}^n$ 中的非空子集，并设 $f:S \rightarrow \mathbb{R}$，则 f 的下位图表示为 hyp(f) 或 $H_f=\left \{ \left ( x, \alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$
定理
设 S 为 $\mathbb{R}^n$ 中的非空凸集，并设 $f:S \rightarrow \mathbb{R}^n$，则 f 为凸集当且仅当其铭文 $E_f$ 为凸集。
证明
设f是凸函数。
证明$E_f$是凸集。
令 $\left ( x_1, \alpha_1 \right ),\left ( x_2, \alpha_2 \right ) \in E_f,\lambda \in\left ( 0, 1 \right )$
在 E_f$ 中显示 $\lambda \left ( x_1,\alpha_1 \right )+\left ( 1-\lambda \right )\left ( x_2, \alpha_2 \right ) \in E_f$
$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2 \right ]\in E_f$
$f\left ( x_1 \right )\leq \alpha _1, f\left ( x_2\right )\leq \alpha _2$
因此，$f\left (\lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f \left ( x_2 \右)$
$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2$
交谈
设$E_f$是凸集。
证明f是凸的。
即，显示是否 $x_1, x_2 \in S,\lambda \left ( 0, 1\right )$
$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \右）$
设 $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right ),f\left ( x_1 \right ), f\left ( x_2 \right ) \in \mathbb{R}$
由于 $E_f$ 是凸集，因此 $\left ( \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )\右 )f\左 ( x_2 \右 )\in E_f$
因此，$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \右)$
凸优化 - Jensen 不等式
设 S 为 $\mathbb{R}^n$ 和 $f:S \rightarrow \mathbb{R}^n$ 中的非空凸集。那么 f 是凸的当且仅当对于每个整数 $k>0$
$x_1,x_2,...x_k \in S, \displaystyle\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geq 0, \forall i=1,2,s,k$,我们有 $f\left ( \displaystyle\sum\limits_{i=1}^k \lambda_ix_i \right )\leq \displaystyle\sum\limits_{i=1}^k \lambda _if\left ( x \right ) $
证明
通过对 k 的归纳。
$k=1:x_1 \in S$ 因此 $f\left ( \lambda_1 x_1\right ) \leq \lambda_if\left (x_1\right )$ 因为 $\lambda_i=1$。
$k=2:\lambda_1+\lambda_2=1$ 和 $x_1, x_2 \in S$
因此，$\lambda_1x_1+\lambda_2x_2 \in S$
因此根据定义， $f\left ( \lambda_1 x_1 +\lambda_2 x_2 \right )\leq \lambda _1f\left ( x_1 \right )+\lambda _2f\left ( x_2 \right )$
令该语句对于 $n < k$ 成立
所以，
$f\left ( \lambda_1 x_1+ \lambda_2 x_2+....+\lambda_k x_k\right )\leq \lambda_1 f\left (x_1 \right )+\lambda_2 f\left (x_2 \right )+...+ \lambda_k f\left (x_k \right )$
$k=n+1:$ 设 $x_1, x_2,....x_n,x_{n+1} \in S$ 和 $\displaystyle\sum\limits_{i=1}^{n+1}= 1$
因此 $\mu_1x_1+\mu_2x_2+.......+\mu_nx_n+\mu_{n+1} x_{n+1} \in S$
因此，$f\left (\mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1} x_{n+1} \right )$
$=f\left ( \left ( \mu_1+\mu_2+...+\mu_n \right)\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+\mu_3}+\mu_{n+ 1}x_{n+1} \右)$
$=f\left ( \mu_y+\mu_{n+1}x_{n+1} \right )$ 其中 $\mu=\mu_1+\mu_2+...+\mu_n$ 和
$y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n}$ 以及 $\mu_1+\mu_{n+1}=1,y \in S$
$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq \mu f\left ( y \right )+\mu_{n +1} f\left ( x_{n+1} \right )$
$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq$
$\left ( \mu_1+\mu_2+...+\mu_n \right )f\left ( \frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n} \right ) +\mu_{n+1}f\left ( x_{n+1} \right )$
$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n +\mu_{n+1}x_{n+1}\right )\leq \left ( \mu_1+ \mu_2+ ...+\mu_n \对）$
$\left [ \frac{\mu_1}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_1 \right )+...+\frac{\mu_n}{\mu_1+ \mu_2+ ...+ \mu_n}f\left ( x_n \right ) \right ]+\mu_{n+1}f\left ( x_{n+1} \right )$
$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right )\leq \mu_1f\left ( x_1 \right )+\mu_2f\left ( x_2 \右)+....$
故得证。
凸优化 - 可微函数
设 S 为 $\mathbb{R}^n$ 中的非空开集，则 $f:S\rightarrow \mathbb{R}$ 被称为在 $\hat{x} \in S$ 处可微，如果存在一个称为梯度向量的向量 $\bigtriangledown f\left ( \hat{x} \right )$ 和一个函数 $\alpha :\mathbb{R}^n\rightarrow \mathbb{R}$ 使得
$f\left ( x \right )=f\left ( \hat{x} \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x-\hat{x} \右)+\左\| x=\hat{x} \right \|\alpha \left ( \hat{x}, x-\hat{x} \right ), \forall x \in S$ 其中
$\alpha \left (\hat{x}, x-\hat{x} \right )\rightarrow 0 \bigtriangledown f\left ( \hat{x} \right )=\left [ \frac{\partial f} {\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} \right ]_{x=\hat{x}}^{T}$
定理
设 S 为 $\mathbb{R}^n$ 中的非空开凸集，并令 $f:S\rightarrow \mathbb{R}$ 在 S 上可微。那么，f 是凸集当且仅当对于 $ x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f\left ( x_2 \right )$
证明
设 f 为凸函数。即，对于 $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right )$
$f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \右）$
$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )+f\左 ( x_2 \右 )$
$ \Rightarrow\lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2+\lambda \left ( x_1-x_2 \right ) \right )- f\左 ( x_2 \右 )$
$\Rightarrow \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^ T\left ( x_1-x_2 \right )\lambda +$
$\左\| \lambda \left ( x_1-x_2 \right ) \right \|\alpha \left ( x_2,\lambda\left (x_1 - x_2 \right )-f\left ( x_2 \right ) \right )$
其中 $\alpha\left ( x_2, \lambda\left (x_1 - x_2 \right ) \right )\rightarrow 0$ as$\lambda \rightarrow 0$
两边除以 $\lambda$，我们得到 -
$f\left ( x_1 \right )-f\left ( x_2 \right ) \geq \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right )$
交谈
设 $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f \left ( x_2 \right ) $
证明 f 是凸的。
由于 S 是凸的，$x_3=\lambda x_1+\left (1-\lambda \right )x_2 \in S, \lambda \in \left ( 0, 1 \right )$
由于 $x_1, x_3 \in S$，因此
$f\left ( x_1 \right )-f \left ( x_3 \right ) \geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 -x_3\right )$
$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - \lambda x_1-\left (1-\lambda \右)x_2\右)$
$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \left ( 1- \lambda\right )\bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - x_2 \右）$
由于 $x_2, x_3 \in S$ 因此
$f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )$
$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda \右)x_2 \右)$
$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \left ( -\lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \对）$
因此，结合上述方程，我们得到 -
$\lambda \left ( f\left ( x_1 \right )-f\left ( x_3 \right ) \right )+\left ( 1- \lambda \right )\left ( f\left ( x_2 \right )-f \left ( x_3 \right ) \right )\geq 0$
$\Rightarrow f\left ( x_3\right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$
定理
设 S 为 $\mathbb{R}^n$ 中的非空开凸集，并设 $f:S \rightarrow \mathbb{R}$ 在 S 上可微，则 f 在 S 上是凸的当且仅当任意 $x_1,x_2 \in S,\left ( \bigtriangledown f \left ( x_2 \right )-\bigtriangledown f \left ( x_1 \right ) \right )^T \left ( x_2-x_1 \right ) \geq 0 $
证明
设 f 是凸函数，然后使用前面的定理 -
$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\leq f\left ( x_1 \right )-f\left ( x_2 \right )$ 和
$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$
将上面两个方程相加，我们得到 -
$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_1-x_2 \right )\leq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_2-x_1 \right )\geq 0$
交谈
令对于任何 $x_1,x_2 \in S,\left (\bigtriangledown f \left ( x_2\right )- \bigtriangledown f \left ( x_1\right )\right )^T \left ( x_2-x_1\right )\盖克0$
证明 f 是凸的。
设$x_1,x_2 \in S$，则根据均值定理，$\frac{f\left ( x_1\right )-f\left ( x_2\right )}{x_1-x_2}=\bigtriangledown f\left ( x\right ),x \in \left ( x_1-x_2\right ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda\right )x_2$ 因为 S 是凸集。
$\Rightarrow f\left ( x_1 \right )- f\left ( x_2 \right )=\left ( \bigtriangledown f\left ( x \right )^T \right )\left ( x_1-x_2 \right )$
对于 $x,x_1$，我们知道 -
$\left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x-x_1 \right )\geq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( \lambda x_1+\left ( 1-\lambda \right )x_2- x_1 \右)\geq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x \right )- \bigtriangledown f\left ( x_1 \right )\right )^T\left ( 1- \lambda \right )\left ( x_2-x_1 \right )\geq 0$
$\Rightarrow \bigtriangledown f\left ( x \right )^T\left ( x_2-x_1 \right )\geq \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )$
结合上述方程，我们得到 -
$\Rightarrow \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$
因此，使用最后一个定理，f 是凸函数。
二次可微函数
设 S 为 $\mathbb{R}^n$ 的非空子集，并设 $f:S\rightarrow \mathbb{R}$ 则 f 被称为在 $\bar{x} \in S 处二次可微$ 如果存在向量 $\bigtriangledown f\left (\bar{x}\right )、\:nXn$ 矩阵 $H\left (x\right )$（称为 Hessian 矩阵）和函数 $\alpha： \mathbb{R}^n \rightarrow \mathbb{R}$ 使得 $f\left ( x \right )=f\left ( \bar{x}+x-\bar{x} \right )=f\左 ( \bar{x} \right )+\bigtriangledown f\left ( \bar{x} \right )^T\left ( x-\bar{x} \right )+\frac{1}{2}\左 ( x-\bar{x} \right )H\左 ( \bar{x} \right )\left ( x-\bar{x} \right )$
其中 $ \alpha \left ( \bar{x}, x-\bar{x} \right )\rightarrow Oasx\rightarrow \bar{x}$
全局最优的充分必要条件
定理
设 f 为二次可微函数。如果 $\bar{x}$ 是局部最小值，则 $\bigtriangledown f\left ( \bar{x} \right )=0$ 且 Hessian 矩阵 $H\left ( \bar{x} \right )$是半正定的。
证明
设$d \in \mathbb{R}^n$。由于 f 在 $\bar{x}$ 处可两次微分。
所以，
$f\left ( \bar{x} +\lambda d\right )=f\left ( \bar{x} \right )+\lambda \bigtriangledown f\left ( \bar{x} \right )^T d+ \lambda^2d^TH\left ( \bar{x} \right )d+\lambda^2d^TH\left ( \bar{x} \right )d+$
$\lambda^2\左\| d \right \|^2\beta \left ( \bar{x}, \lambda d \right )$
但是 $\bigtriangledown f\left ( \bar{x} \right )=0$ 和 $\beta\left ( \bar{x}, \lambda d \right )\rightarrow 0$ 为 $\lambda \rightarrow 0$
$\Rightarrow f\left ( \bar{x} +\lambda d \right )-f\left ( \bar{x} \right )=\lambda ^2d^TH\left ( \bar{x} \right ) d$
由于 $\bar{x }$ 是局部最小值，因此存在 $\delta > 0$ 使得 $f\left ( x \right )\leq f\left ( \bar{x}+\lambda d \right ), \forall \lambda \in \left ( 0,\delta \right )$
定理
设 $f:S \rightarrow \mathbb{R}^n$ 其中 $S \subset \mathbb{R}^n$ 对 S 是二次可微的。如果 $\bigtriangledown f\left ( x\right )=0$ 且$H\left ( \bar{x} \right )$ 是半正定的，对于所有 $x \in S$，则 $\bar{x}$ 是全局最优解。
证明
由于 $H\left ( \bar{x} \right )$ 是半正定的，因此 f 是 S 上的凸函数。由于 f 在 $\bar{x}$ 处是可微且凸的
$\bigtriangledown f\left ( \bar{x} \right )^T \left ( x-\bar{x} \right ) \leq f\left (x\right )-f\left (\bar{x} \right ),\forall x \in S$
由于$\bigtriangledown f\left ( \bar{x} \right )=0, f\left ( x \right )\geq f\left ( \bar{x} \right )$
因此，$\bar{x}$ 是全局最优值。
定理
假设 $\bar{x} \in S$ 是问题 $f:S \rightarrow \mathbb{R}$ 的局部最优解，其中 S 是 $\mathbb{R}^n$ 的非空子集，并且S 是凸的。$min \:f\left ( x \right )$ 其中 $x \in S$。
然后：
$\bar{x}$ 是全局最优解。
如果 $\bar{x}$ 是严格局部最小值或 f 是严格凸函数，则 $\bar{x}$ 是唯一的全局最优解，也是强局部最小值。
证明
设 $\bar{x}$ 为该问题的另一个全局最优解，使得 $x \neq \bar{x}$ 和 $f\left ( \bar{x} \right )=f\left ( \hat{ x} \右)$
由于 $\hat{x},\bar{x} \in S$ 和 S 是凸的，因此 $\frac{\hat{x}+\bar{x}}{2} \in S$ 和 f 严格是凸的。
$\Rightarrow f\left ( \frac{\hat{x}+\bar{x}}{2} \right )< \frac{1}{2} f\left (\bar{x}\right )+ \frac{1}{2} f\left (\hat{x}\right )=f\left (\hat{x}\right )$
这是矛盾的。
因此，$\hat{x}$ 是唯一的全局最优解。
推论
设 $f:S \subset \mathbb{R}^n \rightarrow \mathbb{R}$ 为可微凸函数，其中 $\phi \neq S\subset \mathbb{R}^n$ 为凸集。考虑问题 $min f\left (x\right ),x \in S$，那么 $\bar{x}$ 是一个最优解，如果 $\bigtriangledown f\left (\bar{x}\right )^T \left (x-\bar{x}\right ) \geq 0,\forall x \in S.$
证明
设$\bar{x}$为最优解，即$f\left (\bar{x}\right )\leq f\left (x\right ),\forall x \in S$
$\Rightarrow f\left (x\right )=f\left (\bar{x}\right )\geq 0$
$f\left (x\right )=f\left (\bar{x}\right )+\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\右)+\左\| x-\bar{x} \right \|\alpha \left ( \bar{x},x-\bar{x} \right )$
其中 $\alpha \left ( \bar{x},x-\bar{x} \right )\rightarrow 0$ 为 $x \rightarrow \bar{x}$
$\右箭头f\le