一、基本术语和模型

考虑以下优化模型：

1、最小化点的定义

• 局部极小点（local minimiser）：，若存在 ，使得对所有 ，有
• 严格局部极小点（strict local minimiser）：，若存在 ，使得对所有 ，有
• 全局极小点（global minimiser）：，对所有 ，有

二、凸函数与强凸函数

1、凸函数定义

是凸函数，若对任意 ，，有：

凸函数的图像在任意两点之间，连线上的所有点的函数值都不高于这两点之间的线性插值。换句话说，连接函数图像上任意两点的直线，始终位于函数图像之上或与之重合。直观理解：如果你在函数图像上选取任意两点 和 ，然后在这两点之间画一条直线，那么对于这条线上的任意一点，其纵坐标（线性插值）都大于等于函数在该点的值。这意味着函数图像是“向上弯曲”的，没有“凹陷”。

2、凸函数的梯度性质

设 为凸集， 凸且在 处可微，则有一阶泰勒展开是下界：

推导：

由凸性定义，

令 ，有

取极限，左边为方向导数，即得证。

3、凸优化问题定义

若 为凸函数， 且为凸集合，且 ，则

是凸优化问题。

4、强凸函数定义

是强凸函数，模 ，若对任意 ，，有：

强凸函数的几何意义在于，相比普通凸函数，强凸函数的图像不仅在任意两点之间都在连线下方，还“向上弯曲”得更厉害。具体来说，定义中的额外项 表示函数图像与两点连线之间至少有一个 相关的“距离”。这意味着强凸函数的最小值是唯一的，且优化算法收敛更快。可以类比为抛物线比直线更“陡”，强凸性让函数有更强的“弯曲”特性。

三、光滑函数（L-smooth）

（不必凸）是L-光滑函数，即其梯度是 -Lipschitz 连续：

L-光滑函数的梯度满足 -Lipschitz 连续，意味着函数的斜率（梯度）变化不会太快。具体来说，任意两点 之间，梯度的变化幅度被 控制：

• 越小，梯度变化越平缓，函数曲线越“光滑”；
• 越大，梯度变化可能更剧烈，函数曲线可能更“陡峭”。 几何直观： 在任意两点之间，函数的切线方向不会突然跳变，而是以受限的速度变化。这保证了优化算法（如梯度下降）在搜索最优解时，每一步的梯度信息都不会“失控”，从而有助于算法收敛。

可以把 理解为“最大允许的弯曲度”，它限制了函数的“弯曲”速度，使得函数图像在任意小区间内都不会出现极端的尖锐变化。

四、凸优化性质

1、极小点的性质

设 为凸函数，则：

1. 是局部极小点 是全局极小点
2. 极小点集合 是凸集
3. 若 可微，则在极小点 有

2、光滑与强凸的进一步性质

1. 若 -强凸且可微，则有
2. 若 -光滑，则有

推导：

设 在 上可微。

1. 强凸下的下界：

是 -强凸函数，定义为：

即

由强凸定义，对任意 ，

令 ，用泰勒展开近似 ，有

带入强凸定义，忽略高阶项，得

化简并令 ，得

2. 光滑下的上界：

是 -光滑函数，梯度 -Lipschitz，定义为：

由梯度Lipschitz性质，积分路径上的梯度变化：

用均值不等式和Lipschitz条件，有

即

结论：

• 强凸给出下界，保证函数“弯曲”至少为 ；
• 光滑给出上界，限制函数“弯曲”至多为 。

3、参数关系

若 既 -强凸又 -光滑，则 。

证明：

由上述性质，对任意 ，

故 。

4、强凸函数的极小点唯一性

若 强凸，则全局极小点唯一。

五、收敛速度与收敛率

1、收敛方式的判据

迭代算法收敛通常可通过以下量：

• 当
• 或

2、收敛率定义

设 ，，则

• 线性收敛（linear）：存在 ，使得
• Q-超线性收敛（Q-superlinear）：
• Q-二次收敛（Q-quadratic）：存在 使得

3、次线性收敛（sublinear）

若 的速度比线性慢，则为次线性收敛。

以下序列均次线性收敛：